貪心算法,n分解成自然數(shù)只和,求最大成績(jī)問題

曲美邦尊大牽《算法設(shè)計(jì)與分析》上機(jī)實(shí)驗(yàn)報(bào)告專業(yè)軟件工程班級(jí)軟件1101學(xué)號(hào)04113033同學(xué)姓名岳彥利完成日期2022^11-26.上機(jī)題目及試驗(yàn)環(huán)境上機(jī)題目：最優(yōu)分解問題試驗(yàn)環(huán)境：CPU：英特爾其次代酷睿i3-2330M@2.2GHz雙核內(nèi)存：4G操作系統(tǒng)：windows7軟件平臺(tái)：ubuntu.算法設(shè)計(jì)與分析.對(duì)于n<=4,可以驗(yàn)證其分解成幾個(gè)正整數(shù)的和的乘積是小于n的。.對(duì)于n>4,能證明其能分解成幾個(gè)數(shù)的和使得乘積不小于n。假如分解成1和n-1,那么對(duì)乘積是沒有關(guān)心的，因此，假設(shè)n分解成a和n-a,2〈二a<二n-2.假如a,n-a仍舊>4,那么連續(xù)分解，直至a,n-a<=4。由于每次分解都能使乘積增加，所以最優(yōu)解必是最終分解結(jié)果，也即分解出的數(shù)全是2或3..若1作因數(shù)，則明顯乘積不會(huì)最大。把m分拆成若干個(gè)互不相等的自然數(shù)的和，因數(shù)個(gè)數(shù)越多，乘積越大。為了使因數(shù)個(gè)數(shù)盡可能地多，我們把m分成2+3…+n直到和大于等于m。若和比m大1,則因數(shù)個(gè)數(shù)至少削減1個(gè)，為了使乘積最大，應(yīng)去掉最小的2,并將最終一個(gè)數(shù)(最大)加上1。若和比m大k(k^l),則去掉等于k的那個(gè)數(shù)，便可使乘積最大。.核心代碼intBestDecomepose(int*a)〃求自然乘機(jī)的最大和(inti,j;intd,r=l,sum=0;for(i=2;;i++)(sum+=i;d=(sum-*a);if(d>=0)break;)printf("組成最大成果的自然數(shù)分別是：\\);if(d==l)for(j=3;j<i;j++)printf(*%d",j);)++i；printf(飛d\n",i);r*=i;}else{for(j=2;j<=i;j++)(if(j==d)〃假如j和d相等，就不執(zhí)行continue下面的語句了continue;r*=j;printf(*%d",j);)printfC\n*)；)returnr;).運(yùn)行與調(diào)試yyl@ubuntu:-S./415Inputl.txt:組成最大成績(jī)的自然數(shù)分別是：4outputl.txt:yylgubuntu:-S./415Inputl.txt:23組成最大成績(jī)的自然數(shù)分別是：8圖?.寫程序時(shí)遇到的問題yyieubuntu:-$./4_15Inputl.txt:23組成最大成績(jī)的自然數(shù)分別是：23567outputl.txt:1266yyl@ubuntu:-S./415Inputl.txt:11組成最大成績(jī)的自然數(shù)分別是：245outputl.txt:40yylgubuntu:-S./415Inputl.txt:14組成最大成績(jī)的自然數(shù)分別是：2345outputl.txt:126圖二.大于4的三中狀況截圖yyleubuntu:-S./415Inputl.txt:2outputl.txt:圖三.小于等于4的其中一種狀況截圖.結(jié)果分析和小結(jié)如圖一，是在寫程序時(shí)，在大于4的時(shí)候里面的循環(huán)寫錯(cuò)了，經(jīng)過調(diào)試修改，輸出正確,如圖二和三。如圖二，是大于4的測(cè)試數(shù)據(jù)。在input.txt第一行中第一個(gè)數(shù)代表輸入的數(shù)，其次行數(shù)代表組成這個(gè)數(shù)的最大成果的個(gè)數(shù)。這三組測(cè)試數(shù)都是自由生成的。如圖三，是另一組小于或等于4的其中一種測(cè)試結(jié)果。（2）本次上機(jī)試驗(yàn)的收獲、心得體會(huì)。這次的上機(jī)試驗(yàn)，使我對(duì)貪心算法法有了肯定的熟悉，編程的時(shí)候也有了更多的思路，在編程之前肯定把思路清楚，這樣寫的時(shí)候就比較輕松了。以前對(duì)這種數(shù)學(xué)問題不是很在意，現(xiàn)在覺得學(xué)這門課還得多看看數(shù)學(xué)這方面的學(xué)問，從而能更好的學(xué)好這門課。附錄(C/C++源代碼)#include<stdio.h>#include<stdlib.h>#include<fcntl.h>#include<math.h>#include<time.h>intBestDecomepose(int*a)〃求自然乘機(jī)的最大和inti,j;intd,r=l,sum=O;for(i=2;;i++)(sum+=i;d=(sum-*a);if(d>=0)break;)printf("組成最大成果的自然數(shù)分別是：\n〃)；if(d==l){for(j=3;j<i;j++)(r*=j;printf(*%d",j);)++i;printf(*%d\n”,i);r*=i;)else{for(j=2;j<=i;j++)(if(j==d)〃假如j和d相等，就不執(zhí)行continue下面的語句了continue;r*=j;printf(^%d”,j);)printfreturnr;(main()FILE*fp,*fpl;inta,max;fp二fopen("inputl.txt","wt");〃將隨機(jī)數(shù)寫入文件if(fp==NULL)(printf(^Conotopenthefile!”);exit(0);)srand((int)time(0))；//避開和上次取得數(shù)相同a=l+(int)(25.0*rand0/(RANDMAX+1.0));〃取隨機(jī)數(shù)fprintf(fp,"%d”,a);printf(^Inputl.txt:\nz，);printf(螺d\n",a);fclose(fp);if(a〉4)〃當(dāng)輸入的數(shù)大于4的狀況{max=BestDecomepose(&a);fpl=fopen("output1.txt〃，〃wt〃)；//將大于4的結(jié)果寫入文件if(fpl=NULL)(printf(z，Conotopenthefile!");exit(0);)fprintf(fpl,*%d*,max);fclose(fpl);)elsefpl=fopenroutputl.txt",；〃將小于等于4的結(jié)果寫入文件if(fpl==NULL)printf('Xonotopenthefile!");exit(0);)fprintf(fpl,"%d”,a-1);fclose(fpl);}printf(^outputl.txt:\n");〃輸出文件里的類容fpl