Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Phân tích fibonaci

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Phân tích fibonaci   Thu 03 Jun 2010, 08:09

Như ta đã biết, dãy fibonaci có dạng như sau:
+f(0)=f(1)=1;
+f(i)=f(i-1)+f(i-2) với mọi i>=2.
Như vậy dãy sau chính là dãy fibonaci:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 ........

Ta chứng minh được điều sau: mọi số tự nhiên lớn hơn 0 đều có thể viết dưới dạng tổng của một số số fibonaci. Ví dụ:
9=1+3+5 (tôgnr của 3 số fibonaci)
9=1+8 (tổng của 2 số fibonaci)

Bài toán đặt ra là với một số nguyên dương nhập từ bàn phím, hãy phân tích số ấy ra tổng các số fibonaci sao cho tổng ấy có ít hạng tử nhất
Về Đầu Trang Go down
memehehe
Gà mờ


Tổng số bài gửi : 1
Join date : 31/01/2012

Bài gửiTiêu đề: Re: Phân tích fibonaci   Tue 31 Jan 2012, 21:34

Hi, mình là mem mới, làm quen nhé ^^ big grin
Bài này có thể tạo một dãy các số fibo <=n, xong rùi dùng tham lam để trừ ra :)

Code:
uses crt;
var i,n,k:longint;
        a:array[1..100] of longint;
begin
        clrscr;
        readln(n);
        a[1]:=1; a[2]:=1;
        k:=2;
        while a[k]<n do
        begin
                inc(k);
                a[k]:=a[k-1]+a[k-2];
        end;
        for i:=k downto 1 do
            if n>=a[i] then
                begin
                        if n>a[i] then write(a[i],' + ') else write(a[i]);
                        n:=n-a[i];
                end;
        readln;
end.

Về Đầu Trang Go down
 
Phân tích fibonaci
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến