Bài 2: Số thỏ trên đảo

tải về 13.79 Kb.

Chuyển đổi dữ liệu	25.02.2023
Kích	13.79 Kb.
	#54283

sothotrendao

Yêu cầu
*Ý tưởng

Bài 2: Số thỏ trên đảo
Trong các bài toán cổ có bài toán về số lượng thỏ trên đảo, bài toán có thể mô tả vắn tắt như sau: đầu tiên có 1 thỏ đực và 1 thỏ cái sống trên đảo, đợt sinh đầu tiên chúng sinh được 2 con, cứ như thế lứa thứ 3 được tính bằng tổng số của lứa thứ 2 cộng với lứa trước đó. Ta lần lượt tính được số thỏ sau các đợt sinh sản: 1, 1, 2, 3, 5, 8, 13, ..... Dãy số này trong toán học gọi là dãy Fibonaci.
Muốn viết chương trình tính dãy số này khi có giới hạn nhất định nào đó người ta có thể dùng hàm {f_n}: để thực hiện việc tính toán dãy số trên.
Yêu cầu: Em hãy viết chương trình kiểm tra xem khi cho số nguyên dương N, ta có thể biểu diễn N thành tổng của các số Fibonaci hay không? (2 ≤ N ≤ 10²)
Dữ liệu vào: file văn bản có tên fib.inp chỉ có duy nhất số nguyên dương N.
Dữ liệu ra: file văn bản có tên fib.out chỉ có 1 dòng đó là kết quả tính tổng của N được biểu diễn qua các số Fibonacci và liệt kê theo thứ tự từ lớn đến nhỏ. Mỗi số cách nhau một dấu cách.
Ví dụ biểu diễn số N = 567; 567 = 377 + 144 + 34 + 8 + 3 + 1. Trong đó 377 là số bé hơn và gần 567 nhất, tất cả các số đều là số Fibonacci và được sắp giảm dần.

FIB.INP	FIB.OUT
567	567 = 377 + 144 + 34 + 8 + 3 + 1

*Ý tưởng:
-
var fi:array[1..10000] of longint;
f:text;
m:byte;
i,n:longint;
begin
assign(f,'fib.inp');
reset(f);
readln(f,n);
close (f);
assign(f,'fib.out');
rewrite(f);
fi[1]:=1;
fi[2]:=1;
m:=3;
while ((fi[m-1]+fi[m-2]))<=n do
begin
fi[m]:=fi[m-1]+fi[m-2];
m:=m+1;
end;
while n>0 do
begin
if (fi[m-1]<=n) then
begin
write(f,fi[m-1]);
n:=n-fi[m-1];
if n>0 then
begin
write(f,'+');
end;
end;
m:=m-1;
end;
close(f);
end.

tải về 13.79 Kb.

Chia sẻ với bạn bè của bạn: