我試圖找到“高度復合”的畢達哥拉斯三元組 - 具有多個滿足 a2 b2 = c2 的唯一 a、b（在自然中）的數字（c）。
我撰寫了一個簡短的 python 腳本來找到這些 - 它在 (0,1000) 范圍內回圈 c，并且對于每個 c，找到所有可能的 (a,b)，使得 b < a < c。這是一種更蠻力的方法，我知道如果我讀了一些數論，我可以找到更多針對 a 和 b 不同情況的方法。
我覺得我的腳本效率不是特別高，尤其是對于大型 c。我真的不知道要改變什么或如何提高效率。
我會非常感謝任何幫助或指點！
a = 0
b = 0
l=[]
for i in range (0,1000):
#i is our c.
while a<i:
while b<a:
#for each a, we cycle through b = 1, b = 2, … until b = a.
#Then we make b = 0 and a = a 1, and start the iterative process again.
if a*a b*b == i*i:
l.append(a)
l.append(b)
#I tried adding a break here - my thought process was that we can’t find any
#other b^2 that satisfies a^2 b^2 = i^2 without changing our a^2. This
#actually made the runtime longer, and I don’t know why.
b = b 1
a = a 1
b = 0
if len(l) > 4:
#all our pairs of pythagorean triples, with the c at the end.
print(l, i)
#reset, and find pairs again for i = i 1.
l = []
b = 0
a = 0
uj5u.com熱心網友回復：
您的代碼似乎效率很低，因為您正在執行多次相同的計算。您可以通過不計算無用的東西來提高效率。最重要的細節是 a 和 b 的計算。您正在遍歷 a 和 b 的所有可能值，并檢查它是否是畢達哥拉斯三元組。但是一旦你給自己一個a的值，b就只有一個可能的選擇，所以b回圈就沒用了。
通過洗掉該回圈，您基本上將多項式復雜度降低了一個，這將使其在 c 增長時變得越來越快（與您當前的腳本相比）
此外，您的代碼似乎是錯誤的，因為它錯過了一些三元組。我運行它，發現的第一個三元組是 65 和 85，但 25、50 和 75 也是高度復合的畢達哥拉斯三元組。那是因為您正在檢查len(l)>4，而您應該檢查，len(l)>=4因為您缺少具有兩個分解的數字。
作為比較，我撰寫了一個與您類似的 python 腳本（除了我自己撰寫并試圖使其盡可能高效）。在我的電腦上，你的腳本運行了 66 秒，而我的運行了 4 秒，所以你還有很大的改進空間。
編輯：為了分享，我添加了我的代碼。以下是與您的不同之處的串列：
- 我將從 1 到 N 的所有數字平方存盤在一個名為的串列中，
squares這樣我就可以有效地檢查一個數字是否是一個正方形 - 我將結果存盤在字典中，其中鍵的值
c是對應于的元組串列(a, b) - for 回圈
a從 1 到floor(c/sqrt(2)) - 我沒有回圈 for
b，而是檢查 c2-a2 是否是正方形 - 一般來說，我預先計算了必須多次使用的每個值 (
invsqrt2,csqr)
from math import floor, sqrt
invsqrt2 = 1/sqrt(2)
N=1000
highly_composite_triplets = {}
squares = list(map(lambda x: x**2, range(0,N 1)))
for c in range(2,N 1):
if c%50==0: print(c) # Just to keep track of the thing
csqr = c**2
listpairs = []
for a in range(1,floor(c*invsqrt2) 1):
sqrdiff = csqr-a**2
if sqrdiff in squares:
listpairs.append((a, squares.index(sqrdiff)))
if len(listpairs)>1:
highly_composite_triplets[c] = listpairs
print(highly_composite_triplets)
uj5u.com熱心網友回復：
首先，正如已經提到的，您應該> 4通過>= 4.
為了性能，我建議使用原始畢達哥拉斯三元組樹。它允許生成所有可能的原始三元組，使得給定三元組的三個“孩子”具有至少與“父母”之一一樣大的 c 值。
通過將所有三個值乘以一個系數（直到達到 c 的最大值），可以很容易地從一個原始三元組生成非原始三元組。這必須只對最初的三元組進行，因為其他三元組將隨之而來。
這是獲得最大效率的部分。
然后在第二階段：將這些三元組按其 c 值分組。你可以使用itertools.groupby它。
在第三階段：只選擇至少有 2 個成員（即 4 個值）的組。
這是一個實作：
import itertools
import operator
def pythagorian(end):
# DFS traversal through the pythagorian tree:
def recur(a, b, c):
if c < end:
yield c, max(a, b), min(a, b)
yield from recur( a - 2*b 2*c, 2*a - b 2*c, 2*a - 2*b 3*c)
yield from recur( a 2*b 2*c, 2*a b 2*c, 2*a 2*b 3*c)
yield from recur(-a 2*b 2*c, -2*a b 2*c, -2*a 2*b 3*c)
# Start traversal from basic triplet, and its multiples
for i in range(1, end // 5):
yield from recur(4*i, 3*i, 5*i)
def grouped_pythagorian(end):
# Group by value of c, and flatten the a, b pairs into a list
return [
(c, [a for _, *ab in group for a in ab])
for c, group in itertools.groupby(sorted(pythagorian(end)),
operator.itemgetter(0))
]
def highly_pythagorian(end):
# Select the groups of triples that have at least 2 members (i.e. 4 values)
return [(group, c) for c, group in grouped_pythagorian(end) if len(group) >= 4]
運行函式如下：
for result in highly_pythagorian(1000):
print(*result)
這會在幾分之一秒內產生三元組，并且比您的版本和@Mateo 的答案中的版本快數千倍。
簡化
正如評論中所討論的，我在這里提供了使用相同演算法的代碼，但沒有匯入、串列推導、生成器 ( yield) 和解包運算子 ( *)：
def highly_pythagorian(end):
triples = []
# DFS traversal through the pythagorian tree:
def dfs(a, b, c):
if c < end:
triples.append((c, max(a, b), min(a, b)))
dfs( a - 2*b 2*c, 2*a - b 2*c, 2*a - 2*b 3*c)
dfs( a 2*b 2*c, 2*a b 2*c, 2*a 2*b 3*c)
dfs(-a 2*b 2*c, -2*a b 2*c, -2*a 2*b 3*c)
# Start traversal from basic triplet, and its multiples
for i in range(1, end // 5):
dfs(4*i, 3*i, 5*i)
# Sort the triples by their c-component (first one),
# ...and then their a-component
triples.sort()
# Group the triples in a dict, keyed by c values
groups = {}
for c, a, b in triples:
if not c in groups:
groups[c] = []
groups[c].append(a)
groups[c].append(b)
# Select the groups of triples that have at least 2 members (i.e. 4 values)
results = []
for c, ab_pairs in sorted(groups.items()):
if len(ab_pairs) >= 4:
results.append((ab_pairs, c))
return results
呼叫為：
for ab_pairs, c in highly_pythagorian(1000):
print(ab_pairs, c)
uj5u.com熱心網友回復：
#There is a general formula for pythagoran triples
take 2 numbers, m & n where m > n
a = (m^2) - (n^2)
b = 2mn
c = (m^2) (n^2)
那總是會給你一個畢達哥拉斯三元組。它更有效，但它可能不是您想要的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/447861.html
下一篇：為什么第一個加特林請求較慢？