Project Euler#45:我的逻辑怎么错了



来自Project Euler,问题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 值的三重函数一致的数值

结果得到3个n和A的方程组。用夸克公式求解,得到3个方程组。

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

所以我的逻辑是测试A的值,在这个值上,三个方程给出了一个自然的+ve值。到目前为止,它对数字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

我的逻辑怎么错了?(为涉及的一些数学问题道歉。:)

假设:

  • 所有的六边形也是三角形
  • 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()

几乎很快就会产生140755和你正在寻找的另一个数字,几秒钟后就会产生一个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)

时代看起来很相似,但我没有费心去衡量。

您的逻辑没有错,您的程序只是需要很长时间才能运行(据我估计,它应该在大约一个小时内提供答案)。我知道答案,并通过将i设置为刚好低于它的值来测试您的程序。然后您的程序立即弹出正确的答案。

听从了埃斯库贝的建议。

实现的最简单方法是为每个序列制作3个生成器,并在中路由它们

heapq.merge

然后,如果你找到3个相同的保守密钥,你就得到了解决方案找到这个最简单的方法是usnig

itertools.groupby

相关内容

最新更新