《算法分析与设计实验报告模板2021.docx》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告模板2021.docx（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与设计实验报告实验内容3-2双关系递推数列集合M定义如下：1) leA/3)再无别的数属于M试求集合M元素从小到大排列的第2015个元素与前2015个元素之和。1、设计思路和关键点对数组m (i)设置两个队列：2*m(pl)+l,pl=l,2,3, .3*m(p2)+l,p2=l,23从两队列中选一排头，通过比拟选数值较小者送入数组m中，所谓“排头”就是队列 中尚未选入m的最小的下标。2、伪代码#includeusing namespace std;int main()(int n;int a100001;int s=l;coutvv”请输入 n:n;cinn;int pl = l,p
2、2=l;al=l;for(int i=2;i=n;i+)if(apl*2+lap2*3+l)ai=apl+*2+l;s+=ai; else1 .设计思路和关键点递归：没有拿50时，不能找零，返回0；没人拿100时，无法完成找零，返回0；其 他情况下，最后一个人要么拿50,要么拿100.递推：创立二维数组，表拿50的人数与拿100的人数，没人拿100时，只有一种排队 方式；当拿100的人数多余拿50的人数时，只有0中排队方式；当拿50的人数大于拿100 的人数时，返回递推公式：arrij=arri-1 j+arrij-1J2 .伪代码#include#includeint fun(int m,i
3、nt n)/m代表拿50元的人数，n代表拿100元的人数int x;if(m=0)当m为0时,，没有任何一种排队方式符合题意x=0;)else if(n=0)当n为。时，只有一种排队方式符合题意 x=l;)else if(mn)当mn时一，没有任何一种排队方式符合题意 x=0;)elsex=fun(m-l,n)+fun(m,n-l);最末尾的人要么拿50元要么拿100元，反复利用递 归)return x;)int main()double op,ed;double time;op=clock();int m,n;printf(”请输入手持50元钞票的人数与手持100元钞票的人数：);scanf
4、(n%d&m);scanf(”d”,&n);printf(这d个人排队购票的排队种数有(递归)：d”,m+n,fun(m,n);printf(nnH); ed=clock(); time=ed-op;printf(ntime=%lfmsnn9time);return 0;)3 .运行结果El F:M面、算法实验供验三4-1.exe这20个人排队购票的排队种数有(递归)：16796 time=49155. 000000msProcess exited after 49. 47 seconds with return value 0 请按任意键继续.4-2汉诺塔问题案例参照课本第106页.设计思路
5、和关键点Move函数用来打印移动的路径，fun函数表示第n个盘子的移动情况，当n不为1时，表 示不是最底部的盘子，不能从a移动到c,必须先从c移动到b, n-,反复执行该函数直到 最底部的盘子，然后利用a将b上的n-1个盘子移动到c完成。1 .伪代码#include int k=0;void move(char x,char y)printf(c-%c”,x,y);k+;if(k%5=0)printf(nnH);void fun(int n,char a,char b,char c) if(n=l)move(a,c);elsefun(n-l,a,c,b);move(a,c);fun(n-l,b
6、,a,c);)int main()int n;printf(ninput:H);scanf(n%dH,&n);printf(nnn);fun(n；A,；B,；C,);return 0;)2 .运行结果口 F:墟面、算法实验供验三4-2.exe linput :4一BA-CB-CA-BC-A CBA-BA-CB-CB一A 匕一AB一CA-BA-CB-CProcess exited after 1. 433 seconds with return 谙按任意键继续4-3 m行n列逆转矩阵参照3-6,要求用递归实现，分析递推与递归两种方法的区别和联系，总结递推和递 归各自的特点。1 .设计思路和关键点
7、当外圈赋值完后进入内圈，调用函数，不同的圈数，行列需要赋值的元素不同，所以b+1； 进入内圈，圈数需要减lo2 .伪代码#includeint m,n,arr100100J;void t(int bjnt sjnt d)int i,x,y;x=b;y=b；if(s0) 递归出口return;)if(s- 1 &m=n) arrxy=d;return;)for(i= 1 ;i=m+1 -2*b;i+) arrxy=d;x+;d+;)for(i= 1 ;i=n+1 -2*b;i+) arrxy=d;y+;d+;)for(i= 1 ;i=m+1 -2*b;i+) arrxy=d;x-；d+;if(d
8、m*n) break;)for(i= 1 ;im*n)break;t(b+l,s-l,d);调用内层递归函数 )int main()int x,y,b,s,d;printf(请输入 m n:n);scanf(d”,&m);scanf(n%dH,&n);b=l;d=l;s=n;if(ms)s=m;)t(b,s,d);for(x=l ;x=m;x+)for(y=l ;y=n;y+)printf(H%3darrxy);)printf(nnn);)return 0;3 .运行结果EK F:虚面、算法实验侯验三4-3.exe1 141 141516513201761219185111098Process
9、 exited after 2. 04 seconds with r 请按任意键继续4-4快速排序法和分区交换选择1、随机生成1001个整数，可重复(不同语言实现方式不同，自行百度)2、用快速排序法实现这1001个整数的升序排序；同时用冒泡法或比拟排序法实现，比拟 其与快速排序法在排序时间上的差异；3、用分区交换选择获得1001个数的中位数；2.伪代码#include#include#includeint r 10000;void fun(int n)int t;for(int i= 1 ;i=n-l ;i+)for(int j=i+1 ;jrU)t=ri;ri=rj；)return;)voi
10、d qk(int ml,int m2)int i,j;if(ml=rO&ji)/从右到左判断是否大于基准 j=j-l;如果大于的话，继续判断下一个)if(ij)如果小于基准，那么将此数放置到左分区ri=rj；i=i+l;)while(rii)从左到右判断是否小于基准 i=i+l;如果小于的话，继续判断下一个)if(ij)如果大于基准，那么将此数放置到右半区-i;j二j；)ri=rO;qk(ml,i-l);/在左半区继续排序qk(i+1 ,m2);在右半区继续排序)return;int main() int i,n,t;double opl,edl,op2,ed2;double timel,ti
11、me2;t=time(0)%1000;通过获取系统时间来初始化随机数srand(t);/随机数发生器printf(ninput n:n);scanf(H%dH,&n);printf(参与排序的(1个整数为：n,n);for(i=l ;i=n;i+) ri=rand()%(4*n)+10;随机产生n个数并存放到数组中printf(n%6dri);opl=clock();qk(l,n);printf(n以上d个整数从小到大排序为(快速排序法)：n,n);for(i=l;i=n;i+)printf(”6d”,ri);将排列好的数组输出)printf(HnH);edl=clock();timel=ed
12、l-opl;printf(ntime 1 =%lfmsnn,time 1);op2=clock();fun(n);printf(n以上(1个整数从小到大排序为(比拟排序法)：n,n);for(i=l;im)实现A(n,m)和C(n,m)1 .设计思路1和关键点排序：从第一个数等于1开始递增赋值，范围1n,再给第二个数赋值范围1n,引入标 志位判断第二个数是否与第一个数重复。2 .伪代码#includeint m,n,a5O;int s=O;int p(int k)int ij,u;if(k=m)for(i=l;i=n;i+)ak=i;u=O;for(j=l;j=k-l;j+)if(ak=aj)
13、u=l;)if(u-O)if(k=m)s+;printf();for(j=l；jm):H);scanf(H%d&n);printf(Hinput m(lmm) :5inputm(lm=n):4123412351243124512531254132413251342134513521354142314251432143514521453152315241532153415421543213421352143214521532154231423152341234523512354241324152431243524512453251325142531253425412543312431253142
14、3145315231543214321532413245325132543412341534213425345134523512351435213524354135424123412541324135415241534213421542314235425142534312431543214325435143524512451345214523453145325123512451325134ai=ap2*3+l;s+=ai;if(apl*2+l=ap2*3+l) pl+；p2+;)coutnm=nanendl;coutns=ns;return 0;)3、运行结果口 F:M面、算法实验供验二3-2
15、.exe请输入n：2015m=19831s=18020317Process exited after 21.23 seconds with retur 请按任意键继续3-3多曷序列设x,y,z为非负整数，试计算集合A/ = 2x,35z|x0,y0,z0的元素由小到大排列的多塞序列第n项与前n项之和。1、设计思路和关键点集合M由2的指数，3的指数以及5的指数组成，是三个递推关系，第一项为1, 从第二项开始，设置k循环，在k循环外赋初值：a=2； b=3； c=5； s=l；在k循环中通过 比拟赋值。2、伪代码#includeint main()int k,m,t,p2,p3,p5;double
16、 a,b,c,s,f100;printf(求数列的第m项与前m项和,请输入m:);scanf(n%dn,&m);fl=l ;p2=0;p3=0;p5=0;4-6整数拆分将一个整数n(n0)划分为假设干个零数相加，要求零数大于等于0且小于等于m(m0), 试求共有多少种划分方案？(只求划分方案个数，不用输出具体的划分方案)例如：n=29m=2： 1+1； 2n=3,m=3： 1+1+1； 1+2； 3n=4,m=4： l+l+l+l； 1+1+2； 1+3； 2+2； 4n=5,m=5： l+l+l+l+l； 1+1+1+2； 1+1+3； 1+2+2； 1+4； 2+3； 51.设计思路和关键
17、点当nv=O或m=0时，不符合题意，返回0；当n=l或m=l时，均只有一种划分方式即为1或多个1；当n=m时，返回l+fun(n,n-l)； 1代表整数自身，n-1代表n由假设干个不大于n-1的数相加 得到；当nm时，返回fun(n,m-1 )+fun(n-m,m); m-1代表比m小的数相加情况，而m代表包含它 本身的情况。2 .伪代码#includeint fun(int n,int m)if(n=0|m=0) return 0;else if(n=l|m=l) return 1;else if(n-m)return l+fun(n,n-l);)else if(nm)return (fun
18、(n,m-l)+fun(n-m,m);)int main()int m,n;printf(Hplease input n:n);scanf(H%d&n);printf(Hplease input m:H);scanf(n%dn9&m);printf(共有d 种划分方案,fun(n,m);return 0;)3 .运行结果LI F:虚面算法实验供验三4-6.exeplease input n:6please input m:3共有7种划分方案Process exited after 14. 64 seconds with re 请按任意键继续4-7递归求解双递推摆动数列递推数列：a( 1 )=
19、1 ,a(2i)=a(i)+1 ,a(2i+1 )=a(i)+a(i+1), (i为正整数),试建立递归，求该 数列的第n项与前n项的和。1 .设计思路和关键点对输入的n进行奇偶判断并返回相应的结果。2 .伪代码#include int fun(int n)if(n=l)return 1;)if(n%2=0)return fun(n/2)+l;)if(n%2=l)return fun(n/2)+fun(n/2+1);)int main()int n,s;s=0;printf(请输入 n:);scanf(n%d&n);for(int i=l ;i=n;i+) s=s+fun(i);)printf
20、(Ha=%dH,n,fun(n);printf(nnn);printf(Hs=%dn,s);return 0;3 .运行结果LB卜:昼卸算法头默快取二4-/.exe请输入n: 100a=17s=1774frocess exited after 9.988 seconds with 号按任意键继续.2实验小结总的来说，这次试验题目较多，每一道题都需要去思考挺长时间，但通过本次实验还 是有很大的收获，发现了递推与递归的区别在于递归是逆向解决问题，先从结果出发，一 步一步往回退直到开始，而递推是正向解决问题，从前面的简单项找到问题的规律，根据 得到的通项公式求得问题结果。a=2;b=3;c=5;s=
21、l;for(k=2;k=m;k+) if(ab & ac) fk=a;a=a*2;t=2;p2+;)else if(ba & bgo,”o元素组成的复合幕序列，求复合嘉序列的指数和x+yWn (正整 数n从键盘输入)的各项之和5= 2v3v,x0,y0x+y=O1、设计思路和关键点归纳求和递推关系：当 x+y=O 时,s(l)=l;当 x+y=l 时,s(l )=2+3;当 x+y=2 时,s(2)=22+2*3+32=2*s( 1)+32;当 x+y=3 时，s(3)=23+22*3+2*32+33=2*s(2)+ 33;当 x+y=k 时,s(k)=2*s(k-l)+3*k递推关系为：s(
22、k)=2*s(k)+3k2、伪代码#include int main()int k,n; long sum,t,s100;printf(请输入幕指数和至多为n:);scanf(H%d&n);t=l;sO=l; sum= 1;for(k= 1 ;k=n;k+)t=t*3;/ 迭代得 t=34sk=2*sk-l+t;/ 实施递推sum=sum+sk;printf(“基指数和至多为d的幕序列之和为:dn,n,sum);)3、运行结果请输入塞指数和至多为n: 10塞指数和至多为10的幕序列之和为:261625Process exited after 10. 68 seconds with returi
23、 请按任意键继续.3-5粒子裂变核反响堆中有a和B两种粒子，每秒钟内一个a粒子可以裂变为3个B粒子，而一个 B粒子可以裂变为1个a粒子和2个B粒子。假设在t=0时刻的反响堆中只有一个a粒子， 求在t秒时反响堆裂变产生的a粒子和B粒子数。1 .设计思路和关键点转化为求数列n和m的第t项。2 .伪代码#includeint main()int t,k;longg100;printf(n inputscanf(n%d&t);g0=0；gl3;/确定初始条件for(k=2;k=t;k+)gk=2*gk-l+3*gk-2;/ 完成递推printf(n%d秒时反响堆中B粒子数为:口 nt,gt);prin
24、tf(n%d秒时反响堆中a粒子数为:ld3 .运行结果I F:面算法实验供验二3-5.exeinput t:1010杪时反响堆中8粒子数为:4428610秒时反响堆中a粒子数为：14763Process exited after 1. 522 seconds with ret i青按任意键继续3-6 m行n列逆转矩阵图3-4所示为4行5列逆转矩阵。31617189试应用递推设计构造并输出任意指定m行n列逆转矩阵。1 .设计思路和关键点对输入的m, n,取c=min(m,n),计算数字矩阵的圈数d= (c+1) /2。设置i(ld) 循环，从外圈至内圈，分4边进行地推赋值。2 .伪代码#incl
25、ude int main()int i,j,c,d,h,v,m,n,s,a|3030;printf(n m 行 n 列矩阵，请确定 m,n: )； scanf(,%d,%d,&m,&n);c=n;if(mn) c=m;d=(c+l)/2;s=O;v=O;for(i=l;i=d;i+) v+;for(h=i;h=m-i;h+) s+; ahv=s;for(v=i;vi;h-) s+; ahv=s;if(s=m*n) h=i;break;)for(v=n+ l-i;vi;v) s+; ahv=s;if(s=m*n) v=i;break;)printf(n %d 行%(1 列旋转矩阵为:n”,m,n
26、);for(i=l;iv=m;i+) for(j=l；j=n;j+)printf(nnn);3 .运行结果口 F:M面、算法实验供验二3-6.exem行n列矩阵,请确定m, n: 10, 1010行10列旋转矩阵为:1 36 35 34 3332313029282 37 64 63 6261605958273 38 65 84 8382818057264 39 66 85 9695947956255 40 67 86 97100937855246 41 68 87 9899927754237 42 69 88 8990917653228 43 70 71 7273747552219 44 45
27、 46 47484950512010 11 12 13 141516171819Process exited after 2.041 seconds with return va 请按任意键继续.3-8拓广猴子吃桃有一猴子第1天摘下假设干个桃子，当即吃了一半，还不过瘾，又多吃了 m个。第2天早上又将剩下 的桃子吃掉一半，又多吃了m个。以后每天早上都吃了前一天剩下的一半后又多吃m个。到第n天早上 想再吃时，见只剩下d个桃子了。求第1天共摘了多少个桃子(m,n,d由键盘输入)？1 .设计思路和关键点第一天的桃子数是第二天桃子数加1后的2倍，第二天的桃子数是第三天桃子数加1 后的2倍，第k天的桃子数
28、是第k+1天桃子数加1后的2倍,递推关系为:t(k)=2*(t(k+l)+l) (k=l,2,9)2 .伪代码#include int main() int d,k,m,n; long t1000;piintf(n请确定正整数m,n,d: ”)；scanf(n%d,%d,%d;&m,&n,&d);tn=d;/确定初始条件for(k=n-1 ;k= l;k-)/ 逆推计算 t(l)tk=2*(tk+l+m);printf（n 第 1 天摘桃ld 个。nu,tl）;for（k=l ;k=n-l ;k+） printf（H 第 %d 天面临41d 个桃，n,k,tk）;printf（n 吃 了%41
29、d+%d=%41d 个,tk/2,m,tk/2+1）；printf（H 还剩4kl 个。nH,tk/2-m）;）printf（u第1天早上还剩d个。”,n,d）;3 .运行结果n F:迎面、算法实验供验二3-8.exe请确定正整数叫n, d： 1, 第1天摘桃2558个。10,3第1天面临2558个桃,吃了1279+1=1280个，还来1278个。第2天面1缶1278个桃，吃了639+1=640个,还赢638个。第3天面临638个桃，吃了319+1=320个，还杀318 个。第4天面临318个桃,吃了159+1=160 个,还剩158 个。第5天面临158个桃,吃了79+1=80个，还市78个
30、。第6天面临78个桃，吃了39+1=40个，还赢38个。第7天面临38个桃，吃了19+1=20个，还杀18个。第8天面临18个桃,吃了9+1=10个，还赢8个。第9天面临 8个桃， 第10天早上还剩3个。吃了4+1=5个，还秦3个。Process exited after 11.56 seconds with return value 0 请按任意键继续.3-9找零问题把一张n(nO)元整币兑换成1元、2元、5元、10元、20元、50元的零币，共有多少 种不同兑换种数？1 .设计思路和关键点创立一个数组将零钱的种类放到数组中，增加数组下标表示不同的数值，下标增加到 6时表示零钱种类都试过了一次
31、，结束找零过程。2 .伪代码#include int arr6=50,20,10,5,2,1；int fun( int n,int index) int num=();if(n0)return 0;)if(n=0)return 1;)if(index=6)return 0;)for(int i=0;i=n;i+)num=num+fun(n-i*arrindex9index+l);)return num;)int main()(int n;printf(请输入整币金额：)；scanf(H%dn,&n);printf(整币(1共有d种找零方式”,n,fun(n,。);return 0;3 .运行结果口 F:M面、算法实验供验二3-9.exe请输入整币金额：200整币200共有69118种找零方式Process exited after 10.57 seconds with return value 请按任意键继续一场球赛开始前，售票工作正在紧张进行中。每张球票为50元，有m+n个人排队等待购票，其中 有m个人手持50元的钞票，另外n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至 出现找不开钱的局面的不同排队种数。（约定：开始售票时售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）