Solution to Fibonacci from Jobdu

1 Aug

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).

The solution is as following:

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)

Leave a Reply

Your email address will not be published. Required fields are marked *