Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1023444
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-07-14 15:25:20

把一个给定的整数n划分成m个整数的问题:
Partitioning a given integer n into unique partitions of size m.
like if n=10,m=4,  7 1 1 1 is one such partition. Give all such partitions。
(这里要求不要给出重复的划分,比如5 2 2 1 与 5 1 2 2就是重复的划分。)


#include

int buf[1024]; //数组长度只需大于等于 m 即可
int bp;

void part(int n, int m, int min) //这里设置min值,保证了后划分出来的值要小于等于
                                 //先划分出来的值,从而防止重复。
{
   int i;
   if (m == 0 && n == 0) {
      for (i = bp - 1; i >= 0; i--) printf("%d ", buf[i]);
      printf("\n");
   }else if (m > 0) {
      for (i = min; i <= n; i++) {
         if(m == 1 && n>i){  //这里的判断是为了减少调用part()次数而写的,
            buf[bp] = n;   //为了便于理解,可以把这几句删除。
         }else{              //
            buf[bp++] = i;
            part(n - i, m - 1, i);
            bp--;
         }
      }
   }
}
int main(void)
{
   bp = 0;
   part(10, 4, 1);
   return 0;
}


这里,我又想起了很类似的一个问题,从无限多个一模一样的球中取n个球,分m次取,列出所有取法?
即第一次取几个,第二次取几个......第m次取几个。
这个问题与把整数n划分成m个正整数类似,不同点在于划分正整数时,5 2 2 1 与5 1 2 2是同一个划分,
但取球时,5 2 2 1 与 5 1 2 2是不同的取法。

总共有C(n-1,m-1)中取法。

具体列出取法:
这时只需要把min参数改动即可。
#include

int buf[1024]; //数组长度只需大于等于 m 即可
int bp;

void part(int n, int m)
{
   int i;
   if (m == 0 && n == 0) {
      for (i = bp - 1; i >= 0; i--) printf("%d ", buf[i]);
      printf("\n");
   }else if (m > 0) {
      for (i = 1; i <= n; i++) {
         if(m == 1 && n>i){
            buf[bp] = n;  
         }else{             
            buf[bp++] = i;
            part(n - i, m - 1, i);
            bp--;
         }
      }
   }
}
int main(void)
{
   bp = 0;
   part(10, 4, 1);
   return 0;
}

阅读(699) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~