Bài 40. Cách tính số Fibonacci trong C/C++

cach-tinh-so-fibonacci
cach-tinh-so-fibonacci

Chắc các bạn cũng đã biết dãy Fibonacci là gì rồi. Đó là dãy số mà số tiếp theo là tổng của hai số liền trước, ví dụ: 1, 1, 2, 3, 5, 8, 13, …. Bài viết này sẽ hướng dẫn cho các bạn cách tính số fibonacci bằng phương pháp dùng đệ quy và không dùng đệ quy.

Dùng đệ quy để tính số fibonacci

Công thức truy hồi của dãy fibonacci có dạng: f(n) = f(n-1) + f(n-2) .

Với f(1) = 1;  f(2) =1;

Cách tính số Fibonacci trong C

Cách tính số Fibonacci trong C++

Khi đã có hệ thức truy hồi thì việc viết hàm đệ quy rất đơn giản phải không nào ? Nhưng liệu bạn có thử nhập n lớn ( cỡ 30 – 40 ) không ạ. Nếu thử rồi thì chắc các bạn cũng thấy nó chậm hơn rất nhiều. Nguyên nhân là khi tính số fibonacci thứ 5 chương trình sẽ yêu cầu tính hai số fibonacci thứ 4 và thứ 3. Nó lại tiếp tục như vậy đến khi tính được số fibonacci thứ 2 hoặc thứ 1 mới dừng lại.

Cách tính số fibonacci
Cách tính số fibonacci

Vậy nếu muốn chương trình của chúng ta chạy nhanh hơn thì chúng ta phải khử đệ quy. Cùng làm nhé !

Cách tính số Fibonacci không dùng đệ quy

Ý tưởng cách này là chúng ta sẽ dùng một vòng lặp để tính số Fibonacci .

  • Nếu n = 1 hoặc n = 2 thì chúng ta return 1
  • Sau đó tạo một biến i có giá trị bằng 3
  • Trong vòng while chúng ta tính a = a1 + a2
  • Sau đó gán a1 = a2 và a2 = a cứ chạy đến khi nào i = n thì dừng

Cách tính số Fibonacci trong C++

Tìm 1000 số Fibonacci đầu tiên

Với code trên bạn tìm đến số Fibo thứ 50 là bị tràn số rồi. Code với số nguyên lớn dưới đây sẽ giúp bạn tính được số Fibo thứ 1000 hoặc hơn thế nữa. Có thể bạn sẽ cần đọc bài viết dưới đây trước khi tham khảo code này.

Cộng trừ nhân chia 2 số nguyên lớn trong C/C++

Lời giải cho chương trình in ra 1000 số Fibo đầu tiên.

Dưới đây là giá trị của số Fibo thứ 1000:

Theo dõi lập trình không khó tại:

avatar
  Subscribe  
newest oldest most voted
Notify of
Nguyen Hai
Guest
Nguyen Hai

Anh ơi. Nếu thử với cách cuối thì có vẻ ra kết quả nhanh hơn khi input: 40. Nhưng thử với input: 50 thì ra sai ý ạ

Minh
Guest
Minh

in ra nguyên dãy fib bằng đệ quy thì làm như nào ạ ?

Hùng
Guest
Hùng

code này chỉ thỏa mãn các test với n<=10^6. Muốn thỏa mãn với mọi n thì phải áp dụng nhân ma trận vào nhé các bạn

shiro
Guest
shiro

em muốn tính số fibo thứ 1000 thì làm sao ạ ???

Nguyễn Bảo Trung
Guest
Nguyễn Bảo Trung

Em có đề bài là tìm số tử thứ n của 3*f(n-1)-f(n-2);
nếu dùng cách k dùng hàm đệ quy như trên thì nên sửa các số a1,a2,a ra sao vậy ạ?
Mong thầy trả lời giúp em với ạ!
Em xin cảm ơn!