C++에서 n'번째 피보나치 수의 마지막 자릿수를 찾는 프로그램

이 문제에서는 숫자 N이 주어집니다. 우리의 임무는 C++에서 N번째 피보나치 수의 마지막 자릿수를 찾는 프로그램을 만드는 것입니다.

문제 설명

N번째 피보나치 수의 마지막 숫자(예:LSB)를 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력:N =120 출력:1

솔루션 접근 방식

간단한 솔루션은 직접 피보나치 공식을 사용하여 N번째 항을 찾는 것입니다. 그러나 이 방법은 N이 큰 수일 때 실현 가능하지 않습니다. 그래서 이를 극복하기 위해 60항 후에 마지막 숫자가 반복되는 피보나치 수열의 속성을 사용할 것입니다. 즉. 75번째 항의 마지막 숫자는 135번째 항의 숫자와 같습니다.

즉, 60까지 작업하면 가능한 모든 조합이 제공되고 사용할 용어를 찾기 위해 60으로 숫자의 모드를 찾을 수 있습니다.

예시

#include
using namespace std;
long int fibo(int N){
   long int a=0,b=1,c;
   for(int i=2; i< N;i++) {
      c=a+b;
      a=b;
      b=c;
   }
   return c;
}
int findLastDigitNterm(int N) {
   N = N % 60;
   return ( fibo(N)%10);
}
int main() {
   int N = 683;
   cout<<"The last digit of "<<N<<"th Fibonacci term is "<<findLastDigitNterm(N);
   return 0;
}

출력

The last digit of 683th Fibonacci term is 1