欧拉计划第45题：我的逻辑错在哪里？

Question

欧拉计划第45题：我的逻辑错在哪里？

5

来自欧拉计划，问题45：

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle T_(n)=n(n+1)/2 1, 3, 6, 10, 15, ...

Pentagonal P_(n)=n(3n−1)/2 1, 5, 12, 22, 35, ...

Hexagonal H_(n)=n(2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T_(285) = P_(165) = H_(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

[ http://projecteuler.net/problem=45 ]

现在为了解决它们，我取了三个变量并将方程式等于A。

n(n + 1)/2 = a(3a - 1)/2 = b(2b - 1) = A

A = 三个函数在n、a、b值相同时的数字

结果我们得到了关于n和A的3个方程式。用二次公式求解，我们得到3个方程式。

 (-1 + sqrt(1 + 8*A ) )/2
 ( 1 + sqrt(1 + 24*A) )/6
 ( 1 + sqrt(1 + 8*A ) )/4

我的逻辑是测试A的值，使得三个方程式给出自然数+正值。到目前为止，它对小于40755的数字运行正确，但在接下来的1000万中未能找到下一个。

(编辑): 这是我的Python代码

from math import *

i=10000000
while(1):
    i = i + 1
    if(((-1+sqrt(1+8*i))/2).is_integer()):
        if(((1+sqrt(1+24*i))/6).is_integer()):
            if(((1+sqrt(1+8*i))/4).is_integer()):
                print i
                break

我的逻辑哪里有问题？（很抱歉涉及到一些数学。 :) ）

- Shubham

5

所有六边形数也是三角形数。 - ypercubeᵀᴹ

4

你似乎还在测试所有整数。你可以通过先计算出六边形数，然后再测试它们（是否也是五边形数）来加快速度。 - ypercubeᵀᴹ

1

嗯，is_integer 真的是这样工作的吗？无论数字是否接近整数，在计算后它仍然会以 double 类型出现，所以它不会始终返回 true 吗？也许你应该编写自己的整数检查函数，这样你就知道它在做什么了。 - HexTree

哦，我查了一下这个函数，它确实可以做到你想要的，但是我有点担心舍入误差，所以最好写一个自己的整数测试。当我解决这个问题时，我将平方根向下取整，然后重新应用三角形公式来检查是否回到三角形数。 - HexTree

@ypercube：感谢您的想法。从未想过优化。总是认为这是逻辑缺陷 :)。 - Shubham

3个回答

0

你的逻辑没有问题，只是你的程序运行时间很长（根据我的估计，它应该在大约一个小时内提供答案）。我知道答案，并通过将i设置为略低于它的值来测试了你的程序。然后你的程序立即弹出了正确的答案。

请听从ypercube的建议。

- Lauritz V. Thaulow

0

最简单的实现方式是为每个序列制作3个生成器，然后将它们路由。

heapq.merge

然后，如果您找到3个相同的连续键，则找到了解决方案。最简单的方法是使用

itertools.groupby

- Luka Rahne

1

我认为这种思考问题的方式对于OP来说可能相当陌生... - Karl Knechtel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tzot · Accepted Answer

鉴于以下条件：

所有六边形都是三角形
heapq.merge 对于手头的任务非常方便（高效且节省代码）

那么这个问题就可以得到解决：

import heapq

def hexagonals():
    "Simplified generation of hexagonals"
    n= 1
    dn= 5
    while 1:
        yield n
        n+= dn
        dn+= 4

def pentagonals():
    n= 1
    dn= 4
    while 1:
        yield n
        n+= dn
        dn+= 3

def main():
    last_n= 0
    for n in heapq.merge(hexagonals(), pentagonals()):
        if n == last_n:
            print n
        last_n= n

main()

该程序可以快速生成1、40755和另一个你寻找的数字，并在几秒钟后生成一个14位数。当你认为你已经消耗了足够的电力时，只需停止程序即可。

如果您想避免“不透明”的库，请使用以下main函数（基本上是相同的算法，只是拼写出来而已）：

def main():
    hexagonal= hexagonals()
    pentagonal= pentagonals()
    h= next(hexagonal)
    p= next(pentagonal)
    while 1:
        while p < h:
            p= next(pentagonal)
        if p == h:
            print p
        h= next(hexagonal)

这些时间看起来很相似，但我没有费心去进行基准测试。