07.txt

CC++语言程序百例精解 非常经典的C

int i,k,flag; /*flag=1:数字是质数的标记*/
while(sum>0)
{
i=sum%10; /*取个位的数字*/
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
○○○B 2 2 8 8
————- —————-
○○○○○○ 2 3 6 2 3 6

66.除式还原(1)

给定下列除式，其中包含5个7，其它打×的是任意数字，请加以还原。

× 7 × ————–商
————–
除数——××| ×××××————-被除数
×7 7
————–
× 7 ×
× 7 ×
———-
× ×
× ×
———-
○

*问题分析与算法设计
首先分析题目，由除式本身尽可能多地推出已知条件。由除式本身书已知：
1、被除数的范围是10000到99999，除数的范围是10到99，且可以整除；
2、商为100到999之间，且十位数字为7；
3、商的第一位与除数的积为三位数，且后两位为77；
4、被除数的第三位一定为4；
5、 7乘以除数的积为一个三位数，且第二位为7；
6、商的最后一位不能为0，且与除数的积为一个二位数。
由已知条件就可以采用穷举的方法找出结果。

*程序说明与注释
#include<stdio.h>
int main()
{
long int i;
int j,l;
for(i=10000;i<=99999;i++) /*1. i:被除数*/
if(i%1000-i%100==400) /*4. 被除数的第三位一定为4*/
for(j=10;j<=99;j++) /*1. j: 余数*/
if(i%j==0&&(l=i/j)%100>=70&&l%100<80&&l%10!=0&&l>100&&l<=999)
/*1. 可以整除&& 2.商l在100到999之间且十位数字为7&&6.商的个数不能为0*/
if((j*(l%10))<100&&j*(l%10)>10) /*6. 商的个数与除数的积为二位数*/
if(j*7%100>=70&&j*7%100<80) /*5. 7乘以除数的积的第二位为7*/
if(j*(l/100)%100==77&&j*(l/100)>100)
/*商的第一位与除数的积的后两位为77*/
printf("%ld/%ld=%d\n",i,j,l);
}

*运行结果
51463/53=971。
可以看作为下列算式：

9 7 1
————-
5 3| 5 1 4 6 3
4 7 7
————-
3 7 6
3 7 1
———–
5 3
5 3
———–
○

*问题的进一步讨论
在推出的已知条件中，几所有的条件都是十分明显的，换句话说，推出的已知条件就是对题目的平铺直叙。这种推已知条件的方法十分简单，并且行之有效。

*思考题
下列除式中仅给定了一个8，其它打×的位置上是任意数字，请还原。

× 8 × —————-商
—————-
除数——-×××| ××××××—————被除数
××××
—————
×××
×××
—————
××××
××××
—————
○

 

67.除式还原(2)

下列除式中仅在商中给定了一个7，其它打×的位置全部是任意数字，请还原。

×7××× ————-商
——————
除数 ——————-×××| ×××××××× ————-被除数
×××× ————-1)
—————
××× ————-2)
××× ————-3)
—————
×××× ————-4)
××× ————-5)
—————–
×××× ————-6)
×××× ————-7)
—————–
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]<b
6)的前两位： 10<=d[2]<=99
1)式部分积： b*c[0]>1000
5)式部分积： 100<b*c[1]<1000

*程序说明与注释
#include<stdio.h>
int main()
{
int a[4],b,c[3],d[4],i=1;
for(a[0]=1010;a[0]<=1377;a[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]<b)
for(a[2]=0;a[2]<=9;a[2]++)
for(c[1]=7;c[1]<=8;c[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)
{
printf("No%2d:",i++);
printf("%d%d%d%d%d/",a[0],a[1],a[2],a[3]/10,a[3]%10);
printf("%d=",b);
printf("%d%d%d%d%d\n",c[0],7,c[1],0,c[2]);
}
}
*运行结果：
No 1:12128316/124=97809

*思考题
下列除式中“×”所在的位置全部是任意数字，请还原。
×××××
——————-
××× | ××××××××
××××
——————
××××
×××
—————
×××
×××
———–
××××
××××
———–
0

68.九位累进可除数

求九位累进可除数。所谓九位累进可除数就是这样一个数：这个数用到1到9这九个数字组成，每个数字刚好只出现一次。这九个位数的前两位能被2整除，前三位能被3整除……前N位能被N整除，整个九位数能被9整除。

*问题分析与算法设计
问题本身可以简化为一个穷举问题：只要穷举每位数字的各种可能取值，按照题目的要求对穷举的结果进行判断就一定可以得到正确的结果。
问题中给出了“累进可除”这一条件，就使得我们可以在穷举法中加入条件判断。在穷举的过程中，当确定部分位的值后，马上就判断产生的该部分是否符合“累进可除”条件，若符合，则继续穷举下一位数字；否则刚刚产生的那一位数字就是错误的。这样将条件判断引入到穷举法之中，可以尽可能早的发现矛盾，尽早地放弃不必要穷举的值，从而提高程序的执行效率。
为了达到早期发现矛盾的目的，不能采用多重循环的方法实行穷举，那样编出的程序质量较差。程序中使用的算法不再是穷举法，而是回朔法。

*程序说明与注释
#include<stdio.h>
#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<i;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;
else a[i]++;
}
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("\nThe progressire divisiable number is:");
for(k=1;k<=NUM;k++) /*输出计算结果*/
printf("%d",a[k]);
if(a[NUM-1]<NUM) a[NUM-1]++;
else a[NUM-1]=1;
not_finish=0;
printf("\n");
}
}
}

