数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找具有给定索引的 N 个斐波那契数的 GCD
这里我们必须找到具有给定索引的 n 个斐波那契项的 GCD。因此，我们首先必须获得最大索引并生成斐波那契项，一些斐波那契项如下：0、1、1、2、3、5、8、13、21、34、……索引从 0 开始。因此，第 0 个索引处的元素为 0。如果我们必须在索引 {2、3、4、5} 处找到斐波那契项的 gcd，那么这些项为 {1、2、3、4}，所以这些数的 GCD 为 1。
我们将使用一种有趣的方法来完成此任务。要获得第 i 和第 j 个斐波那契项的 GCD，例如 GCD(Fibo(i)，Fibo(j))，我们可以将其表示为 Fibo(GCD(i，j))
示例
#include <iostream>
#include <algorithm>
using namespace std;
int getFiboTerm(int n){
int fibo[n + 2];
fibo[0] = 0; fibo[1] = 1;
for(int i = 2; i<= n; i++){
fibo[i] = fibo[i - 1] + fibo[i - 2];
}
return fibo[n];
}
int getNFiboGCD(int arr[], int n){
int gcd = 0;
for(int i = 0; i < n; i++){
gcd = __gcd(gcd, arr[i]);
}
return getFiboTerm(gcd);
}
int main() {
int indices[] = {3, 6, 9};
int n = sizeof(indices)/sizeof(indices[0]);
cout << "GCD of fibo terms using indices: " <<
getNFiboGCD(indices, n);
}输出
GCD of fibo terms using indices: 2
更新于：2019 年 10 月 21 日
173 次浏览
广告