Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1387
Question Name: Fibonacci
Question Description: find the Fibonacci number F(N).
Input: may contains multiple test cases. Each case is a single line, including one integer as the N.
Output: the Fibonacci number F(N).
1 2 3 4 | Input: 3 Output: 2 |
The solution is as following:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | /** * Filename : Fibonacci.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-01 * JDK used : 1.7 * Change log: None */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.List; public class Fibonacci { // There are multiple inquiries on Fibonacci numbers. Cache the previous // computing result for later usage. private List<Long> cache = new ArrayList<Long>(); private Integer cacheCount = 0; public Fibonacci() { // Initialize the cache system with F(0) and F(1). cache.add(0L); cache.add(1L); cacheCount = 2; } /** * Get one specific Fibonacci number. * @param n: the n(th) Fibonacci number to return. Zero-based numbering. * @return long: the n(th) Fibonacci number. */ public Long getFibonacci(Integer n) { if (n >= cacheCount) { // If we have not computed the F(n). Long temp; for (int i = cacheCount; i <= n; ++i) { temp = cache.get(i-2) + cache.get(i-1); cache.add(temp); } cacheCount = n + 1; } return cache.get(n); } public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); Fibonacci FibComputer = new Fibonacci(); while (st.nextToken() != StreamTokenizer.TT_EOF) { System.out.println(FibComputer.getFibonacci((int)st.nval)); } } } |
Variant One:
Question (Frog Jump): The frog can jump one step or two steps. To finish n steps, how many different paths are there?
Solution: return F(n+1)
Variant Two:
Question (Crazy Frog Jump): The frog can jump one step or two steps or three or … or N steps. To finish N steps, how many different paths are there?
Solution: return 2^(N-1)
Variant Three:
Question (Frog Jump): We use the 2*1 block and/or 1*2 block to cover an 2*N area. How many distinct solution are there?
Solution: return F(n+1)