斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368…
这个数列从第3项开始,每一项都等于前两项之和。
表达式:F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)
分治法 算法设计模式: Divide-and-Conquer§
实现:
#include <stdio.h>
int fib(int n)
{
if (n == 0 || n == 1)
{
return n;
}
return fib(n - 1) + fib(n - 2);
}
int main()
{
int i;
for (i = 0; i <= 12; i++)
{
printf("%d \n", fib(i));
}
return 0;
}
动态规划法 算法设计模式:求解决策过程最优化 1.寻找转态转移方程式 2.利用状态转移方程式自底向上求解问题
实现:
#include <stdio.h>
int fib(int *dp, int n)
{
if(n == 0 || n == 1)
{
dp[n] = n;
return dp[n];
}
if (dp[n - 1] == 0)
{
dp[n - 1] = fib(dp, n - 1);
}
if (dp[n - 2] == 0)
{
dp[n - 2] = fib(dp, n - 2);
}
dp[n] = dp[n - 1] + dp[n - 2];
return dp[n];
}
int main()
{
int i;
int dp[25] = {0};
for (i = 0; i <= 20; i++)
{
printf("%d\n", fib(dp, i));
}
return 0;
}