求教一个分解整数问题
在做一个小题目，分解开后就剩这么个问题了：
如何将一个整数分解成用指定范围内的无重复的整数的和的形式。
比如;将14分解成2至7间的整数的和的形式。
7+4+3
7+5+2
6+5+3
5+4+3+2
我实现了将一个整数分解成一系列整数的和的形式，但有重复，也不能在指定范围内分解，而且20以上时间开销较大。
比如将5分解：1+1+1+1+1 2+1+1+1 2+2+1 3+1+1 3+2 4+1
有用的是3+2 4+1 ,又如果指定在1到3 内分解，就只有2+3满足了。
望个位高手指点一二。。。
[解决办法]
一个取巧点的办法：【5分解，定在1到3 为例】
把指定区间数据累加求和，1+2+3 ＝ 6；
然后计算这个累加和 和预期结果的差值 6-5 ＝1，
1 在 指定的区间内部，
OK， 去掉该值即可。
[解决办法]
这个简单，另外写两个函数：
bool special_filed()
{
//把每一组结果装进一个数组
//对每一组进行扫描，凡是在范围之外的返回假
}
bool unique_if()
{
//把每一组结果装进一个数组
//对每一组进行扫描，凡是碰到有两个一样的元素的返回假
}
其实上面的函数可以用泛型算法更易
[解决办法]
这样的方法有一个问题，
如果数据比较大， 区间比较大，
当这个 累加和 和 给定值 相差过大的时候，
就无效了（因为 差值可能比 给定值还大，也就是这个 差值 也需要和求取给定的过程一样，导致一个死循环）
但是对于一些简单的情况还是有效的，
而且方法非常简单 ～
[解决办法]
下面是一个不限制范围的分解，修改一下应该就可以满足你的需要
#include <stdio.h>
int n;
int tot=0;
int a[100];
void print(int t)
{
int i;
printf( "%d=%d ",n,a[0]);
for (i=1;i <=t;i++)
{
printf( "+%d ",a[i]);
}
printf( "\n ");
}
void go(int t,int now)
{
a[t]=now;print(t);
int i;
for (i=a[t-1];now-i> =i;i++)
{
a[t]=i;
a[t+1]=now-i;
tot++;
go(t+1,now-i);
}
}
int main(int argc, char *argv[])
{
int i,j,k,l;
printf( "input n: ");scanf( "%d ",&n);
if (n==0) n=10;
for (i=1;i*2 <=n;i++)
{
a[0]=i;
go(1,n-i);
}
printf( "total=%d\n ",tot);
system( "PAUSE ");
return 0;
}
[解决办法]
下面的代码满足lz的要求，当然，这个实现很简洁，还有很大的优化空间，不过，优化就是lz自己的事情了：）
#include <stdio.h>
int solution[128];
int si;
void cal (int low, int high, int k)
{
if (k == 0)
{
for (int i = 0; i < si - 1; i++)
printf ( "%d+ ", solution[i]);
printf ( "%d\n ", solution[si - 1]);
}
else
{
for (int i = high; i > = low; i--)
{
solution[si++] = i;
cal (low, i - 1, k - i);
--si;
}
}
}
int main ()
{
cal (2, 7, 14);
return 0;
}
