資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚學
法律研究n 的最小平方數之和\n
任意數字均可用一些完全平方數之和表示。本問題中，我們需要找出表示給定值所需的最小完平方項數。
令此值為 94，因此 95 = 92 + 32 + 22 + 12。因此，答案為 4
其思路是，從 1 開始，我們進一步獲得完全平方數。當值為 1 至 3 時，它們必須僅由 1 構成。
輸入和輸出
Input: An integer number. Say 63. Output: Number of squared terms. Here the answer is 4. 63 =72 + 32 + 22 + 1
演算法
minSquareTerms(value)
輸入：給定值。
輸出：達到給定值的最小平方項數。
Begin define array sqList of size value + 1 sqList[0] := 0, sqList[1] := 1, sqList[2] := 2, sqList[3] := 3 for i in range 4 to n, do sqList[i] := i for x := 1 to i, do temp := x^2 if temp > i, then break the loop else sqList[i] := minimum of sqList[i] and (1+sqList[i-temp]) done done return sqList[n] End
示例
#include<bits/stdc++.h>
using namespace std;
int min(int x, int y) {
return (x < y)? x: y;
}
int minSquareTerms(int n) {
int *squareList = new int[n+1];
//for 0 to 3, there are all 1^2 needed to represent
squareList[0] = 0;
squareList[1] = 1;
squareList[2] = 2;
squareList[3] = 3;
for (int i = 4; i <= n; i++) {
squareList[i] = i; //initially store the maximum value as i
for (int x = 1; x <= i; x++) {
int temp = x*x; //find a square term, lower than the number i
if (temp > i)
break;
else squareList[i] = min(squareList[i], 1+squareList[itemp]);
}
}
return squareList[n];
}
int main() {
int n;
cout << "Enter a number: "; cin >> n;
cout << "Minimum Squared Term needed: " << minSquareTerms(n);
return 0;
}輸出
Enter a number: 63 Minimum Squared Term needed: 4
已更新： 17-6 月-2020
448 次觀看
廣告