`
txf2004
  • 浏览: 6830909 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

经典算法:整数划分问题

 
阅读更多

整数划分问题(算法分析与设计P12):将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数和方案。例如正整数6有如下11种不同的划分:

  1. 6
  2. 5+1
  3. 4+2,4+1+1
  4. 3+3,3+2+1,3+1+1+1
  5. 2+2+2,2+2+1+1,2+1+1+1+1
  6. 1+1+1+1+1+1

由于将思路写作注释更方便理解,就不再在前面赘述了,给出代码及思路如下:

  1. #include
  2. intlist[255];
  3. // num: 要分割的原始数字, n: 当前要分割的数字, k: 已经分割出的数量, sum: 已分割出的数字之和
  4. voidsplit(intnum,intn=0,intk=0,intsum=0){
  5. // 如果当前要分割的数字未传入,则当前分割的数字即为要分割的原始数字,减少传入参数数量
  6. if(n==0){
  7. n=num;
  8. }
  9. // 如果已分割的数字之和等于要分割的原始数字,即分割完毕
  10. if(sum+n==num){
  11. // 将最后一个数字存入数组
  12. list[k]=n;
  13. // 判断已分割的数字是否后面小于前面,防止重复
  14. boolflag=true;
  15. // 暂时未想到更好办法去除重复项,每次都要遍历数组,性能较低
  16. for(inti=1;i<=k;++i){
  17. if(list[i]>list[i-1]){
  18. flag=false;
  19. }
  20. }
  21. // 如果数组合法,则输出
  22. if(flag){
  23. printf("%d",list[0]);
  24. for(inti=1;i<=k;++i){
  25. printf("+%d",list[i]);
  26. }
  27. printf("\n");
  28. }
  29. }
  30. // 从小到大进行分割
  31. for(inti=1;i<n;++i){
  32. // 分割剩下的数字存入数组
  33. list[k]=n-i;
  34. // 分割出的数字继续分割
  35. split(num,i,k+1,sum+n-i);
  36. }
  37. }
  38. intmain(){
  39. intn;
  40. while(~scanf("%d",&n)){
  41. split(n);
  42. }
  43. return0;
  44. }



=======================签 名 档=======================

原文地址(我的博客):http://www.clanfei.com/2012/12/1672.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================





分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics