斐波那契数列动态规划c++
时间: 2023-09-22 07:11:53 浏览: 140
以下是使用动态规划求解斐波那契数列的 C++ 代码:
```c++
#include <iostream>
using namespace std;
int Fibonacci(int n) {
// 创建一个数组来存储斐波那契数列的值
int fib[n+1];
fib[0] = 0;
fib[1] = 1;
// 使用动态规划计算斐波那契数列的值
for (int i = 2; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}
int main() {
int n = 10;
cout << "斐波那契数列第" << n << "项的值为:" << Fibonacci(n) << endl;
return 0;
}
```
该代码中,我们使用一个数组 `fib` 来存储斐波那契数列的值,数组下标从 0 开始,因此数组的长度应为 `n+1`。接着,我们初始化数组的前两个元素为 0 和 1,然后使用循环计算出数组中的剩余元素,即斐波那契数列的值。最后,返回数组中第 `n` 个元素的值即可。
运行上述代码得到的输出为:
```
斐波那契数列第10项的值为:55
```
相关问题
斐波那契数列c++动态规划
斐波那契数列是指这样一个数列:0、1、1、2、3、5、8、13、21、34、……,其中每一项都等于前两项之和。c++动态规划法求斐波那契数列的思路是:先定义一个数组F,F[i]表示斐波那契数列中第i个数的值,然后通过循环计算F[i]的值,最后返回F[n]即可得到斐波那契数列中第n个数的值。具体实现可以参考以下代码:
```
#include <iostream>
using namespace std;
int number(int* F, int n) {
if (n == 0) return F[0];
else if (n == 1) return F[1];
else {
for (int i = 2; i <= n; i++) {
F[i] = F[i - 1] + F[i - 2];
}
return F[n];
}
}
int main() {
int n, num;
int F[10];
cin >> n;
F[0] = 0;
F[1] = 1;
num = number(F, n);
cout << num << endl;
return 0;
}
```
斐波那契数列快速幂c++
斐波那契数列是一个经典的数学问题,它的定义是:第一个和第二个数为1,从第三个数开始,每个数都是前两个数的和。即:1, 1, 2, 3, 5, 8, 13, 21, ...
快速幂是一种优化指数运算的算法,可以在较短的时间内计算出较大的指数幂。在斐波那契数列中,我们可以使用快速幂算法来计算第n个斐波那契数。
以下是使用C++实现斐波那契数列快速幂的代码:
```cpp
#include <iostream>
// 使用快速幂算法计算斐波那契数列
int fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int a = 1, b = 1;
int c = 0, d = 1;
int temp1, temp2;
while (n > 0) {
if (n % 2 == 1) {
temp1 = a * c + b * d;
temp2 = b * c + d * (a + b);
a = temp1;
b = temp2;
}
temp1 = c * c + d * d;
temp2 = d * (2 * c + d);
c = temp1;
d = temp2;
n /= 2;
}
return a;
}
int main() {
int n;
std::cout << "请输入要计算的斐波那契数列的位置:";
std::cin >> n;
int result = fibonacci(n);
std::cout << "第" << n << "个斐波那契数是:" << result << std::endl;
return 0;
}
```
阅读全文