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

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

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

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

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