/*在古埃及，人们使用单位分数的和(形如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 */

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

晕，乌鸦又开始害人了~先LOOK LOOK题目先

既然都是用分子为1的分数相加，那我们可不可以这样

原数=1/2+1/3+1/4+1/5+1/6+....+1/1000

然后从中挑选出我们需要的，不要的就删掉。不知道行不行。

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

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

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

思考了就会有提高！

偶想问个弱智问题：C语言允许用new和delete吗？我想到一个步骤要用new

“首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好”

判断从这句话入手，待续……

这个问题的解是无穷的。

思路一：

例：3/7

3/7=1/7+1/7+1/7

=1/7+2/14+3/21

=1/7+1/14+1/14+1/21+1/21+1/21+1/21

=。。。。。

思路二：

如何求得“加数”是最少？是不是可以这样：

假定一个 1/a （a为自然数） 。。。。（1）

1/a < 3/7 .............. (2)

求得满足（1）（2）且a为最小值，（ 当a为最小值时，即1/a为最大值 ）

令 1. 3/7 -1/a = x/y

2. x/y - 1/a1 = x1/y1

。。。。

重复上述过程 直到x==1

这里的a是这样求的

如：3/7

3/7 -1/a --> 3a/7a - 7 / 7a

则： (3a-7)/7a为最小值时且 》0

即 3a-7>0

a>7/3

a= 7/3 + 1

分解并不是很难

===================================

但是，这里有个问题，我想不明白：

假定有：任意 a/b 则如何证明其最少加数？

我们来看看：

有 a/b （a,b是已知数，a<b ）,假定有1/x 1/y (x,y为自然数）

a/b = 1/x +1/y

=(y+x)/xy

则有: axy=by +bx

by+bx-axy=0

y= -bx / (b-ax) （用上面的 3/7 代进去则为 y= -7x / (7 - 3x)

注意到没有？ 用X（ 2<= x <= 无穷大）代入，只要 y 的值是个整数，则

a/b =1/x + 1/y 有解，也就是说，如果不能否定

对任意a<b, y= -bx / (b-ax) y一定有个整数解

那么，任意a/b (a<b) 其加数最少是2项，即 1/x+1/y

写得乱了一点，想看的就看一下吧

[此贴子已经被作者于2004-07-28 16:33:16编辑过]