View Full Version : Fibonaci
Tinh tong n so Fibonaci dau tien ,chi duoc dung 3 bien .
Nho cac huynh de giup!
CrazyBabe
02-10-2002, 10:26
A:=1;
B:=1;
For Z:=3 to N do
Begin
C:=B+A;
Write(C,' ')
A:=B;
B:=C;
End;
Ok ?
3 bien co ma ,ro rang la ban dung 5 bien roi con gi ?
N,Z,A,B,C
not ok
Function Fibonaci (n : Integer) : Integer
If((n = 0) Or (n = 1)) then
Fibonaci := 1
Else
Fibonaci := Fibonaci (n-1) + Fibonaci (n-2);
End;
Procedure WriteFibonaci(n : Integer)
i : Integer;
For i := 1 To n Do
Writeln('Fibonaci ',i,' : ',Fibonaci(i));
End;
**** Lâu quá nhớ không rõ nữa ,nhưng hình như là vậy.
Dãy Fibonaci hiện có hai cách tính là Đệ quy (TopDown) và dùng Stack(EndUp).
-Phương pháp tôi dùng là TopDown .
Hoan hô quangvu dùng đệ quy được đấy
trong pascal không có "==" đâu nha đừng lôi C vào đây
Sao lại vội khẳng định thế hả quangvu. Nên đọc chương trình trước chứ :
số fib[n] = fib[n-1] + fib[n-2]
nên ta chỉ cần 2 biến lưu lại số thứ n-1 và n-2 là được rồi
Chương trình của CrazyBabe đúng rồi đó chứ.
Góp vui nhé
begin
asm
mov cx,n
sub cx,2
mov bx,1
mov dx,1
xor ax,ax
@loop:
mov ax,bx
add ax,dx
mov bx,dx
mov dx,ax
{ viết ra ax }
{ quên mất rồi các bác thông cảm}
loop @loop
end;
end.
Chương trình này có được coi là hợp lệ không? dùng 0 biến!!
Ông này ăn gian quá ,không dùng biến bộ nhớ mà lại dùng biến thanh ghi.Không hợp lệ . . . nhưng quá hay.
skywalker
05-10-2002, 15:42
sao anh zero viết gì em ko hiểu gì hết vậy, anh giăng lại được ko
please
ý anh ta thế này :
mov cx,n ;Đặt cx = n
sub cx,2 ;cx = cx - 2
mov bx,1 ;đặt bx = 1
mov dx,1 ;đặt dx = 1
xor ax,ax ;đặt ax = 0
@loop: ;bắt đầu lặp , cx = cx - 1
mov ax,bx ;ax = bx
add ax,dx ;ax = ax + dx ,tức Fi = F(i-1) + F(i-2)
mov bx,dx ;bx = dx ,bx = F(i-1)
mov dx,ax ;dx = ax ,dx =F(i-2)
{ viết ra ax }
{ quên mất rồi các bác thông cảm}
loop @loop
trong trường hợp này ax = F(i) ,bx = F(i-1) ,dx = F(i-2).
Chú QuangVu làm thế là không hay rồi.
Thứ nhất làm đệ qui thì hàm đệ qui đóng vai trò như một biến còn gì.
Thứ hai là ct đó mới đưa ra được các số Fibonaci thôi ,chưa tính đựoc tổng của n số.
Còn ct viết băng hợp ngữ thì cũng vậy .Ví dụ như vòng lặp chẳng hạn ,dùng nhãn @loop như vậy thì không hay rồi .Đã vậy còn dùng đén 4 thanh ghi liền ,phạm qui rồi
CrazyBabe
06-10-2002, 17:57
Chà, xin lũi nhá, không đọc kĩ đề mừ:
A:=1;
B:=1;
Write(A,' ',B);
Repeat
A:=A+B;
B:=A-B;
Write(' ',A);
Dec(N);
Until N=2;
Ok không ?
skywalker
06-10-2002, 22:51
vậy thì cách của zero có phải viết trên pascal ko, hình như trên pascal đâu có những thủ tục đó
Thanks CrazyBabe
Nhưng mà chương trình của bạn mới chỉ đưa ra n số Fibonaci đầu tiên
Đề bài là đưa ra tổng n số đầu tiên cơ mà.
Not ok
Ù ù cạc cạc
07-10-2002, 21:32
To sky: muốn dùng các đoạn mã asem trong pascal chỉ cần chèn trong đoạn lệnh ghép: asm end
To hmtz: Câu hỏi khoai quá tui thử tí nhá:
BEGIN
write('Vào số n: ');readln(n);
A:=1;B:=1;t:=2;
write(A,B: 6);
while n>2 do
begin
A:=a+b;
t:=t+a;
write(A:6);
b:=a-b;
end;
writeln('Tổng của ',n,' số fibonaci đầu tiên là: ',t);
END.
Ù ù cạc cạc dùng 4 biến rồi :a,b,n,t
Để tính ta phải tiến hành mã hoá n ,để n có thể là một số cho biết là có n số F phải tính ,vừa là một số để lưu trử tông các F
-Ta nhân n cho 100'000,n -> N
-6 số phí sau để lưu trử tổng F
-Số trước lưu trử n
*Chương trình dùng 3 biến
1.N
2.i (ở hay hàm WriteFibonaci và Fibonaci cũng chỉ là một)
3.Fibonaci
---> Hợp lý
Function Fibonaci (i : Long) : Long
If((n = 0) Or (n = 1)) then
Fibonaci := 1
Else
Fibonaci := Fibonaci (i-1) + Fibonaci (i-2);
End;
Procedure WriteFibonaci(N : Long)
i : Long;
N = N * 100000 ;
For i := 1 To (N div 100000) Do
N = N + Fibonaci (i);
Writeln('Tong F là : ',(N mod 100000));
End;
real_time
09-10-2002, 13:14
quangvu ơi cái vụ này bạn lại nhầm nữa rồi longint chi dến tầm 10 số thôi nếu đem n=1000 hay lớn hơn mà nhân với 100000 thì sẽ sai đó. nếu không thì lại phải tốn thời gian viết xử lý với số lớn mất thời gian lắm đúng không.
real_time
09-10-2002, 13:24
tôi có cách này dùng 3 biến moi người thử cho ý kiến nha!
var
t,n:longint;
function fibo(n:longint):longint;
begin
if (n=0) or (n=1) then fibo:=1;
if (n=2) then fibo:=2
if n>2 then fibo:=fibo(n-1)+fibo(n-2);
end;
begin
n:=0;
repeat
n:=n+1;
t:=t+fibo(n);
until n=n{so can tim}
write(t);
end.
{có lẽ là rất tốn bộ nhớ và cũng có nhược điểm là chưa tính được số lớn}
Bài viết được gửi bởi real_time_program
quangvu ơi cái vụ này bạn lại nhầm nữa rồi longint chi dến tầm 10 số thôi nếu đem n=1000 hay lớn hơn mà nhân với 100000 thì sẽ sai đó. nếu không thì lại phải tốn thời gian viết xử lý với số lớn mất thời gian lắm đúng không.
Sao lại không được ,LongInt đến tầm 10 số mà mình chỉ dùng có 6 số thấp để lưu tổng F ,còn lại 4 số cao để lưu n.Vẩn nhỏ hơn 10 số.
Vả lại ,đâu chỉ là bài mẩu minh hoạ ,kiểu LonInt sẽ bị tràng nếu n quá lớn .Khi cần có nhu cầu tính n lớn ta có thể thay kiểu LongInt bằng kiểu khác lớn hơn mà ,như . . . SuperLongInt chẳng hạng.
OK
Bài viết được gửi bởi real_time_program
tôi có cách này dùng 3 biến moi người thử cho ý kiến nha!
var
t,n:longint;
function fibo(n:longint):longint;
begin
if (n=0) or (n=1) then fibo:=1;
if (n=2) then fibo:=2
if n>2 then fibo:=fibo(n-1)+fibo(n-2);
end;
begin
n:=0; **********
repeat
n:=n+1;
t:=t+fibo(n);
until n=n{so can tim} *********
write(t);
end.
{có lẽ là rất tốn bộ nhớ và cũng có nhược điểm là chưa tính được số lớn}
Sau lại là n=n ,nếu vậy nó chỉ chạy đúng một lần.Và n bắt đầu từ 0 (n=0) thế nó kết thúc ở đâu ?
Tuy nhiên ,chương trình bạn viết rất hay và đúng hướng rồi đó ,sửa lại một tẹo là ổn ngay.
CrazyBabe
10-10-2002, 11:19
Chà chà, lại thiểu năng đọc thiếu rùi, nhưng ko sao, có vấn đề gì đâu nhể, tổng N số fibo đầu tiên bằng số fibo thứ N+2 trừ đi 1 (Tự chứng minh nhá) vì thế ct của tôi sửa lại thế này là xong:
A:=1;B:=1;
Repeat
A:=A+B;
B:=A-B;
Dec(N);
Until N=0;
Write(A-1); -> A là số fibo thứ N+2, right ?
Còn lèo nhèo gì nữa không ?
Góp ý tẹo: Mí bài này quan trọng là thuật toán chứ kĩ thuật không quan trọng, chứ tính số fibo tăng tương đương cấp số nhân thì chỉ đến 100 đã đi xa rùi, lấy đâu ra đến 10000 hả ? Mình giả sử giải với số vô hạn đi được hông ?
Cách giải của CrazyBaby rất hay
Đây là cách của mình:
If (n==1) return 1;
a=2;b=1;
While(n>2)
{
a=a+b+1;
b=a-b-1;
n--;
}
return a;
Cần định nghĩa : thế nào là một biến, kiểu dùng của quangvu thì có khác gì mảng đâu, nếu muốn tránh array thì cho một cái biến động là xong.
Khác chứ ,bởi vì mảng là một tập N biết riên biệt .Mà mình ở đây là "Chẻ đôi LongInt" mà.
Vả lại ,mình chỉ muốn minh hoạ bài trên thôi.Cách chẻ biến còn được gọi là mã hoá biến mình rất hay áp dụng trong một số đoạn code đặc biệt.
real_time
19-10-2002, 15:56
mình chưa hiểu lắm thế nào là "chẻ đôi Longint" ? quangvu giải thích giùm với
Nếu bạn có học qua ASM thì hẵn bạn biết thủ thuật này ,ASM có một thanh ghi (biến) là AX .Biết có 16 bit và người ta có thể dùng "nửa" biến là AH và AL ,phần nửa trên là AH còn nửa dưới là AL.
Trong mã hoá người ta cũng có khi dùng cách này ,giống bạn xé một tấm ảnh ra và dùng từng phần của tấm ảnh vậy.
real_time
20-10-2002, 16:25
à đúng rồi mình đã hiểu! (bạn sẽ dùng nửa dưới làm biến chạy còn nửa trên dùng để là nơi kết thúc chứ gì)
Quang Vu nếu dùng một con trỏ rồi cấp cho nó 16 byte rồi chia làm 4 khoảng -4 byte (longint) thế thì được coi là dùng mấy biến?
Bài viết được gửi bởi Zero
Quang Vu nếu dùng một con trỏ rồi cấp cho nó 16 byte rồi chia làm 4 khoảng -4 byte (longint) thế thì được coi là dùng mấy biến?
???!!!
Ù ù cạc cạc
22-10-2002, 16:44
ê nếu ko cho biết n thì làm sao tính?
chương trình chỉ có 3 biến thui: t,a,b
Tính tổng n số mà không có n thì . . . khỏi tính ,Hỏi kiểu nài Ù ù cạc cạc là phải :")
real_time
25-10-2002, 13:55
nhưng quangvu nè nếu như m_ số đó lớn hơn maxlongint div 2 thôi thì cách chia 2 phần của quangvu bị teo mất rồi
Bài của Crazybaby hay tuyệt (nhưng hình như bạn nhầm tổng =số F(n+2)-2 chứ)
Còn hmtz120 có thể dịch bài của bạn sang Pascal không ? (Mình chưa học C)
Mình đề nghị kết hợp lời giải của các bạn để chỉ phải dùng 2 biến thôi:
Procedure Solve;
Var a,b:longint;
Begin
a:=1;
b:=1;
While n+3>2 do
Begin
a:=a+b;
b:=a-b;
n:=n-1;
End;
Write('Tong = ',a-2);
End;
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.