我知道如何使用蠻力方法檢查數字是否可以表示為兩個平方的和。
def sumSquare( n) :
i = 1
while i * i <= n :
j = 1
while(j * j <= n) :
if (i * i j * j == n) :
print(i, "^2 ", j , "^2" )
return True
j = j 1
i = i 1
return False
但是如何為 n 個不同的正整數做到這一點。所以問題是：
檢查數字是否可以寫為“n”個不同平方和的函式
我有一些例子。
例如
- is_sum_of_squares(18, 2) 將是錯誤的，因為 18 可以寫成兩個平方的和 (3^2 3^2) 但它們并不不同。
- (38,3) 是正確的，因為 5^2 3^2 2^2 = 38 和 5!=3!=2。
我無法if為更多值擴展條件。我認為可以通過遞回來完成，但是我遇到了問題。
我發現這個函式非常有用，因為它可以找到數字可以分成的平方數。
def findMinSquares(n):
T = [0] * (n 1)
for i in range(n 1):
T[i] = i
j = 1
while j * j <= i:
T[i] = min(T[i], 1 T[i - j * j])
j = 1
return T[n]
但是我又不能用遞回來做到這一點。可悲的是，我無法將頭環繞在它周圍。我們幾周前開始學習它（我在高中），它與迭代方法非常不同。
uj5u.com熱心網友回復：
遞回方法：
def is_sum_of_squares(x, n, used=None):
x_sqrt = int(x**0.5)
if n == 1:
if x and x_sqrt**2 == x and x_sqrt not in used:
return [x_sqrt]
return None
used = used or set()
for i in set(range(max([1, *used]), x_sqrt 1)).difference(used):
squares = is_sum_of_squares(x-i**2, n-1, used.union([i]))
if squares:
return squares [i]
return None
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/357740.html
上一篇：C中的計數排序-不完全排序
下一篇：3皇后問題有通用的公式嗎？