/*在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？

首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越 好。 如： 19/45=1/3 + 1/12 + 1/180

19/45=1/3 + 1/15 + 1/45

19/45=1/3 + 1/18 + 1/30,

19/45=1/4 + 1/6 + 1/180

19/45=1/5 + 1/6 + 1/18. 最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。 给出a,b(0<a<b<1000),编程计算最好的表达方式。

输入：a b
输出：若干个数，自小到大排列，依次是单位分数的分母。

样例
输入：
19 45

输出：
5 6 18 */

这个题目不很难，大家可以想想（还是算法第一代码第二）

这样不好吧，你怎么知道我要的分数不在1/1000以内呢？再所这么搜索就有些像穷举了（这可是万不得以的算法）

再想想，一定有更好的方法

大家加油！努力吧（和我的上个题目有些相似，都是分解数的，但一定程度上不相同）

思考了就会有提高！

你的思路1我觉得不对劲。你这么分解总存在相同的加数，除非象你说的无穷，那不等于每解决吗？因为我要加数个数尽量小……

思路二我真的看不太懂……

大家再想想吧，体会一下，说不定会又意外的收获哦。

认真地看了一下，终于看懂knocker的意思了，这个想法不错，先确定搜索的范围，

但搜索你怎么实现呢？如果分数刚好不能分成两个，又怎么确定范围呢？还有都是分成N份如何保证最优解呢？

以上是我做这题时考虑的问题。大家可以思考一下。

或许有很多方法，我总相信——方法绝不会只有一个，大家可以放开自己的思路去想，找出属于自己的算法。

顶！楼上的是不是害怕了（开玩笑）

当你好好想想时，问题时不会难的。我的代码差不多50行，还不是很复杂。

[此贴子已经被作者于2004-07-30 16:56:41编辑过]

沉得好快，

没人做出来吗？（再没人做我只好自己解答了）

我对这道题的解答：（最好定义一个分数运算，保证准确度）

初看这个题目，我也有点摸不找头脑，方法是搜索（这是我想了一番后确定的）

我想最理想的情况是我搜索道的第一个解就是最优解（谁不希望这样）

先说搜索算法：以分2个为例：把以个分数分成两个，其中必有以个比原分数的1/2大，那么范围就有了，我只要搜索所有比原分数的1/2大的分数（很有限），然后判断另一个分数是否满足条件就可以了。搜索应该从满足条件最小的分数到最大的——这样可以保证第一次就搜索到最优解。

我已经把分两个的算法说了，由于要晚自习，没时间了，剩下的大家想想，我晚上放学再来看看。

再说分成N个的算法：

这N个数里面必然有一个比原数的1/N大，那我先找出所有满足条件的数。剩下的就变成了一个N-1的问题。

很明显是可以有第归函数解决的（定义一个分N份的函数，第归调用直到N=2）

当然这么搜索可能会重复，而且是否为最优还不得而知，解决得办法是让搜索有序化，这一次搜索到得数必须比上一

个小（这是我上一个题目的精华思想，在这里也起了大作用）这样得到的必定是最小得加数，要让这个数尽量大（最优

解得要求）就是前面得数尽量小，解决这个只要确定搜索方向就可以了——从小到大搜

举个例子：对于2/5大于它得一半的分数有：1/2，1/3，1/4我们把搜索方向确定为1/4到1/2，这样先搜索到得数总是比后搜索到得数小，也就是最后剩下得数会大。

把搜索函数写好后，先搜索N=2得情况，没有，再搜索N=3的情况，以次类推，

当然这样的搜索你可能会怀疑N太大时…… 其实就我目前的测试看来，还没出现过N>3的情况。

好了，有不懂的可以提出来。我又要去上学了。（如果需要我把代码也贴上来）