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

9
7125

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.

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:

Bài học của mình đến đây là kết thúc.

 

 

 

avatar
4 Comment threads
5 Thread replies
5 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
Nguyễn Văn HiếushiroHùngMinhNguyen Hai Recent comment authors
  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 ý ạ

Nguyễn Văn Hiếu
Admin
Nguyễn Văn Hiếu

Số Fib thứ 50 thì tràn số rồi em à(chắc là ra số âm hả?), vì nó là một số rất lớn vượt quá giới hạn của kiểu int

Nguyen Hai
Guest
Nguyen Hai

Vâng anh ơi. E có thử thay thế = cả các kiểu dl khác r, cũng k đc ạ. Lạ thật

Nguyễn Văn Hiếu
Admin
Nguyễn Văn Hiếu

Ắt hẳn nó là con số rất lớn, em có thể kiểm chứng bằng cách in các số Fib từ 1 đến 50 để xem khi nào bắt đầu tràn số nhé.
Tham khảo thêm bài Phạm vi giá trị các kiểu dữ liệu trong C/C++

Minh
Guest
Minh

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

Nguyễn Văn Hiếu
Admin
Nguyễn Văn Hiếu

Em có hàm đệ quy tìm số fib thứ n rồi thì em chỉ cần for vào in ra thôi
func fib(int n) {};

For i from 0 to n
print fib(i)

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 Văn Hiếu
Admin
Nguyễn Văn Hiếu

Bài viết đã cập nhật code để tính tới số Fibo thứ 1000 nhé em