欧拉计划问题45

#1 楼

算术

项目Euler的问题旨在教育您数学和程序设计。了解这些三角形，五角形和六边形的实际含义是一个好主意，而不是盲目地应用给定的公式。

一个性能改进将是找到一种方法来生成连续的元素每个序列而不会将\ $ n \ $插入涉及除法的公式中。 （除法运算往往很慢。使用/而不是//运算符进行浮点除法的速度甚至更慢，并且这也导致您必须将结果强制返回给int。）如果采用五角形数\ $ P_n \ $的公式，则可以找出该序列中连续元素之间的差的另一个公式。 br /> P_n＆= \ frac {n（3n-1）} {2} = \ frac {3n ^ 2-n} {2} \\
P_ {n + 1}＆= \ frac {（ n + 1）（3（n + 1）-1）} {2} = \ frac {（n + 1）（3n + 2）} {2} = \ frac {3n ^ 2 + 5n + 2} {2 } \\
P_ {n + 1}-P_n＆= \ frac {（3n ^ 2 + 5n + 2）-（3n ^ 2-n）} {2} = \ frac {6n + 2} { 2} = 3n + 1
\ end {align}
$$

如果对三角，平方和六边形进行相同的操作，则会发现： />
$$
\开始{align}
T_ {n + 1}-T_n＆= n + 1 \\
P_ {n + 1}-P_n＆= 3n + 1 \\
H_ {n + 1}-H_n＆= 4n + 1
\ end {align}
$$

考虑平方数会是\ $ S_ {n + 1}-S_n = 2n + 1 \ $，则可以看到产生polyg的模式一般情况下是整数。

算法

您的策略是为每个序列生成一百万个元素并查找共同存在的元素。

首先，一百万是一个任意限制。您可能需要不到一百万才能找到下一个共同的元素（在这种情况下您浪费了执行时间），或者您可能需要超过一百万（在这种情况下您必须提高限制并再次运行代码） ）。如果您的算法不必依靠猜测，那就太好了。第百万个六边形数不可能与任何东西重合，所以这是浪费的。

第三，将序列存储为列表。搜索列表（例如terms in triangle）涉及检查该列表中的每个元素（所谓的O（n）操作）。搜索一个set只需要O（1）时间。因此，只需更改

triangle = []
pentagonal = []
hexagonal = []

和

        triangle.append(product.triangle())
        pentagonal.append(product.pentagonal())
        hexagonal.append(product.hexagonal())

>
到

triangle = set()
pentagonal = set()
hexagonal = set()

和

        triangle.add(product.triangle())
        pentagonal.add(product.pentagonal())
        hexagonal.add(product.hexagonal())

使执行时间从数百秒缩短下降到大约2秒。更好的是，可以使用设置交集运算符main()来简化&函数：如果您写“ pentagonal”和“ hexagonal”，请使用“ triangular”而不是“ triangle”。

Shape类根本不存在。这是调用带有数字参数的三个函数的一种非常怪异和神秘的方式。

for _, terms in enumerate(hexagonal)是enumerate的荒谬用法。如果仍然要丢掉索引，为什么不写for terms in hexagonal呢？以及为什么您的迭代变量是复数形式（terms而不是term）？

如果您可以说“给我下一个五角形数字”，您的代码将更具表现力。在Python中执行此操作的一个好方法是定义一个生成器，以便您可以编写next(pentagonal_numbers)。

建议的解决方案

def main():
    generate()
    triangle_number = triangle & pentagonal & hexagonal
    print(sorted(triangle_number))
    print(time.time() - startTime, "seconds")

如果考虑到每个六角形数字也是三角形数，则可以完全忽略三角形数字：

from itertools import count

def polygonal_numbers(sides):
    result = 0
    for n in count():
        yield result
        result += (sides - 2) * n + 1

tt, pp, hh = polygonal_numbers(3), polygonal_numbers(5), polygonal_numbers(6)
t = p = 0 
for h in hh:
    while p < h: p = next(pp)
    while t < h: t = next(tt)
    if t == p == h > 40755:
        print(h)
        break

我的最后一个解决方案需要大约50毫秒才能在我的计算机上运行。

#2 楼

代码

limit = 1000000
triangle = []
pentagonal = []
hexagonal = []
triangle_number = []

全局变量无助于可读性。

triangle和triangle_number有什么区别？这些名称并不能帮助我理解它们代表什么。

class Shape:
    def __init__(self, term):
        self.term = term

    def triangle(self):
        return int(self.term * (self.term + 1) / 2)

    def pentagonal(self):
        return int(self.term * (3 * self.term -1) / 2)

    def hexagonal(self):
        return int(self.term * (2 * self.term - 1))

