Kiểm tra số Fibo bằng code C

#1

Mọi người ơi. Có cách code C nào để kiểm tra 1 số có phải là số Fibonacci không ạ?
Mảng động em cũng chưa được học nên không biết làm thế nào. Mong mn giúp em ạ

#2

Không cần mảng đâu :smiley: chỉ cần 3 biến với vòng lặp thôi.

1 Like
#3

Anh có thể giải thích rõ hơn k ạ? Vì e tự học nên nhiều điều chưa rõ.

#4

Quay lại công thức (truy hồi) Fn+1 = Fn + Fn-1. Rõ ràng ta chỉ cần lưu hai số để tính số tiếp theo của dãy Fibo, thêm một biến kết quả là 3.
Vậy ta có thể đặt 3 biến t1, t2 và kq sao cho t1 = F[n-1] && t2 = F[n] && kq == t1+t2. Ở bước lặp tiếp theo ta sẽ cho t1 = F[n] và t2 = F[n+1] để kq ra F[n+2] (vâng, chính là quy nạp). Do t2 đang giữ F[n] nên ta phải gán t1 = t2 trước, sau đó mới lấy t2 = kq, cuối cùng lấy kq = t1+t2. Vậy là xong. 3 biến là vừa đúng.

1 Like
#5

  • Bạn tìm đọc dãy Fibonacci trước nha.

  • Cách hiện thực hàm tính fibonacci theo đệ quy

int fibonacci(int n)
{
     if(n <= 1) return n;
     else return fibonacci(n -1) + fibonacci(n - 2);
}
1 Like
#6

mình nghĩ bài này chỉ 1 vòng while là ok :)))

#7

vd kinh điển của quy hoạch động …:smiley:

#8

Ừ :smiley: đây là giai đoạn sau khi tìm ra công thức truy hồi thì hiện thực nó để hạn chế số ô nhớ cần dùng.

Với kiểu n-1 và n-2 thì có thể swap 2 biến vẫn được nhưng tính lại vẫn là 3 biến. Với mảng QHĐ hai chiều thì swap hai dòng là tốt hơn cả.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?