检查第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。因此,我们可以说第15个斐波纳契项可被10整除。
让我们看一下获得想法的算法。
算法
fiboDivTen(term)
Begin if term is divisible by 15, then return true end if return false End
示例
#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