主题:程序计算机技能竞赛题???
煜煜
[专家分:0] 发布于 2005-06-15 15:02:00
设计一个程序,把一个真分数表示为埃及分数之和的形式。
所谓埃及分数,是指分子为1的形式。如:7/8=1/2+1/3+1/24
回复列表 (共6个回复)
沙发
moz [专家分:37620] 发布于 2005-06-15 17:09:00
可不可以是 1/4+1/4+1/4+1/8 ?
可以把分母分解质因子.
如果是可以的话干脆就是
1/8+1/8+1/8+1/8+1/8+1/8+1/8得了.
板凳
飞鸟12 [专家分:2830] 发布于 2005-06-16 12:22:00
不错的题目,是得好好想想
3 楼
prairiewolf [专家分:290] 发布于 2005-06-25 15:11:00
1楼的对不对啊,怎么也不回话啊
4 楼
staa [专家分:3690] 发布于 2005-06-28 23:43:00
这个题比较适合用贪婪法:
0.给出纯分数s(s<1)
1.m=2
2.如果大于1/m,则s=s-1/m -->5
3.如果s=0则6
4.m=m+1
5.回到2
6.结束
5 楼
moz [专家分:37620] 发布于 2005-06-29 08:32:00
作者:rickone
专家分:3440
会员信息
发短消息
所属BLOG
发表时间:2005-5-12 17:28:00 [回复]
每2小时送iPod Shuffle一台!连送20天!免费注册就可获得!
--------------------------------------------------------------------------------
楼主
埃及分数
Time Limit:2s Memory Limit:1000k
Total Submit:2159 Accepted:301
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
在古埃及,人们使用单位分数的和(形如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),编程计算最好的表达方式。
Input
第一行:N 表示有N组测试数据,每组测试数据为一行包含a,b(0〈a〈b〈1000)。
Output
每组测试数据若干个数,自小到大排列,依次是单位分数的分母。
Sample Input
1
19 45
Sample Output
5 6 18
Source
oibh
我觉得有难度,并且有意思。
6 楼
moz [专家分:37620] 发布于 2005-06-29 08:32:00
附和STAA
我来回复