C/C++語言經(jīng)典、實(shí)用、趣味程序設(shè)計(jì)編程百例精解（3）



21.4位反序數(shù)

 

設(shè)N是一個(gè)四位數(shù)，它的9倍恰好是其反序數(shù)，求N。反序數(shù)就是將整數(shù)的數(shù)字倒過來形成的整數(shù)。例如：1234的反序數(shù)是4321。

*問題分析與算法設(shè)計(jì)
可設(shè)整數(shù)N的千、百、十、個(gè)位為i、j、k、l，其取值均為0~9，則滿足關(guān)系式：
(i*103+j*102+10*k+l)*9=(l*103+k*102+10*j+i)
的i、j、k、l即構(gòu)成N。

*程序說明與注釋
#include<stdio.h>
int main()
{
int i;
for(i=1002;i<1111;i++) /*窮舉四位數(shù)可能的值*/
if(i%10*1000+i/10%10*100+i/100%10*10+i/1000==i*9)
/*判斷反序數(shù)是否是原整數(shù)的9倍*/
printf("The number satisfied stats condition is: %d\n",i);
/*若是則輸出*/
}

*運(yùn)行結(jié)果
The number satisfied states condition is:1089
22.求車速

一輛以固定速度行駛的汽車，司機(jī)在上午10點(diǎn)看到里程表上的讀數(shù)是一個(gè)對稱數(shù)(即這個(gè)數(shù)從左向右讀和從右向左讀是完全一樣的)，為95859。兩小時(shí)后里程表上出現(xiàn)了一個(gè)新的對稱數(shù)。問該車的速度是多少？新的對稱數(shù)是多少？

*問題分析與算法設(shè)計(jì)
根據(jù)題意，設(shè)所求對稱數(shù)為i，其初值為95589，對其依次遞增取值，將i值的每一位分解后與其對稱位置上的數(shù)進(jìn)行比較，若每個(gè)對稱位置上的數(shù)皆相等，則可判定i即為所求的對稱數(shù)。

*程序說明與注釋
#include<stdio.h>
int main()
{
int t,a[5]; /*數(shù)組a存放分解的數(shù)字位*/
long int k,i;
for(i=95860;;i++) /*以95860為初值，循環(huán)試探*/
{
for(t=0,k=100000;k>=10;t++) /*從高到低分解所取i值的每位數(shù)*/
{ /* 字，依次存放于a[0]~a[5]中*/
a[t]=(i%k)/(k/10);
k/=10;
}
if((a[0]==a[4])&&(a[1]==a[3]))
{
printf("The new symmetrical number kelometers is:%d%d%d%d%d\n",
a[0],a[1],a[2],a[3],a[4]);
printf("The velocity of the car is: %.2f\n",(i-95859)/2.0);
break;
}
}
}

*運(yùn)行結(jié)果
The new symmetrical number kelometers is:95959.
The velocity of the car is:50.00

*思考題
將一個(gè)數(shù)的數(shù)碼倒過來所得到的新數(shù)叫原數(shù)的反序數(shù)。如果一個(gè)數(shù)等于它的反序數(shù)，則稱它為對稱數(shù)。求不超過1993的最大的二進(jìn)制的對稱數(shù)。

 

23.由兩個(gè)平方三位數(shù)獲得三個(gè)平方二位數(shù)

 

已知兩個(gè)平方三位數(shù)abc和xyz，其中a、b、c、x、y、z未必是不同的；而ax、by、cz是三個(gè)平方二位數(shù)。請編程求三位數(shù)abc和xyz。

*問題分析與算法設(shè)計(jì)
任取兩個(gè)平方三位數(shù)n和n1，將n從高向低分解為a、b、c，將n1從高到低分解為x、y、z。判斷ax、by、cz是否均為完全平方數(shù)。