*运行结果
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…，直到放入全部3张牌。注意在计数时要跳过非空的盒子，只对空盒子计数。最后牌在盒子中的顺序，就是魔术师手中原来牌的顺序。
这种人工的方法是行之有效的，计算机可以模拟求解。

*程序说明与注释
#include<stdio.h>
int a[14];
int main()
{
int i,n,j=1; /*j:数组(盒子)下标，初始时为1号元素*/
printf("The original order of cards is:");
for(i=1;i<=13;i++) /*i:要放入盒子中的牌的序号*/
{
n=1;
do{
if(j>13) j=1; /*由于盒子构成一个圈，j超过最后一个元素则指向1号元素*/
if(a[j]) j++; /*跳过非空的盒子，不进行计数*/
else{ if(n==i) a[j]=i; /*若数到第i个空盒子，则将牌放入空盒中*/
j++;n++; /*对空盒计数，数组下标指向下一个盒子*/
}
}while(n<=i); /*控制空盒计数为i*/
}
for(i=1;i<=13;i++) /*输出牌的排列顺序*/
printf("%d ",a[i]);
printf("\n");
}

*运行结果
The original order of cards is:1 8 2 5 10 3 12 11 9 4 7 6 13

70.魔术师的猜牌术(2)

魔术师再次表演，他将红桃和黑桃全部迭在一起，牌面朝下放在手中，对观众说：最上面一张是黑桃A，翻开后放在桌上。以后，从上至下每数两张全依次放在最底下，第三张给观众看，便是黑桃2，放在桌上后再数两张依次放在最底下，第三张给观众看，是黑桃3。如此下去，观众看到放在桌子上牌的顺序是：
黑桃 A 2 3 4 5 6 7 8 9 10 J Q K
红桃 A 2 3 4 5 6 7 8 9 10 J Q K
问魔术师手中牌的原始顺序是什么？

*问题分析与算法设计
本题可在上题的基础上进行编程，不同的在于计数的方法和牌的张数，这些并不影响我们求解题目的思路，仍可按照倒推的方法，得到原来魔术师手中的牌的顺序。

*程序说明与注释
#include<stdio.h>
int a[27];
int main()
{
int i,n,j=1;
a[1]=1; /*初始化第一张牌*/
printf("The original order of cards is:(r:rad b:block):\n");
for(i=2;i<=26;i++)
{
n=1;
do{
if(j>26) j=1; /*超过最后一个元素则指向1号元素*/
if(a[j]) j++; /*跳过非空的盒子，不进行计数*/
else{
if(n==3) a[j]=i; /*若数到第3个空盒子，则将牌放入空盒中*/
j++; n++; /*对空盒计数，数组下标指向下一个盒子*/
}
}while(n<=3); /*控制空盒计数为3*/
}
for(i=1;i<=26;i++) /*输出牌的排列顺序*/
{
printf("%c",a[i]>13? 'r':'b');
printf("%d ",a[i]>13? a[i]-13:a[i]);
if(i==13) printf("\n");
}
printf("\n");
}

*运行结果
The original order of cards is:(r:rad b:black):
b1 r6 b10 b2 r12 r3 b3 b11 r9 b4 r7 b12 b5
r4 r13 b6 b13 r11 b7 r5 r1 b8 r8 r10 b9 r2