算法之美：斐波那契数列（Fibonacci sequence）
斐波那契数列指的是这样一个数列 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§
- if |P|≤n0
- then return(ADHOC§)
- 将P分解为较小的子问题 P1 ,P2 ,…,Pk
- for i←1 to k
- do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
- T ← MERGE(y1,y2,…,yk) △ 合并子问题
- return(T)）
实现：
#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;
} 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-03-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
