当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2724埃及分数
1233+

题目大意:将一个分数化成若干个分数之和,要求这些分数分子都是1,分母递增,方案有多种,输出加数最少的,加数相同,输出最小分数最大的。

题目描述

来源:BIO 1997 Round 1 Question 3

在古埃及,人们使用单位分数的和(形如 $\frac{1}{a}​$​​ 的,a 是自然数)表示一切有理数。如:$\frac{2}{3} = \frac{1}{2} + \frac{1}{6}​$​​,但不允许 $\frac{2}{3} = \frac{1}{3} + \frac{1}{3}​$​​,因为加数中有相同的。对于一个分数 $\frac{a}{b}$​​,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如:

$\frac{19}{45} = \frac{1}{3} + \frac{1}{12} + \frac{1}{180}​$

$\frac{19}{45} = \frac{1}{3} + \frac{1}{15} + \frac{1}{45}​$

$\frac{19}{45} = \frac{1}{3} + \frac{1}{18} + \frac{1}{30}​$

$\frac{19}{45} = \frac{1}{4} + \frac{1}{6} + \frac{1}{180}​$

$\frac{19}{45} = \frac{1}{5} + \frac{1}{6} + \frac{1}{18}​$

最好的是最后一种,因为 $\frac{1}{18}$​​ 比 $\frac{1}{180}, \frac{1}{45}, \frac{1}{30}, \frac{1}{18}​$​​ 都大。

注意,可能有多个最优解。如:

$\frac{59}{211} = \frac{1}{4} + \frac{1}{36} + \frac{1}{633} + \frac{1}{3798}​$

$\frac{59}{211} = \frac{1}{6} + \frac{1}{9} + \frac{1}{633} + \frac{1}{3798}​$

由于方法一与方法二中,最小的分数相同,因此二者均是最优解。

给出 a,b,编程计算最好的表达方式。保证最优解满足:最小的分数 ≥$1/10^7$。

输入

一行两个整数,分别为 ab 的值。

输出

输出若干个数,自小到大排列,依次是单位分数的分母。

提示

样例输入

19 45

样例输出

5 6 18

解题思路

直接爆搜,不知道搜索多深,我们可以从小到大枚举深度、枚举分数个数,找不到再多加一个,这样可以避免深度大了复杂度过高。因为每次搜索复杂度差不多,而且深度小的搜索得更快,所以这样多次并不会降低多少速度。

对于n个分数,我们可以从小到大枚举每个分数的分母i,a/b – 1/i得到的新分子分母继续枚举即可。最终必须得到1/c的格式,且c大于上一个的分母。

枚举每个分母时,需要确定范围,最小是前一个分母加1,最大如果是d/c,那么n-k+1个加起来必须大于a/b(至少2个,分母不同后面更小)。继续优化范围,就是分母至少填b/a,如2/9,填1/4是不行的,必须不超过a/b。因为还剩下至少两个,所以还是要多加1,相等也不行。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,,,

SSOJ2724埃及分数:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!