Trong bài toán này, chúng ta được cung cấp một giá trị nguyên N. Nhiệm vụ của chúng ta là sử dụng chương trình C + + để tìm Số không Fibonacci thứ N .
Chuỗi Fibonacci tạo ra số tiếp theo bằng cách thêm hai số trước đó. Chuỗi Fibonacci bắt đầu từ hai số - F0 &F1. Các giá trị ban đầu của F0 &F1 có thể được lấy tương ứng là 0, 1 hoặc 1, 1.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 5
Đầu ra
10
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm số Fibonacci và sau đó in n số đầu tiên không có trong Số Fibonacci.
Một giải pháp khác là sử dụng công thức số fibonacci và sau đó tiếp tục cộng khoảng cách giữa hai số fibonacci liên tiếp. Cuối cùng, giá trị của tổng tất cả các khoảng trống sẽ dẫn đến kết quả đầu ra mong muốn. Ở đây, chúng tôi sẽ sử dụng ý tưởng hợp lý để bẻ khóa.
Thuật toán
-
Tạo ba biến sẽ theo dõi phần tử hiện tại, phần tử trước đó và phần tử trước đó.
-
Mặc dù số lượng Fibonacci không phải là số âm, hãy sử dụng công thức đơn giản của số Fibonacci - Fib (n) =Fib (n-1) + Fib (n-2).
-
Để tính số lượng không phải Fibonacci bằng cách sử dụng công thức n =n + (curr-prev-1).
-
-
Bây giờ, để lấy số không phải Fibonacci thứ n, hãy trừ số trước đó cho n.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include<iostream>
using namespace std;
int findNthNonFiboNumber(int n){
int lastLastVal = 1, lastVal = 2, currVal = 3;
while (n > 0){
lastLastVal = lastVal;
lastVal = currVal;
currVal = lastLastVal + lastVal;
n = n - (currVal - lastVal - 1);
}
n = n + (currVal - lastVal - 1);
return (lastVal + n);
}
int main(){
int n = 7;
cout<<"Nth non fibonacci number is "<<findNthNonFiboNumber(n);
return 0;
} Đầu ra
Nth non fibonacci number is 12