形状没有术语：它有侧面。具体而言，由于我们在谈论常规形状，因此它具有两个属性：边数和每边的长度。

如果您真的想使用类练习结构化代码，则该类应该是Solver。

    for _, terms in enumerate(hexagonal):
        if len(triangle_number) == 3:
            break
        elif terms in triangle and terms in pentagonal:
            triangle_number.append(terms)
            print(terms)

如果要测试x in ys，则ys最好是set而不是list，否则必须进行线性搜索。


算法

当前算法可以总结如下：

fix a large limit
generate `limit` terms in each of the sequences
for term in first_sequence
    if term in second_sequence and term in third_sequence:
        term is a candidate solution

限制是猜测，可能是太小而找不到解决方案，或者太大而又浪费大量时间来生成项。

如果您注意到所有序列都在严格增加，则可以执行一种合并：

while problem not solved:
    initialise each of the sequences at the first term
    if all sequences have the same current term:
        term is a candidate solution
    advance one of the sequences which has the smallest current term

项目Euler不仅是数学，还涉及编程。我们再来看一下这些术语公式：$$ T_n = \ frac {n（n + 1）} {2} \\ H_n = n（2n-1）$$
我们可以将后者改写为$$ H_n = \ frac {（2n−1）（2n）} {2} $$
您能找到可以简化搜索的主要简化方法吗？

还有更复杂的数学改进，但这不是地方。请查看解决问题后可以访问的Project Euler讨论线程，如果您可以从中提取问题，请在我们的姊妹网站math.stackexchange.com上提问。

#3 楼

我想将其包含为习惯于编写需要类的解决方案的一种做法。和其他技术。

在这种特殊情况下，Shape并不需要真正存在-正如您已经确定的那样。由于每种方法仅依赖于term，因此您可以简单地使三个函数都接受一个整数。

还有其他一些可以改进的地方：
此：

return int(self.term * (self.term + 1) / 2)

可以

return self.term * (self.term + 1) // 2

枚举到/dev/null
>

您不需要调用枚举-您不需要使用索引。只需使用for terms in hexagonal。

#4 楼

代码如此之慢的主要原因是因为您在main中的for循环会花费大部分时间检查逻辑上不可能成立的事情。每个数字组中都有一百万个元素，在for循环的每次迭代中，您将一个值与其他200万个其他值进行比较，而大多数情况下它们都不是真实的。 br />

尽可能少地更改，并考虑到@Peter Taylor所说的所有sequences are increasing。我能够使程序的运行时间从452.8s到3.2s。

您确实应该考虑其他答案突出显示的内容。这不仅是因为它看起来并不好，而且很难理解。如果在任意"limit"上添加另一个任意0，则可能会很快耗尽内存。您实际上不需要预先计算任何值即可解决问题。

#5 楼

Python是应对此类挑战的理想语言选择，主要是因为使用set很容易。基本上，任何指出“找到一个符合这些条件的数字”的挑战都可以认为是一个相交问题。我们想找到\ $ T \ cap P \ cap H \ $，三角形，五角形和六角形数字的交集。

根据您的Python版本，您可能无法访问“海象运算符”“ :=”。但是，在这种情况下，它非常方便。但是，我们可以滤除非三角形的五边形数，并滤除既不是五角形也不是三角形的六边形数。

通过使用其他答案中给出的优化，它也可以写为：

容易适应多种不同的问题，并提供了很多抽象及其性能。

#6 楼

懒惰是程序员的美德。

这些人在理论上花费的时间比在实践中懒惰的方式花费的时间更多。

这里的主要问题是大量不必要的工作，尤其是在存储方面。

您无缘无故地不断追加到数组。您不需要旧数字的历史记录。把它们丢掉。追加到数组很昂贵-经常必须将整个范围重新分配到一个新数组中，然后从旧数组中复制。

请注意，您可以重新排列它们而不会产生影响。这与“找到前5个同时也是3和6的问题”是相同的问题，因为它们都直接向上移动，这意味着任何一个都将是第一个。

好。您无需跟踪任何内容。迭代其中一列。每问三个，“这是另一个吗？如果是，请问“这也是另外一个吗？”如果是，则返回成功；否则，返回成功。

所以，实际上，您需要一种有效的方法来询问“这是一个foo-angular数字吗？”

通过构建和搜索表格来做到这一点。真傻只需颠倒两个“是否也是”列上的数学运算即可。

几乎所有这些工作都可以进行。

三角形和六角形很容易反转，因此五边形是我会保持原样。

