int flag;
for(i=0;i<=4;++i) /*被乘数的第一位*/ for(j=5;j<=9;++j) /*被乘数的第二位*/ for(k=0;k<=4;++k) /*被乘数的第三位*/ {
term=100*i+10*j+k; /*被乘数*/
for(flag=0,n=0;n<4&&!flag;) /*乘数的第一位*/
flag=jud((t3=++n*100*term)/100,\判断第三个部分积*/ if(flag) {
for(flag=0,m=0;m<4&&!flag;) /*乘数的第二位*/ flag=jud((t2=++m*10*term)/10,\判断第二个相同时，返回1*/ return 1; else return 0; }
*运行结果 3 7 2 × 2 4 6 ———- 2 2 3 2 1 4 8 8 7 4 4 ———— 部分积*/ if(flag) {
for(flag=0,l=5;l<9&&!flag;) /*乘数的第三位*/
flag=jud(t1=++l*term,\判断第一个部分积*/ if(flag&&jud(t1+t2+t3,\判断乘式的积*/ print(term,n*100+m*10+l,t1,t2,t3); } } } }
void print(long a,long b,long s1,long s2,long s3) /*打印结果*/ {
printf(\printf(\printf(\\\n\
printf(\printf(\\\n\printf(\}
int jud(long q,char *pflag) /*判断一个数的每一位是否满足要求的判断函数*/
/*q:需要判断的数。pflag:标志字符串，A用1表示，Z用0表示。标志串排列顺序：个十百…*/ {
while(q!=0&&*pflag!=NULL) /*循环判断对应位的取值范围是否正确*/
if(*pflag-'0'!=(q>=5?1:0)) /*标志位与对应的位不符，返回0*/ return 0; else {
q/=10;++pflag; /*若相符则取下一位进行判断*/ }
if(q==0&&*pflag==NULL) /*q的位数与标志字符串的长度
9 1 5 1 2 *思考题
E代表数字0到9中的偶数数字，O代表奇数数字，请还原下列乘式。 E E O 2 8 5 × O O 答案 × 3 9 ———– ———– E O E O 2 5 6 5 E O O 8 5 5 ———– ———– O O O O O 1 1 1 1 5 65.乘式还原(2) 有乘法算式如下： ○○○ × ○○ ———— ○○○○ ○○○○ ———— ○○○○○
18个○的位置上全部是素数(1、3、5或7)，请还原此算式。 *问题分析与算法设计
问题中虽然有18数位，但只要确定乘数和被乘数后经过计算就可确定其它的数位。
乘数和被乘数共有5个数位，要求每个数都是质数。完全可以采用穷举的方法对乘数和被乘数进行穷举，经过判断后找出答案。但是这种方法给人的感觉是―太笨了‖，因为组成的数字只是质数(4个)，完全没有必要在那么大的范围内进行穷举，只需要试探每一位数字为质数时的情况即可。
采用五重循环的方法实现对于5个数字的穷举，前面的许多例题中都已见过。循环实现简单易行，但嵌套的层次太多，需要穷举的变量的数量直接影响到循环嵌套的层数，这种简单的实现方法缺少技巧性。本例的程序中给出了另外一种同样功能的算法，该
- 36 -
算法的实现思想请阅读程序。
程序中并没有直接对质数进行穷举，而是将每个质数与1到4顺序一一对应，在穷举时为处理简单仅对1到4进行穷举处理，待要判断产生的乘积是否满足条件时再利用一个数组完成向对应质数的转换。请体会程序中的处理方法。程序中使用的算法实际上是回朔法。 *程序说明与注释 #include
#define NUM 5 /*需要穷举的变量数目*/ #define C_NUM 4 /*每个变量的值的变化范围*/ int a[NUM+1]; /*为需要穷举的变量开辟的数组*/
/*a[1]:被乘数的百位，a[2]：十位,aa[3]:个位 a[4]:被乘数的十位 a[5]:个位*/
/*判断乘式的积是否满足题目条件*/ {
printf(\若满足题意，则打印结果*/ printf(\printf(\\\n\printf(\printf(\printf(\\\n\printf(\}
i=NUM; /*为穷举下一个可能取值作准备*/ } } int b[]={0,2,3,5,7}; /*存放质数数字的数组，不使用第0号元素*/
int f(long sum); int main() {
int i,not_finish=1;
i=2; /*i:将要进行处理的元素的指针下标。设置初始值*/ a[1]=1; /*为第1号元素设置初始值*/
while(not_finish) /*not_finish:程序运行没结束标记*/ {
while(not_finish&&i<=NUM)
/*处理包括第i个元素在内的后续元素，找出当前条件下的一种各个变量的一种可能的取值方法*/
if(a[i]>=C_NUM) /*当要处理的元素取超过规定的C_NUM时*/
if(i==1&&a[1]==C_NUM)
not_finish=0; /*若1号元素已经到C_NUM，则处理全部结束*/
else a[i–]=0; /*将要处理的元素置0，下标-1(回退一个元素)*/
else a[i++]++; /*当前元素值加1后下标指针加1*/ if(not_finish) {
long int sum1,sum2,sum3,sum4; /*定义临时变量*/ sum1=b[a[1>*100+b[a[2>*10+b[a[3>; /*计算被乘数*/
/*利用数组的下标与质数的对应关系完成序号1到4向质数的转换*/
sum2=sum1*b[a[5>; /*计算乘数个位与被乘数的部分积*/ sum3=sum1*b[a[4>; /*计算乘数十位与被乘数的部分积*/ if(sum2>=2222&&sum2<=7777&&f(sum2)&&sum3>=2222&&sum3<=7777&&f(sum3)) /*判断两部分积是否满足题目条件*/
if((sum4=sum2+sum3*10)>=22222&&sum4<=77777&&f(sum4))
}
int f(long sum) /*判断sum的每一位数字是否是质数，若不是返回0，若是返回1*/ {
int i,k,flag; /*flag=1:数字是质数的标记*/ while(sum>0) {
i=sum; /*取个位的数字*/
for(flag=0,k=1;!flag&&k<=C_NUM;k++) if(b[k]==i) {
flag=1;break; }
if(!flag) return 0; else sum=sum/10; } return 1; }
*运行结果 7 7 5 × 3 3 ———- 2 3 2 5 2 3 2 5 ———– 2 5 5 7 5 *思考题
以下乘式中，A、B、C代表一确定的数字，○代表任意数字，请复原。 A B C 2 8 6 × B A C × 8 2 6
————- 答案： ———— ○○○○ 1 7 1 6 ○○A 5 7 2
- 37 -
○○○B 2 2 8 8 ————- —————- ○○○○○○ 2 3 6 2 3 6 66.除式还原(1)
给定下列除式，其中包含5个7，其它打×的是任意数字，请加以还原。
× 7 × ————–商 ————–
除数——××| ×××××————-被除数 ×7 7 ————– × 7 × /*商的第一位与除数的积的后两位为77*/ printf(\}
*运行结果
51463/53=971。 可以看作为下列算式： 9 7 1 ————- 5 3| 5 1 4 6 3 4 7 7 ————- 3 7 6 × 7 × ———- × × × × ———- ○
*问题分析与算法设计
首先分析题目，由除式本身尽可能多地推出已知条件。由除式本身书已知：
1、被除数的范围是10000到99999，除数的范围是10到99，且可以整除；
2、商为100到999之间，且十位数字为7； 3、商的第一位与除数的积为三位数，且后两位为77； 4、被除数的第三位一定为4；
5、 7乘以除数的积为一个三位数，且第二位为7； 6、商的最后一位不能为0，且与除数的积为一个二位数。 由已知条件就可以采用穷举的方法找出结果。 *程序说明与注释 #include
long int i; int j,l;
for(i=10000;i<=99999;i++) /*1. i:被除数*/
if(i00-i0==400) /*4. 被除数的第三位一定为4*/ for(j=10;j<=99;j++) /*1. j: 余数*/
if(i%j==0&&(l=i/j)0>=70&&l0<80&&l!=0&&l>100&&l<=999)
/*1. 可以整除&& 2.商l在100到999之间且十位数字为7&&6.商的个数不能为0*/
if((j*(l))<100&&j*(l)>10) /*6. 商的个数与除数的积为二位数*/
if(j*70>=70&&j*70<80) /*5. 7乘以除数的积的第二位为7*/
if(j*(l/100)0==77&&j*(l/100)>100)
3 7 1 ———– 5 3 5 3 ———– ○
*问题的进一步讨论
在推出的已知条件中，几所有的条件都是十分明显的，换句话说，
推出的已知条件就是对题目的平铺直叙。这种推已知条件的方法十分简单，并且行之有效。 *思考题
下列除式中仅给定了一个8，其它打×的位置上是任意数字，请还原。
× 8 × —————-商 —————-
除数——-×××| ××××××—————被除数 ×××× ————— ××× ××× ————— ×××× ×××× ————— ○
67.除式还原(2)
下列除式中仅在商中给定了一个7，其它打×的位置全部是任意数字，请还原。 ×7××× ————-商 ——————
除数 ——————-×××| ×××××××× ————-被除数 ×××× ————-1)
- 38 -
————— ××× ————-2) ××× ————-3) —————
×××× ————-4) ××× ————-5) —————– ×××× ————-6) ×××× ————-7) —————– 0
*问题分析与算法设计
这道题是不可能用单纯的穷举法求解的，一则计算时间太长，二for(b=112;b<=142;b++) for(c[0]=8;c[0]<=9;c[0]++)
if(b*c[0]>1000&&(d[0]=a[0]-b*c[0])>=10&&d[0]<100)
for(a[1]=0;a[1]<=9;a[1]++)
if((d[1]=d[0]*10+a[1]-b*7)>=100&&d[1] if(b*c[1]<1000&&(d[2]=d[1]*10+a[2]-b*c[1])>=10&&d[2]<100) for(a[3]=0;a[3]<=99;a[3]++) for(c[2]=8;c[2]<=9;c[2]++) if(d[2]*100+a[3]-b*c[2]==0) 则难于求出除式中各部分的值。 对除式进行分析，改可能多地推出限制条件： 由3)可以看出，商的第二位7乘除数得一个三位数，所以除数<=142。 由除数乘商的第一位为一个四位数可知，商的第一位只能为8或9且除数>=112。同时商的第五位也为8或9数的前四位一定<=142*9+99且>=1000+10。 由4)、5)、6)可以看出，4)的前两位一定为―10‖；5)的第一位一定为―9‖；6)的前两位一定在10到99之间；商的第四位一定为为0。 由 5)的第一位一定是―9‖和―112‖<=除数<=142可知：商的第三位可能为7或8。 由除式本身可知：商的第四位为0。 由 1)可知：除数X商的第一位应当为一个四位数。 由 5)可知：除数X商的第三位应当为一个三位数。 编程时为了方便，将被除数分解：前四位用a[0]表示，第五位用a[1]，第六位用a[2]，第七八两位用a[3];除数用变量b表示；分解商：第一位用c[0]，第五位用c[2];其它的部分商分别表示为：2)的前两位为d[0]，4)的前三位为d[1]，6)的前二位为d[2]。将上述分析用数学的方法综合起来可以表示为： 被除数： 1010<=a[0]<=1377 0<=a[1]<=9 0<=a[2]<=9 0<=a[3]<=99 除数： 112<=b <=142 商： 8<=c[0]<=9 7<=c[1]<=8 8<=c[2]<=9 2)的前两位： 10<=d[0]<=99 4)的前三位： 100<=d[1]1000 5)式部分积： 100 int a[4],b,c[3],d[4],i=1; for(a[0]=1010;a[0]<=1377;a[0]++) { printf(\ printf(\); printf(\ printf(\} } *运行结果： No 1:12128316/124=97809 *思考题 下列除式中―×‖所在的位置全部是任意数字，请还原。 ××××× ——————- ××× | ×××××××× ×××× —————— ×××× ××× ————— ××× ××× ———– ×××× ×××× ———– 0 68.九位累进可除数 求九位累进可除数。所谓九位累进可除数就是这样一个数：这个数用到1到9这九个数字组成，每个数字刚好只出现一次。这九个位数的前两位能被2整除，前三位能被3整除……前N位能被N整除，整个九位数能被9整除。 *问题分析与算法设计 问题本身可以简化为一个穷举问题：只要穷举每位数字的各种可 - 39 - 能取值，按照题目的要求对穷举的结果进行判断就一定可以得到正确的结果。 问题中给出了―累进可除‖这一条件，就使得我们可以在穷举法中加入条件判断。在穷举的过程中，当确定部分位的值后，马上就判断产生的该部分是否符合―累进可除‖条件，若符合，则继续穷举下一位数字；否则刚刚产生的那一位数字就是错误的。这样将条件判断引入到穷举法之中，可以尽可能早的发现矛盾，尽早地放弃不必要穷举的值，从而提高程序的执行效率。 为了达到早期发现矛盾的目的，不能采用多重循环的方法实行穷举，那样编出的程序质量较差。程序中使用的算法不再是穷举法，而是回朔法。 *程序说明与注释 #include else /*第i位已经满足要求，处理第i+1位*/ if(++i<=NUM) /*i+1处理下一元素，当i没有处理完毕时*/ if(a[i-1]==NUM) a[i]=1; /*若i-1的值已为NUM，则a[i]的值为1*/ else a[i]=a[i-1]+1; /*否则，a[i]的初值为a[i-1]值的\下一个\值*/ } if(not_finish) { printf(\for(k=1;k<=NUM;k++) /*输出计算结果*/ #define NUM 9 int a[NUM+1]; int main() { int i,k,flag,not_finish=1; long sum; i=1; /*i:正在处理的数组元素，表示前i-1个元素已经满足要求，正处理的是第i个元素*/ a[1]=1; /*为元素a[1]设置初值*/ while(not_finish) /*not_finish=1:处理没有结束*/ { while(not_finish&&i<=NUM) { for(flag=1,k=1;flag&&k if(a[k]==a[i])flag=0; /*判断第i个元素是否与前i-1个元素重复*/ for(sum=0,k=1;flag&&k<=i;k++) { sum=10*sum+a[k]; if(sum%k)flag=0; /*判断前k位组成的整数是否能被k整除*/ } if(!flag) /*flag=0:表示第i位不满足要求，需要重新设置*/ { if(a[i]==a[i-1]) /*若a[i]的值已经经过一圈追上a[i-1]*/ { i–; /*i值减1，退回处理前一个元素*/ if(i>1&&a[i]==NUM) a[i]=1; /*当第i位的值达到NUM时，第i位的值取1*/ else if(i==1&&a[i]==NUM) /*当第1位的值达到NUM时结束*/ not_finish=0; /*置程序结束标记*/ else a[i]++; /*第i位的值取下一个,加1*/ } else if(a[i]==NUM) a[i]=1; printf(\ if(a[NUM-1] *运行结果 The progressire divisible number is: 381654729 *思考题 求N位累进可除数。用1到9这九个数字组成一个N(3<=N<=9)位数，位数字的组成不限，使得该N位数的前两位能被2整除， 前3位能被3整除，……，前N位能被N整除。求满足条件的N位数。 69.魔术师的猜牌术(1) 魔术师利用一副牌中的13张黑桃，预先将它们排好后迭在一起，牌面朝下。对观众说：我不看牌，只数数就可以猜到每张牌是什么，我大声数数，你们听，不信？你们就看。魔术师将最上面的那张牌数为1，把它翻过来正好是黑桃A，将黑桃A放在桌子上， 然后按顺序从上到下数手上的余牌，第二次数1、2，将第一张牌放在这迭牌的下面，将第二张牌翻过来，正好是黑桃2，也将它放在桌子上，第三次数1、2、3，将前面两张依次放在这迭牌的下面，再翻第三张牌正好是黑桃3。这样依次进行将13张牌全翻出来，准确无误。问魔术师手中的牌原始顺序是怎样安排的？ *问题分析与算法设计 题目已经将魔术师出牌的过程描述清楚，我们可以利用倒推的方法，很容易地推出原来牌的顺序。 人工倒推的方法是：在桌子上放13空盒子排成一圈，从1开始顺序编号，将黑桃A放入1号盒子中，从下一个空盒子开始对空的盒子计数，当数到第二个空盒子时，将黑桃2放入空盒子中， 然后再从下一个空盒子开始对空盒子计数，顺序放入3、4、5…， - 40 -