贪心算法
用贪心法求解最优分解问题:设n是一个正整数,现在要求将n分解为若干个互不相同的自然数之和,且使这些自然数的乘积最大。求大神指教 这道题咋做??
#include<stdio.h> #include<math.h> int main() { int a,b,i; int max; printf("请输入被分解的数:"); while (scanf("%d",&a)&&a<0) printf("不能输入负数,请重新输入!\n"); b=a; a/=3; max=pow(3,a); if (b%3==1) max=max*4/3; if (b%3==2)max=max*2; printf("分解结果为:\nmax="); for (i=0;i<a-1;i++) printf("3*"); if (b%3==0&&b) printf("3"); if (b%3==1&&b>1) printf("2*2"); if (b%3==2&&b>2) printf("3*2"); if (b==2) printf("2"); if (b==1) printf("1"); if (b)printf("=%d\n",max); else printf("0\n"); return 0; }