实验一 算法分析与设计
一、实验目的
1. 掌握递归程序的概念和递归程序的编写。 2. 编写两种或以上算法解决同一个问题，对算法性能比较，从而认识到算法设计的重
要性。
二、实验内容
1、用递归函数解决汉诺塔问题，并输出圆盘移动的过程。 汉诺塔(Hanoi)问题。
设有三个塔座X、Y、Z，n个圆盘。这些圆盘大小互不相同， 初始时，这些编号为1，2， …，n的圆盘从大到小依次放在塔座X上。最底下为最大圆盘。要求将该塔座上的圆盘移到另一个塔座Z上，并按照同样顺序放置。圆盘移动时， 满足以下规则： ① 一次只能移动一个圆盘；② 任何时刻不允许将大的圆盘放在小的圆盘之上； ③ 圆盘可以放在X、Y和Z的任一塔座上。
输入较大的n值，观察执行时间变化。 #include
void Hanoi(char x,char z,char y,int n) {
if(n==1) printf(\ else {
Hanoi(x,y,z,n-1);
printf(\ Hanoi(y,z,x,n-1); } }
main() {
int n;
printf(\输入n的值:\\n\ scanf(\
printf(\阶汉诺塔移动步骤\ Hanoi('X','Z','Y',n); }
当输入n超过20时执行时间超过3分钟，执行时间较长
2、选择以下两个问题之一，设计两种算法进行求解。输入两个较大的整数分别测试两种算
法的性能并比较： （1）n元买n只鸡
（2）已知两个非负整数m、n，求这两个数的最大公因数。