//
you're reading...
Bài tập huấn luyện, Đề huấn luyện bằng tiếng Anh

English problems: Fibonacci series

[Return problems page]


In mathematics, the Fibonacci series is defined by the following recurrence relation:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
i.e. nth element is formed by adding elements at (n-1) and (n-2)
So, first 10 fibonacci numbers will be:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Given a number n, find F(n).
Example:
Input: 6
Output: 8
Input: 10
Output: 55


Algorithm/Insights


Recursive Solution:
1. Boundary Condition: If n = 0 or n = 1, return n
2. Return F(n-1) + F(n-2)
F(n-1) = F(n-2) + F(n-3)
We see that F(n-2) will be computed again for F(n-1). So, a lot of redundant calculations.
Time Complexity: Exponential


Efficient Solution:


The problem can be solved by Dynamic Programming because it has both the properties:
1. Overlapping Subproblems –
As F(n) = F(n-1) + F(n-2), computation of nth fibonacci number requires (n-1) and (n-2) fibonacci numbers.
Further F(n-1) = F(n-2) + F(n-3), and so on
So, we see that there are overlapping sub problems.
2. Optimal Substructure –
If subproblems F(n-1) and F(n-2) are computed optimally, then the solution to F(n) is also optimal. Hence it satisfies optimal substructure property.
So, if we store the solutions to subproblems here, we can find next fibonacci number efficiently without computing the values again.
Also, as F(n) = F(n-1) + F(n-2), we need only the last 2 values of the series to find the next value. Hence, we do not need to store all subproblem solutions but only the previous 2 i.e. F(i-1) and F(i-2). Once we have F(i), for calculating F(i+1) we just need F(i) and F(i-1), and therefore we can discard F(i-2) as it is not needed further.
So starting with F(0) = 0, F(1) = 1, we can use bottom up approach to calculate F(n)
1. Boundary Condition: If n = 0 or n = 1, return n
2. Take a = 0, b = 1
3. Loop n-2 times, and calculate
c = a+b
a = b
b = c
4. Return c

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 209,568 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: