Bài toán về số Fibonacci (tổng hợp một số dạng toán)

68
Lập trình C++

Bài toán. Số Fibonacci:

a) Tìm số Fibonacci thứ n (n <= 40)

b) Tìm các số Fibonacci nhỏ hơn hoặc bằng n.

c) Tìm các số Fibonacci nằm trên đoạn [m, n].

d) Tìm các số vừa là số Fibonacci vừa là số nguyên tố trên đoạn [m, n].

Yêu cầu: Nhập vào số n. Trong file đầu ra ghi 4 kết quả như trên. Ví dụ: 

FIBONACCI.INP

FIBONACCI.OUT

3 40

102334155

1 1 2 3 5 8 13 21 34

5 8 13 21 34

5 13

Code tham khảo:

#include <iostream>
#include <cmath>
using namespace std;
int nguyenTo(int n) {
    if (n < 2) return 0;
    int i;
    int s = sqrt(n);
    for (i = 2; i <= s; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}
int Fibonacci(int n) {
    int a1 = 1, a2 = 1;
    if (n == 1 || n == 2) return 1;
    int i = 3, a;
    while (i <= n) {
        a = a1 + a2;
        a1 = a2;
        a2 = a;
        i++;
    }
    return a;
}
int main() {
    freopen("FIBONACCI.INP","r",stdin);
    freopen("FIBONACCI.OUT","w",stdout);
    int m, n, i = 0;
    cin >> m >> n;
    // So Fibonacci thu n:
    cout << Fibonacci(n) << endl;
    // So Fibonacci < n:
    for (i = 0; i < n; i++) {
        if (Fibonacci(i) < n) cout << Fibonacci(i) << " ";
    }
    cout << endl;
    // So Fibonacci nam trong doan [m,n]:
    for (i = 0; i < n; i++) {
        if (Fibonacci(i) > m && Fibonacci(i) < n)
            cout << Fibonacci(i) << " ";
    }
    cout << endl;
    // So Fibonacci vua la so nguyen to doan [m,n]:
    i = m;
    while (Fibonacci(i) < n) {
        int fi = Fibonacci(i);
        if(nguyenTo(fi)) {
            if (fi > m)
                cout << fi << " ";
        }
        i++;
    }
    return 0;
}