写点思路 备忘

用递归

2L写思路，3L上代码。

递归函数f(int sum,int start)。num是当前数字，起始时为正整数m。start起始时为0。

写一个for循环，从start+1开始循环到sqrt(num).判断f(num-i*i,i)是否符合条件

num==0，表明这些不同数字的平方和正好等于num，return true

num<0,表明这些不同数字的平方和已经超出了num，return false

实际代码中for循环应放在两个if判断后面

别忘了最后return false（i循环到sqrt(num)时，num如果仍然大于0，以上条件均不满足）

为什么i循环到sqrt(num)?互不相同整数的平方和，不相同整数最多时，满足i*(i+1)*(2*i+1)/6=m即可（平方和公式）

不相同整数最少时（1个），就是sqrt(num)。这个数字是满足把m表示成互不相同整数的平方和的最大整数。

int f(int num, int start)

{

if (num < 0)return false;//num小于0，平方和已超出num

if (num == 0)return true;//num等于0，平方和正好等于num

for (int i = start + 1; i <= sqrt(num); i++)//从start+1开始循环，循环到sqrt(num)

{

if (f(num - i * i, i))return true;//当发现一种情况满足条件时，返回true，不再循环。

}

return false;

}

原文已经迁移至这里啦～今后将不在讨论版更新。