E is coming from FRANCE. (法国人) F is coming from U.S.. (美国人) *问题的进一步讨论
生成条件矩阵然后使用消去法进行推理判断是一种常用的方法。对于解决较为复杂的逻辑问题是十分有效的。 *思考题
地理课上老师给出一张没有说明省份的中国地图，从中选出五个省从1到5编号，要大家写出省份的名称。交卷后五位同学每人只答了二个省份的名称如下，且每人只答对了一个省，问正确答案是什么？
A 答：2号陕西，5号甘肃 B 答：2号湖北，4号山东 C 答：1号山东，5号吉林 D 答：3号湖北，4号吉林 &&15-j-score[2][1]!=15-k-score[3][1]) {
score[1][2]=i;score[1][3]=15-i-7; /*将满足条件的结果记入数组*/
score[2][2]=j;score[2][3]=15-j-8; score[3][2]=k;score[3][3]=15-k-9; }
for(who=0,i=1;i<=3;i++,printf(\for(j=1;j<=3;j++) {
printf(\输出各家孩子的得分情况*/ if(score[i][j]==1)who=i; /*记录最后一名的家庭序号*/ }
E 答：2号甘肃，3号陕西 57.谁家孩子跑最慢
张王李三家各有三个小孩。一天，三家的九个孩子在一起比赛短跑，规定不分年龄大小，跑第一得9分，跑第2得8分，依此类推。比赛结果各家的总分相同，且这些孩子没有同时到达终点的，也没有一家的两个或三个孩子获得相连的名次。已知获第一名的是李家的孩子，获得第二的是王家的孩子。问获得最后一名的是谁家的孩子？ *问题分析与算法设计
按题目的条件，共有1+2+3+…+9=45分，每家的孩子的得分应为15分。根据题意可知：获第一名的是李家的孩子，获第二名的是王家的孩子，则可推出：获第三名的一定是张家的孩子。由―这些孩子没有同时到达终点的‖可知：名次不能并列，由―没有一家的两个或三个孩子获得相连的名次‖可知：第四名不能是张家的孩子。
程序中为了方便起见，直接用分数表示。 *程序说明与注释 #include
int i,j,k,who;
score[1][1]=7; /*按已知条件进行初始化：score[1]:张家三个孩子的得分*/
score[2][1]=8; /*score[2]:王家三个孩子的得分*/ score[3][1]=9; /*李家三个孩子的得分*/
for(i=4;i<6;i++) /*i:张家孩子在4到6分段可能的分数*/ for(j=4;j<7;j++) /*j:王家孩子在4到6分段可能的分数*/ for(k=4;i!=j&&k<7;k++) /*k:李家孩子在4到6分段可能的分数*/
if(k!=i&&k!=j&&15-i-score[1][1]!=15-j-score[2][1] /*分数不能并列*/
&&15-i-score[1][1]!=15-k-score[3][1]
if(who==1) /*输出最后判断的结果*/ printf(\
Zhang.\\n\else if(who==2) printf(\
Wang.\\n\
else printf(\family Li.\\n\}
*运行结果 7 5 3 8 6 1 9 4 2
The last one arrived to end is a child from family Wang.
(获得最后一名的是王家的孩子。 58.拉丁方阵
构造 NXN 阶的拉丁方阵(2<=N<=9)，使方阵中的每一行和每一列中数字1到N只出现一次。如N=4时： 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3
*问题分析与算法设计
构造拉丁方阵的方法很多，这里给出最简单的一种方法。观察给出的例子，可以发现：若将每 一行中第一列的数字和最后一列的数字连起来构成一个环，则该环正好是由1到N顺序构成；对于第i行，这个环的开始数字为i。按照 此规律可以很容易的写出程序。下面给出构造6阶拉丁方阵的程序。 *程序说明与注释 #include
int i,j,k,t;
- 31 -
printf(\for(j=0;j for(i=0;i t=(i+j)%N; /*确定该拉丁方阵第i 行的第一个元素的值*/ for(k=0;k printf(\} } int count; /*计数器*/ int main() { static int a[]={1,2,3,4,5,6}; /*初始化数组*/ printf(\are:\\n\ for(a[1]=a[0]+1;a[1]<=5;++a[1]) /*a[1]必须大于a[0]*/ for(a[2]=a[1]+1;a[2]<=5;++a[2]) /*a[2]必须大于a[1]*/ for(a[3]=a[0]+1;a[3]<=5;++a[3]) /*第二行的a[3]必须大于a[0]*/ for(a[4]=a[1]>a[3]?a[1]+1:a[3]+1;a[4]<=5;++a[4]) *运行结果 The possble Latin Squares of order 6 are: 1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2 2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3 3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4 4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5 5 6 1 2 3 4 6 1 2 3 4 5 1 2 3 4 5 6 6 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 1 4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5 5 6 1 2 3 4 6 1 2 3 4 5 1 2 3 4 5 6 6 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 1 1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2 2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3 3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4 59.填表格 将1、2、3、4、5和6 填入下表中，要使得每一列右边的数字比左边的数字大，每一行下面的数字比上面的数字大。按此要求，可有几种填写方法？ *问题分析与算法设计 按题目的要求进行分析，数字1一定是放在第一行第一列的格中，数字6一定是放在第二行第三列的格中。在实现时可用一个一维数组表示，前三个元素表示第一行，后三个元素表示第二行。先根据原题初始化数组，再根据题目中填 写数字的要求进行试探。 *程序说明与注释 #include /*第二行的a[4]必须大于左侧a[3]和上边a[1]*/ if(jud1(a)) print(a); /*如果满足题意，打印结果*/ } int jud1(int s[]) { int i,l; for(l=1;l<4;l++) for(i=l+1;i<5;++i) if(s[l]==s[i]) return 0; /*若数组中的数字有重复的，返回0*/ return 1; /*若数组中的数字没有重复的，返回1*/ } void print(int u[]) { int k; printf(\for(k=0;k<6;k++) if(k%3==0) /*输出数组的前三个元素作为第一行*/ printf(\ else /*输出数组的后三个元素作为第二行*/ printf(\} *运行结果 The possble table satisfied above conditions are: No.1: No.2: No.3: No.4: No.5: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 4 5 6 3 5 6 3 4 6 2 5 6 2 4 6 60.1~9分成1：2：3的三个3位数 将1到9 这九个数字分成三个3位数，分求第一个3位数，正好是第二个3位数的二倍，是第三个3位数的三倍。问应当怎样分法。 *问题分析与算法设计 问题中的三个数之间是有数学关系的，实际上只要确定第一个三 - 32 - 位数就可以解决问题。 试探第一个三位数之后，计算出另外两个数，将其分别分解成三位数字，进行判断后确定所试探的数是否就是答案。 需要提醒的是：试探的初值可以是123，最大值是333。因为不可能超出该范围。 *程序与程序设计 #include int m,count=0; for(m=123;m<=333;m++) /*试探可能的三位数*/ C/C++语言经典、实用、趣味程序设计编程百例精解（7） 61.1~9组成三个3位的平方数 将1、2、3、4、5、6、7、8、9九个数字分成三组，每个数字只能用一次，即每组三个数不允许有重复数字，也不许同其它组的三个数字重复，要求每组中的三位数都组成一个平方数。 *问题分析与算法设计 本问题的思路很多，这里介绍一种简单快速的算法。 首先求出三位数中不包含0且是某个整数平方的三位数，这样的三位数是不多的。然后将满足条件的三位数进行组合，使得所选if(ok(m,a)&&ok(2*m,a+3)&&ok(3*m,a+6)) /*若满足题意*/ printf(\/*输出结果*/ } int ok(int t,int *z) /*分解t的值，将其存入z指向的三个数组元素，若满足要求返回1*/ { int *p1,*p2; for(p1=z;p1 *p1=t; /*分解整数*/ t/=10; for(p2=a;p2 if(*p1==0||*p2==*p1)return 0; /*若重复则返回*/ } return 1; /*否则返回1*/ } *运行结果 No.1:192 384 576 No.2:219 438 657 No.3:273 546 819 No.4:327 654 981 *思考题 求出所有可能的以下形式的算式，每个算式中有九个数位，正好用尽1到9这九个数字。 1)○○○+○○○=○○○ (共有168种可能的组合) 2)○×○○○○=○○○○ (共有2种可能的组合) 3)○○×○○○=○○○○ (共有7种可能的组合) 4)○×○○○=○○×○○○ (共有13种可能的组合) 5)○×○○○=○×○○○○ (共有28种可能的组合) 6)○○×○○=○×○○○○ (共有7种可能的组合) 7)○○×○○=○○×○○○ (共有11种可能的组合) 出的3个三位数的9个数字没有重复。 程序中可以将寻找足条件的三位数的过程和对该三位数进行数字分解的过程结合起来。 *程序说明与注释 #include int a[20],num[20][3],b[10]; /*a:存放满足条件的三位数*/ /*若不是10 的倍数，则分解三位数*/ /*分解该三位数中的每一个数字*/ int i,j,k,m,n,t,flag; printf(\ for(j=0,i=11;i<=31;i++) /*求出是平方数的三位数*/ if(i!=0) /*若不是10的倍数，则分解三位数*/ { k=i*i; /*分解该三位数中的每一个数字*/ num[j+1][0]=k/100; /*百位*/ num[j+1][1]=k/10; /*十位*/ num[j+1][2]=k; /*个位*/ if(!(num[j+1][0]==num[j+1][1]||num[j+1][0]==num[j+1][2]|| num[j+1][1]==num[j+1][2])) /*若分解的三位数字均不相等*/ a[++j]=k; /*j:计数器，统计已找到的满足要求的三位数*/ } for(i=1;i<=j-2;++i) /*从满足条件的三位数中选出三个进行组合*/ { b[1]=num[i][0]; b[2]=num[i][1]; b[3]=num[i][2]; for(t=i+1;t<=j-1;++t) { b[4]=num[t][0]; /*取第t个数的三位数字*/ b[5]=num[t][1]; - 33 - b[6]=num[t][2]; for(flag=0,m=1;!flag&&m<=3;m++) /*flag:出现数字重复的标记*/ for(n=4;!flag&&n<=6;n++) /*判断两个数的数字是否有重复*/ if(b[m]==b[n])flag=1; /*flag=1:数字有重复*/ if(!flag) for(k=t+1;k<=j;k++) { b[7]=num[k][0]; /*取第k个数的三位数字*/ b[8]=num[k][1]; b[9]=num[k][2]; for(flag=0,m=1;!flag&&m<=6;m++) /*判断前两个数字for(i=1;i<=8;i++) /*输入个数*/ { printf(\scanf(\ii+=a[i]; } printf(\****\\n\ if(ii%2) /*和为奇数则输入的8个数不可用*/ { printf(\cube!\\n\exit(0); 是否*/ for(n=7;!flag&&n<=9;n++) /*与第三个数的数字重复*/ if(b[m]==b[n])flag=1; if(!flag) /*若均不重复则打印结果*/ printf(\} } } } *运行结果 The 3 squares with 3 different digits each are: 361,529,784 *思考题 将1、2、3、4、5、6、7、8、9九个数字分成二组，每个数字只能用一次，一组形成一个5位数，另一组形成一个4位数，使得前者为后者的n倍。求所有满足条件的5位数和4位数。(注意：N的最大值等于68,68以内的某些N也是不可能的。不可能的N值包括：1、10、11、20、21、25、30、31等共32个。) 62.由8个整数形成奇特的立方体 任意给出8个整数，将这8个整数分别放在一个立方体的八个顶点上，要求每个面上的四个数之和相等。 *问题分析与算法设计 简化问题：将8个顶点对应数组中的8个元素，将―每个面上的四个数之和皆相等‖转换为数组无素之间和的相等关系。这里的关键在于正确地将立方体的8个顶点与数组的8个元素对应。 可以利用简单的穷举方法建立8个数的全部排列。 *程序说明与注释 #include int a[9],ii=0,i,a1,a2,a3,a4,b1,b2,b3,b4,flag; } for(flag=0,a1=1;a1<=8;a1++) /*flag:完成标记.flag=1;表示完成*/ for(a2=1;a2<=8;a2++) /*采用八重循环建立八个整数的全排列*/ if(a2!=a1) /*前两个数不能相同*/ for(a3=1;a3<=8;a3++) if(a3!=a2&&a3!=a1) /*前三个数不能相同*/ for(a4=1;a4<=8;a4++) if(a4!=a3&&a4!=a2&&a4!=a1) /*前四个数不能相同*/ for(b1=1;b1<=8;b1++) if(b1!=a4&&b1!=a3&&b1!=a2&&b1!=a1) /*不能相同*/ for(b2=1;b2<=8;b2++) if(b2!=b1&&b2!=a4&&b2!=a3&&b2!=a2&&b2!=a1) for(b3=1;b3<=8;b3++) if(b3!=b2&&b3!=b1&&b3!=a4&&b3!=a3&&b3!=a2&&b3!=a1) /*不能取相同的数*/ for(b4=1;b4<=8;b4++) if(b4!=b2&&b4!=b1&&b4!=b3&&b4!=a4&&b4!=a3&&b4!=a2&&b4!=a1) if(a[b1]+a[b2]+a[b3]+a[b4]==ii/2 &&a[a1]+a[a2]+a[b1]+a[b2]==ii/2 &&a[a1]+a[a4]+a[b1]+a[b4]==ii/2) { flag=1;goto out; /*满足条件则将flag置1后退出*/ } out: if(flag) { printf(\follow:\\n\ printf(\\\n\printf(\\\n\printf(\printf(\ - 34 - printf(\printf(\\\n\ printf(\\\n\} else printf(\cube!\\n\} *运行结果 Please enter [1] number:20 Please enter [2] number:45 Please enter [3] number:39 Please enter [4] number:25 Please enter [5] number:29 if(r!=p&&r!=e&&r!=a&&p*1000+e*100+a*10+r-(a*100+r*10+a) ==p*100+e*10+a) { printf(\printf(\printf(\\\n\printf(\} } *运行结果 PEAR 1098 - ARA - 989 Please enter [6] number:7 Please enter [7] number:3 Please enter [8] number:2 Sorry they can't be constructed required cube! *思考题 程序中建立全排列的方法效率太低，算法虽然简单但程序过于冗余。请读者自行设计新的算法完成同样的工作。 63.减式还原 编写程序求解下式中各字母所代表的数字，不同的字母代表不同的数字。 PEAR - ARA ——– PEA *问题分析与算法设计 类似的问题从计算机算法的角度来说是比较简单的，可以采用最常见的穷举方法解决。程序中采用循环穷举每个字母所可能代表的数字，然后将字母代表的数字转换为相应的整数，代入算式后验证算式是否成立即可解决问题。 *程序说明与注释 #include int p,e,a,r; for(p=1;p<=9;p++) /*从1到9穷举字母p的全部可能取值*/ for(e=0;e<=9;e++) /*从0到穷举字母e的全部可能取值*/ if(p!=e) /*p不等于e*/ for(a=1;a<=9;a++) /*从0到9穷举字母a的全部可能取值*/ if(a!=p&&a!=e) for(r=0;r<=9;r++) /*从0到9穷举字母r的全部可能取值*/ ———- —— PEA 109 *思考题 请复原下面的和式。不同的字母代表不同的数字。 SEVEN 82524 82526 THREE 19722 19722 + TWO 答案： + 106 + 104 ———- ———– ———– TWELVE 102352 102352 64.乘式还原 A代表数字0到9中的前五个数字，Z代表后五个数字，请还原下列乘式。 A Z A × A A Z ———— A A A A A A Z Z Z A A ———— Z A Z A A *问题分析与算法设计 问题本身并不复杂，可以对乘式中的每一位使用穷举法，最终可以得到结果。本题的关键在于怎样有效的判断每个部分积的每一位是否满足题意，这一问题处理不好，编写的程序会很长。程序实现中采用了一个判断函数，通过传入函数的标志字符串对所有的数进行统一的判断处理。 *程序说明与注释 #include void print(long a,long b,long s1,long s2,long s3); int jud(long q,char *pflag); int main() { long i,j,k,l,m,n,term,t1,t2,t3; - 35 -