小明与小红的故事:http://acm.hit.edu.cn/ojs/show.php?Proid=100082&Contestid=11
我的思路是这样的：一个小10位的n位数，可以这样分割，分割0次即保留全部；分割1次为两段有n-1种组合；分割2次有n-2种组合；分割3次有n-3种组合、、、每分成一种组合就对行成的组合分别平方然后相加成新的数判断是否等于给定的数，不等的话再重新开始分割直到第8次、、、、具体代码：
#include <stdio.h>
#include <math.h>
int zwz,ci,zh,min; //zh=转换次数不能大与8,zwz为用户输入数的位置,min最少次数
long s[10][2],sz[9][10]; //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==s[zwz][1])
{
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;
// printf(" cf=%d,zh=%d\n",cf,zh);
a2=0; //用来计算各个平方和
for(xh=0;xh<cf+1;xh++) //每次分解完成后计算各个平方然后相加
{ //同时判断是不是超出8次,是否超过10000000
// printf("%ld ",sz[zh][xh]);
a2=a2+sz[zh][xh]*sz[zh][xh];
if(a2>10000000) break;
}
// getch();
if(a2>10000000) continue ; //如果超出,到下一个循环
else if(a2==s[zwz][1])//相加结果正是且没超过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; //准备返回到调用此函数处
}
return 0;
}
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;
for(i=0;i<2;i++) //先测试两组，全部通过再改
scanf("%ld%ld",&s[i][0],&s[i][1]);
while(zwz<i)
{
zh=0; //转换次数清0
min=10; //min=10重新找步数少的方法
zhhuan(s[zwz][0]); //zwz=正在处理的那一组的位置
zwz+=1;
printf("%d , %d\nNext:%ld %ld\npress any key to continue!",zwz,min>8?min=-1:min,s[zwz][0],s[zwz][1]);
getch();
}
getch();
}
不知道怎么回事，能依次分解第二组第一个数但是判断的还是第一组的第二个数，而且while循环也退不出来，代码本来就很乱，变量也多，找错误的时间比写出代码的时间都长，找的头疼的很，希望交流指点下
