给出一个n，可以找出n个整数使它们的倒数和等于1，那个到底有多少组这样的整数呢？

Question

例如：n=2时，只有1/2+1/2这一组；
n=3时，有1/2+1/3+1/6，1/4+/4+1/2，1/3+1/3+1/3三组，
那么n=4呢？任意给你一个n呢？这个组数有多少呢？
请给出一种算法，或者直接给出n和组数k的关系。
我写了个程序算出来：n=4时，k=14；n=5时，k=147。具体是那些我就不写出了，n=4的14种我都写出来了，而且想了很久没想出第15种，暂且就认为是对的吧。
程序还有点问题，正在该，但是就算改好了，对于较大的n计算起来也是很费劲，唉，如果有高手能给出较好的解法，再给100分也不足惜啊……

Answer 1

n=4时；1/2+1/3+1/12+1/12；1/2+1/4+1/8+1/8；1/2+1/6+1/6+1/6；1/3+1/3+1/6+1/6；1/3+1/3+1/4+1/12；1/4+1/4+1/4+1/4 共6种；k=(n-1)*n/2。

数学[英语：mathematics，源自古希腊语μθημα（máthēma）；经常被缩写为math或maths]，是研究数量、结构、变化、空间以及信息等概念的一门学科。

数学是人类对事物的抽象结构与模式进行严格描述的一种通用手段，可以应用于现实世界的任何问题，所有的数学对象本质上都是人为定义的。从这个意义上，数学属于形式科学，而不是自然科学。不同的数学家和哲学家对数学的确切范围和定义有一系列的看法。

发展历史

数学（汉语拼音：shù xué；希腊语：μαθηματικ；英语：mathematics或maths），其英语源自于古希腊语的μθημα（máthēma），有学习、学问、科学之意。古希腊学者视其为哲学之起点，“学问的基础”。

另外，还有个较狭隘且技术性的意义——“数学研究”。即使在其语源内，其形容词意义凡与学习有关的，亦被用来指数学。

其在英语的复数形式，及在法语中的复数形式加-es，成mathématiques，可溯至拉丁文的中性复数（mathematica），由西塞罗译自希腊文复数τα μαθηματικά（ta mathēmatiká）。

Answer 2

n=2时,只有一组:(1/2+1/2);
n=3时,有三组:(1/2+1/3+1/6), (1/2+1/4+1/4) , (1/3+1/3+1/3);
n=4时,组数就较多了,现利用"因数分解法"求解:
只要把n=3时各组其中一个变为两个分数就行了!
例如:1/2+1/3+1/6.
(1)现把1/2分解为两个分子为1的分数,其分母的平方为2²=4,4=1x4=2x2.
得1/2=1/(2+1)+1/(2+4)或1/(2+2)+1/(2+2).
即:n=4的两组解:(1/3+1/3+1/6+1/6), (1/3+1/4+1/4+1/6);
(2)若把1/3分解为两个分子为1的分数,其分母的平方为:3²=9=1x9=3x3.
得1/3=1/(3+1)+1/(3+9)或1/3=1/(3+3)+1/(3+3).
即:n=4的两组解为(1/2+1/4+1/6+1/12), (1/2+1/6+1/6+1/6).
(3)同样的方法:1/6分母"6"的平方为6²=36,36=1x36=2x18=3x12=4x9=6x6.
得1/6=1/(6+1)+1/(6+36)或1/6=1/(6+2)+1/(6+18)或1/6=1/(6+3)+1/(6+12)或1/6=1/(6+4)+1/(6+9)或1/6=1/(6+6)+1/(6+6).
即n=4的五组解为:(1/2+1/3+1/7+1/42), (1/2+1/3+1/8+1/24),(1/2+1/3+1/9+1/18),(1/2+1/3+1/10+1/15),(1/2+1/3+1/12+1/12).
(4)按照同样类似的办法,可以从n=3时的答案中分解出n=4的其他答案:
(1/4+1/4+1/4+1/4),(1/2+1/4+1/5+1/20),(1/2+1/4+1/6+1/12),(1/2+1/4+1/8+1/8),
(1/3+1/3+1/4+1/12).
即n=4时的答案有十四组解:
(1/3+1/3+1/6+1/6), (1/3+1/4+1/4+1/6), (1/2+1/4+1/6+1/12), (1/2+1/6+1/6+1/6),
(1/2+1/3+1/7+1/42), (1/2+1/3+1/8+1/24),(1/2+1/3+1/9+1/18),(1/2+1/3+1/10+1/15),(1/2+1/3+1/12+1/12),(1/4+1/4+1/4+1/4),(1/2+1/4+1/5+1/20),(1/2+1/4+1/6+1/12),(1/2+1/4+1/8+1/8), (1/3+1/3+1/4+1/12).
n=5时的组数,按照上面的分解方法,得到的组数会更多,请楼主往下想想吧!追问

说实话我也这样想了，但是这个方法只适合手工的模拟，要写成程序很麻烦（会生成重复的，所以要去重），我最先的思路也就是这样的，但是5就会有一百多种……实在是不好手工完成，所以我现在想先找一种合适的算法，让计算机来实现，然后再看看有没有什么更简明的规律来。
不管怎样，谢谢你的认真回复，写这么多，累着您了，呵呵。

Answer 3

n=4时
1/2+1/3+1/12+1/12
1/2+1/4+1/8+1/8
1/2+1/6+1/6+1/6

1/3+1/3+1/6+1/6
1/3+1/3+1/4+1/12

1/4+1/4+1/4+1/4 共6种
k=(n-1)*n/2

推了半天才推出来的，请采纳 采纳后有具体解释。

参考资料：推了

Answer 4

这个题我们机房刚刚做过一道一样的题，是NOIP2011的模拟题，当时数据给的是N<=10，所以说如果你要算n=11的话1秒内是解决不了了。。。。
10一下的话可以用预处理部分和，然后直接搜索，加上下界剪枝，然后就可以了。没有高效的算法和递推公式。如果你要看原题的话，也许我可以找到。。。追问

我的是写了个递归函数程序，f（m，n，1/k）表示：把m分为n个分数，这些分数小于等于1/k 的分解数，则f（m，n，1/k）=f（m，n，1/（k+1））+f（m-1/k，n+1，1/k），但是不知道是递归边界没写好，或者是就是递归层数太多，我的程序只能算到5，6的时候会报错，到现在也没改好，唉，要不你贴下你的代码吧。看着就你的回答比较靠谱，谢谢了。

追答

这道题真的是搜索不是递归。。。。。。。。。也不是其他算法。。。。。。

追问

找到了些资料，好像就是没有什么比较好的解法，你说的比较靠谱，分给你吧，记的把你的代码贴出来。

Answer 5

1, 1, 3, 14, 147, 3462, 294314, 159330691，。。。
埃及分数，古老的经典问题，有很多现成的参考资料。
解数序列请见http://oeis.org/A002966，其中的链结可找到不少资源，包括算法追问

我也找到这个网站了，谢过。

参考资料：http://oeis.org/A002966

本回答被提问者采纳