*程序說明與注釋
#include<stdio.h>
#include<math.h>
void f(int n,float* s);
int main()
{
int i,t;
float a[3],b[3];
print("The possible perfect squares combinations are:\n");
for(i=11;i<=31;++i) //窮舉平方三位數(shù)的取值范圍
for(t=11;t<=31;++t)
{
f(i*i,a); //分解平方三位數(shù)的各位，每位數(shù)字分別存入數(shù)組中
f(t*t,b);
if(sqrt(a[0]*10+b[0]) == (int)sqrt(a[0]*10+b[0])
&& sqrt(a[1]*10+b[1]) == (int)sqrt(a[1]*10+b[1])
&& sqrt(a[2]*10+b[2]) == (int)sqrt(a[2]*10+b[2]) )
{
printf("%d and %d\n,i*i,t*t"); //若三個(gè)新的數(shù)均是完全平方數(shù)，則輸出
}
}
}

 

/* ———————————————-
分解三位數(shù)n的各位數(shù)字，將各個(gè)數(shù)字從高到低依次存入指針s所指向的數(shù)組中
————————————————*/

void f(int n,float* s)
{
int k;
for(k=1000;k>=10;++s)
{
*s = (n%k) /(k/10);
k /=10;
}
}

*運(yùn)行結(jié)果
The possible perfect squares combinations are:
400 and 900
841 and 196

*思考題

求這樣一個(gè)三位數(shù)，該三位數(shù)等于其每位數(shù)字的階乘之和。
即 abc = a! + b! + c!
(正確結(jié)果：145 = 1! + 4! +5!)

 

24.阿姆斯特朗數(shù)

 

如果一個(gè)正整數(shù)等于其各個(gè)數(shù)字的立方和，則稱該數(shù)為阿姆斯特朗數(shù)(亦稱為自戀性數(shù))。
如 407=43+03+73就是一個(gè)阿姆斯特朗數(shù)。試編程求1000以內(nèi)的所有阿姆斯特朗數(shù)。

*問題分析與算法設(shè)計(jì)
可采用窮舉法，依次取1000以內(nèi)的各數(shù)(設(shè)為i)，將i的各位數(shù)字分解后，據(jù)阿姆斯特朗數(shù)的性質(zhì)進(jìn)行計(jì)算和判斷。

*程序說明與注釋
#include<stdio.h>
int main()
{
int i,t,k,a[3];
printf("There are follwing Armstrong number smaller than 1000:\n");
for(i=2;i<1000;i++) /*窮舉要判定的數(shù)i的取值范圍2~1000*/
{
for(t=0,k=1000;k>=10;t++) /*截取整數(shù)i的各位(從高向低位)*/
{
a[t]=(i%k)/(k/10); /*分別賦于a[0]~a[2}*/
k/=10;
}
if(a[0]*a[0]*a[0]+a[1]*a[1]*a[1]+a[2]*a[2]*a[2]==i)
/*判斷i是否為阿姆斯特朗數(shù)*/
printf("%5d",i); /*若滿足條件，則輸出*/

}
printf("\n");
}

*運(yùn)行結(jié)果
There are following Armstrong number smaller than 1000:
153 370 371 407

25.完全數(shù)

 

如果一個(gè)數(shù)恰好等于它的因子之和，則稱該數(shù)為“完全數(shù)”。

*問題分析與算法設(shè)計(jì)
根據(jù)完全數(shù)的定義，先計(jì)算所選取的整數(shù)a(a的取值1~1000)的因子，將各因子累加于m，若m等于a，則可確認(rèn)a為完全數(shù)。

*程序說明與注釋
#include<stdio.h>
int main()
{
int a,i,m;
printf("There are following perfect numbers smaller than 1000:\n");
for(a=1;a<1000;a++) /*循環(huán)控制選取1~1000中的各數(shù)進(jìn)行判斷*/
{
for(m=0,i=1;i<=a/2;i++) /*計(jì)算a的因子，并將各因子之和m=a，則a是完全數(shù)輸出*/
if(!(a%i))m+=i;
if(m==a)
printf("%4d ",a);
}
printf("\n");
}

