算法设计--王茂林

《算法设计--王茂林》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验一递归与分治姓名：王茂林班级：信息1411学号：2014125104指导老师：潘老师实验目的：理解递归与分治算法设计思想和方法。实验课时：4学时实验原理：一个规模为n的复杂问题的求解：可以划分成若干个规模较小vn的子问题进行求解，再将子问题的解合并成原问题的解，这便是分治的思想。若划分成的每一个子问题都与原问题的性质相同，可用相同的求解方法；当子问题规模划分一定小时，子问题的解己知，则逆求原问题的解，这是递归的思想。实验题A:1、汉诺塔(hanoi)问题。设有A、B、C共3根塔座，在塔座A上堆叠n个金盘，每个盘大小不同,只

2、允许小盘在大盘之上，最底层的盘最大，如下图所示。现在要求将A上的盘全都移到C上，在移的过程中要遵循以下原则：每次只能移动一个盘；圆盘可以插在A、B和C任一个塔座上；在任何时刻，大盘不能放在小盘的上面。bhanoi问题递归求解思想：我们把一个规模为n的hanoi问题：1到n号盘按照移动规则从A上借助B移到C上表示为H(A,B,C,n)；原问题划分成如下三个子问题：(1)将1到n・l号盘按照移动规则从A上借助C移到B上H(A,C,B,n-l);(2)将n号盘从A上直接移到C上；(3)将1到n・l号盘按照移动规则从B上借助A移到C上

3、H(B,A,C,n-l);经过三个子问题求解，原问题的也即求解完成。hanoi问题递归求解代码：voidH(charA,charB,charC,intn){if(n>0){H(A,C,B,n-l);printf(44%dfrom%cto%c,,,n,A,C);H(B,A,C,n-l);・c语言实验代码:#includevoidhanoi(intn,charX,charY,charZ){if(n==1)printf(”把%c移动到%cM,X,Z);eIse{hanoi(n-1,X,Z,Y);printf(“

4、把%c移动到%cM,X,Z);hanoi(n~1,YfX,Z);}}main(){intm;printfC*请输入盘子的数目：“)；scanf("%d",&m);printfC*要移动的盘子执行的步骤为：%dH,m);hanoi(m,'A',*B','C');}实验结果：^^7町"C:USERSADMINISTRATORD请输入盘子的数目：3要移动的盘子执行的步骤为：3把a移动到c把A慈动封jB把C移动到B把a移动到C把B移动到a把B彩刼至ijc把A移动到CPressanykeytocontinue2、二分查找问

5、题（1）设a[0:n-l]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组屮时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组屮时，i和j相同，均为x在数组屮的位置。rj>•卜•卜•.、•.、•.、•.、•广•卜•卜•卜

6、%r•r••.、•.、•.、<

7、••卜•卜•卜r•r•代码显示:#includeintbinarySearch(inta[]9intnjntx9int&i9in

8、t&j)//a[]为要搜索的数组;n为数组元素的个数;x为要查询的元素值;//i为小于x的最大元素位置;j为大于x的最小元素的位置intmiddle;〃中值intright=n-l;//数组的右边界intleft=O;//数组的左边界while(left<=right)middle=(left+right)/2;if(x==a[middle]){i=j=middle;returnmiddle;}if(x>a[middle])Ieft=middle+1;else//2016年11月3日测试成功。right=middle-l;i=

9、right;j=left;}return-1;〃查询失败}intmain(void)intj;intmiddle;intb[]={l，234,5,6,7,8，12,22};〃用来测试的数组middle=binarySearch(bJ0,134%j)；//调用二分搜索算法〃查询成功printf(Hthex'spositionis:%d,iis%d,jis%d",middle,ij);}else〃查询失败{printf(u找不到这个元素：％d，jis%dn,ij);}return0;}结果显ZK：S-C:USERSAD

10、MINISTRATORDESKTOP草稿Debugkk.exw找不到这个元素：8,jis9Pressanykegtocontinue方法二：如果存在，必须返回下标#includeusingnamespacestd;constintSIZE=12;i