이 문제에서 정수 값 N이 주어집니다. 우리의 임무는 C ++ 프로그램을 사용하여 N번째 비피보나치 수를 찾는 것입니다. .
피보나치 수열은 두 개의 이전 숫자를 더하여 후속 숫자를 생성합니다. 피보나치 수열은 F0과 F1의 두 숫자로 시작합니다. F0 및 F1의 초기 값은 각각 0, 1 또는 1, 1을 취할 수 있습니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
N = 5
출력
10
해결 방법
이 문제에 대한 간단한 해결책은 피보나치 수를 찾은 다음 피보나치 수에 없는 처음 n개의 수를 인쇄하는 것입니다.
또 다른 솔루션은 피보나치 수식을 사용한 다음 두 피보나치 수 사이의 간격을 연속적으로 추가하는 것입니다. 마침내 모든 갭의 합 값은 원하는 결과를 낳을 것입니다. 여기서 우리는 크래킹에 대한 합리적인 아이디어를 사용할 것입니다.
알고리즘
-
현재 요소, 이전 요소 및 이전 요소를 추적할 세 개의 변수를 만듭니다.
-
비 피보나치의 개수가 음수가 아닌 동안 피보나치 수 − Fib(n)=Fib(n-1)+Fib(n-2)의 간단한 공식을 사용하십시오.
-
공식 n=n+(curr-prev-1)을 사용하여 비 피보나치 수의 개수를 얻으려면
-
-
이제 n번째 비 피보나치 수를 얻으려면 n에서 이전 수를 뺍니다.
예
솔루션 작동을 설명하는 프로그램
#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;
} 출력
Nth non fibonacci number is 12