大榕树——让我们共成长!
大榕树 myDrs.org
您的位置:大榕树 \ 编程       |  Logo语言   |  Pascal语言   |  信息学奥赛   |  高考保送    |  HTML版本
|  Pascal语言>>Pascal练习>>埃及分数之和         本站全文搜索: 友情提示:

埃及分数之和
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

来 源:网络之家
共有6418位读者阅读过此文

  • 上篇文章组合三位平方数
  • 下篇文章筛法的应用

  • 发送邮件
    保存页面 打印文章 HTML版本 发表评论

    □- 近期热门文章 □- 相关文章
    1. NOIP2006竞赛大纲 [8307]
    2. 七类高中生具有保送资格 [5911]
    3. NOI2006获奖选手名单 [4956]
    4. 关于举办NOIP2006模拟赛的通告 [4107]
    5. Turbo Pascal各语句运行速... [3595]
    6. Turbo王者归来新Delphi免费... [3182]
    7. IOI2006我国4名选手全部获得金... [2946]
    8. 关于APIO2007与IOI2007... [2764]
    9. noip倒计时 by 枯叶蝴蝶 [2684]
    10. 朱泽园:思想上的金牌更重要 [2169]
    矩形条覆盖问题的贪心算法
    埃及分数之和
    贪心法矩阵胚理论介绍
    贪心法基础
     

    关于本站 | 合作伙伴 | 联系方式
    大榕树 版权所有 ©1999-2006 www.myDrs.org 闽ICP备05000721号