Algorithm: perfect square

23 Oct 2018

给一个正整数 n，写一个函数找到若干个完全平方数（比如 1，4，9，…）使得他们的和等于 n。要求为你需要让平方数的个数最少，输出需要的最少的平方数的个数。
格式：
输入每一行输入一个 整数 n，输出每一行输出需要最少的平方数的个数。

样例输入
n = 12
n = 13
样例输出
3
//12 = 4 + 4 + 4
2
//13 = 4 + 9

解:

#include <iostream>
#include <cmath>
using namespace std;

int perfect_square(int number);
int main(){
        cout<<perfect_square(10)<<endl;
        return 0;
}
int perfect_square(int number){
        int result=-1;
        int start=floor(sqrt(number));
        cout<<"start:"<<start<<endl;
        if((int)pow(start,2)==number){
            return 1;
        }
        return 1+perfect_square(number-pow(start,2));
}