大榕树 \ Pascal语言 \ Pascal练习

埃及分数之和

原文链接：http://www.mydrs.org/program/list.asp?id=234

例：
          设计一个程序，把一个真分数表示为埃及分数之和的形式。
问题分析：
        所谓埃及分数，是指分子为1的形式。古代埃及有一个非常奇怪的习惯，他们喜欢把一个分数表示为若干个分子为1的分数之和的形式。如，7/8=1/2+1/3+1/24。
    下面介绍其中一种算法――贪心算法。贪心算法是由数学家菲波那契提出的，基本思想是：
设某个真分数的分子为A，分母为B；
把B除以A的商的整数部分加1后的值作为埃及分数的某一个分母；
将A乘以C减去B作为新的A；
将B乘以C作为新的B；
如果A大于1且能整除B，则最后一个分母为B/A；
如果A＝1，则最后一个分母为B；
否则转步骤（2）。
如：7/8=1/2+1/3+1/24
步骤
A
B
C
AC－B
BC
1
7
8
2
6
16
2
6
16
3
2
48
3
2
48
24
8/11=1/2+1/5+1/37+1/4070
步骤
A
B
C
AC－B
BC
1
8
11
2
5
22
2
5
22
5
3
110
3
3
110
37
1
4070
4
1
4070
4070
解题步骤：
用变量A表示分子，变量B表示分母；
C=B\A+1
A=A*C-B,B=B*C
打印1/C
若A>1且B/A=B\A，则C=B/A
若A＝1，则C=B,打印1/C
转步骤（2）。
　
程序清单：
CLS
DO
    INPUT "a,b="; a, b
LOOP UNTIL a < b
PRINT a; "/"; b; "=";
DO
    c = b \ a + 1
    a = a * c - b: b = b * c
    PRINT "1/"; c;
    IF b / a = b \ a THEN PRINT "+1/"; b / a: END
    IF a > 1 THEN PRINT "+";
LOOP WHILE a > 1
PRINT "+1"; b
END

作者：
来源：网络之家
时间：2001-10-06

上一篇：组合三位平方数
下一篇：筛法的应用