我有一個演算法問題：我們如何確定一個數字是否等于一些不同平方數的總和？例如：50 = 4*4 5*5 3*3
而且，如果是真的，我怎樣才能找到我們可以寫成幾個不同平方和的狀態數？
25 = 5^2 0 或 3^2 4^2 它有 2 個狀態。
我對 2 個數字沒問題，我知道我們可以用遞回解決它。
這是我在java中的2個數字代碼：
import java.util.Scanner;
public class SemiCharismatic {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = input.nextInt();
input.close();
if (isSquare(number) == true) {
System.out.print("YES");
System.exit(0);
} else {
for (int i = 1; i < number; i ) {
int j = number - i;
if (isSquare(i) == true && isSquare(j) == true) {
System.out.print("YES");
System.exit(0);
}
}
System.out.print("NO");
}
}
static boolean isSquare(int number) {
boolean result = false;
if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) {
result = true;
}
return result;
}
}
uj5u.com熱心網友回復：
這可以看作是硬幣交換問題（見這里）。
解決硬幣交換問題的一種方法是遞回，正如另一個答案所建議的：
def is_sum_squared_rec(number, candidates=None, idx=None):
if candidates is None:
candidates = np.arange(1, int(np.floor(np.sqrt(number))) 1) ** 2
idx = len(candidates) - 1
if (number > 0 and idx == -1) or number < 0:
return False
if number == 0:
return True
return is_sum_squared_rec(number, candidates, idx-1) or is_sum_squared_rec(number-candidates[idx], candidates, idx-1)
但是在這種情況下實作硬幣交換問題的另一種非遞回方法如下：
def is_sum_squared(number):
counts = [1] [0] * number
candidates = np.arange(1, int(np.floor(np.sqrt(number))) 1) ** 2
for candidate in candidates:
for jj in range(number, candidate-1, -1):
counts[jj] = counts[jj - candidate]
return counts[number] > 0
這種方法避免了執行冗余計算并且應該比遞回方法更快。
非遞回方法可以進一步改進，因為我們不想要整個計數，只要它可以分解為候選的總和。因此我們可以引入一個提前停止條件：
def is_sum_squared_early_stop(number):
counts = [1] [0] * number
candidates = np.arange(1, int(np.floor(np.sqrt(number))) 1) ** 2
for candidate in candidates:
for jj in range(number, candidate-1, -1):
counts[jj] = counts[jj - candidate]
if counts[number] > 0:
return True
return counts[number] > 0
非遞回演算法的運行時間是 O(n*sqrt(n))，而 scape 要求是 O(n)。
定時
對于number = 400，時間產生以下結果：
%timeit is_sum_squared_rec(400)
1.88 ms ± 177 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared(400)
1.05 ms ± 76.8 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared_early_stop(400)
796 μs ± 127 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
幾乎提高了 3 倍。當我們檢查時，number=3000我們得到：
%timeit is_sum_squared_rec(3000)
1.81 s ± 152 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit is_sum_squared(3000)
24.5 ms ± 581 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit is_sum_squared_early_stop(3000)
14.3 ms ± 556 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
而且我們有超過2個數量級的差異
uj5u.com熱心網友回復：
這個問題是子集和問題的一個變種。
在這里，您必須創建自己的一組（如下所述），并且您的數字是問題的目標總和。
要創建一個集合，請形成一個數字陣列[square of numbers from {1 to sqrt(n)}]
所以你的陣列看起來像：[1,4,9... sqrt(n)^2]
解釋為什么 sqrt(n)： 任何大于 sqrt(n) 的數的平方也將大于 n。因此，添加更多內容不會導致解決方案。
然后應用子集集演算法，如此處所述
isSubsetSum(set, n, sum)
= isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/455057.html