算法分析与设计实验一

实验一 算法分析与设计

一、实验目的

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，求这两个数的最大公因数。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析与设计实验一在线全文阅读。