给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。

本文主要是介绍给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出 n = 12, 返回 3 因为 12 = 4 + 4+ 4。

给出 n = 13, 返回 2 因为 13 = 4 + 9。

/*
*思路：
*1设置n的副本为t
*2.先求出平方数小于t的最大整数数maxSqrt
*3.将maxSqrt*maxSqrt放到二维数组arr[i]，且t-=maxSqrt*maxSqrt
*4.反复进行2~3，直到t为0
*5.设置i+=1
*6.反复进行1~5，直到i>maxSqrt
*7.分析arr，求出平方数的个数最少的情况给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。
给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。
给出 n = 13, 返回 2 因为 13 = 4 + 9。*/
#include<iostream>
#include<math.h>#include<vector>
using namespace std;//求出平方数小于x的最大整数数
int getMaxSqrt(int x)
{float s = sqrt((double)x);int a = floor(s);return a;
}void Test(int n)
{int temp = n;	// sum n = 12vector<int> ar;vector<vector<int>> arr;int maxSqrt = getMaxSqrt(n);int sum = 0;int  j = 0;int MaxSqrt = maxSqrt;for(int i = maxSqrt; i > 0; i--){while(temp > 0){ar.push_back(maxSqrt * maxSqrt);temp -= maxSqrt * maxSqrt;//sum += maxSqrt * maxSqrt;maxSqrt = getMaxSqrt(temp);}//for(vector<int>::iterator iter = ar.begin(); iter != ar.end(); iter++)//	cout<<*iter<<' ';//cout<<endl;arr.push_back(ar);ar.clear();maxSqrt = --MaxSqrt;temp = n;}//计算个数最小的情况int minLen = arr[0].size();int index = 0;for(int i = 0; i < arr.size(); i++){if(arr[i].size() < minLen){minLen = arr[i].size();index = i;}}for(int i = 0; i < arr[index].size(); i++){cout<<arr[index][i]<<' ';}cout<<endl;
}int main()
{Test(12);Test(13);//system("pause");return 0;
}