算法设计与分析实验

1、WORD格式-专业学习资料-可编辑IntegerFactorizationDescription问题描述：大于1的正整数n可以分解为:n=Xl*X2*-*Xmo例如，当n=12时，共有8种不同的分解式：12=12：12=6*2；12=4*3：12=3*4；12=3*2*2；12=2*6；12=2*3*2；12=2*2*3o编程任务：对于给定的正整数n,编程计算n共有多少种不同的分解式。Input输入由多组测试数据组成。每组测试数据输入第一行有1个正整数n(ln2000000000)oOutput对应每组输入，输出计算出的不同的分解式数。SampleInput12SampleOutput8程序如

2、下：#include<stdio.h>#include<math.h>structDPintnum;intsum;d50000=0;intmax=0;voidqsort(intlow,inthigh,structDPkey)inti=low,j=high;structDPtag=keyi;if(i<j)(do(while(tag.num<keyj.num&&ij)j一一;学习资料分享if(i<j)(keyi=keyj;i+；while(tag.num>=keyi.num&&i<j)i+;if(i<j)(

3、keyj=keyi;J；)while(i<j);keyi=tag;qsort(low,j-l,key);qsort(i+1,high,key);)intdfs(intleft)inti,p;int1,r,m;intcount=0;1=0;r=max;while(l<=r)m=(l+r)>>1;if(dmLnum<left)l=m+l;elser=m-l;)p=l;if(dp.sum)returndp.sum;for(i=l;i<=di.num;i+)if(left%di.num=0)count+=dfs(left/dEi.num);)dLpLsum=coun

4、t;returncount;)intmain(void)inti,j,tmp;intn;scanf&n);tmp=sqrt(n);for(i=l;i<=tmp;i+)if(n%i=0)dmax.num=i;max+;dmax.num=n/i;max+;max;qsort(0,max,d);d0.sum=l;printf(%dn,dfs(n);return0;)比赛安排Description设有2、(n<=6)个球队进行单循环比赛，计划在2、-1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2X-1天内每个队都与不同的对手比赛。例如2时的比赛安排：队1234比赛1

5、=23=4一天匚32二4二天1=42=3三天Input输入由多组测试数据组成。每组测试数据输入一个正整数代表题目中的noOutput对应每组输入，输出如样例所示。<1>1-2,3-4表示第一天1队与2队，3队与4队比赛SampleInput2SampleOutput3-4<2>l-3,2-4<3>l-4,2-3程序如下：#include<stdio.h>inta8080;voidcopy(intn)intm,i,j;m=n/2;for(i=l;i<=m;i+)for(j=l;j<=m;j+)(aij+m=aij+m;ai+mj=aij

6、+m;ai+mj+m=aij;)voidwz(intn)(if(n=l)al1=1;return;elsewz(n/2);copy(n);)intmain()(intn,i,j,m,f,k;while(scanf&n)!=EOF)k=l;for(i=0;i<n;i+)k*二2;wz(k);m=0;for(j=2;j<=k;j+)m+;f=l;for(i=l;i<=k;i+)(if(aij!=0)if(f)printf(z/<%d>%d-%d，z,m,i,aij);f=0;elseprintf(,%d-%d/z,i,aij);aaijj=0;)printf(

7、n)；)又是Hanoi塔问JDescriptionA、B、C是3个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,，n,奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A上的这一叠圆盘移到塔座B上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则(1)：每次只能移动1个圆盘；规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则(3)：任何时刻都不允许将同色圆盘叠在一起；规则(4)：在满足移动规则(1)-的前提下，可将圆盘移至A,B,C中任一塔座上。按照上述四种规则移动过程中，如将圆盘从A柱移到B柱，则称B

8、柱使用一次。例如要将塔座A上2个圆盘，按上述四种规则移动到B柱，A柱使用0次，B柱使用2次，C柱使用1次。试设计一个算法，统计用最少的移动次数将塔座A上的n个圆盘移到塔座B上并仍按同样顺序叠置时，A柱、B柱、C柱的使用次数。编程任务：对于给定的正整数n,编程计算最优移动方案时，A柱、B柱、C柱的使用次数。Input输入由多组测试数据组成。每组测试数据的第1行是给定的正整数n。Output对应每组输入，输出的每一行由三个相互空格的正整数组成，分别表示塔座A的使用次数、塔座B的使用次数及塔座C的使用次数。SampleInput2SampleOutput021程序如下：Sinclude<ios

9、tream>usingnamespacestd;classHanoiprivate:intnumA,numB,numC;public：Hanoi0;voidMoveHanoi(intnum,charA,charB,charC);voidCaluater(charchi,charch2);voidDisplay0;Hanoi：:Hanoi0numA=0;numB=0;numC=0;voidHanoi：:Caluater(charchi,charch2)if(ch2='A')numA+;elseif(ch2='B')numB+;elsenumC+;voidHa

