实验4
实验4-1-1 最大公约数和最小公倍数
本题要求两个给定正整数的最大公约数和最小公倍数。
输入格式:
输入在一行中给出两个正整数M和N（≤1000）。
输出格式:
在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。
输入样例:
511 292
输出样例:
73 2044
#include<stdio.h>int main(){int m,n,t;scanf("%d %d",&m,&n);int a=m,b=n;while(n>0){t=m%n;m=n;n=t;}printf("%d %d",m,a*b/m); }
·因为m，n在后面值发生了变化，所以要在前面保存他们的原始值。
·最小公倍数和最大公约数的关系：当你求出了两个数的最大公约数，那么最小公倍数就是这两个数的乘积除以最大公约数。
即：
最小公倍数=m原始值*n原始值/最大公约数
实验4-1-2 求奇数和
本题要求计算给定的一系列正整数中奇数的和。
输入格式:
输入在一行中给出一系列正整数，其间以空格分隔。当读到零或负整数时，表示输入结束，该数字不要处理。
输出格式:
在一行中输出正整数序列中奇数的和。
输入样例:
8 7 4 3 70 5 6 101 -1
输出样例:
116
#include<stdio.h>int main(){int x,sum=0;scanf("%d",&x);while(x>0){if(x%2!=0){sum+=x;}scanf("%d",&x);}printf("%d",sum);}
实验4-1-3 找出最小值
本题要求编写程序，找出给定一系列整数中的最小值。
输入格式：
输入在一行中首先给出一个正整数n，之后是n个整数，其间以空格分隔。
输出格式：
在一行中按照“min = 最小值”的格式输出n个整数中的最小值。
输入样例：
4 -2 -123 100 0
输出样例：
min = -123
#include<stdio.h>int main(){int n,min,x;scanf("%d",&n);scanf("%d",&x);min=x;for(int i=1;i<n;i++){scanf("%d",&x);if(x<min){min=x;}}printf("min = %d",min);}
实验4-1-4 求整数的位数及各位数字之和
对于给定的正整数N，求它的位数及其各位数字之和。
输入格式：
输入在一行中给出一个不超过109的正整数N。
输出格式：
在一行中输出N的位数及其各位数字之和，中间用一个空格隔开。
输入样例：
321
输出样例：
3 6
#include<stdio.h>int main(){int n,t,count=0,sum=0;scanf("%d",&n);do{t=n%10;sum+=t;n=n/10;count++;}while(n>0);printf("%d %d",count,sum);}
实验4-1-5 韩信点兵
在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝建立了卓越的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了知道有多少兵，同时又能保住军事机密，便让士兵排队报数：
按从1至5报数，记下最末一个士兵报的数为1；
再按从1至6报数，记下最末一个士兵报的数为5；
再按从1至7报数，记下最末一个士兵报的数为4；
最后按从1至11报数，最末一个士兵报的数为10；
请编写程序计算韩信至少有多少兵。
输入格式：
本题无输入
输出格式：
输出韩信至少拥有的士兵人数。
#include<stdio.h>int main(){for(int i=22;;i++){if(i%5==1&&i%6==5&&i%7==4&&i%11==10){printf("%d",i);break;}}}
实验4-1-6 求分数序列前N项和
本题要求编写程序，计算序列 2/1+3/2+5/3+8/5+… 的前N项之和。注意该序列从第2项起，每一项的分子是前一项分子与分母的和，分母是前一项的分子。
输入格式:
输入在一行中给出一个正整数N。
输出格式:
在一行中输出部分和的值，精确到小数点后两位。题目保证计算结果不超过双精度范围。
输入样例:
20
输出样例:
32.66
#include<stdio.h>int main(){double sum=0,fenzi=2,fenmu=1;int n;scanf("%d",&n);for(int i=1;i<=n;i++){sum+=fenzi/fenmu;double temp=fenmu;fenmu=fenzi;fenzi=fenzi+temp;}printf("%.2f",sum);}
实验4-1-7 特殊a串数列求和
给定两个均不超过9的正整数a和n，要求编写程序求a+aa+aaa++⋯+aa⋯a（n个a）之和。
输入格式：
输入在一行中给出不超过9的正整数a和n。
输出格式：
在一行中按照“s = 对应的和”的格式输出。
输入样例：
2 3
输出样例：
s = 246
#include<stdio.h>int main(){int a,n,sum=0;scanf("%d %d",&a,&n);int t=a;for(int i=1;i<=n;i++){sum+=t;t=t*10+a;}printf("s = %d",sum);}
实验4-1-8 求给定精度的简单交错序列部分和
本题要求编写程序，计算序列部分和 1 - 1/4 + 1/7 - 1/10 + … 直到最后一项的绝对值不大于给定精度eps。
输入格式:
输入在一行中给出一个正实数eps。
输出格式:
在一行中按照“sum = S”的格式输出部分和的值S，精确到小数点后六位。题目保证计算结果不超过双精度范围。
输入样例1:
4E-2
输出样例1:
sum = 0.854457
输入样例2:
0.02
输出样例2:
sum = 0.826310
#include<stdio.h>#include<math.h>int main(){double i=1,sign=1;double eps,sum=0;double x;scanf("%lf",&eps);// 1 - 1/4 + 1/7 - 1/10 + ... do{x=sign*1/(3*i-2);sum+=x;sign=-sign;i++;}while(fabs(x)>eps);printf("sum = %.6f",sum);}
实验4-1-9 猜数字游戏
猜数字游戏是令游戏机随机产生一个100以内的正整数，用户输入一个数对其进行猜测，需要你编写程序自动对其与随机产生的被猜数进行比较，并提示大了（“Too big”），还是小了（“Too small”），相等表示猜到了。如果猜到，则结束程序。程序还要求统计猜的次数，如果1次猜出该数，提示“Bingo!”；如果3次以内猜到该数，则提示“Lucky You!”；如果超过3次但是在N（>3）次以内（包括第N次）猜到该数，则提示“Good Guess!”；如果超过N次都没有猜到，则提示“Game Over”，并结束程序。如果在到达N次之前，用户输入了一个负数，也输出“Game Over”，并结束程序。
输入格式:
输入第一行中给出两个不超过100的正整数，分别是游戏机产生的随机数、以及猜测的最大次数N。最后每行给出一个用户的输入，直到出现负数为止。
输出格式:
在一行中输出每次猜测相应的结果，直到输出猜对的结果或“Game Over”则结束。
输入样例:
58 4
70
50
56
58
60
-2
输出样例:
Too big
Too small
Too small
Good Guess!
#include<stdio.h>int main(){int num,N,count=0;scanf("%d %d",&num,&N);//num要猜的那个随机数 N最大次数 int x;//x每次猜的数 do{scanf("%d",&x);count++;if(x<0){printf("Game Over\n");break;}if(count>N){printf("Game Over\n");break;}if(x>num){printf("Too big\n");}else if(x<num){printf("Too small\n");}else{//1次猜出if(count==1){printf("Bingo!\n");break;}else if(count<=3){//3次以内printf("Lucky You!\n");break;}else if(count>3&&count<=N){//大于3次旦小于等于nprintf("Good Guess!\n");break;} }}while(x>0);}
实验4-1-10 兔子繁衍问题
一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假如兔子都不死，请问第1个月出生的一对兔子，至少需要繁衍到第几个月时兔子总数才可以达到N对？
输入格式:
输入在一行中给出一个不超过10000的正整数N。
输出格式:
在一行中输出兔子总数达到N最少需要的月数。
输入样例:
30
输出样例:
9
#include<stdio.h>int main(){int N,x1=1,x2=1,x3;scanf("%d",&N);int i;if(N==1){i=1;printf("%d",i);}else{for(i=2;x3<N;i++){x3=x1+x2;x1=x2;x2=x3;}printf("%d",i);}}
分析：
月份: 1 2 3 4 5 6 7 8…
对数: 1 1 2 3 5 8 13 21…
可以发现兔子的对数是一个斐波那契数列
且第一个月的时候就是原生的那一对兔子，他们还没有开始繁殖，从第三个月开始繁殖
实验4-1-11 高空坠球
皮球从某给定高度自由落下，触地后反弹到原高度的一半，再落下，再反弹，……，如此反复。问皮球在第n次落地时，在空中一共经过多少距离？第n次反弹的高度是多少？
输入格式:
输入在一行中给出两个非负整数，分别是皮球的初始高度和n，均在长整型范围内。
输出格式:
在一行中顺序输出皮球第n次落地时在空中经过的距离、以及第n次反弹的高度，其间以一个空格分隔，保留一位小数。题目保证计算结果不超过双精度范围。
输入样例:
33 5
输出样例:
94.9 1.0
#include<stdio.h>int main(){double h,n,sum=0;scanf("%lf %lf",&h,&n);for(int i=1;i<=n;i++){sum+=h;h=h/2;if(i<n){sum+=h;}}if(n==0){printf("%.1f %.1f",0,0);}else{printf("%.1f %.1f",sum,h);}}
实验4-1-12 黑洞数
黑洞数也称为陷阱数，又称“Kaprekar问题”，是一类具有奇特转换特性的数。
任何一个各位数字不全相同的三位数，经有限次“重排求差”操作，总会得到495。最后所得的495即为三位黑洞数。所谓“重排求差”操作即组成该数的数字重排后的最大数减去重排后的最小数。（6174为四位黑洞数。）
例如，对三位数207：
第1次重排求差得：720 - 27 ＝ 693；
第2次重排求差得：963 - 369 ＝ 594；
第3次重排求差得：954 - 459 ＝ 495；
以后会停留在495这一黑洞数。如果三位数的3个数字全相同，一次转换后即为0。
任意输入一个三位数，编程给出重排求差的过程。
输入格式：
输入在一行中给出一个三位数。
输出格式：
按照以下格式输出重排求差的过程：
序号: 数字重排后的最大数 - 重排后的最小数 = 差值
序号从1开始，直到495出现在等号右边为止。
输入样例：
123
输出样例：
1: 321 - 123 = 198
2: 981 - 189 = 792
3: 972 - 279 = 693
4: 963 - 369 = 594
5: 954 - 459 = 495
#include<stdio.h>int buble(int arr[3]){//冒泡排序for(int i=0;i<3;i++){for(int j=1;j<=2-i;j++){if(arr[j]<arr[j-1]){int temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}}return arr[3];}int main(){int arr[3],max,min,n,count=0;scanf("%d",&n);do{arr[0]=n/100;//百位 arr[1]=n%100/10;//十位 arr[2]=n%10;//个位 buble(arr);max=arr[2]*100+arr[1]*10+arr[0];min=arr[0]*100+arr[1]*10+arr[2];count++;printf("%d: %d - %d = %d\n",count,max,min,max-min);n=max-min;}while((max-min)!=495);}
实验4-2-2 求e的近似值
自然常数 e 可以用级数 1+1/1!+1/2!+⋯+1/n!+⋯ 来近似计算。本题要求对给定的非负整数 n，求该级数的前 n+1 项和。
输入格式:
输入第一行中给出非负整数 n（≤1000）。
输出格式:
在一行中输出部分和的值，保留小数点后八位。
输入样例:
10
输出样例:
2.71828180
#include<stdio.h>double fact(int x){double p=1;for(int i=1;i<=x;i++){p=p*i;}return p;}int main(){int n;scanf("%d",&n);double sum=1;for(int i=1;i<=n;i++){sum+=1/fact(i);}printf("%.8f",sum);}
实验4-2-3 验证“哥德巴赫猜想”
数学领域著名的“哥德巴赫猜想”的大致意思是：任何一个大于2的偶数总能表示为两个素数之和。比如：24=5+19，其中5和19都是素数。本实验的任务是设计一个程序，验证20亿以内的偶数都可以分解成两个素数之和。
输入格式：
输入在一行中给出一个(2, 2 000 000 000]范围内的偶数N。
输出格式：
在一行中按照格式“N = p + q”输出N的素数分解，其中p ≤ q均为素数。又因为这样的分解不唯一（例如24还可以分解为7+17），要求必须输出所有解中p最小的解。
输入样例：
24
输出样例：
24 = 5 + 19
#include<stdio.h>#include<math.h>int isPrime(int x){int isPrime=1;if(x==1||x%2==0&&x!=2) isPrime=0;//x=1或x是＞2的偶数 不是素数 else {for(int i=3;i<=sqrt(x);i+=2){//判断3开始的奇数是否为素数 if(x%i==0){isPrime=0;break;}}}return isPrime;}int main(){int N,f=0;scanf("%d",&N);for(int p=2;p<N;p++){for(int q=2;q<N;q++){if(isPrime(p)&&isPrime(q)&&(p+q==N)){printf("%d = %d + %d",N,p,q);f=1;break;}}if(f) break;}}
虽然输入样例里的数据，结果正确，但是当n较大时，pat上运行超时
改进后的程序：
#include<stdio.h>#include<math.h>int isPrime(int x){int isPrime=1;if(x==1||x%2==0&&x!=2) isPrime=0;else {for(int i=3;i<=sqrt(x);i+=2){if(x%i==0){isPrime=0;break;}}}return isPrime;}int main(){int N,f=0;scanf("%d",&N);for(int p=2;p<=N/2;p++){int q=N-p;if(isPrime(p)&&isPrime(q)){printf("%d = %d + %d",N,p,q);break;}}}
双重循环简化为一层循环，直接判断p和N-p是否为素数
实验4-2-4 换硬币
将一笔零钱换成5分、2分和1分的硬币，要求每种硬币至少有一枚，有几种不同的换法？
输入格式:
输入在一行中给出待换的零钱数额x∈(8,100)。
输出格式:
要求按5分、2分和1分硬币的数量依次从大到小的顺序，输出各种换法。每行输出一种换法，格式为：“fen5:5分硬币数量, fen2:2分硬币数量, fen1:1分硬币数量, total:硬币总数量”。最后一行输出“count = 换法个数”。
输入样例:
13
输出样例:
fen5:2, fen2:1, fen1:1, total:4
fen5:1, fen2:3, fen1:2, total:6
fen5:1, fen2:2, fen1:4, total:7
fen5:1, fen2:1, fen1:6, total:8
count = 4
#include<stdio.h>int main(){int x,count=0,total;scanf("%d",&x);//按5分、2分和1分硬币的数量依次从大到小的顺序for(int i=x/5;i>=1;i--){//5for(int j=x/2;j>=1;j--){//2for(int k=x;k>=1;k--){//1if(i*5+j*2+k==x){total=i+j+k;printf("fen5:%d, fen2:%d, fen1:%d, total:%d\n",i,j,k,total);count++;}}} }printf("count = %d",count);}
实验4-2-5 水仙花数
水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。
输入格式:
输入在一行中给出一个正整数N（3≤N≤7）。
输出格式:
按递增顺序输出所有N位水仙花数，每个数字占一行。
输入样例:
3
输出样例:
153
370
371
407
#include<stdio.h>#include<math.h>int main(){int n,sum;scanf("%d",&n);int mask=pow(10,n);int m=mask/10;for(int i=m;i<mask;i++){sum=0;int x=i;for(int j=1;j<=n;j++){int d=x%10;x=x/10;sum+=pow(d,n);}if(sum==i){printf("%d\n",i);}}}
注意：这样做虽然结果是对的，但是当N=7时在pat上运行会超时，所以需要优化一下程序，上面的程序中pow调用次数太多导致超时，所以建立一个数组p[10]来保存个位数字的n次方，避免重复计算。
下面是改进后的程序：
#include<stdio.h>#include<math.h>int main(){int n,sum;scanf("%d",&n);int mask=pow(10,n);int m=mask/10;int p[10];//保存个位数字的n次方，避免重复计算for(int i=0;i<10;i++){p[i]=pow(i,n);}for(int i=m;i<mask;i++){sum=0;int x=i;for(int j=1;j<=n;j++){int d=x%10;x=x/10;sum+=p[d];}if(sum==i){printf("%d\n",i);}}}
实验4-2-6 输出三角形字符阵列
本题要求编写程序，输出n行由大写字母A开始构成的三角形字符阵列。
输入格式：
输入在一行中给出一个正整数n（1≤n<7）。
输出格式：
输出n行由大写字母A开始构成的三角形字符阵列。格式见输出样例，其中每个字母后面都有一个空格。
输入样例：
4
输出样例：
A B C D
E F G
H I
J
#include<stdio.h>int main(){int n,ascll=65;scanf("%d",&n);for(int i=n;i>=1;i--){int t=i;while(t>0){printf("%c ",ascll);ascll++;t--;} printf("\n");} }
实验4-2-7 找完数
所谓完数就是该数恰好等于除自身外的因子之和。例如：6=1+2+3，其中1、2、3为6的因子。本题要求编写程序，找出任意两正整数m和n之间的所有完数。
输入格式：
输入在一行中给出2个正整数m和n（1<m≤n≤10000），中间以空格分隔。
输出格式：
逐行输出给定范围内每个完数的因子累加形式的分解式，每个完数占一行，格式为“完数 = 因子1 + 因子2 + … + 因子k”，其中完数和因子均按递增顺序给出。若区间内没有完数，则输出“None”。
输入样例：
2 30
输出样例：
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
#include<stdio.h>int main(){int m,n,sum,flag=0;scanf("%d %d",&m,&n);for(int i=m;i<=n;i++){sum=0;for(int j=1;j<i;j++){if(i%j==0){sum+=j;}}if (sum == i){flag = 1;printf("%d = 1", i);//1是所有数的因子 for(int k=2;k<i;k++){if(i%k==0){printf(" + %d",k);}} printf("\n");}}if(flag==0){printf("None");}}
思路：
（1）先求出这个数的因子，然后求因子的和
（2）如果和等于这个数，就再算一次他的因子，依次输出
（3）flag是用来判断m到n之间是否存在这样的完数
实验4-2-8 输出整数各位数字
本题要求编写程序，对输入的一个整数，从高位开始逐位分割并输出它的各位数字。
输入格式：
输入在一行中给出一个长整型范围内的非负整数。
输出格式：
从高位开始逐位输出该整数的各位数字，每个数字后面有一个空格。
输入样例：
123456
输出样例：
1 2 3 4 5 6
#include<stdio.h>int main(){int x,count=0;scanf("%d",&x);int t=x;//count为x的位数do{x=x/10;count++;}while(x>0);int mask=1;while(count>1){mask=mask*10;count--;}//分解x的每一位，因为算位数时x改变了所以提前用t保存x的值while(mask>0){int d=t/mask;t=t%mask;mask=mask/10;printf("%d ",d);}}
实验4-2-9 梅森数
形如2n−1的素数称为梅森数（Mersenne Number）。例如22−1=3、23−1=7都是梅森数。17，双目失明的瑞士数学大师欧拉证明了231−1=2147483647是一个素数，堪称当时世界上“已知最大素数”的一个记录。
本题要求编写程序，对任一正整数n（n<20），输出所有不超过2n−1的梅森数。
输入格式：
输入在一行中给出正整数n（n<20）。
输出格式：
按从小到大的顺序输出所有不超过2n−1的梅森数，每行一个。如果完全没有，则输出“None”。
输入样例：
6
输出样例：
3
7
31
#include<stdio.h>#include<math.h>int Mersenne(int k);int main(){int n;int aim,count=0;scanf("%d",&n);for(int i=2;i<=n;i++){aim=pow(2,i)-1;if(Mersenne(aim)){printf("%d\n",aim);count++;}}if(count==0) printf("None");//没有就输出nonereturn 0;}int Mersenne(int k){int i;int flag=0;for(i=2;i<k;i++){//判断是否是素数if(k%i==0){flag=1;//flag=1不是素数break;}}return !flag;}
以上练习题如果大家有更好的方法可以在评论区告诉我哦~