*運(yùn)行結(jié)果
TThere are following perfect numbers smaller than 1000:
6 28 496

 

26.親密數(shù)

如果整數(shù)A的全部因子(包括1，不包括A本身)之和等于B；且整數(shù)B的全部因子(包括1，不包括B本身)之和等于A，則將整數(shù)A和B稱為親密數(shù)。求3000以內(nèi)的全部親密數(shù)。

*問題分析與算法設(shè)計(jì)
按照親密數(shù)定義，要判斷數(shù)a是否有親密數(shù)，只要計(jì)算出a的全部因子的累加和為b，再計(jì)算b的全部因子的累加和為n，若n等于a則可判定a和b是親密數(shù)。計(jì)算數(shù)a的各因子的算法：
用a依次對i(i=1~a/2)進(jìn)行模運(yùn)算，若模運(yùn)算結(jié)果等于0，則i為a的一個(gè)因子；否則i就不是a的因子。

*程序說明與注釋
#include<stdio.h>
int main()
{
int a,i,b,n;
printf("There are following friendly–numbers pair smaller than 3000:\n");
for(a=1;a<3000;a++) /*窮舉1000以內(nèi)的全部整數(shù)*/
{
for(b=0,i=1;i<=a/2;i++) /*計(jì)算數(shù)a的各因子，各因子之和存放于b*/
if(!(a%i))b+=i; /*計(jì)算b的各因子，各因子之和存于n*/
for(n=0,i=1;i<=b/2;i++)
if(!(b%i))n+=i;
if(n==a&&a<b)
printf("%4d..%4d ",a,b); /*若n=a，則a和b是一對親密數(shù)，輸出*/
}
}

*運(yùn)行結(jié)果
There are following friendly–numbers pair smaller than 3000:
220.. 284 1184.. 1210 2620.. 2924
27.自守?cái)?shù)

自守?cái)?shù)是指一個(gè)數(shù)的平方的尾數(shù)等于該數(shù)自身的自然數(shù)。例如：
252=625 762=5776 93762=87909376
請求出200000以內(nèi)的自守?cái)?shù)

*問題分析與算法設(shè)計(jì)
若采用“求出一個(gè)數(shù)的平方后再截取最后相應(yīng)位數(shù)”的方法顯然是不可取的，因?yàn)橛?jì)算機(jī)無法表示過大的整數(shù)。
分析手工方式下整數(shù)平方(乘法)的計(jì)算過程，以376為例：
376 被乘數(shù)
X 376 乘數(shù)
———-
2256 第一個(gè)部分積=被乘數(shù)*乘數(shù)的倒數(shù)第一位
2632 第二個(gè)部分積=被乘數(shù)*乘數(shù)的倒數(shù)第二位
1128 第三個(gè)部分積=被乘數(shù)*乘數(shù)的倒數(shù)第三位
———-
141376 積
本問題所關(guān)心的是積的最后三位。分析產(chǎn)生積的后三位的過程，可以看出，在每一次的部分積中，并不是它的每一位都會(huì)對積的后三位產(chǎn)生影響。總結(jié)規(guī)律可以得到：在三位數(shù)乘法中，對積的后三位產(chǎn)生影響的部分積分別為：
第一個(gè)部分積中：被乘數(shù)最后三位*乘數(shù)的倒數(shù)第一位
第二個(gè)部分積中：被乘數(shù)最后二位*乘數(shù)的倒數(shù)第二位
第三個(gè)部分積中：被乘數(shù)最后一位*乘數(shù)的倒數(shù)第三位
將以上的部分積的后三位求和后截取后三位就是三位數(shù)乘積的后三位。這樣的規(guī)律可以推廣到同樣問題的不同位數(shù)乘積。
按照手工計(jì)算的過程可以設(shè)計(jì)算法編寫程序。

