贪心算法,n分解成自然数只和,求最大成绩问题

曲美邦尊大牵《算法设计与分析》上机实验报告专业软件工程班级软件1101学号04113033同学姓名岳彦利完成日期2022^11-26.上机题目及试验环境上机题目：最优分解问题试验环境：CPU：英特尔其次代酷睿i3-2330M@2.2GHz双核内存：4G操作系统：windows7软件平台：ubuntu.算法设计与分析.对于n<=4,可以验证其分解成几个正整数的和的乘积是小于n的。.对于n>4,能证明其能分解成几个数的和使得乘积不小于n。假如分解成1和n-1,那么对乘积是没有关心的，因此，假设n分解成a和n-a,2〈二a<二n-2.假如a,n-a仍旧>4,那么连续分解，直至a,n-a<=4。由于每次分解都能使乘积增加，所以最优解必是最终分解结果，也即分解出的数全是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相等，就不执行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的时候里面的循环写错了，经过调试修改，输出正确,如图二和三。如图二，是大于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相等，就不执行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