Bàn về giải thuật kiểm tra một số có phải là số Fibonaci hay không

[luckyluke]

Như các bạn đều biết thì số Fibonaci là một số có tính truy hồi ngặt, nghĩa là phải biết F(0) thì mới tính được F(n). Mình có viết một hàm Kiểm tra xem một số n có phải là số Fibonacci ko như sau:

Trước hết viết một hàm tính số Fibonaci thứ i fibo(i), (cái này dùng đệ quy) ai cũng biết.

Sau đó viết hàm kiemtra

kq=1;
do
{
          i++;
}while (fibo(i)<n)

if (fibo(i)==n)
     return 1;
else
     return 0;

Như vậy nếu fibo(i) = n thì n sẽ là số fibo thứ i.

Có bạn nào còn thuật toán khác chạy nhanhn hơn ko, vì mình thấy càng trở về phía bên phải của trục số thì các số fibo sẽ phân bố càng thưa, như vậy nếu dùng cách trên sẽ chạy hơi lâu.

[NT_OnlyLove]

kq=1;
do
{
          i++;
}while (fibo(i)<n)

if (fibo(i)==n)
     return 1;
else
     return 0;

Như vậy nếu fibo(i) = n thì n sẽ là số fibo thứ i.

Trước tôi làm các phép toán với số fibo tôi cũng dùng đệ quy.
Nhưng hình như bài này có thể làm bằng Quy Hoạch Động ( Cái này tôi chưa có nghiên cứu).
Tuy nhiên đoạn code trên của bạn tôi chưa hiểu "kái" kq=1; là gì rứa.
Với lại :

if (fibo(i)==n)

nó sẽ gọi lại một lần nữa fibo(i). Bạn nghĩ xem nó sẽ như thế nào với cái phía trên bạn đã gọi một lần rồi?
Bạn có thể để một biến Tmp=fibo(i); ở trên, khi đó chỉ cần

if(Tmp == n) return 1;//true
return false;//cái này khỏi phải else làm gì nữa

Đó chỉ là cái tôi thấy không hợp lý trong đoạn code của bạn.
Bạn có thể post bài hoàn chỉnh của bạn lên mọi người sẽ đưa ra ý kiến.
Như vậy sẽ rõ ràng hơn là post một đoạn mập mờ như trên.
Thân.

[rox_rook]

Tìm sách giải thuật của Lê Minh Hoàng mà đọc, giải Fina thì dùng QHD là ok nhất rùi. Công thức truy hồi cho bài này cũng rất đơn giản, có thể nói là cơ bản nhất của QHD.