Tin học - 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<n do
	 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 
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 tính mảng 2 chiều F = an, khi đó kết quả bài toán số fibonaci thứ n chính là F[1,2].
	Bạn nào không nhớ rõ về cách nhân 2 ma trận thì có thể xem thêm đoạn chương trình sau:
//Tinh Fibonaci thu n O(logn): nhan ma tran
const
 base=1000007;
type
 matrix=array[1..2,1..2] of int64;
var
 n:int64;
Function nhan(a,b:matrix):matrix;
 var c:matrix;
 begin
 c[1,1]:=(a[1,1]*b[1,1] + a[1,2]*b[2,1]) mod base;
 c[1,2]:=(a[1,1]*b[1,2] + a[1,2]*b[2,2]) mod base;
 c[2,1]:=(a[2,1]*b[1,1] + a[2,2]*b[2,1]) mod base;
 c[2,2]:=(a[2,1]*b[1,2] + a[2,2]*b[2,2]) mod base;
 exit(c);
 end;
Function mu(a:matrix; n:int64):matrix;
 var b:matrix;
 begin
 if n=1 then exit(a);
 b:=mu(a, n div 2);
 b:=nhan(b,b);
 if n mod 2 = 0 then exit(b) else exit(nhan(b,a));
 end;
Function Fibo(n:int64):int64;
 var a,f:matrix;
 begin
 if n<=2 then exit(1);
 a[1,1]:=1; a[1,2]:=1; a[2,1]:=1; a[2,2]:=0;
 f:= mu(a,n);
 exit(f[1,2]);
 end;
BEGIN
 readln(n);
 write(fibo(n));
 readln;
END.
Trên đây là kinh nghiệm của tôi khi giải quyết vấn đề về bài toán Fibonaci thứ n. Chúc các bạn thành công!