[转载]阶乘和积分解问题

mathe · 发表于 2010-3-5 11:00:30

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

http://tieba.baidu.com/f?kz=723550649 n个正整数，可以有相同的，他们和是1到n所有整数的和，积是1到n所有整数的积，问n最大能到多少，使得这n个数只能是1到n所有整数链接中已经给出: 1*6*7*10=2*3*5*14 1+6+7+10=2+3+5+14 所以余下工作量很小了。谁写个程序穷举一下？ ------------------------ 扩展问题: 求N个正整数（可以存在相等的数），要求和为${N(N+1)}/2$,积为$N!$的解的数目如N=8,有4个解: [8, 7, 6, 5, 4, 3, 2, 1] [9, 7, 5, 4, 4, 4, 2, 1] [10, 7, 4, 4, 4, 3, 3, 1] [10, 7, 6, 4, 3, 2, 2, 2]

gxqcn · 发表于 2010-3-5 11:15:15

题目读的很费解。比如说，LZ所举例子中对应的n是多少？

mathe · 发表于 2010-3-5 11:15:28

呵呵，本来想用C写，不过先试用了一下Pari/Gp，发现已经很快了。

vf(N)=
{
a=vector(N);
P=N!;
S=(N*(N+1))/2;
s=0;p=P;
search(1,N);
}
search(step, total)=
{
local(v,c);
v=divisors(p);
for(u=1,length(v),
c=v[u];
if(c+s>S,break());
if(step>1&&c>a[step-1],break());
a[step]=c;
s=s+c;
p=p/c;
if(step<total,
search(step+1,total),
if(s==S&&p==1,print(a)));
p=p*c;
s=s-c;
)
}

复制代码

(11:12) gp > vf(7) [7, 6, 5, 4, 3, 2, 1] (11:12) gp > vf(8) [8, 7, 6, 5, 4, 3, 2, 1] [9, 7, 5, 4, 4, 4, 2, 1] [10, 7, 4, 4, 4, 3, 3, 1] [10, 7, 6, 4, 3, 2, 2, 2] 所以N=8的时候分解已经不唯一了。不过N=7只有唯一分解 [8,6,3]~[9,4,4]

gxqcn · 发表于 2010-3-5 11:29:32

是不是找两组相同数目的正整数，满足和相等且积亦相等？如果是这样的话，n可以任意大。

mathe · 发表于 2010-3-5 11:32:57

其中一组指定是1~N这N个数，要求不存在另外一组

mathe · 发表于 2010-3-5 11:39:19

我们可以改进一下难度，改为计算对于每个N分别有多少个解。相当于求N个正整数（可以存在相等的数），要求和为${N*(N+1)}/2$,积为$N!$的解的数目

gxqcn · 发表于 2010-3-5 11:39:42

为什么“要求不存在另外一组”？

mathe · 发表于 2010-3-5 11:42:57

1～n本身这一组总是存在的呀。

mathe · 发表于 2010-3-5 11:45:59

用Pari/Gp计算出来的参考结果: (11:41) gp > vf(8) %9 = 4 (11:42) gp > vf(9) %10 = 12 (11:42) gp > vf(10) %11 = 30 (11:42) gp > vf(11) %12 = 31 (11:42) gp > vf(12) %13 = 112 不过再计算下去有点难度了

wayne · 发表于 2010-3-5 11:55:13

题目都还没看懂，。，

账号		自动登录	找回密码
密码			欢迎注册

[擂台] [转载]阶乘和积分解问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。