返回信息流求算法: 把一个数M分成N个整数的和. 如把5分成3个数的和有:0+0+5,0+1+4,0+2+3,1+2+2............
唔，本人编程不好，但临时有急用。给个思路就免了吧，我的智商想不出来的。谁要是恰好有代码就贴一下吧，万分感谢！！！
这是一条镜像帖。来源：北邮人论坛 / cpp / #48460同步于 2010/12/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
[求助]把一个数分成N个数的和
dooon
2010/12/28镜像同步14 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
LZ还是多学习一下递归吧，这是个很基础的问题
谁有编译器test一下，差不多就是这样做的
void solve(int m, int n, int s, int t, int *a)
{
int i;
if (t==n-1) {
for (i=0; i<n-1; i++)
printf("%d ", a[i]);
printf("%d\n", m-s);
} else {
for (i=0; i<=m-s; i++) {
a[t]=i;
solve(m, n, s+i, t+1, a);
}
}
}
调用：solve(5,3,0,0,a);
数组a需要足够大于等于n
【 在 dooon 的大作中提到: 】
: 求算法: 把一个数M分成N个整数的和. 如把5分成3个数的和有:0+0+5,0+1+4,0+2+3,1+2+2............
: 唔，本人编程不好，但临时有急用。给个思路就免了吧，我的智商想不出来的。谁要是恰好有代码就贴一下吧，万分感谢！！！
: --
: ...................
sorry，看你的意思需要的是唯一的排列，那这样吧：
void solve(int m, int n, int s, int t, int *a)
{
int i;
if (t==n-1) {
if ((n==1)?1:((m>=s+a[n-2])?1:0)) {
for (i=0; i<n-1; i++)
printf("%d ", a[i]);
printf("%d\n", m-s);
}
} else {
for (i=(t>0)?a[t-1]:0; i<=m-s; i++) {
a[t]=i;
solve(m, n, s+i, t+1, a);
}
}
}
代码看不懂我不解释
【 在 math 的大作中提到: 】
: LZ还是多学习一下递归吧，这是个很基础的问题
: 谁有编译器test一下，差不多就是这样做的
: void solve(int m, int n, int s, int t, int *a)
: ...................
C++的一个实现：
void print(int arr[], int len)
{
static int count = 0;
count ++;
cout<<"NO."<<count<<" = ";
for(int i=0;i<len;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
void partion_num(int m, int n, int min = 0 )
{
int i = 0;
int *data = 0L;
if( n < 0 ) return;
if( m < n*min ) return;
data = new int[n];
//initialize first partion!
for(i = 0; i< n-1;i++){
data[i] = min;
}
data[n-1] = m - (n-1)*min;
do{
print(data,n);
//adjust next partion!
for(i=n-1;i>0;i--){
if( data[i] > data[i-1] + 1 ){
data[i]--;
data[i-1]++;
break;
}
}
}while(i>0);
delete[] data;
}
=================================================
调用 ： partion_num(5,3);
输出：
NO.1 = 0 0 5
NO.2 = 0 1 4
NO.3 = 0 2 3
NO.4 = 1 1 3
NO.5 = 1 2 2
======================
调用：partion_num(10,3,1);
输出：
NO.1 = 1 1 8
NO.2 = 1 2 7
NO.3 = 1 3 6
NO.4 = 1 4 5
NO.5 = 2 3 5
NO.6 = 2 4 4
NO.7 = 3 3 4