斐波那契数列动态规划写算法c语言
时间: 2024-10-09 09:13:34 浏览: 39
斐波那契数列是一个经典的动态规划问题,通常递归形式简单直观,但是效率较低,因为它会重复计算许多子问题。而通过动态规划,我们可以存储已经计算过的值以避免冗余计算。下面是一个使用C语言实现的斐波那契数列动态规划算法:
```c
#include <stdio.h>
// 动态规划函数
int fibonacci(int n) {
if (n <= 0) {
return 0; // 0和负数的斐波那契数都是0
}
if (n == 1 || n == 2) {
return 1; // 基本情况,前两个数都是1
}
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]; // 返回第n个斐波那契数
}
int main() {
int n = 10; // 测试数字,你可以改变它
printf("The %dth Fibonacci number is: %d\n", n, fibonacci(n));
return 0;
}
```
相关问题
Fibonacci数列动态规划c语言
Fibonacci数列是一个非常经典的动态规划问题,其定义为:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2)。即,第n个Fibonacci数等于第n-1个Fibonacci数和第n-2个Fibonacci数之和。
下面是使用动态规划算法求解Fibonacci数列的C语言代码:
```c
#include <stdio.h>
int dp[100]; //记录Fibonacci数列中第i个数的值
int Fibonacci(int n)
{
int i;
//初始化dp数组
dp[0] = 0;
dp[1] = 1;
//动态规划求解
for (i = 2; i <= n; i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
//返回第n个Fibonacci数
return dp[n];
}
int main()
{
int n, f;
//读入n
printf("请输入n:");
scanf("%d", &n);
//计算第n个Fibonacci数
f = Fibonacci(n);
//输出结果
printf("第%d个Fibonacci数为:%d\n", n, f);
return 0;
}
```
其中,dp[i]表示Fibonacci数列中第i个数的值。在动态规划求解时,从第3个数开始遍历,dp[i]等于dp[i-1]和dp[i-2]的和。最终,dp[n]即为第n个Fibonacci数的值。
斐波那契数列非递归算法c语言
斐波那契数列的非递归算法可以通过循环实现,具体步骤如下:
1. 定义三个变量a、b、c,分别表示斐波那契数列的前两项和当前项。
2. 将a和b初始化为1,表示斐波那契数列的前两项。
3. 通过循环计算斐波那契数列的第n项,每次将a和b的值相加,得到c的值,然后将b的值赋给a,将c的值赋给b,继续循环计算下一项,直到计算到第n项为止。
4. 返回计算得到的第n项的值。
下面是斐波那契数列的非递归算法的C语言代码实现:
```
int Fibonacci(int n)
{
int a = 1, b = 1, c = 1;
if (n <= 0)
{
return 0; }
else if (n <= 2)
{
return 1;
}
else
{
for (int i = 3; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
}
```
阅读全文