数据结构
网络
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 次观看
广告