07.txt

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

C/C++语言经典、实用、趣味程序设计编程百例精解（7）



61.1~9组成三个3位的平方数

 

将1、2、3、4、5、6、7、8、9九个数字分成三组，每个数字只能用一次，即每组三个数不允许有重复数字，也不许同其它组的三个数字重复，要求每组中的三位数都组成一个平方数。

*问题分析与算法设计
本问题的思路很多，这里介绍一种简单快速的算法。
首先求出三位数中不包含0且是某个整数平方的三位数，这样的三位数是不多的。然后将满足条件的三位数进行组合，使得所选出的3个三位数的9个数字没有重复。
程序中可以将寻找足条件的三位数的过程和对该三位数进行数字分解的过程结合起来。

*程序说明与注释
#include<stdio.h>
int main()
{
int a[20],num[20][3],b[10]; /*a:存放满足条件的三位数*/
/*若不是10 的倍数，则分解三位数*/
/*分解该三位数中的每一个数字*/
int i,j,k,m,n,t,flag;
printf("The 3 squares with 3 different digits each are:\n");
for(j=0,i=11;i<=31;i++) /*求出是平方数的三位数*/
if(i%10!=0) /*若不是10的倍数，则分解三位数*/
{
k=i*i; /*分解该三位数中的每一个数字*/
num[j+1][0]=k/100; /*百位*/
num[j+1][1]=k/10%10; /*十位*/
num[j+1][2]=k%10; /*个位*/
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];
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(n=7;!flag&&n<=9;n++) /*与第三个数的数字重复*/
if(b[m]==b[n])flag=1;
if(!flag) /*若均不重复则打印结果*/
printf("%d,%d,%d\n",a[i],a[t],a[k]);
}
}
}
}

*运行结果
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<stdio.h>
#include<stdlib.h>
int main()
{
int a[9],ii=0,i,a1,a2,a3,a4,b1,b2,b3,b4,flag;
for(i=1;i<=8;i++) /*输入个数*/
{
printf("Please enter [%d]number:",i);
scanf("%d",&a[i]);
ii+=a[i];
}
printf("******************************************\n");
if(ii%2) /*和为奇数则输入的8个数不可用*/
{
printf("Sorry they can't be constructed required cube!\n");
exit(0);
}
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("They can be constructed required cube as follow:\n");
printf(" /%2d…………/%2d\n",a[a4],a[a3]);
printf(" %2d/…………%2d/|\n",a[a1],a[a2]);
printf(" | | | |\n");
printf(" | | | |\n");
printf(" | %2d| | |%2d\n",a[b4],a[b3]);
printf(" /……………./\n");
printf(" %2d/………….%2d/\n",a[b1],a[b2]);
}
else printf("Sorry they can't be constructed required 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
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<stdio.h>
int main()
{
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的全部可能取值*/
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(" PEAR %d%d%d%d\n",p,e,a,r);
printf(" -ARA - %d%d%d\n",a,r,a);
printf("…………………….\n");
printf(" PEA %d%d%d\n",p,e,a);
}
}

*运行结果
PEAR 1098
- ARA - 989
———- ——
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<stdio.h>
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;
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,"001"); /*判断第三个部分积*/
if(flag)
{
for(flag=0,m=0;m<4&&!flag;) /*乘数的第二位*/
flag=jud((t2=++m*10*term)/10,"1100"); /*判断第二个部分积*/
if(flag)
{
for(flag=0,l=5;l<9&&!flag;) /*乘数的第三位*/
flag=jud(t1=++l*term,"0000"); /*判断第一个部分积*/
if(flag&&jud(t1+t2+t3,"00101")) /*判断乘式的积*/
print(term,n*100+m*10+l,t1,t2,t3);
}
}
}
}

void print(long a,long b,long s1,long s2,long s3) /*打印结果*/
{
printf("\n %ld\n",a);
printf("*) %ld\n",b);
printf("………………….\n");
printf(" %ld\n %ld\n %ld\n",s1,s2/10,s3/100);
printf("………………….\n");
printf(" %ld\n",a*b);
}
int jud(long q,char *pflag) /*判断一个数的每一位是否满足要求的判断函数*/
/*q:需要判断的数。pflag:标志字符串，A用1表示，Z用0表示。标志串排列顺序：个十百…*/
{
while(q!=0&&*pflag!=NULL) /*循环判断对应位的取值范围是否正确*/
if(*pflag-'0'!=(q%10>=5?1:0)) /*标志位与对应的位不符，返回0*/
return 0;
else
{
q/=10;++pflag; /*若相符则取下一位进行判断*/
}
if(q==0&&*pflag==NULL) /*q的位数与标志字符串的长度相同时，返回1*/
return 1;
else return 0;
}

*运行结果
3 7 2
× 2 4 6
———-
2 2 3 2
1 4 8 8
7 4 4
————
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个数字的穷举，前面的许多例题中都已见过。循环实现简单易行，但嵌套的层次太多，需要穷举的变量的数量直接影响到循环嵌套的层数，这种简单的实现方法缺少技巧性。本例的程序中给出了另外一种同样功能的算法，该算法的实现思想请阅读程序。
程序中并没有直接对质数进行穷举，而是将每个质数与1到4顺序一一对应，在穷举时为处理简单仅对1到4进行穷举处理，待要判断产生的乘积是否满足条件时再利用一个数组完成向对应质数的转换。请体会程序中的处理方法。程序中使用的算法实际上是回朔法。

*程序说明与注释
#include<stdio.h>
#define NUM 5 /*需要穷举的变量数目*/
#define C_NUM 4 /*每个变量的值的变化范围*/
int a[NUM+1]; /*为需要穷举的变量开辟的数组*/
/*a[1]:被乘数的百位，a[2]：十位,aa[3]:个位 a[4]:被乘数的十位 a[5]:个位*/
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))
/*判断乘式的积是否满足题目条件*/
{
printf(" %d\n",sum1); /*若满足题意，则打印结果*/
printf("* %d%d\n",b[a[4>,b[a[5>);
printf("……………………\n");
printf(" %d\n",sum2);
printf(" %d\n",sum3);
printf("……………………\n");
printf(" %d\n",sum4);
}
i=NUM; /*为穷举下一个可能取值作准备*/
}
}
}
int f(long sum) /*判断sum的每一位数字是否是质数，若不是返回0，若是返回1*/
{