如果三角形是“三角形x是（x *（x + 1））/ 2，”

然后在数学上，您有“ n = x（x + 1）/ 2”。

求解n，得到“ x ^ 2 + x-2n = 0”或“ x =（sqrt（1 + 8n）-1）/ 2”

因此，

const triangle_from = x => (Math.sqrt(1+(x*8))-1)/2;

function is_triangular(x) {
  const pip = triangle_from(x);
  return pip == Math.floor(pip);
}

现在，您实际上可以扔掉它了；欧拉（Euler）在骗你，我在滥用它是为了向您展示如何在不实际为您完成工作的情况下进行工作。因为每个六边形也是三角形。到您测试它是否为六边形时，它已经在袋子中了。您可以这样跳过批发。

您可以保留五角形的现有符号，因为我们使用它来驱动公交车。另外，测试您的他妈的代码。由于第一次在数学和JS之间的运算顺序差异，我弄错了。只需在165上运行它，看看它是否与问题描述相符。

const to_pentagon = x => (x * ((3 * x)-1)) / 2;

然后就只是

function find_triple(cursor = 165, bail = 1000000) { // question says "after 40755," which is pentagonal #165
  while (true) {
    if (from_start >= bail) { throw new RangeException("exceeded safety cap"); }
    const current = to_pentagon(cursor);
    if (is_hexagonal(current)) { return cursor; }  
    ++cursor;
  }
}

如果您感到棘手，则可以写为

function find_triple(cursor = 165, bail = 1000000) { // question says "after 40755," which is pentagonal #165
  while (true) {
    if (from_start >= bail) { throw new RangeException("exceeded safety cap"); }
    if (is_hexagonal(to_pentagon(cursor++))) { return --cursor; }  
  }
}

#7 楼

您可以轻松地检查H（n）= T（2n-1）。因此，所有六角形数字都是三角形数字，这意味着我们可以完全忽略三角形数字。

要计算五边形数，请执行以下操作：从p = 1，dp = 4开始。要获取下一个五边形数，请让p = p + dp，dp = dp +3。

要计算六边形，请执行以下操作：从h = 1开始，dh =5。要获取下一个六边形，请使h = h + dh，dh = dh + 4。查找所有五角形和六边形（因此也就是三角形）的数字的代码：

在几秒钟内达到64位数字。如果想更进一步，请稍稍更改代码：“ diff”等于前一个代码的h-p，但是它会小很多，因此使用64位整数会更进一步。

Let p = 1, dp = 4
Let h = 1, dh = 5

Forever:
    If p = h then output p. 
    Let h = h + dh, dh = dh + 4
    Repeat
        Let p = p + dp, dp = dp + 3
    While p < h

输出相等的五边形和六边形数字的索引。在使用八年的MacBook上，检查每个索引所需的时间不到6纳秒，每分钟检查超过100亿个索引，或者每天检查大约150万亿个索引。 n = 1,042,188,953的Hn也是五边形和三角形。还有另一个这样的Hn，n超过2010亿。 Hn约为8.175 x 10 ^ 22。使用这种方法寻找另一种解决方案可能需要几天或几周的时间。

如果想更进一步，请对整数n求解p（m）= h（n），将m计算为实数。随着n变大，作为n的函数的m将越来越接近线性函数。然后，您可以使用GCD算法快速找到m接近整数的值。您将需要多精度算术，但是它将很快为您提供任意大的解决方案。 （如果P（m）= H（n），则m≈n * sqrt（4/3）-（sqrt（1/12）-1/6），误差小于4 / n ^ 2，因此开始对于某些n，您可以使用GCD算法找到下一个n，其中m = n * sqrt（4/3）-（sqrt（1/12）-1/6）在整数的3.5 / n ^ 2之内。

#8 楼

正如200_success所说，您可以查看如何导出数字以一一生成数字。

因此，与其创建所有数字并检查交叉点，不如通过简单的算法查看五边形和六边形数字。如果它们相等，就完成了。如果五边形数大于六边形数，则检查下一个六边形数是否相等。如果六角形数字较大，则检查下一个五边形数字。

pentagon_index = 165
pentagon_number = 40755+3*165+1

hexagon_index = 143
hexagon_number = 40755+4*143+1

max_tries = 10**6

for i in range(max_tries):
    if pentagon_number < hexagon_number:
        pentagon_index +=1
        pentagon_number += 3*pentagon_index+1
    if pentagon_number > hexagon_number:
        hexagon_index +=1
        hexagon_number += 4*hexagon_index+1
    if pentagon_number == hexagon_number:
        break