回 帖 发 新 帖 刷新版面

主题:由浅入深,请教各位高手…  近来看看也好啊,多谢了……

有3个数a,b和c,它们都可能是从0到m中的任意一个数,m是自己输入的,求它们的和等于m的所有中组合,这道题相信大家都会做,它的C++代码如下:
1   #include<iostream.h>
2   void main()
3    {
4    int a,b,c,m;
5         cin>>m;
6    for(a=0;a<=m;a++)
7        for(b=0;b<=m;b++)
8            for(c=0;c<=m;c++)
9                if(a+b+c==m)                 
10          cout<<"{"<<a<<","<<b<<","<<c<<"}  "<<endl;
11    }
输出结果为(我输入的m=4):  {0,0,4}  {0,1,3}  {0,2,2}  {0,3,1}  {0,4,0} {1,0,3} {1,1,2}  {1,2,1} {1,3,0}  {2,0,2}  {2,1,1}  {2,2,0}  {3,0,1} {4,0,0}.
 注意第6,7,8行,它们除了标识符不同以为,其它都一样,假设题目要求的不只3个数a,b,c,后面还有更多的标识符,可以用数组来表示,如B[0],B[1],B[1],B[1],…………数组的元素个数也为自己任意输入,我想请教大家,这道题怎样才能用递归来实现,麻烦各位了

回复列表 (共2个回复)

沙发

活活,看到组合问题就好爽。

第1你这个不是组合,组合中对于{0,0,4}{4,0,0}是相同的组态;第2第三重循环可以省去;第3,递归的程序这样写:

dfs(int c)//处理第c个标识符B[c]
{
   if(c==n)
   {判断是否满足组态的条件,如果满足就输出组态}
   else
   {
       for(遍历所有的1,2,...m)
       {
            B[c] <- 1,2,...m
            dfs(c+1) //处理下一个
       }
   }
}

板凳

嗯。。定义一个偏序关系就可以了,比如a <= b <= c

我来回复

您尚未登录,请登录后再回复。点此登录或注册