Bài toán tìm số Fibonaci thứ n

BÀI TOÁN TÌM SỐ FIBONACI THỨ N
Lê Thanh Phú – 0942.25.07.87
Có lẽ đây là bài toán rất kinh điển được nhắc đến khi các bạn bồi dưỡng học sinh giỏi. trước hết ta nhắc lại về dãy số Fibonaci:
Định nghĩa:


Bài toán 1: Cho một số tự nhiên n (n<=40) bạn hãy lập trình tìm số Fibonaci thứ n?
Ta thấy với n<=40 thì phương án đầu tiên ta cân nhắc đến đó chính là đệ quy:
Nhìn vào công thức trên ta thấy ngay bản chất đệ quy, việc tính Fn ta có thể viết ngay rất dễ dàng và ngắn gọn:
Function Fb(n:longint):int64;
Begin
If (n<=2) then exit(1) else fb:=fb(n-1) + fb(n-2);
End;
Ta sẽ nhận xét về cách làm này thông qua ví dụ sau:
Khi ta gọi: x:=Fb(10) thì việc tính fb(10) này sẽ tính như sau:
X:= fb(9) + fb(8)
X:= fb(7) + fb(8) + fb(6) + fb(7)
X:= fb(5) + fb(6) + fb(6) + fb(7) + fb(4) + fb(5) + fb(5) + fb(6)
…..
Ta thấy ngay bước thứ 3: có rất nhiều lời gọi hàm trùng lặp nhau: f6 gọi 3 lần, f5 gọi 3 lần … chính điều này làm cho thời gian thực thi thuật toán này rất lớn. Chính vì vậy thuật toán đệ quy này chỉ chạy được với dữ liệu nhỏ. Với n>=44 thuật toán trên không khả thi.
Bài toán 2: bạn hãy lập trình tìm số Fibonaci thứ n? (n<=105) vì kết quả có thể rất lớn nên ta chỉ lấy kết quả là phần dư khi chia cho 106+7.
* Ý tưởng 1: QHĐ O(n) để tìm số fibonaci thứ n
Gọi F[i] là số Fibonaci thứ i.
Khi đó ta thấy việc tính mảng F này rất nhanh chóng:
Function Fibo(n:longint):int64;
Var i:longint;
Begin
f[1]:=1; f[2]:=1;
For i:=1 to n do f[i] : = (f[i-1] + f[i-2]) mod base;
Exit(f[n]);
End;
* Ý tưởng 2: QHĐ O(n) để tìm số Fibonaci thứ n
Ta nhận thấy để tính Fn thì chỉ cần quan tâm đến F[n-1] và f[n-2] vậy ta đã lãng phí bộ nhớ dành cho mảng F.
Ý tưởng là ta sẽ dùng 3 biến fn, f1, f2: để lần lượt tính:
Funtion Fibothu_n(n:longint):int64;
Var f1,f2,k,i:int64;
Begin
if (n=1) or (n=2) then exit(1) else
Begin
f1:=1; f2:=1; fn:=f1+f2; i:=3;
While i Begin
f1:=f2; f2:=fn; fn:=f1+f2;
i:=i+1;
End;
Exit(fn)
End;
End;
* Nhận xét: Ý tưởng 2 tốt hơn ý tưởng 1 rất nhiều về không gian bộ nhớ, tuy nhiên 2 ý tưởng này xét về độ phức tạp vẫn còn rất lớn:
Sau đây ta xét bài toán thứ 3 như sau:
Bài toán 3: Nguồn http://laptrinh.ntu.edu.vn/Problem/Details/1163
Xét dãy số Fibonaci {Fn} theo định nghĩa:
F1 = F2 = 1
Fn = Fn - 1 + Fn - 2 với mọi n > 2
Cho n, hãy tính Fn và đưa ra số dư của Fn chia cho (106 + 7)
Dữ liệu vào: n (0 < n ≤ 1015)
Dữ liệu ra: một số nguyên – số dư tìm được
Ta nhận thấy với n<=1015 thì 2 cách làm QHĐ với độ phức tạp O(n) không khả thi. Để giải quyết vấn đề này ta dùng phương pháp nhân ma trận.
Phương án sau được đề xuất bởi Donald E. Knuth:
/
Vậy để tìm số Fibonaci thứ n đơn giản ta chỉ cần tính a mũ n (Với a là ma trận cơ sở như trên).
Giả sử ta