代码之家 › 专栏 › 技术社区 › rustyshackleford

python中不使用范围的高效迭代

math for-loop python

rustyshackleford · 技术社区 · 7 年前

我正在处理的问题45 Project Euler 是的。提示如下:

三角形、五边形和六边形数字由以下公式生成:

T型 _n个 = n个 ( n个 +1)/2个

第页 _n个 = n个 (三) n个 –1)/2个

小时 _n个 = n个 (二) n个 1)

可以证明 _{二百八十五} =P _{一百六十五} =小时 ₁₄₃ =40755个。

找到下一个也是五边形和六边形的三角形数。

我确实有一个有效的解决方案,但是我在提供一个不依赖于使用任意值 range 是的。

我的当前代码:

import collections
import time
start_time = time.time()

nums = []

for x in range(56000):
    t, p, h = (x * (x + 1) / 2) , x * (((3 * x) - 1) / 2), (x * ((2 * x) - 1))
    nums.extend([t, p, h])

j = [i for i, count in collections.Counter(nums).items() if count > 2]
pos = j.index(40755)
result = j[pos + 1]
print result
print("--- %s seconds ---" % (time.time() - start_time))

输出:

1533776805

---0.197566986084秒---

如果不使用 范围 ?我希望得到相同的输出,但不指定迭代次数。我试着用 itertools.count ,但搜索 nums 与上述条件匹配的值的列表花费太长时间。

提前谢谢。

1 回复 | 直到 7 年前

Rory Daulton 7 年前

一个更好的方法是循环遍历所有六边形数的索引,然后看到这些数也是五边形数。(正如@mbo在评论中告诉我的,所有的六边形数字也是三角形数字,所以我们可以跳过这个检查。)没有必要尝试任何更高的六边形数字。这是我解决这个问题的代码,它使用 while 没有任何循环 range 是的。问你是否需要更多的解释,从三角形或五边形的数字计算索引的公式。

"""Project Euler #0045 Triangular, pentagonal, and hexagonal

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.

ANSWER: T(55385) = P(31977) = H(27693) = 1533776805
"""
from math import sqrt

_1_50 = 1 << 50  # 2**50 == 1,125,899,906,842,624
known_answer_hexagonal = 143

n_hex = known_answer_hexagonal
x = 1
while x <= _1_50:
    n_hex += 1
    x = n_hex * (2 * n_hex - 1)  # we know this is hexagonal

    sqrt_pen = sqrt(1 + 24 * x)
    if not sqrt_pen.is_integer():
        continue
    n_pen = (sqrt_pen + 1) / 6
    if not n_pen.is_integer():
        continue
    sqrt_tri = sqrt(1 + 8 * x)  # all hexagonal numbers are also triangular
    n_tri = (sqrt_tri - 1) / 2

    print('T({}) = P({}) = H({}) = {}'.format(
            int(n_tri), int(n_pen), int(n_hex), int(x)))
    break

在我的系统里,这个 0.026999950408935547 几秒钟,而你的代码 0.12299680709838867 比我的代码长4倍多的秒。

推荐文章

Google User · Django管理员在`list_display中未显示`creation_date`字段`

9 月前

user29747013 · 如何创建一个新的数据框架,其中包含原始数据框架中列的聚合列?

9 月前

ÎÎÎ½Î· ÎÎ®Î¹Î½Î¿Ï · Python lxml.html语法错误:使用lxml find时XPATH的谓词无效

9 月前

user29715306 · from_users=和chats=电视节目中的差异

9 月前

Redshoe · 当执行numpy.genfromtxt()时,python是否会读取文件的所有行?

9 月前

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

9 月前

prayner · 更新嵌套字典包含列表中的项

10 月前

Bringo Jr · 我可以在O(n)中解决这个问题吗?

10 月前

Dave · 如何在for循环中修改列表值

10 月前

Shukurullox Komiljonov · 从记录中获得相互和解。使用SQL

10 月前