3

现在我正在尝试解决Project Euler 71。

考虑分数 n/d，其中 n 和 d 是正整数。如果 n

如果我们按大小升序列出 d ≤ 8 的约简真分数集，我们得到：

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/ 5、5/8、2/3、5/7、3/4、4/5、5/6、6/7、7/8

可以看出，2/5 是紧靠 3/7 左边的分数。

通过按大小升序列出 d ≤ 1,000,000 的简化真分数集，找到紧靠 3/7 左侧的分数的分子。

当前代码：

from fractions import Fraction
import math

n = 428572
d = 1000000

x = Fraction(3,7)

best = Fraction(0)

while d > 1:
    if Fraction(n,d) >= x:
        n-=1
    else:
        y = Fraction(n,d)
        if (x - y) < (x - best):
            best = y
        d -= 1
        n = int(math.ceil(d*0.428572))

print(best.denominator)

解释：

from fractions import Fraction
import math

分数和 math.ceil 需要。

n = 428572
d = 1000000

这两个变量代表原始问题中的n和d陈述。数字以这种方式开始，因为这是一个稍大的表示3/7（稍后将转换为分数）。

x = Fraction(3,7)

best = Fraction(0)

x 只是一个快速参考，Fraction(3,7)所以我不必继续输入它。best用于跟踪最接近3/7但仍在其左侧的分数。

while d > 1:

如果d <= 1并且n必须小于1检查的意义何在？那就别查了。

if Fraction(n,d) >= x:
    n-=1

如果分数最终大于或等于3/7它不在它的左边，所以继续减去n它直到它在它的左边3/7。

    else:
        y = Fraction(n,d)
        if (x - y) < (x - best):
        best = y

如果它在左边，3/7看看3/7减号best或y（它等于我们需要检查的分数）是否更接近于 0。更接近于 0 的那个将是最左边的，或者最接近于3/7。

        d -= 1
        n = int(math.ceil(d*0.428572))

不管最佳改变与否，分母都需要改变。因此，从分母中减去 1 并设置 n 分数（n，d）略大于（添加额外的 ceil 方法以确保它更大！）而不是3/7修剪测试空间。

print(best.denominator)

最后打印问题想要的内容。

笔记

更改d为8和更改n为4（如测试用例）给出了5分母的所需结果。保持原样给出：999997.

有人可以向我解释我做错了什么吗？

4

3 回答 3

4

这不是做事的正确方法。您应该使用Stern-Brocot 树。您根本不必弄乱浮点数。

于 2012-07-01T05:01:02.473 回答
2

你做错了什么：

找到分子

除此之外，遵循@Antimony 的建议并了解 Stern-Brocot 树，这很有用而且很有趣。

于 2012-07-01T05:06:13.330 回答
1

不是为了让你觉得自己很傻。但是您的答案完全正确，请再次阅读问题并将最后一行更改为：

print( best.numerator )

此外，为了记录，有一种更有效的计算方法。

于 2012-07-01T05:12:45.873 回答