Tìm dãy số Fibonacci trong C++

Đây là bài 12/15 bài của series môn học TH Nhập môn lập trình

1. Dãy số Fibonacci là gì?

Dãy số Fibonacci là dãy vô hạn các số nguyên dương bắt đầu bằng hai phần tử 0 và 1. Các phần tử sau đó tuân theo quy tắc: mỗi phần tử luôn bằng tổng hai phần tử trước nó. Ví dụ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,…

Công thức truy hồi của dãy số Fibonacci là: S(n) = S(n-1) + S(n-2) với S(0) = 0 và S(1) = 1.

Ví dụ dãy số Fibonacci

Trong lập trình, có 2 dạng yêu cầu phổ biến khi thao tác với dãy số Fibonacci là:

1. Nhập n, xuất ra n chữ số đầu tiên trong dãy số Fibonacci

2. Tìm phần tử thứ n trong dãy số Fibonacci

Trong bài này, các ví dụ sẽ chủ yếu giải quyết yêu cầu: nhập n, xuất n chữ số đầu tiên trong dãy số Fibonacci.

2. Tìm dãy số Fibonacci sử dụng vòng lặp (loop) trong C++

Đoạn code bên dưới sử dụng vòng lặp for để tìm dãy số Fibonacci trong C++.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cout << "Nhap vao mot so nguyen duong: ";
    cin >> n;

    int n1 = 0, n2 = 1;
    if (n == 1) {
        cout<<n1;
    } else if (n == 2) {
        cout<<n1<<" "<<n2;
    } else {
        cout<<n1<<" "<<n2;
        int tempNthTerm;
        for (int i = 3; i <= n; i++) {
            tempNthTerm = n1 + n2;
            cout<<" "<<tempNthTerm;
            n1 = n2;
            n2 = tempNthTerm;
        }
    }

    return 0;
}

Kết quả

Nhap vao mot so nguyen duong: 5
0 1 1 2 3

3. Tìm dãy số Fibonacci sử dụng đệ quy (recursion) trong C++

Đoạn code bên dưới sử dụng đệ quy để tìm dãy số Fibonacci trong C++.

#include <iostream>
#include <cmath>
using namespace std;

//Ham de quy tim day so Fibonacci
int findFibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return findFibonacci(n - 2) + findFibonacci(n - 1);
}
    
int main() {
    int n;
    cout << "Nhap vao mot so nguyen duong: ";
    cin >> n;

    for (int i = 0; i < n; i++) {
        cout<<findFibonacci(i)<<" ";
    }

    return 0;
}

Bài này đã trình bày cách sử dụng vòng lặp for và đệ quy để xuất n chữ số đầu tiên trong dãy số Fibonacci. Các bạn hãy viết chương trình C++ tìm phần tử thứ n trong dãy số Fibonacci.

5/5 - (1 bình chọn)
Bài trước và bài sau trong môn học<< Biện luận và giải phương trình bậc hai với C++Chương trình C++ tìm số ngày của tháng trong một năm >>
Chia sẻ trên mạng xã hội:

Để lại một bình luận

Lưu ý:

1) Vui lòng bình luận bằng tiếng Việt có dấu.

2) Khuyến khích sử dụng tên thật và địa chỉ email chính xác.

3) Mọi bình luận trái quy định sẽ bị xóa bỏ.