1) Các con thỏ không bao giờ chết
2) Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái)
3) Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới
Giả sử từ đầu tháng 1 có một cặp mới ra đời thì đến giữa tháng thứ n sẽ có bao nhiêu cặp.
Ví dụ, n = 5, ta thấy:
Giữa tháng thứ 1: 1 cặp (ab) (cặp ban đầu)
Giữa tháng thứ 2: 1 cặp (ab) (cặp ban đầu vẫn chưa đẻ)
Giữa tháng thứ 3: 2 cặp (AB)(cd) (cặp ban đầu đẻ ra thêm 1 cặp con)
Giữa tháng thứ 4: 3 cặp (AB)(cd)(ef) (cặp ban đầu tiếp tục đẻ)
Giữa tháng thứ 5: 5 cặp (AB)(CD)(ef)(gh)(ik) (cả cặp (AB) và (CD) cùng đẻ)
Bây giờ, ta xét tới việc tính số cặp thỏ ở tháng thứ n: F(n)
Nếu mỗi cặp thỏ ở tháng thứ n – 1 đều sinh ra một cặp thỏ con thì số cặp thỏ ở tháng thứ n sẽ là:
F(n) = 2 * F(n – 1)
Nhưng vấn đề không phải như vậy, trong các cặp thỏ ở tháng thứ n – 1, chỉ có những cặp thỏ đã có ở tháng thứ n – 2 mới sinh con ở tháng thứ n được thôi. Do đó F(n) = F(n – 1) + F(n – 2) (= số cũ + số sinh ra). Vậy có thể tính được F(n) theo công thức sau:
• F(n) = 1 nếu n ≤ 2
• F(n) = F(n – 1) + F(n – 2) nếu n > 2
(Trích: Cấu trúc dữ liệu và giải thuật – Lê Minh Hoàng)
BEGIN
write('Nhap so thang: ');
readln(thang);
IF thang>2 THEN
BEGIN
tn_2:=1; {Thang dau tien co 1 cap tho}
tn_1:=1; {Thang thu 2 van co 1 cap tho}
FOR i:=3 TO thang DO
BEGIN
tn:=tn_1 + tn_2;
tn_2:=tn_1;
tn_1:=tn;
END;
END
ELSE
tn:=1;
writeln('So con tho sau ',thang,' thang la: ',2*tn);
readln
END.
Lưu ý: hiện nay có một số sai khác về định nghĩa dãy Fibonacci như sau:
• F(n) = 1 nếu n < 2
• F(n) = F(n – 1) + F(n – 2) nếu n >= 2
hoặc theo định nghĩa trên wikipedia:
• F(n) = n nếu n < 2
• F(n) = F(n – 1) + F(n – 2) nếu n >= 2
Nhãn:
Bài tập Pascal,
Câu lệnh lặp,
Vòng lặp for
Previous Article
Keep this going please, great job!
Feel free to visit my weblog bankruptcy florida
lúc 01:57 16 tháng 3, 2013
bạn ơi cho mình hỏi bài toán này sử dụng giải thuật nào trong các giải thuật sau vậy
-giảm để trị
-quay lui
-vét cạn
lúc 22:33 3 tháng 3, 2014
cho mình hỏi luôn: Cho trước số tự nhiên N, hãy tìm biểu diễn Fibonaci của số N.
lúc 20:33 23 tháng 6, 2014
rat hay
lúc 21:59 4 tháng 3, 2019
{$R+,Q+,B-}
uses crt;
const
fi='D:\{tuy chinh}\dulieuchinh\lazarus\phaithumuc\GREEND.INP';
fo='D:\{tuy chinh}\dulieuchinh\lazarus\phaithumuc\GREEND.OUT';
nmax=100;
var
f: text;
a: array[1..nmax,1..nmax] of byte;
temp,c: array[1..nmax,1..nmax] of integer;
code: array[1..nmax] of integer;
fx,fy: array[1..nmax] of integer;
p,q,qu,trx,trys: array[1..nmax] of integer;
first,clast: integer;
n,num,cc:integer;
tcp: longint;
found:boolean;
procedure kt_queue;
begin
first:=1; clast:=0;
end;
procedure them(x: integer);
begin
inc(clast);
qu[clast]:=x;
end;
function lay: integer;
begin
lay:=qu[first];
inc(first);
end;
procedure nhap;
var i,j: integer;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
read(f,code[i]);
while not seekeof(f) do
begin
read(f,i,j);
a[i,j]:=1;
a[j,i]:=1;
end;
close(f);
end;
procedure tinhc;
var i,j,k: integer;
begin
for i:=1 to n do
for j:=1 to n do
if a[i,j]=0 then temp[i,j]:=maxint div 2
else temp[i,j]:=a[i,j];
for i:=1 to n do temp[i,i]:=0;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (temp[i,j]>temp[i,k]+temp[k,j])
then
temp[i,j]:=temp[i,k]+temp[k,j];
for i:=1 to n do
for j:=1 to n do
c[i,j]:=-temp[code[i],j];
end;
procedure tinhfxfy;
var i,j: integer;
begin
fillchar(fy,sizeof(fy),0);
for i:=1 to n do
begin
fx[i]:=-maxint div 2;
for j:=1 to n do
if fx[i]p[i])and(fx[i]+fy[j]=c[i,j]) then
begin
trys[j]:=i;
if q[j]=0 then begin found:=true; cc:=j;
exit;
end
else xuly(j);
end;
end;
end;
procedure tang;
var i,j,k: integer;
begin
k:=cc;
repeat
j:=k;
i:=trys[j];
k:=p[i];
p[i]:=j;
q[j]:=i;
until k=0;
inc(num);
end;
procedure sunhan;
var min,i,j: integer;
begin
min:=maxint div 2;
for i:=1 to n do
if trx[i]<>0 then
for j:=1 to n do
if (trys[j]=0) and (min>fx[i]+fy[j]-c[i,j]) then
min:=fx[i]+fy[j]-c[i,j];
for i:=1 to n do
if trx[i]<>0 then fx[i]:=fx[i]-min;
for j:=1 to n do
if trys[j]<>0 then fy[j]:=fy[i]+min;
end;
procedure tinhkq;
var i: integer;
begin
tcp:=0;
for i:=1 to n do inc(tcp,c[i,p[i]]);
end;
procedure dieukien;
begin
repeat
chbitim;
timduong;
if found then tang else sunhan;
until num=n;
tinhkq;
end;
procedure inkg;
var i: integer;
begin
assign(f,fo); rewrite(f);
writeln(f,abs(tcp));
close(f);
end;
begin
nhap;
chuanbi;
dieukien; {xongbai}
inkg;
end.
lúc 22:02 4 tháng 3, 2019
Đăng nhận xét