python - 我如何解决这个十亿迭代和？欧拉计划问题 94，Python

问题描述

问题——问题 94，欧拉计划——Python——几乎等边三角形

*很容易证明，不存在边长整面积、面积整的等边三角形。然而，几乎等边三角形 5-5-6 的面积为 12 个正方形单位。

我们将把一个几乎等边三角形定义为两个边相等且第三条边相差不超过一个单位的三角形。

求所有边长和面积为整数且周长不超过十亿 (1,000,000,000) 的几乎等边三角形的周长之和。*

输出：518408346

我有一个非常低效的解决方案，如下所示：

我尝试暴力破解（花费了相当长的时间）（使用 for 循环）
然后我在条件中添加检查它是否是三角形（两条边之和大于第三条）
接下来，我在周长变量中定义了值，并为面积变量使用了简单的几何图形
接下来，为了检查它们是否有效，对于周长，我使用了一种类型方法来检查它是否是 int 并且因为我不能对 area 做同样的事情（因为即使它是一个整数，它也将是 float 的一部分类），我使用模 1 == 0 来检查它是否是整数
如果它满足条件，我将它添加到我的最终“周长总和”变量中。

代码如下：

import time
start = time.time()
plst = 0
o = 100000
for i in range(1,o):
    j = i+1
    if 2*i > j and j > 0:
        p = 2*i + j
        a = 0.5 * j* ((i**2 - (j/2)**2)**0.5)
        # if p > 100:
        #     break
        # else:
        #     pass
        if type(p) == int and a % 1 == 0:
            print(i)
            print('\t', p)
            plst += p
        else:
            pass
    else:
        pass
for k in range(1,o):
    b = k-1
    if 2*k > b and b > 0:
        p = 2*k + b
        a = 0.5 * b* ((k**2 - (b/2)**2)**0.5)
        # if p > 100:
        #     break
        # else:
        #     pass
        if type(p) == int and a % 1 == 0:
            print(k)
            print('\t', p)
            plst += p
        else:
            pass
    else:
        pass
print(plst)
print(f'{time.time() - start} seconds')

笔记：

是的，我知道我的 o 值是 100000。
是的，我注释掉了检查周长变量是否超过十亿的条件，因为我在达到十亿之前遇到了问题。
不要介意注释代码。 我有两个问题需要帮助 按优先顺序排列
当我运行代码时，直到 10000，它运行良好且快速，但是当我跳到 100000 时，我意识到输出中弹出了一些不必要的值。（如 93686、93686、93687）

答：我认为这是不必要的，因为当我搜索这个时，一个网站显示了一个最终会产生答案的值表，而 93686 不是其中的一部分。（这是网站，https://blog.dreamshire。 com/project-euler-94-solution/）

B. 但是我在我的程序中找不到错误，我尝试了这些“不必要”数字的面积，令人惊讶的是，面积竟然是一个整数，这让我感到惊讶，这导致我得到了错误的答案

那么有人可以解释错误是什么吗？

2. 有人可以给我一个有效的解决方案，并用 Python 进行适当的解释吗？

我使用 python 3.8

标签： pythonpython-3.x

解决方案

您完全可以在不使用平方根的情况下获得结果。事实上，它可以只使用加法和乘法来获得：

如果我们将一个几乎等边三角形定义为 (a,a,c)，则 c 为 a+1 或 a-1。(a,a,c) 三角形的高度可以使用由底边 (c/2) 的一半构成的直角三角形作为斜边来计算a。

                                               Pythagorean
                        /|\                |\  Triangle  
                       / | \               | \   
 c = a +/- 1        a /  |  \ a            |  \ a 
                     /  h|   \           h |   \  
                    /    |    \            |    \
                   /_____|_____\           |_____\
                         c                   c/2
                     c/2   c/2

为此，要产生一个整数曲面，h并且c/2必须是整数，并且 (h,c/2,a) 必须是毕达哥拉斯三元组。

基于此，我们可以遍历可能的（偶数）值，同时依次c推进相应的值。h随着c增加，h这将允许我们简单地将 h^2 与 a^2 - (c/2)^2 匹配以检测毕达哥拉斯三元组。

def almostEqui(maxPerimeter):
    h = 1
    for c in range(2,maxPerimeter//3+2,2):
        cc4 = c*c//4
        for a in (c-1,c+1):
            hh = a*a - cc4
            while h*h < hh:
                h += 1
            if h*h == hh and 2*a+c <= maxPerimeter:
                yield a,a,c
        h -= 1 

def euler94():
    return sum(a+b+c for a,b,c in almostEqui(1000000000))

euler94() 函数在我的笔记本电脑上在 2.21 分钟（133 秒）内返回 518408346。这比计算平方根大约快 2.5 倍。

[编辑]一种更快的方法是生成毕达哥拉斯原始三元组，并检查它们在加倍时是否形成几乎等边三角形：

这是一个基于 Euclid 的原始毕达哥拉斯三元组互素公式的生成器函数：

from math import gcd
def genTriples(k): # primitive pythagorean triangles a,b,c where a<b<c<k
    n,m = 1,2
    while m*m+1<k:                  # while c<k (for largest m producing c)
        if n>=m: n,m = m%2,m+1      # n reached m, advance m, reset n
        c = m*m+n*n                 # compute c 
        if c >= k: n=m;continue     # skip remaining n when c >= k
        if gcd(n,m) == 1:           # trigger on coprimes
            yield m*m-n*n,2*m*n,c   # return a,b,c triple
        n += 2                      # advance n, odd with evens

输出：

from time import time
start=time()

N = 1000000000
result = 0
for a,b,c in genTriples(N//3+2):
    if abs(2*a-c)==1:               # (c,c,2*a) almost equilateral triangle
        result += 2*a+2*c
    if abs(2*b-c)==1:               # (c,c,2*b) almost equilateral triangle
        result += 2*b+2*c

print(time()-start)  # 51 seconds
print(result)        # 518408346

这比以前的方法快 2 倍以上。

python - 我如何解决这个十亿迭代和？欧拉计划问题 94，Python

问题描述

解决方案

推荐阅读