Chương trình C++ tìm số không Fibonacci thứ N

Mô tả bài toán

Cho N, tìm số nguyên thứ N không phải là số Fibonacci.

Ví dụ

N=5 → Output: 10 (dãy Fibonacci: 0,1,1,2,3,5,8,13...; không Fibonacci: 4,6,7,9,10...).

Giải thuật

Khoảng trống giữa hai số Fibonacci liên tiếp F_i và F_i+1 chứa đúng (F_i+1 - F_i - 1) số không Fibonacci. Duyệt các cặp Fibonacci liên tiếp, trừ dần N cho đến khi N rơi vào khoảng trống hiện tại.

Mã nguồn C++

#include <iostream>
using namespace std;

int findNthNonFiboNumber(int n) {
    int lastLast = 1, last = 2, curr = 3;
    while (n > 0) {
        lastLast = last;
        last = curr;
        curr = lastLast + last;
        n -= (curr - last - 1);
    }
    n += (curr - last - 1);
    return last + n;
}

int main() {
    int n = 7;
    cout << "Nth non fibonacci number is " << findNthNonFiboNumber(n);
    return 0;
}

Đầu ra

Nth non fibonacci number is 12