10、noi：:MoveHanoi(intnum,charA,charB,charC)if(num>0)MoveHanoi(num-l,A,C,B);Caluater(A,B);MoveHanoi(num-l,C,B,A);voidHanoi：:Display()cout«numA«/z>z«numC«endl;intmainOintnn;while(cin>>nn)Hanoih;h.MoveHanoi(nn,'A','B','C');h.Display0;return0;Permutat

11、ionwithRepetitionDescriptionR=rl,r2,，rn是要进行排列的n个元素。其中元素rl,r2,，rn可能相同。试设计一个算法，列出R的所有不同排列。编程任务：给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。Input输入由多组测试数据组成。每组测试数据的第1行是元素个数n,1烂n烂500o接下来的1行是待排列的n个元素。Output对应每组输入，将计算出的n个元素的所有不同排列输出，每种排列单独一行。最后1行中的数是排列总数。SampleInput4aaccSampleOutputaaccacacaccacaaccacaccaa6程序如下：#includ

12、e<stdio.h>#includealgorithmusingnamespacestd;intans;intok(charstr,inta,intb)if(b>a)for(inti=a;i<b;i+)if(stri=strb)return0;return1;voidperm(charstr,intk,intm)inti;if(k=m)ans+;for(i=0;i<=m;i+)printf(，z%cz，,stri);printfCn");)elsefor(i=k;i<=m;i+)if(ok(str,k,i)swap(strk,stri);perm(

13、str,k+1,m);swap(strk,stri);)intmain(intargc,char*argv)charstr1000;intn;while(scanf&n)!=EOF)ans=0;scanf(传s”,str);perm(str,0,n-l);printf(“%dn,ans);)return0;ProblemC:整数划分问题Description将正整数n表示成一系列正整数之和：n=nl+n2+nk,其中nl2n2enkL正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。例如正整数6有如下11种不同的划分：6：5+1：4+2,4+1+1；3+3,3+2+1,3

14、+1+1+1；2+2+2,2+2+1+1,2+1+1+1+1；l+1+l+l+l+loInput输入包含n+1行；第一行是一个整数n,表示有n个测试用例；第2至n+1每行一个正整数。Output对应每组输入，输出正整数n的不同划分个数。SampleInput256SampleOutput711程序如下：#include<stdio.h>intsplit(intn,intm);intmainOintk,i;inta100;scanf&k);for(i=0;i<k;i+)scanf;)for(i=0;i<k;i+)printf(%dn”,split(ai,ai);)

15、intsplit(intn,intm)if(n<l)|(m<l)return0;if(n=l)|(m=l)return1;if(n<m)returnsplit(n,n);if(n=m)returnsplit(n,m-l)+l;returnsplit(n,m-l)+split(n-m,m);双色Hanoi塔问，DescriptionA、B、C是3个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,，n,奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A上的这一叠圆盘移到塔座B上，并仍按同样顺序叠置。在移动圆盘时

16、应遵守以下移动规则：规则(1)：每次只能移动1个圆盘；规则：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则(3)：任何时刻都不允许将同色圆盘叠在一起；规则(4)：在满足移动规则(1)-的前提下，可将圆盘移至A,B,C中任一塔座上。试设计一个算法，用最少的移动次数将塔座A上的n个圆盘移到塔座B上，并仍按同样顺序叠置。编程任务：对于给定的正整数n,编程计算最优移动方案。Input输入由多组测试数据组成。每组测试数据的第1行是给定的正整数n。Output对应每组输入，输出的每一行由一个正整数k和2个字符cl和c2组成，表示将第k个圆盘从塔座cl移到塔座。2上。SampleInput3Sampl

17、eOutput1AB2AC1BC3AB1CA2CB1AB程序如下：Sinclude<stdio.h>intsplit(intn,intm);intmainOintk,i;inta100;scanf&k);for(i=0;i<k;i+)scanf('Rd",&ai);)for(i=0;i<k;i+)printf("%dn”,split(ai,ai);)intsplit(intn,intm)if(n<l)|(m<l)return0;if(n=l)|(m=l)return1;if(n<m)returnsplit(n

18、,n);if(n=m)returnsplit(n,m-l)+l;returnsplit(n,m-l)+split(n-m,m);再次hanoi塔问题Description古老的汉诺塔问题是：用最少的步数将N个半径互不相等的圆盘从1号柱利用2号柱全部移动到3号柱，在移动的过程中小盘要始终在大盘的上面。现在再加上一个条件：不允许直接把盘从1号柱移动到3号柱，也不允许直接把盘从3号柱移动到1号柱。把盘按半径从小到大用1N编号。每种状态用N个整数表示，第i个整数表示i号盘所在的柱的编号。则N=2时的移动方案为(1,1)2(2,1)2(3,1)2(3,2).(2,2)2(1,2)2(1,3)2(2,3).(3,3)初始状态为第。步，编程求在某步数时的状态。Input输入的第1行为整数T(1WTW50000),表示输入数据的组数。接下来的丁行，每行有两个整数N,M(1WNW19,OWMW移动N个