首页  >  文章  >  后端开发  >  一个高效的方法来检查第n个斐波那契数是否是10的倍数?

一个高效的方法来检查第n个斐波那契数是否是10的倍数?

王林
王林转载
2023-09-05 08:05:08768浏览

一个高效的方法来检查第n个斐波那契数是否是10的倍数?

这里我们将看到一种有效的方法来检查第 n 个斐波那契项是否是 10 的倍数。假设斐波那契项为 {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987}。因此,这里第 15 个斐波那契数(从 0 开始计数)可以被 10 整除。对于 16,它将返回 true。

一种最简单的方法是生成直到给定项的斐波那契数,并且检查是否能被10整除?但这个解决方案并不好,因为它不适用于较大的项。

另一个好的方法如下 -

斐波那契项 - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

这些数字(标记为粗体字母)可以被2整除。它们的间隔是3个斐波那契项。同样,请检查 -

斐波那契项:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

每第 5 项都可以被 5 整除。现在 3 和 5 的 LCM 是 15。所以我们可以说每 15th 斐波那契项都可以被 10 整除。

让我们看看算法来理解这个想法。

算法

fiboDivTen(term)

Begin
   if term is divisible by 15, then
      return true
   end if
   return false
End

Example

的中文翻译为:

示例

#include<iostream>
using namespace std;
bool fiboDivTen(int term) {
   if(term % 15 == 0){
      return true;
   }
   return false;
}
int main() {
   int term = 45;
   if (fiboDivTen(term))
      cout << "Divisible";
   else
      cout << "Not Divisible";
}

输出

Divisible

以上是一个高效的方法来检查第n个斐波那契数是否是10的倍数?的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除