Bài giảng 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 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: Các con thỏ không bao giờ chết. 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). 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: 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à 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.6n 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 chương trình con tính các giá trị cache còn lại bằng thuật toán đệ quy. Sau đó chương trình con sẽ thực hiện công việc của nó. Nó sẽ kiểm tra nếu cache[n] bằng UNKNOWN thì sẽ tiếp tục quá trình tính toán. Tại cache[n] sẽ lưu trữ giá trị cho Fibcache(n) được tính bằng tổng của hai số Fibcache trước nó là Fibcache(n-1) và Fibcache(n-2). Khi đó Fibache(n-1) sẽ lấy giá trị tại cache[n-1], Fibcahe[n-2] lấy giá trị tại cache[n-2]. Tiếp tục như vậy tới cache[2] và cache[1] thì được thay bằng giá trị đã được khởi tạo ban đầu. Từ đó có thể giải thích được tại sao cây đệ quy (Hình 1.2) chỉ có các cuộc gọi bên trái mà không có các cuộc gọi bên phải. Các cuộc gọi bên phải sẽ lấy giá trị đã được lưu trữ mà không cần tính lại. Nói một cách dễ hiểu, có một mảng tra cứu tạo ra để theo dõi giá trị Fibcache đã tính lúc trước với chỉ số quy định trong mảng. Ví dụ như, khi tính Fibcache(4) sẽ được lưu trong cache[4] với giá trị là 3, khi chương trình đi để tính Fibocache(5) nó sẽ lấy giá trị cache[4] đã tồn tại trong mảng mà không cần tính lại Fibcache(4) lần nữa. 2.3 Tính số Fibonacci bằng quy hoạch tuyến tính 2.3.1 Mảng một chiều Chúng ta có thể tính toán F(n) trong thời gian tuyến tính dễ dàng hơn bằng gỡ bỏ tất cả các cuộc gọi đệ quy và quy định cụ thể rõ ràng thứ tự của các đánh giá về mối quan hệ tái phát. Ở đây, các số Fibonacci đã tính trước đó được lưu giữ trong mảng một chiều. Chúng ta đánh giá các số Fibonacci từ nhỏ nhất tới lớn nhất và lưu trữ tất cả các kết quả, nên chúng ta có Fi-1 và Fi-2 đã sẵn sàng bất cứ khi nào chúng ta cần tính Fi. Mỗi giá trị của n được tính toán đơn giản là tổng của hai số nguyên. (1). Xây dựng mảng F[1..n] với F[1]=1 và F[2]=1; (2). Tính các phần tử F[i], với i=2..n theo công thức F[i]=F[i -1]+F[i-2]; (3).Trả về giá trị của F[n]. 2.3.2 Lặp không đệ quy Quá trình nghiên cứu kĩ hơn cho thấy rằng chúng ta không cần lưu trữ tất cả các giá trị trung gian cho toàn bộ thời gian thực hiện. Bởi vì tái phát phụ thuộc vào hai đối số, chúng ta chỉ cần giữ lại hai giá trị cuối cùng chúng ta đã thấy. Cũng bắt đầu tính các số Fibonacci từ dưới lên, bắt đầu từ hai biến lưu hai giá trị back1=0 và back2=1. Khi vòng lặp được duyệt qua tổng của back1 và back2 được gán cho biến phụ next. Sau đó back1 được gán giá trị của back2 và back2 được gán giá trị của next. Vậy sau khi đi qua vòng lặp lần 1, ta có back1=back2 và back2=back1+back2 = next. C. PHẦN KẾT LUẬN 1. Chương trình và kết quả test 1.1 Thuật toán 1: Đệ quy program fibonacci; var n:integer; Fib:integer; function F(n:integer):integer; begin if n=0 then F:=0; if n=1 then F:=1; if n>1 then F:=F(n-1)+F(n-2); end; BEGIN write('nhap so fibonacci thu n');readln(n); Fib:=F(n); write('So fibonacci thu',n,'la: ',Fib); readln; end. * kết quả test 1.2 Thuật toán 2: Caching program fibonacci_cache; var cache:array[1..300] of integer; n,i,Fib:integer; const UNKNOWN=-1; function fibcache(n:integer):integer; begin if ( cache[n]=UNKNOWN ) then cache[n]:=fibcache(n-1)+fibcache(n-2); fibcache:=cache[n]; end; BEGIN write('nhap so nguyen n= ');readln(n); cache[1]:=1; cache[2]:=1; for i:=3 to n do cache[i]:=UNKNOWN; Fib:=fibcache(n); write('so fibonacci thu F',n,' la ',Fib); readln; END. * kết quả test 1.3 Thuật toán 3: mảng một chiều program gt3_fibonacci; var F:array[1..100] of integer; n,i:integer; BEGIN write('nhap so nguyen n ');readln(n); F[1]:=1; F[2]:=1; for i:=3 to n do F[i]:=F[i-1]+F[i-2]; writeln('so fibonacci thu ',n,'la ',F[n]); readln; END. * kết quả test 1.4 Thuật toán 4: Lặp không đệ quy program gt4_fibonacci; var n,i:integer; next,back1,back2:integer; BEGIN write('nhap so fibonacci thu ');readln(n); back1:=0; back2:=1; for i:=2 to n do begin next:=back1+back2; back1:=back2; back2:=next; end; write('so fibonacc thu ',n,'=',next); readln; END. * kết quả test 2. Đánh giá thuật toán Thuật toán 1: * Ưu điểm: Tốn ít bộ nhớ Dễ hiểu * Nhược điểm: Độ phức tạp về thời gian của giải thuật là theo hàm số mũ, cụ thể là O(n2) nên chương trình này cần có thời gian cấp số nhân để chạy. → Vì thế mà giải thuật này thường chỉ được dùng trong mục đích giảng dạy, đặc biệt là để minh họa cho việc phân tích hiệu quả của một giải thuật. Nó cũng là một cách để đánh giá hiệu suất của một chương trình dịch.  Thuật toán 2: * Ưu điểm: Độ phức tạp về thời gian O(n) bởi vì chức năng đệ quy Fib(k) là gọi chính xác 2 lần cho mỗi giá trị 0 ≤ k ≤ n, giảm thời gian tính toán + Nhớ đệm kết quả từ các cuộc gọi đệ quy, tránh được quá trình tính toán lại * Nhược điểm: Tốn bộ nhớ Không phù hợp với các thuật toán đệ quy như sắp xếp nhanh, thụt lùi, tìm kiếm chuyên sâu. Caching có ý nghĩa chỉ khi không gian của các giá trị tham số khác biệt là đủ khiêm tốn mà chúng ta có thể đủ khả năng chi phí lưu trữ. Thuật toán 3: * Ưu điểm: Độ phức tạp về thời gian O(n) giúp giảm bớt thời gian tính toán * Nhược điểm: Dữ liệu được lưu giữ đã vượt hơn nhu cầu (vì lưu giữ tất cả các số Fibonacci trước đó), vì vậy, nó hơi tốn bộ nhớ Thuật toán 4: * Ưu điểm: Độ phức tạp về thời gian O(n) giúp giảm bớt thời gian tính toán * Nhược điểm: Tốn bộ nhớ ( tốn ít hơn giải thuật 3 vì chỉ phải lưu hai số Fibonacci kế trước)