赞
踩
从第三项开始,每一项是前两项的和,给定数n,求F(n)。
列出前五项
F(0) | F(1) | F(2) | F(3) | F(4) | |
F(n) | 0 | 1 | 1 | 2 | 3 |
F(n-1)+F(n-2) | 1+0 | 1+1 | 2+1 |
运用动态规划
设计状态:从第三项开始每一次求第n项都转移到求n-1项和n-2项
写出状态转移方程:F(n)=F(n-1)+F(n-2);
设定初始状态:当n=0、1时,F(0)=0,F(1)=1。
执行状态转移
返回最终解
- #include<stdio.h>
- int fib(int n);
- int main()
- {
- int num;
- printf("Please enter the num:");
- scanf("%d",&num);
- printf("%d\n",fib(num)); //调用函数
-
- return 0;
- }
- int fib(int n)
- {
- int F[31];
- int i;
- F[0]=0;
- F[1]=1; //设定初始状态
- for(i=2;i<=n;i++)
- {
- F[i]=F[i-1]+F[i-2]; //执行状态转移
- }
- return F[n]; //返回最终解
- }
1>动态规划步骤
2>设计状态
3>写出状态转移方程
4>设定初始状态
5>执行状态转移
6>返回最终解
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。