自动化实验报告

09504 谷美慧 宫雪

上机二 汉诺塔问题的实现及其优化

一，问题描述：假设又耽搁分别命名为A,B,C的塔座，在塔座B上有N个直

径大小各不相同，从小到大编号为1,2，…..n的圆盘。现在要求将塔座B上的n个圆盘一直到塔座A上，并按照同样地顺序叠放，当移动圆盘时应遵循下面规则： 1， 每次只移动一个圆盘 2， 圆盘可以放在A,B,C中任意一个上面； 3， 任何时刻都不能将一个较大的圆盘压在较小的圆盘上。

要求：用程序模拟上述问题的解决方法，并输出移动的总次数，原判的个数从键盘输入

二，算法思路：如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就

将它直接搬至C，当有两个盘子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。

1）1个盘子。因为只有一个盘子，只要直接把盘子从A座移到C座。

（2）2个盘子。先将一个盘子从A移到B，再将第二个盘子从A移到C,再将第一个盘子从B移到C

（3）3个盘子。

（1）将A座上2个盘子移动到B座上(借助C)； （2）将A座上的一个盘子移动到C座上； （3）将B座上2个盘子移到C座上（借助A）。 第二步直接实现，第一步的方式可以分解为：

1.1， 将A上一个盘子从A移到C——>将A上一个盘子从A移到B——>将C上一个盘子

从C移到B。

第三步可以分解为：将B上一个盘子从B移到A——>将B上一个盘子从B移到C——>将A上一个盘子从A移到C上。则移动三个盘子的步骤为：A——>C,A——>B,C——>B,A——>C,B——>A,B——>C,A——>C.共七步。由此推出N个盘子需要移动2-1 则移动N个的方法就可以知道了 1， 将A上n-1个盘子借助C移到B

2， 将A座上剩下的一个盘子移到C盘上 3， 将n-1个盘子从B 座借助A移到C上

三，程序如下

四．测试结果如下

五，程序分析：

移动N个盘子的工作就可以按照以下过程进行： 1) hanoi (n-1,one,three,two);

2) 将一个盘子从a移动到b上move(one,three)； 3) hanoi(n-1,two,one,three)； 如此循环，直到n==1时，结束。

上机三 排序算法的实现及其优化

1,问题的描述:理解冒泡排序的算法；基于冒泡排序，理解快速排序

的算法；编写快速排序的程序；进行排序分析

2，算法思路：快速排序是对冒泡排序的一种改进：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

A[1] A[2] A[3] A[4] A[5] A[6] A[7]：

49 38 65 97 76 13 27

进行第一次交换后： 27 38 65 97 76 13 49

( 按照算法的第三步从后面开始找

进行第二次交换后： 27 38 49 97 76 13 65

( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后： 27 38 13 97 76 49 65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后： 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态 {49 38 65 97 76 13 27}

进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

分别对前后两部分进行快速排序 {13} 27 {38}

结束 结束 {49 65} 76 {97}

49 {65} 结束

结束

3，程序及程序分析如下：

#include

#define LENGTH 100 /*数组最大存放量*/ void paixu(long int shuju[],short int shangbiao,short int xiabiao); void main() {

short int i,n;

long int shuju[LENGTH]; printf(\"要输入多少个数?\\n\"); scanf(\"%d\

getchar(); /*干掉个多事的回车符*/ printf(\"请输入一组数:\\n\");

for(i=0;ifor(i=0;igetchar();

getchar(); /*暂停看结果*/ }

void paixu(long int shuju[],short int shangbiao,short int xiabiao) {

short int i=shangbiao,j=xiabiao; /*i和j用来确定还需要判断排序的范围上下标*/

short int shu=i; /*记录基准点*/ long int zhongjie;

if(shangbiao{

while(ifor(;j>shu;j--) /*对基准数右边扫描*/ {

if(shuju[j]zhongjie=shuju[j];

shuju[j]=shuju[shu]; /*进行交换*/ shuju[shu]=zhongjie;

shu=j; /*确定交换后的基准数*/ break; /*跳出循环*/ } }

i++; /*往右推*/

for(;iif(shuju[i]>shuju[shu])/*如果左边有比基准数大的*/ {

zhongjie=shuju[i];

shuju[i]=shuju[shu]; /*交换*/ shuju[shu]=zhongjie; shu=i; /*交换后的基准点*/ break; } }

j--; /*往左推*/

}/*执行完后,比基准点小的都在左边,比基准点大的都在右边了*/ paixu(shuju,shangbiao,shu-1); /*对左边比基准点小的再次进行排序*/ paixu(shuju,shu+1,xiabiao); /*对右边比基准点大的再次执行上面的排序方法*/

} /*直到只剩下要排序一个数为止,此时整个数组已经排序好了*/ }

四，测试数据结果

五，程序分析：

例如：待排序的数组A的值分别是：（初始关键数据X：=49） A[1] A[2] A[3] A[4] A[5] A[6] A[7]： 49 38 65 97 76 13 27

进行第一次交换后： 27 38 65 97 76 13 49 进行第二次交换后： 27 38 49 97 76 13 65

( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 ) 进行第三次交换后： 27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找) 进行第四次交换后： 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示： 初始状态{49 38 65 97 76 13 27}

进行一次快速排序之后划分为{27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序{13}27{38} 结束结束{49 65} 76 {97} 49 {65} 结束

上机四约瑟夫环境算法的实现

1，问题描述

已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 2，算法思路

这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head 解决问题的核心步骤：（程序的基本算法）

1.建立一个具有n个链结点，无头结点的循环链表； 2.确定第1个报数人的位置；

3.不断地从链表中删除链结点，直到链表为空。 三，源程序

#include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList init(){ LinkList L;

L=(LinkList)malloc(sizeof(LNode)); L->next=L; return(L); }

LinkList create(int n){ LinkList L,p,r; int i; L=init(); r=L;

L->data=1;

for(i=2;i<=n;i++){

p=(LinkList)malloc(sizeof(LNode)); p->data=i; r->next=p; r=p; }

r->next=L; return (L); }

int main(){ int i,j,n,k,m; LinkList L,p,r;

scanf(\"%d %d %d\ if(n==0||k==0||m==0){

printf(\"n,k,m must be larger than 0!\"); return 0; }

if(k>n){

printf(\"n must be larger than k!\"); return 0; }

L=create(n); p=L;

for(i=1;inext; for(i=0;inext; r=p;

p=p->next;

printf(\"%4d\ if(r!=p){

r->next=p->next; free(p);

p=r->next; } }

free(p);

system(\"pause\"); }

测试结果和测试数据

n=9,m=5,k=1。即程序从1开始报数，数到5的时候5出列，6又从1开始报数，数到5的那个人又出列，即1出列，以此类推，得到结果5 1 7 4 3 6 9 2 程序分析