例二:解数字谜,找出一个五位数符合以下竖式的条件,输出该五位数和结果的六位数。
问题分析:
法一:枚举法。范围为30000--99999的五位数(因为只有30000以上的数乘以最高位才可能得到六位数),取符合要求的五位数来做乘法,对得到的结果再进行判断看是否满足条件。时间复杂度为99999-30000+1=70000。
法二:构造式的枚举法。构造符合条件的五位数,A取值从3--9,B、C取值从0--9,构造符合后与A相乘,判断其是否满足积的要求,找出所有可能的解。时间复杂度为7*10*10=700,因为是三重循环。
法三:构造式的枚举法——除法。D的取值从1--9,A的取值从3--9,判断D是否可被A整除,整除后将得到的结果即被乘数进行判断,看其最高位是否与A相等且是否符合ABCAB的样式,如果都符合则找到一个解。时间复杂度为7*9=63,因为是二重循环。
代码:
法一代码:
#include <stdlib.h>
#include <stdio.h>
//枚举法
int main()
{
int x,B1,A2,C,B4,A5,D,D0;//定义五位数的每位A5B4CB2A1和六位数D
int D1,D2;
int i;
for(x=30000;x<=99999;x++)//从30000开始遍历五位数,因为从30000开始乘以五位数的最高位A5才有可能得到六位数
{
B1=x%10;//拆五位数的每一位
A2=(x/10)%10;
B4=(x/1000)%10;
A5=x/10000;
if(B1==B4 && A2==A5)//如果满足要求的五位数形式则开始运算
{
D=x*A5;
D0=D;//暂存一下D,对D0进行处理来判断是否符合结果的六位数形式
D1=D0%10;//D1存储六位数的最后一位即个位数
for(i=0;i<5;i++)//拆六位数的每一位,判断其是否都是一样的
{
D2=D1;//D2得到后面的位
D0=D0/10;//D0重新赋值为前面几位
D1=D0%10;//D1再次获得前面几位中的最后一位
if(D1!=D2) //如果相邻两位不一样跳出for循环
break;
}
if(i==5)//如果i=5说明遍历了结果的六位数的每一位,都一样
printf("%d--%d\n",x,D);//输出被乘的五位数和结果的六位数
}
}
}
法二代码:
#include <stdlib.h>
#include <stdio.h>
//枚举式的构造法
int main()
{
int A,B,C,F,D,D0,D1,D2;
int i;
for(A=3;A<10;A++)
{
for(B=0;B<10;B++)
{
for(C=0;C<10;C++)
{
F=A*10000+B*1000+C*100+A*10+B;//构造符合条件的被乘数ABCAB
D=F*A;//得到相乘后的结果
D0=D;//对结果进行判断
D1=D0%10;
for(i=0;i<5;i++)
{
D2=D1;
D0=D0/10;
D1=D0%10;
if(D1!=D2)
break;
}
if(i==5)
printf("%d--%d\n",F,D);
}
}
}
}
法三代码:
#include <stdlib.h>
#include <stdio.h>
//构造式的枚举法--除法
int main()
{
int A,F,D,D0;
for(A=3;A<10;A++)
{
for(D0=1;D0<10;D0++)//D0为D的每一位
{
D=D0*100000+D0*10000+D0*1000+D0*100+D0*10+D0;//构造D
if(D%A==0)
{
F=D/A;//得到被乘数F;
if(F/10000==A && (F/10)%10==A)//判断F是否为ABCBA形式
{
if((F/1000)%10==F%10)
printf("%d--%d\n",F,D);
}
}
}
}
}
运行结果: