藍(lán)橋杯 四平方和 JAVA

暴力但是剪枝+注意組合數(shù)

因?yàn)槭墙M合情況，所以從下一層的for應(yīng)要從上一層的起始開(kāi)始。

　　四平方和定理，又稱為拉格朗日定理：

　　每個(gè)正整數(shù)都可以表示為至多4個(gè)正整數(shù)的平方和。
　　如果把0包括進(jìn)去，就正好可以表示為4個(gè)數(shù)的平方和。

for(int i=0;i<=n;i++) {? //注意數(shù)據(jù)范圍，每個(gè)數(shù)值一定會(huì)小于N的開(kāi)根號(hào)。

? ? for(int j=i;j<=n;j++) { //注意 從i開(kāi)始

? ? ???? for(int k=j;k<=n;k++) {

? ????????? for(int m=k;m<=n;m++) {

? ????????????? int cur = i*i+j*j+k*k+m*m;

????????????? ? if(cur>N) break; //剪枝，不然過(guò)不了

????????????????? ? if(cur==N) {

? ????????????????????????? System.out.println(i+" "+j+" "+k+" "+m);

? ????????????? ???????? return ;

? ????????????????????? }

? ????????????? }

? ????????? }

? ????? }

? ? }