算法設(shè)計(jì)與分析實(shí)驗(yàn)

1、WORD格式-專業(yè)學(xué)習(xí)資料-可編輯IntegerFactorizationDescription問(wèn)題描述：大于1的正整數(shù)n可以分解為:n=Xl*X2*-*Xmo例如，當(dāng)n=12時(shí)，共有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編程任務(wù)：對(duì)于給定的正整數(shù)n,編程計(jì)算n共有多少種不同的分解式。Input輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)輸入第一行有1個(gè)正整數(shù)n(ln2000000000)oOutput對(duì)應(yīng)每組輸入，輸出計(jì)算出的不同的分解式數(shù)。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一一;學(xué)習(xí)資料分享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設(shè)有2、(n<=6)個(gè)球隊(duì)進(jìn)行單循環(huán)比賽，計(jì)劃在2、-1天內(nèi)完成，每個(gè)隊(duì)每天進(jìn)行一場(chǎng)比賽。設(shè)計(jì)一個(gè)比賽的安排，使在2X-1天內(nèi)每個(gè)隊(duì)都與不同的對(duì)手比賽。例如2時(shí)的比賽安排：隊(duì)1234比賽1

5、=23=4一天匚32二4二天1=42=3三天Input輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)輸入一個(gè)正整數(shù)代表題目中的noOutput對(duì)應(yīng)每組輸入，輸出如樣例所示。<1>1-2,3-4表示第一天1隊(duì)與2隊(duì)，3隊(duì)與4隊(duì)比賽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塔問(wèn)JDescriptionA、B、C是3個(gè)塔座。開(kāi)始時(shí)，在塔座A上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1,2,，n,奇數(shù)號(hào)圓盤(pán)著藍(lán)色，偶數(shù)號(hào)圓盤(pán)著紅色，如圖所示?，F(xiàn)要求將塔座A上的這一疊圓盤(pán)移到塔座B上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則(1)：每次只能移動(dòng)1個(gè)圓盤(pán)；規(guī)則(2)：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則(3)：任何時(shí)刻都不允許將同色圓盤(pán)疊在一起；規(guī)則(4)：在滿足移動(dòng)規(guī)則(1)-的前提下，可將圓盤(pán)移至A,B,C中任一塔座上。按照上述四種規(guī)則移動(dòng)過(guò)程中，如將圓盤(pán)從A柱移到B柱，則稱B

8、柱使用一次。例如要將塔座A上2個(gè)圓盤(pán)，按上述四種規(guī)則移動(dòng)到B柱，A柱使用0次，B柱使用2次，C柱使用1次。試設(shè)計(jì)一個(gè)算法，統(tǒng)計(jì)用最少的移動(dòng)次數(shù)將塔座A上的n個(gè)圓盤(pán)移到塔座B上并仍按同樣順序疊置時(shí)，A柱、B柱、C柱的使用次數(shù)。編程任務(wù)：對(duì)于給定的正整數(shù)n,編程計(jì)算最優(yōu)移動(dòng)方案時(shí)，A柱、B柱、C柱的使用次數(shù)。Input輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)的第1行是給定的正整數(shù)n。Output對(duì)應(yīng)每組輸入，輸出的每一行由三個(gè)相互空格的正整數(shù)組成，分別表示塔座A的使用次數(shù)、塔座B的使用次數(shù)及塔座C的使用次數(shù)。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是要進(jìn)行排列的n個(gè)元素。其中元素rl,r2,，rn可能相同。試設(shè)計(jì)一個(gè)算法，列出R的所有不同排列。編程任務(wù)：給定n以及待排列的n個(gè)元素。計(jì)算出這n個(gè)元素的所有不同排列。Input輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)的第1行是元素個(gè)數(shù)n,1爛n爛500o接下來(lái)的1行是待排列的n個(gè)元素。Output對(duì)應(yīng)每組輸入，將計(jì)算出的n個(gè)元素的所有不同排列輸出，每種排列單獨(dú)一行。最后1行中的數(shù)是排列總數(shù)。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:整數(shù)劃分問(wèn)題Description將正整數(shù)n表示成一系列正整數(shù)之和：n=nl+n2+nk,其中nl2n2enkL正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。例如正整數(shù)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行；第一行是一個(gè)整數(shù)n,表示有n個(gè)測(cè)試用例；第2至n+1每行一個(gè)正整數(shù)。Output對(duì)應(yīng)每組輸入，輸出正整數(shù)n的不同劃分個(gè)數(shù)。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塔問(wèn)，DescriptionA、B、C是3個(gè)塔座。開(kāi)始時(shí)，在塔座A上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1,2,，n,奇數(shù)號(hào)圓盤(pán)著藍(lán)色，偶數(shù)號(hào)圓盤(pán)著紅色，如圖所示?，F(xiàn)要求將塔座A上的這一疊圓盤(pán)移到塔座B上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)

16、應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則(1)：每次只能移動(dòng)1個(gè)圓盤(pán)；規(guī)則：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則(3)：任何時(shí)刻都不允許將同色圓盤(pán)疊在一起；規(guī)則(4)：在滿足移動(dòng)規(guī)則(1)-的前提下，可將圓盤(pán)移至A,B,C中任一塔座上。試設(shè)計(jì)一個(gè)算法，用最少的移動(dòng)次數(shù)將塔座A上的n個(gè)圓盤(pán)移到塔座B上，并仍按同樣順序疊置。編程任務(wù)：對(duì)于給定的正整數(shù)n,編程計(jì)算最優(yōu)移動(dòng)方案。Input輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)的第1行是給定的正整數(shù)n。Output對(duì)應(yīng)每組輸入，輸出的每一行由一個(gè)正整數(shù)k和2個(gè)字符cl和c2組成，表示將第k個(gè)圓盤(pán)從塔座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塔問(wèn)題Description古老的漢諾塔問(wèn)題是：用最少的步數(shù)將N個(gè)半徑互不相等的圓盤(pán)從1號(hào)柱利用2號(hào)柱全部移動(dòng)到3號(hào)柱，在移動(dòng)的過(guò)程中小盤(pán)要始終在大盤(pán)的上面?，F(xiàn)在再加上一個(gè)條件：不允許直接把盤(pán)從1號(hào)柱移動(dòng)到3號(hào)柱，也不允許直接把盤(pán)從3號(hào)柱移動(dòng)到1號(hào)柱。把盤(pán)按半徑從小到大用1N編號(hào)。每種狀態(tài)用N個(gè)整數(shù)表示，第i個(gè)整數(shù)表示i號(hào)盤(pán)所在的柱的編號(hào)。則N=2時(shí)的移動(dòng)方案為(1,1)2(2,1)2(3,1)2(3,2).(2,2)2(1,2)2(1,3)2(2,3).(3,3)初始狀態(tài)為第。步，編程求在某步數(shù)時(shí)的狀態(tài)。Input輸入的第1行為整數(shù)T(1WTW50000),表示輸入數(shù)據(jù)的組數(shù)。接下來(lái)的丁行，每行有兩個(gè)整數(shù)N,M(1WNW19,OWMW移動(dòng)N個(gè)