《计算机算法与设计分析实验报告.doc》由会员分享，可在线阅读，更多相关《计算机算法与设计分析实验报告.doc（20页珍藏版）》请在金锄头文库上搜索。
1、计算机算法与设计剖析实验报告班级：姓名：学号：目录11122334551527388182103121211220114318计算机组织与系统构造实验报告实验一分治与递归（4学时）一：基本递归算法一、实验目的与要求1、熟习C/C+语言的集成开发环境；2、经过本实验加深对递归过程的理解二、实验内容：掌握递归算法的观点和基本思想，剖析并掌握“整数区分”问题的递归算法。三、实验题随意输入一个整数，输出结果可以用递归方法实现整数的区分。#includeusingnamespacestd;intmain()inta,b,c;intq(intn,intm);cout请输入整数及大于最大加数的数ab;c=q
2、(a,b);cout所需要的区分数为：cendl;return0;intq(intn,intm)if(n1)|(m1)return0;if(n=1)|(m=1)return1;if(nm)returnq(n,n);if(n=m)returnq(n,m-1)+1;returnq(n,m-1)+q(n-m,m);实验结果：结果剖析：实验时入得数据为：所要区分的整数是7，他的区分的最大加数的值不得大于7，依据实质其区分的状况为15种，因此可知其程序的运转结果是正确的。1计算机组织与系统构造实验报告二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题
3、：在一个2k2k个方格构成的棋盘中，恰有一个方格与其他方格不一样，称该方格为一特别方格，且称该棋盘为一特别棋盘。在棋盘覆盖问题中，要用图示的4种不一样形态的L型骨牌覆盖给定的特别棋盘上除特别方格之外的全部方格，且任何2个L型骨牌不得重叠覆盖。三、程序代码：#includeusingnamespacestd;inttile=0;/全局变量，表示特别格的号intboard10001000;intmain()inttr,tc,dr,dc,size;inttile=0;/全局变量，表示特别格的号voidchessBoard(inttr,inttc,intdr,intdc,intsize);cout输入
4、数据trtcdrdcsize;coutendlendl;chessBoard(tr,tc,dr,dc,size);for(inti=1;i=size;i+)for(intj=1;j=size;j+)coutboardij;coutendl;return0;voidchessBoard(inttr,inttc,intdr,intdc,intsize)/左上角行号、列号，特别格的行号、列号棋盘大小if(size=1)return;/?tiaochuintt=+tile,/L型骨牌号？s=size/2;/切割棋盘/覆盖左上角子棋盘if(drtr+s&dctc+s)/特别方格在此棋盘中chessBoa
5、rd(tr,tc,dr,dc,s);else/此棋盘中无特别方格2计算机组织与系统构造实验报告/ 用t号L型骨牌覆盖右下角boardtr+s-1tc+s-1=t;/ 覆盖其他方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);/覆盖右上角子棋盘if(dr=tc+s)/特别方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else/此棋盘中无特别方格/用t号L型骨牌覆盖左下角boardtr+s-1tc+s=t;/覆盖其他方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);/覆盖左下角子棋盘if(dr=tr+s&dc=tr+s&dc=tc
6、+s)/特别方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s);else/用t号L型骨牌覆盖左上角boardtr+stc+s=t;/覆盖其他方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);试验运转结果三：二分搜寻一、实验目的与要求1、熟习二分搜寻算法；3计算机组织与系统构造实验报告2、初步掌握分治算法；二、实验题1、设a0:n-1是一个已排好序的数组。请改写二分搜寻算法，使适当搜寻元素x不在数组中时，返回小于x的最大元素的地点I和大于x的最大元素地点j。当搜寻元素在数组中时，I和j同样，均为x在数组中的地点。三、程序代码：#includeusing
7、namespacestd;intmain()intconstlength=100;intn,x;intalength;cout挨次输入数组的长度，数组内容，要查找的数n;/输入数组的长度for(inti=0;iai;cinx;voidBinarySearch(inta,intn,intx);BinarySearch(a,n,x);return0;voidBinarySearch(inta,intn,intx)/n:数组长度，i，j分别表示下标inti,j,mid=0,left=0;intright=n-1;while(left=0)intmid=(left+right)/2;if(x=amid
8、)i=j=mid;break;if(xamid)left=mid+1;elseright=mid-1;if(i=j)&(i=0)cout所找的数据在数组中下标为：iendl;4计算机组织与系统构造实验报告elsei=right;j=left;cout所找的数据不在数组中，其前后下标为：i,jendl;如上图所示数组的长度为5，其内容挨次为12345，所要找的数据位3，他的下表正好是2，结果是正确的如上图数组的长度为7，输入的数组是1346789，所要查找的数字式5，它不在数组中，其前后的下表分别为2,3结果是正确的。实验小结：第一个实验自己做了出来，但是第二个实验卡了好久，对棋盘覆盖问题上课听
9、懂了可是应用到实质上就有点问题了，最后仍是在同学的帮助下达成的！后边的这个提升题也是查考同学的，固然自己没能做出来，可是感觉仍是应当去学习！实验二动向规划算法一：最长公共子序列问题一、实验目的与要求1、熟习最长公共子序列问题的算法；2、初步掌握动向规划算法；二、实验题若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递加下标序列i1,i2,ik使得关于全部j=1,2,k有：zj=xij。比如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递加下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序
10、列时，称Z是序列X和Y的公共子序列。三、实验程序#includeusingnamespacestd;5计算机组织与系统构造实验报告intfun(char*x)char*y=x;while(*y+);returny-x-1;voidLCSLength(char*x,char*y,intm,intn,intc,intb)inti,j;for(i=1;i=m;i+)ci0=0;for(i=1;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;voidLCS(inti,intj,char*x,intb)if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);pri
