埃及分数之和
http://www.mydrs.org 10/6/2001 大榕树
例: 设计一个程序,把一个真分数表示为埃及分数之和的形式。 问题分析: 所谓埃及分数,是指分子为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
|