是这样的，每分一次就计算平方和判断条件，不满足再把和带到函数在分一直到进入第8次函数，还不满足就退到第7次，第7次进行第二次分割，再计算，再进入第8次不满足在退到7次，7次分3次。。。。直到7次的所以可能组合完就退到6次，分6的第二，一直这样往前退，中途记住满足条件的最小次数

#include <stdio.h>
#include <math.h>
int zwz,ci,zh,min; /*zh=转换次数不能大与8,zwz为用户输入数的位置,min最少次数*/
long s[10][2],sz[9][10],ab; /* sz[][]存放被分解开的各个数,s[10][2]存放用户输入的几组数 */
int qws(long a) /* 取a的位数 */
{
int c;
long a2=a;
for(c=0;a2!=0;a2/=10)c++;
return c;
} /* 判断给定数是几位数然后返回n */
int fenjie(long a,int b) /* a=要分的数,b=分成的段数,c=a的长度 */
{
int n,i,j=b,xh,cf=ci,kk; /* j=数组当前位置cf表示进入此函数时要分解的段数 */
long a2; /* kk,n,i,xh都是为了循环计数 */
if(zh>8)return 0;
n=qws(a)-b+1; /* b=当前进入的循环次数,也是数组sz[zh][?]当前位置 */
if(b==0) /* 当把a从长度分割到1个时即分0次时 */
{
if(a<3163) /* 当a值大于3162时,它的平方就大于10000000 */
{
a2=a*a; /* a的平方带入到下个循环 */
if(a2==ab)
{
if(min>zh)min=zh+1;
else return 0;
}
else
if(zh>=min) return 0; /* 如果循环次数大于或等于已知最小步数min则返回 */
else
{
++zh; /* 并给zh增加1 */
zhhuan(a2);
--zh; /* 退出函数后zh再减1 */
}
}
else return 0;
}
else
{
for(i=0;n-i>0;i++) /* 把给定新数value分解成n块存放到数组sz[]中 */
{ /* 当某个值大于3162时,它的平方就大于10000000 */
a2=a%(long)pow10(i);
if(a2!=0 && a2<3163)
sz[zh][j]=a%(long)pow10(i);
else continue; /* 跳过0和平方大于10000000的 */
if(b==1) /* 当循环到达最里层 */
{
if(a!=0)
sz[zh][0]=a/(long)pow10(i);
else sz[zh][0]=a;
a2=0; /* 用来计算各个平方和 */
for(xh=0;xh<cf+1;xh++) /* 每次分解完成后计算各个平方然后相加 */
{ /* 同时判断是不是超出8次,是否超过10000000 */
a2=a2+sz[zh][xh]*sz[zh][xh];
if(a2>10000000) break;
}
if(a2>10000000) continue ; /* 如果超出,到下一个循环 */
else if(a2==ab) /* 相加结果正是且没超过8次 */
{
if(zh<min)
{
/* 屏蔽以下代码可以跳过输出转换过程*/
for(kk=0;kk<=zh;kk++) /* //////////////可以看到转换过程 */
{
printf("\nzh=%d: ",kk);
for(xh=0;sz[kk][xh]!=0;xh++)printf("%ld ",sz[kk][xh]);
} /* //////////////用来观察转换过程 */
printf("a2=%ld,min=%d,zh=%d\n",a2,min,zh);/* ////////// */
/* 屏蔽以上代码可以跳过输出转换过程*/
min=zh; /* 准备返回到调用此函数处 */
}
}
else if(a2<10000000 && zh<min)
{
++zh; /* 准备分解新合成的数 */
zhhuan(a2);
--zh;
}
}
else
{
fenjie(a/(long)pow10(i),b-1);
}
}
}
return 0;
}
zhhuan(long a)
{
int ch,n;
if(zh>8)return;
ch=qws(a); /* ch=取a的长度 */
while(ch>0)
{
if(ch==1 && a<3163)sz[zh][0]=a;
sz[zh][ch]=0; /* 没分之前给后一个位置0方便以后逐个输出 */
ci=--ch; /* 分解次数,a的位数 */
fenjie(a,ch); /* ch表示把a分几次 */
}
return ;
}
main()
{
int i,j=0;
for(i=0;i<2;i++) /* 先测试两组，全部通过再改 */
scanf("%ld%ld",&s[i][0],&s[i][1]);
while(j<i)
{
zh=0; /* 转换次数清0 */
min=10; /* min=10重新找步数少的方法 */
ab=s[j][1];
zhhuan(s[j][0]); /* zwz=正在处理的那一组的位置 */
++j;
printf("%d , %d\nNext:%ld %ld\npress any key to continue!\n",j,min>8?min=-1:min,s[j][0],s[j][1]);
getch();
if(j>=i)break;
zwz=j;
}
getch();
}
把原来需要得到的数变量换成了ab，增加了变量j替换zwz控制循环和s[][]下标