求dfs写法
  • 板块灌水区
  • 楼主King__Norman
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/6/10 21:06
  • 上次更新2023/11/4 22:02:53
查看原帖
求dfs写法
226483
King__Norman楼主2021/6/10 21:06
问题 埃及分数

在古埃及,人们使用单位分数的和(形如 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),试编程计算最好的表达方式

样例输入

19 45

样例输出

5 6 18

注:0<a<b<1000

2021/6/10 21:06
加载中...