《斐波纳契数列》
题目描述:斐波那契数列是一组第一位和第二位为1，从第三位开始，后一位是前两位和的一组递增数列，
像这样的：1、1、2、3、5、8、13、21、34、55。 写出第n项。
非递归思想
算法思路
和辗转相除法的非递归解法好像
辗转相除法是while循环以及中间是百分号
这里是for循环以及中间是加号（f3=f2+f1）
for循环是知道循环次数的循环，while循环是单一限制条件的循环
代码实现
int Fibno2(int n)
{
int num1 = 1;
int num2 = 1;
int tmp = 0;
int i = 0;
if (n < 3)
{
return 1;
}
else
{
for (i = 0; i>n-3; i++)
{
tmp = num1 + num2;
num1 = num2;
num2 = tmp;
}
return tmp;
}
}
递归思想
算法思路
本题的递推条件为： f(n)=f(n-1)+f(n-2) f(1)=1,f(2)=1;
递推条件的限制条件 f(1)=1,f(2)=1是递归的限制条件
递推条件的公式是递归的主体部分
这样来想递归是不是特别简单
递归和非递归的区别：
这里的非递归是从前往后推从而得到结论的，例如通过f(1)和f(2)得f(3)， 通过f(2)和f(3)得f(4)...
递归却是从后往前，要求 f(9)，就要求f(8)和f(7),要求f(8)，就要求f(7)和f(6)
递归的具体过程这里就不赘述了，递归是先由后往前，再由前往后得到f(9)，进行了两轮
非递归是直接由前往后到f(9) ，进行了一轮
代码实现
int Fibon1(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
else
{
return Fibon1(n - 1) + Fibon1(n - 2);
}
}
int main()
{
int n = 0;
int ret = 0;
scanf("%d", &n);
ret = Fibon1(n);
printf("ret=%d", ret);
return 0;
}
《台阶问题》
题目描述:有n阶台阶，每次可以跨一阶或者二阶，求总共有多少种走法?
暴力思想
算法思路
给个分析的例子：
有一个11级的台阶，一个人可走一步也可走两步，问这个人有多少种方法走完这个台阶？
解：
①只用一步走：1+1+1+1+1+1+1+1+1+1+1=11，共11步，只有C11,1=1种走法。
②用了一次两步走：1+1+1+1+1+1+1+1+1+2=11，共10步，有C10,1 =10种走法。
③用了两次两步走：1+1+1+1+1+1+1+2+2=11，共9步，有C9,2 =36种走法。
④用了三次两步走：1+1+1+1+1+2+2+2=11，共8步，有C8,3= 56种走法。
⑤用了四次两步走：1+1+1+2+2+2+2=11，共7步，有C7,4=35种走法。
⑥用了五次两步走：1+2+2+2+2+2=11，共6步，有C6,1=6种走法。
总共有1+10+36+56+35+6=144种
代码实现
递归思想
算法思路
只有一个台阶的话，只有1种走法，
2级台阶的话，可以一步一个台阶走，也可以一步2个台阶走，共有2种走法。
当台阶数大于等于3之后，可以这么分析：
如果最后一步走一个台阶，那么就是n-1个台阶的走法的种类，
如果最后一步走两个台阶，那么就是n-2个台阶的走法的种类，
所以n个台阶的走法种类就是n-1个台阶和n-2个台阶的走法的总和。
因此，这是一个递归函数。也是一个裴波那契函数。
代码实现
public int getResultByRecursion(int n){
if (n <1) {
return 0;
}
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
return getResultByRecursion(n-1) + getResultByRecursion(n-2);
}
算法分析
时间复杂度为2的n次方。
image
没错，这是一棵二叉树，如图所示，这里同样颜色的表示重复计算的节点，而且多数都不止重复计算了一次。我们可以对此进行优化，使用哈希表存储已经计算的节点，不再重复计算。
备忘录算法
算法思路
将计算过的保存起来
代码实现
public int getResultByMap(int n, Map<Integer,Integer> map){
if (n <1) {
return 0;
}
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
if(map.containsKey(n)){
return map.get(n);
}else{
int value = getResultByMap(n-1,map) + getResultByMap(n-2,map);
map.put(n,value);
return value;
}
}
算法分析
时间复杂度和空间复杂度都为O(n)。其实，我们无非使用了空间换时间，但这里很多节点不用保存，比如说，我们自底向上地来考虑这个问题，n为1和2时是显而易见的，当n=3时，可通过1和2的结果来得出，当n=4时，可通过2和3的结果来得出，我们只需要保存最近的两个结果就可以了。所以，还可以进一步优化。
动态规划
代码实现
public int getResultByDP(int n){
if (n <1) {
return 0;
}
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
int a = 1;
int b = 2;
int temp = 0;
for (int i = 3; i < n+1 ; i++) {
temp = a + b;
a = b;
b= temp;
}
return temp;
}
算法分析
时间复杂度为O(n)，空间复杂度为O(l)。
《跳台阶》
楼梯有n(100 > n > 0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。
递归思想
代码实现
#include <iostream>
using namespace std;
int a[105];
int main(){
a[1]=1;
a[0]=1;
a[2]=2;
int n;
while(cin>>n&&n!=0){
for(int i=2;i<=n;i++){
a[i]=a[i-1]+a[i-2]+a[i-3];
}
cout<<a[n]<<endl;
}
return 0;
}
《变态跳台阶》
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级，。。。，它也可以跳上n级，求该青蛙跳上一个n级的台阶总共有多少种方法？
《兔子问题》
题目描述:有一对小兔子，小兔子过Z个月长大，一对大兔子X个月生Y对小兔子，求n个月后的兔子总对数。
问题一：
有一对小兔子，小兔子过5个月长大，一对大兔子3个月生4对小兔子，求n个月后的兔子总对数。
f(n)表示n个月后的兔子总数
f(n)=n那个月原有的兔子+n那个月新生的兔子
n那个月原有的兔子是：f(n-1)
n那个月新生的兔子是：n-x那个月成熟的兔子，也就是n-x-z那个月所有的兔子，因为n-x-z那个月所有的兔子在n-x那个月的时候都成熟了
故f(n)= f(n-1)+ f(n-x-z)(y/x)；这里必须是(y/x)，这是每个月生产的。
这个表达式也适合于一个月生一对的情况；
一个月的情况可以看成成熟+不成熟，和原来的+新生的。而多个月的情况看成后一种比较好，因为看成前一种会超级麻烦。
到本题，也就是f(n)= f(n-1)+ f(n-x-z)y；也就是f(n)= f(n-1)+ f(n-8)(4/3)；
问题二：
有一对小兔子，小兔子过5个月长大，一对大兔子3个月生4对小兔子，求n个月后的大兔子总对数。
用f(n)表示大兔子，那么
f(n)= 上个月的大兔子数+这个月新长成的大兔子数
上个月的大兔子数是：f(n-1)
这个月新长成的大兔子数是：因为兔子需要5个月长大，所以应该是n-5个月那个月的新出生的兔子，
n-5个月那个月的新出生的兔子是n-5-3那个月的所有大兔子数，因为大兔子经过三个月才能下崽崽，
故f(n)=f(n-1)+f(n-5-3)*(4/3);
其实因为我把它看成每月生产(4/3)对兔子，所以不需要再减3
代码实现
#include <iostream>
using namespace std;
//前八个月的兔子总对数都是一对，initTotalRabbit[1]表示第一个月
double initTotalRabbit[9]={0,1,1,1,1,1,2.3333,3.6667,5};
double calcTotalRabbit(int n){
if(n<=8)
return initTotalRabbit[n];
else
return calcTotalRabbit(n-1)+ calcTotalRabbit(n-8)*(4.0/3);
}
//前五个月的大兔子数目为0，initBigRabbit[1]表示第一个月的大兔子数目
double initBigRabbit[9]={0,0,0,0,0,0,1,1,1};
double calcBigRabbit(int n){
if(n<=8)
return initBigRabbit[n];
else
return calcBigRabbit(n-1)+ calcBigRabbit(n-5)*(4.0/3);
}
int main(){
for(int i=1;i<=20;i++){
double total=calcTotalRabbit(i);
double big=calcBigRabbit(i);
printf("月份：%3d 兔子总对数：%6.2lf 大兔子对数：%6.2lf 小兔子对数：%6.2lf\n",i,total,big,total-big);
}
return 0;
}
网友评论