第2章 算法效率分析基础

2.2 渐进符号和基本效率类型

类型按照增长次数的升序排列

2.4 递归算法的数学分析

反向替代法

分析递归算法时间效率的通用方案

汉诺塔游戏

手写的详细步骤

四个盘子时：

代码实现

#include <stdio.h>
int m=0;
void Move(int n,char A,char B,char C)//A和B柱并不固定，可以互换，A是盘子所在的塔，B是辅助塔，C是目标塔,函数的目的是把A上的n个盘子通过B全部转移到C
{
        m++;
        //设置移动盘子的结束条件（当只有一个盘子时直接从A或B柱移到C柱）,如果A当前还有一个盘子那么就把他直接移动到C
        if(n == 1) 
        {
                printf("%c -> %c\n",A,C);
        }
    	//否则开始递归
    	else
        {		
            	//递归， 将A上编号为1至n-l的圆盘移到B, C做辅助塔；
                Move(n-1,A,C,B);
                //直接将编号为n的圆盘从A移到C;
                printf("%c -> %c\n",A,C);
 				//递归， 将B上编号为1至n-1的圆盘移到C, A做辅助塔
                Move(n-1,B,A,C);
        }
}
int main()
{
        int n;
        printf("请输入盘子数：");
        scanf("%d",&n);
        //如果有五个盘子，和A，B，C三个柱子，否则开始递归.
        Move(n,'A','B','C');
        printf("移动次数：%d次",m);
}

递推式求解

2.5 例题：计算第n个斐波那契数

初始条件：F[0]=0,F[1]=1

方法一：

int F(int n)
{
    if(n<=1)return n;
    else return F(n-1)+F(n-2);
}

方法二：

int Fib(int n)
{
	int F[2];
	F[0] = 0;
	F[1] = 1;
	if (n <= 1)
	{
		return F[n];
	}
	else
	{
		for (int i = 2; i <= n; i++)
		{
			F[i % 2] = F[0] + F[1];
		}
		return F[n % 2];
	}
}

方法三：

方法四：