数据组合有关问题，有想法的请进

数据组合问题，有想法的请进
输入两个正整数M、N，0<M<=N,N为由不大于M的数组成。
例如：N=3，M=2。
组合情况有3种：
3=1+2；(a)
3=2+1；(b)
3=1+1+1；
此处a、b属于不同种情况。
请输出组合的种数，并把每种情况也输出。

我想问的是有没有像快速排序、最有二叉树等等这样现成的算法可用，
如果没有请提供以下解决这类问题的思路，
请不要把那种没有任何注释的大段代码贴出来，
授人以鱼不如授人以渔，解决问题的思路更重要
当然如果鱼和渔都给那就更好了（哈哈，有点贪得无厌了）
ps：如果能提供鱼请提供c语言的，谢谢喽。

本人分数不多请谅解。



c语言 算法
[解决办法]
零钱兑换方法,你能翻墙吗?看这篇文章,这是求这类问题的通解:

http://goo.gl/KeOW0b

你不用管同时"既有种数同时也要把每种情况都输出",你只要找到了每种情况,自然就有种数了,所以关键还是找到方法,求出所有的拆分情况.
[解决办法]

引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

这个算不同那不就是C(n-1,m-1)种可能性么

你说的这个Cx,y我知道，当这个只是能得出组合情况有几种，不能把每种情况也输出，
我要的是既有种数同时也要把每种情况都输出出来。

都能理解答案为什么是C(n-1,m-1)了那还写不出代码？要是连x个东西里取y个的代码都写不出那我就没办法了。

这公式不对把m＝4,n=3,
有1111，112，121，13，211，22，31，7种，应该没有漏的把

嗯我把整个题就理解错了。我以为m是分成的和的数的个数。m是限制和里每个数的上限的话那就是个比较恶心的线性递推了。程序当然好算。公式的话那特征多项式的解能不能写出来都是个问题。
只需要输出个数的话各种优化，m^2*logn什么的都没问题。当然lz要输出所有解的话，那只能老老实实把指数个解一个个搜出来。
[解决办法]
static int M =3 ,N=5;
 static void check(int[] a,int index){
    if(index == a.length){
    int sum=0;
    for(int i:a){
    sum+=i;
    }
    if(sum != N){
    return;
    }
    for(int i:a){
    System.out.print(i+",");
    }
    System.out.println();
    return ;
    }    
 for(int val=1;val<=M;val++){ 
 a[index] = val;
 check(a,1+index);
   }   
   }
public static void main(String[] args) throws Exception{
int i = N;
while(i > 0){
int[] a = new int[i];
check(a,0);
i--;
}
}
做了几个测试，没发现啥问题。虽然没有注释，好在代码比较短。
Java写的，不过LZ应该也能看的懂。
有错误请抛砖

查看更多 下一篇