数据结构
网络
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
更新日期: 2020 年 6 月 17 日
449 次浏览
广告