貪心算法,n分解成自然數只和,求最大成績問題

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