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*/
{