*程序說明與注釋
#include<stdio.h>
int main()
{
long mul,number,k,ll,kk;
printf("It exists following automorphic nmbers small than 200000:\n");
for(number=0;number<200000;number++)
{
for(mul=number,k=1;(mul/=10)>0;k*=10);
/*由number的位數(shù)確定截取數(shù)字進(jìn)行乘法時(shí)的系數(shù)k*/
kk=k*10; /*kk為截取部分積時(shí)的系數(shù)*/
mul=0; /*積的最后n位*/
ll=10; /*ll為截取乘數(shù)相應(yīng)位時(shí)的系數(shù)*/
while(k>0)
{
mul=(mul+(number%(k*10))*(number%ll-number%(ll/10)))%kk;
/*(部分積+截取被乘數(shù)的后N位*截取乘數(shù)的第M位)，%kk再截取部分積*/
k/=10; /*k為截取被乘數(shù)時(shí)的系數(shù)*/
ll*=10;
}
if(number==mul) /*判斷若為自守?cái)?shù)則輸出*/
printf("%ld ",number);
}
}

*運(yùn)行結(jié)果
It exsts following automorphic numbners smaller than 200000:
0 1 5 6 25 76 376 625 9376 90625 109376
28.回文數(shù)

打印所有不超過n(取n<256) 的其平方具有對稱性質(zhì)的數(shù)(也稱回文數(shù))。

*問題分析與算法設(shè)計(jì)
對于要判斷的數(shù)n，計(jì)算出其平方后(存于a)，將a的每一位進(jìn)行分解，再按a的從低到高的順序?qū)⑵浠謴?fù)成一個(gè)數(shù)k(如n=13，則a=169且k=961)，若a等于k則可判定n為回亠數(shù)。

*程序說明與注釋

原程序好像有錯(cuò)，而且比較費(fèi)解，現(xiàn)基于原程序修改如下（如果讀者還發(fā)現(xiàn)錯(cuò)誤請?zhí)岢觯?
#include<stdio.h>
int main(void)
{
int m[16],n,i,t,count=0;
long unsigned a,k;
printf("No. number it's square(palindrome)\n");
for(n=1;n<256;n++) /*窮舉n的取值范圍*/
{
k=0;t=1;a=n*n; /*計(jì)算n的平方*/

for(i=0;a!=0;i++) /*從低到高分解數(shù)a的每一位存于數(shù)組m[0]~m[16]*/
{
m[i]=a%10;//這個(gè)是取得a的個(gè)位，整個(gè)循環(huán)合起來就可以取得各個(gè)位
a/=10;
}

int j=0;
for(i–;j<i;j++,i–)//因?yàn)閚的平方的各個(gè)位都存在數(shù)組中了，下面判斷是不是對稱
if(m[j]!=m[i])break;//只要有一位不是對稱，那就說明不是對稱，就可以退出了

//所有的位都對稱就說明是對稱了，這樣就可以打印出結(jié)果了
if(j>=i)printf("%2d%10d%10d\n",++count,n,n*n);

}

return 0;
}

*運(yùn)行結(jié)果
No. number it's square(palindrome)
1 1 1
2 2 4
3 3 9
4 11 121
5 22 484
6 26 676
7 101 10201
8 111 12321
9 121 14641
10 202 40804
11 212 44944

//下面程序是原來的，有錯(cuò)，而且費(fèi)解
#include<stdio.h>
int main(void)
{
int m[16],n,i,t,count=0;
long unsigned a,k;
printf("No. number it's square(palindrome)\n");
for(n=1;n<256;n++) /*窮舉n的取值范圍*/
{
k=0;t=1;a=n*n; /*計(jì)算n的平方*/

for(i=1;a!=0;i++) /*從低到高分解數(shù)a的每一位存于數(shù)組m[1]~m[16]*/
{
m[i]=a%10;//安安注：這個(gè)是取得a的個(gè)位，整個(gè)循環(huán)合起來就可以取得各個(gè)位,并存于數(shù)組中，為了是下面判斷是不是對稱
a/=10;
}

for(;i>1;i–)
{
k+=m[i-1]*t;
t*=10;
}
if(k==n*n)
printf("%2d%10d%10d\n",++count,n,n*n);
}

return 0;
}

 

