Tài nguyên dạy học

Thành viên trực tuyến

0 khách và 0 thành viên

Chào mừng quý thầy cô, quý phụ huynh, các em học sinh...

     Năm học 2014-2015, được sự chỉ đạo của BGH nhà trường, ban CNTT kiện toàn và tiếp tục đi vào hoạt động thường xuyên. Với mục tiêu trọng tâm của năm là củng cố, khai thác và vận hành hệ thống website, thư viện học liệu điện tử nhằm tạo điều kiện để các thầy cô giáo trao đổi kinh nghiệm, nguồn thông tin tham khảo bổ ích cho các em học sinh, Ban Quản trị, Ban biên tập web rất cám ơn sự chia sẻ của quý thầy cô giáo và các em học sinh.

     Mọi thắc mắc về việc đăng tin, bài trên website trang tin, quý thầy cô vui lòng liên hệ thầy giáo Đỗ Văn Kiện 0974015895.

     Thắc mắc về việc đăng bài viết, đề thi, bài giảng lên thư viện violet, quý thầy cô liên hệ cô Trương Thị lê Na 01649786828.

    Thắc mác trong quá trình nhập điểm, xem điểm, quý thầy cô vui lòng liên hệ thầy Lê Minh Hiếu 0915003286. Email: minhhieuqt@gmail.com.

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

Nhấn vào đây để tải về
Hiển thị toàn màn hình
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Lê Thanh Phú (trang riêng)
Ngày gửi: 15h:40' 15-09-2015
Dung lượng: 19.2 KB
Số lượt tải: 109
Số lượt thích: 0 người
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
 
Gửi ý kiến