Số Fibonacci

Bắt nguồn từ bài toán con thỏ, nhà toán học người Italia tên là Fibonacci đã định nghĩa mối quan hệ tái phát và từ đó số Fibonacci ra đời. Nó đã thu hút rất nhiều sự quan tâm của các nhà nghiên cứu trên thế giới và người ta đã nghiên cứu ra nhiều cách tính Fibonacci trên máy tính sao cho độ phức tạp về thời gian của giải thuật là nhỏ nhất. Dưới đây là sự ra đời của số Fibonacci và các thuật toán của nó....
Nội dung trích xuất từ tài liệu:
Số Fibonacci MỤC LỤC A. PHẦN GIỚI THIỆU………………………………………………..1 B. PHẦN NỘI DUNG……………………………………………….…1 1. Sự ra đời của số Fibonacci……………………………………………2 1.1 Bài toán mở đầu………………………………………………… 2 1.2 Định nghĩa số Fibonacci………………………………………….2 2. Giải thuật tính số Fibonacci…………………………………………..3 2.1 Tính số Fibonacci bằng đệ quy…………………………………...3 2.2 Tính số Fibonacci bằng caching………………………………….4 2.3 Tính số Fibonacci bằng quy hoạch tuyến tính……………………5 2.3.1 Mảng một chiều……………………………………………...5 2.3.2 Lặp không đệ quy……………………………………………5 C. PHẦN KẾT LUẬN…………………………………………………6 1. Chương trình và kết quả test………………………………………….6 1.1 Thuật toán 1………………………………………………………6 1.2 Thuật toán 2………………………………………………………6 1.3 Thuật toán 3………………………………………………………7 1.4 Thuật toán 4………………………………………………………8 2. Đánh giá thuật toán…………………………………………………...9 1 A. PHẦN GIỚI THIỆU LỜI MỞ ĐẦU Bắt nguồn từ bài toán con thỏ, nhà toán học người Italia tên là Fibonacci đã định nghĩa mối quan hệ tái phát và từ đó số Fibonacci ra đ ời. Nó đã thu hút rất nhiều sự quan tâm của các nhà nghiên cứu trên thế giới và người ta đã nghiên cứu ra nhiều cách tính Fibonacci trên máy tính sao cho độ phức tạp về thời gian của giải thuật là nhỏ nhất. Dưới đây là s ự ra đ ời c ủa s ố Fibonacci và các thuật toán của nó. B. PHẦN NỘI DUNG 1. Sự ra đời của số Fibonacci 1.1 Bài toán mở đầu Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản c ủa các c ặp thỏ. Bài toán được đặt ra như sau: 1. Các con thỏ không bao giờ chết. 2. Hai năm sau khi ra đời một cặp th ỏ mới sẽ sinh ra một c ặp th ỏ con (một đực, một cái). 3. Khi đã sinh con rồi thì cứ mỗi năm tiếp theo chúng l ại sinh đ ược một cặp con mới. Giả sử bắt đầu từ một cặp mới ra đời thì đến năm th ứ n s ẽ có bao nhiêu cặp? 1.2 Định nghĩa số Fibonacci Từ bài toán con thỏ ta xét n=6 ta thấy: Năm thứ 1: 1 cặp (cặp ban đầu). Năm thứ 2: 1 cặp (cặp ban đầu vẫn chưa đẻ) Năm thứ 3: 2 cặp (đã có thêm một cặp con) Năm thứ 4: 3 cặp (cặp đầu vẫn đẻ thêm) Năm thứ 5: 5 cặp (cặp con bắt đầu đẻ) Năm thứ 6: 8 cặp (cặp con vẫn đẻ tiếp) Bây giờ ta xét tới việc tính số cặp thỏ ở năm thứ n: F(n) Ta thấy nếu mỗi cặp thỏ ở năm thứ (n-1) đều sinh con thì: F(n)=2*(n-1) Nhưng không phải như vậy. Trong các cặp thỏ ở năm thứ (n-1) ch ỉ có những cặp đã có ở năm thứ (n-1) mới sinh con ở năm thứ n được thôi. Do đó: F(n)=F(n-2) + F(n-1) Vì vậy số Fibonacci được định nghĩa theo công thức sau: 2 Dãy bắt đầu từ hai số F(0)=0 và F(1)=1. Như vậy, các số đầu tiên của dãy Fibonacci là: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765. 2. Giải thuật tính số Fibonacci 2.1 Tính số Fibonacci bằng đệ quy Từ định nghĩa về số Fibonacci, ta có công thức tính số Fibonacci th ứ n bằng mối quan hệ tái phát sau: F(n)=F(n-1)+F(n-2) Kể từ khi chúng được xác định bằng công thức đệ quy, có dễ dàng để viết một chương trình đệ quy để tính số Fibonacci thứ n. Quá trình th ực hiện cho thuật toán đệ quy được minh họa bằng cây đệ quy của nó, nh ư được minh họa trong hình 1.1 Hình 1.1 Cây tính toán cho máy tính số Fibonacci đệ quy Từ cây đệ quy, để tìm F(n) ta biểu diễn F(n) = F(n-1)+F(n-2). Sau đó thay thế cả hai số này bằng tổng của hai số Fibonacci bậc thấp hơn, cứ tiếp tục như vậy cho tới khi F(0) và F(1) xuất hiện thì được thay bằng các giá trị của chúng theo định nghĩa. Do đó với các trường hợp cơ sở F(0)=0 và F(1)=1. Sau đó F(2)=F(1)+F(0)=1; F(3)=F(2)+F(1)=F(1)+F(0)+F(1)=2; tiếp tục các cu ộc g ọi đ ệ quy v ới các số Fibonacci tiếp theo ta được F(4)=3, F(5)=5, F(6)=8…,F(12)=144… Nhận thấy giải thuật đệ quy tính toán lặp đi l ặp l ại nhi ều l ần cùng m ột giá trị, ví dụ như trong tính toán F(6), chúng ta cần phải tính toán F(5) và 3 F(4). Để tính F(5) một lần nữa cần phải tính toán F(4). Vì vậy, ở đây F(4) tính toán trên cả hai mặt của cây đệ quy, và F(2) được tính toán không dưới 5 lần. Kể từ khi Fn+1/Fn ≈ φ = (1+√5)/2 ≈ 1.61803, điều đó có nghĩa rằng F(n)>1.6n. Kể từ khi cây đệ quy chỉ có 0 và 1 lá, tổng h ợp đ ến một s ố lượng lớn như vậy có nghĩa là phải mất ít nhất 1.6 n lá hoặc cuộc gọi thủ tục 2.2 Tính số Fibonacci bằng caching Trên thực tế, chúng ta có thể làm tốt hơn nhiều. Chúng ta có thể lưu trữ ( hoặc cache) một cách rõ ràng kết quả của mỗi tính toán Fibonacci F(k) trong bảng cấu trúc dữ liệu được lập chỉ mục bởi tham số k. Hình 1.2: Các tính toán Fibonacci cây khi bộ nhớ đệm giá trị Để tính F(n) ta gọi một chương trình Fib. Điều này khởi t ạo m ột b ộ nh ớ cache, khởi tạo hai giá trị ban đầu cache[1] và cache[2], rồi gán UNKNOWN cho tất cả các phần cache còn lại mà chưa có giá trị. Sau đó gọi một ...