c++面试题求解的个数效率近可能高

uurabit
Hit to heart
等级:

发表于：2008-07-08 22:01:30 楼主

正整数ai≤xi≤bi ,1≤i≤n;n为正整数, x1+x2+……xn=s;已知s的解;求x有多少组解给出算法思路效率要尽可能高
题的大概意思就这样吧

问题点数：20 回复次数：14 修改删除举报引用回复

csdn5211
多情总被无钱伤
等级:

发表于：2008-07-08 22:04:151楼得分:1

哈哈，这就是传说中的组合数学问题了。有公式的，千万别自己算。

修改删除举报引用回复

GoAssemblyNow
老陈
等级:

发表于：2008-07-08 22:07:232楼得分:0

楼主可否把问题表达得清楚点。

修改删除举报引用回复

macfan
心静一静,太浮躁了.
等级:

发表于：2008-07-08 22:36:453楼得分:2

公式没看太懂.
应该还是用穷举.

修改删除举报引用回复

fallening
龖之赫，霆之砉
等级:

发表于：2008-07-08 22:40:514楼得分:0

个人感觉应该有直接算数解

转去算法版让那边的高手看看

修改删除举报引用回复

cqqqq
cqqqq
等级:

发表于：2008-07-10 00:36:005楼得分:1

文字描述:
有N个正整数,每个正整数都在一个固定的范围内,这些正整数和为一个定值.求可能的情况有多少种?

修改删除举报引用回复

ybw20041910
20041910
等级:

发表于：2008-07-10 11:22:166楼得分:2

文字描述:
有N个正整数,每个正整数都在一个固定的范围内,这些正整数和为一个定值.求可能的情况有多少种?
你的描述不对，“每个正整数都在一个固定的范围内”这句话有误解，用例子：1 <x1 <4，4 <x2 <7.........

修改删除举报引用回复

lixianmin
☆
等级:

发表于：2008-07-10 18:22:487楼得分:3

这个我想应该可以用公式算出来，组合数学问题，把条件放宽：正整数1≤xi≤s-1 ,1≤i≤n;n为正整数, x1+x2+……xn=s;这样则相当于把s个球摆成一列直线，则中间会出现s-1个空格，在这s-1个空格里取n-1个，就会把它们分成n堆，显然这n堆球都满足[1, s-1]的条件，　因此转化成一个组合问题C(s-1, n-1)，　当ai≤xi≤bi 时，通过加减可以把左边的ai变成1，但对右边的bi如何处理，我现在还不太确定，也许会有相应的公式支持

修改删除举报引用回复

ytunx
等级:

发表于：2008-07-10 21:02:248楼得分:2

只知道，这个数应该在1到10＾（bi - ai）次方之间

修改删除举报引用回复

tailzhou
幸福的尾巴
等级:

发表于：2008-07-10 21:08:269楼得分:0

这是一个整数分解问题;

生成函数为：(x^a1+x^(a1+1)+...x^b1)(x^a2+x^(a2+1)+...+x^b2)*...*(x^an+x^(an+1)+...+x^an)

解的个数为x^s项的系数

修改删除举报引用回复

tailzhou
幸福的尾巴
等级:

发表于：2008-07-10 21:14:3010楼得分:0

很难有直接的公式去计算；

可以用dp来计算;
假设dp[i][j]表示xi+...+xn=j的解的个数;

那么:
dp[i-1][j]=sum(dp[i][k]) j-b(i-1) <=k <=j-a(i-1);

修改删除举报引用回复

tailzhou
幸福的尾巴
等级:

发表于：2008-07-10 21:17:3511楼得分:4

dp[i-1][j]=sum(dp[i][k]) j-b(i-1) <=k <=j-a(i-1);
==>
dp[i-1][j]=sum(dp[i][k]) 其中j-b(i-1) <=k <=j-a(i-1);

可以做一下变换，xi都取a1;

那么问题就转换成了：
０≤xi≤bi-ai ,1≤i≤n;n为正整数, x1+x2+...+xn=s'=s-sum(a1..an)

修改删除举报引用回复

yujie_v
tocy
等级:

发表于：2008-07-13 10:49:1612楼得分:0

有待考虑

修改删除举报引用回复

hugsnow
抱雪
等级:

发表于：2008-07-23 10:21:0513楼得分:5

等式写成,
y1+a1+y2+a2+...+yn+an=s=>
y1+y2+..+yn=s-sum(a1...an),y1>=0;
显然，就是把s-sum(a1...an)个数放到n个不同的盒子中，允许有盒空，则解的个数是可重组合数
C(s-sum(a1...an)+n-1,s-sum(a1...an)).

修改删除举报引用回复