*運(yùn)行結(jié)果
No. number it's square(palindrome)
1 1 1
2 2 4
3 3 9
4 11 121
5 22 484
6 26 676
7 101 10201
8 111 12321
9 121 14641

29.求具有abcd=(ab+cd)2性質(zhì)的四位數(shù)

3025這個(gè)數(shù)具有一種獨(dú)特的性質(zhì)：將它平分為二段，即30和25，使之相加后求平方，即(30+25)2，恰好等于3025本身。請求出具有這樣性質(zhì)的全部四位數(shù)。

*問題分析與算法設(shè)計(jì)
具有這種性質(zhì)的四位數(shù)沒有分布規(guī)律，可以采用窮舉法，對所有四位數(shù)進(jìn)行判斷，從而篩選出符合這種性質(zhì)的四位數(shù)。具體算法實(shí)現(xiàn)，可任取一個(gè)四位數(shù)，將其截為兩部分，前兩位為a，后兩位為b，然后套用公式計(jì)算并判斷。

*程序說明與注釋
#include<stdio.h>
int main()
{
int n,a,b;
printf("There are following number with 4 digits satisfied condition\n");
for(n=1000;n<10000;n++) /*四位數(shù)N的取值范圍1000~9999*/
{
a=n/100; /*截取N的前兩位數(shù)存于a*/
b=n%100; /*截取N的后兩位存于b*/
if((a+b)*(a+b)==n) /*判斷N是否為符合題目所規(guī)定的性質(zhì)的四位數(shù)*/
printf("%d ",n);
}
}

*運(yùn)行結(jié)果
There are following numbers with 4 digits satisfied condition:
2025 3025 9801

30.求素?cái)?shù)

求素?cái)?shù)表中1~1000之間的所有素?cái)?shù)

*問題分析與算法設(shè)計(jì)
素?cái)?shù)就是僅能衩1和它自身整除的整數(shù)。判定一個(gè)整數(shù)n是否為素?cái)?shù)就是要判定整數(shù)n能否被除1和它自身之外的任意整數(shù)整除，若都不能整除，則n為素?cái)?shù)。
程序設(shè)計(jì)時(shí)i可以從2開始，到該整數(shù)n的1/2為止，用i依次去除需要判定的整數(shù)，只要存在可以整除該數(shù)的情況，即可確定要判斷的整數(shù)不是素?cái)?shù)，否則是素?cái)?shù)。

*程序說明與注釋
#include<stdio.h>
int main()
{
int n1,nm,i,j,flag,count=0;
do{
printf("Input START and END=?");
scanf("%d%d",&n1,&nm); /*輸入求素?cái)?shù)的范圍*/
}while(!(n1>0&&n1<nm)); /*輸入正確的范圍*/
printf("………..PRIME TABLE(%d–%d)…………\n",n1,nm);
if(n1==1||n1==2) /*處理素?cái)?shù)2*/
{
printf("%4d",2);
n1=3;count++;
}
for(i=n1;i<=nm;i++) /*判定指定范圍內(nèi)的整數(shù)是否為素?cái)?shù)*/
{
if(!(i%2))continue;
for(flag=1,j=3;flag&&j<i/2;j+=2)
/*判定能否被從3到整數(shù)的一半中的某一數(shù)所整除*/
if(!(i%j))flag=0; /*若能整除則不是素?cái)?shù)*/
if(flag) printf(++count%15?"%4d":"%4d\n",i);
}
}

*思考題
請找出十個(gè)最小的連續(xù)自然數(shù)，它們個(gè)個(gè)都是合數(shù)(非素?cái)?shù))