C++程序：查找第n个斐波那契数的最后一位数字

在这个问题中，我们给定一个数字N。我们的任务是创建一个C++程序来查找第N个斐波那契数的最后一位数字。

问题描述

我们需要找到第N个斐波那契数的最后一位数字（即最低有效位）。

让我们举个例子来理解这个问题，

输入：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

Ayush Gupta

更新于：2020年10月9日

468 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习