蓝桥杯——趣味分数问题（2017.2.17）

一、最大公约数与最小公倍数（GCD，LCM）

        输入两个正整数m，n，求它们的最大公约数与最小公倍数

法一：枚举法

源代码：

#include <stdio.h>void fun(int m,int n){	int i;	int gcd,lcm;                  //最大公约数与最小公倍数 	for(i=(m>n?n:m);i>=1;i--)	{		if(m%i==0 && n%i==0)		{			gcd=i;			break;		}	}	lcm=m*n/gcd;	PRintf("%d %d/n",gcd,lcm);}int main(){	int m,n;	while(scanf("%d %d",&m,&n)!=EOF)		fun(m,n); } 法二：辗转相除法
        思想：（1）用较大的数m除以较小的数n，得到的余数存储到变量p中，即p=m%n；
                     （2）上一步中较小的除数n和得出的余数b构成新的一对数，并分别赋值给m和n，继续做上面的除法；
                     （3）若余数为0，其中较小的数（即除数）就是最大公约数，否则重复（1）（2）两步。
源代码：
#include <stdio.h>void fun(int m,int n){	int p,q,t;	int gcd,lcm;	q=m*n;	if(m<n)	{		t=m;		m=n;		n=t;	}	while(n!=0)         //接下来的循环中m为最大公约数，n为余数 	{		p=m%n;		m=n;		n=p;	}	gcd=m;	lcm=q/gcd;	printf("%d %d/n",gcd,lcm);}int main(){	int m,n;	while(scanf("%d %d",&m,&n)!=EOF)		fun(m,n);} 程序截图：
二、歌星大奖赛
        某歌星大奖赛中，有10个评委为参赛选手打分，分数为1~100分。选手最后得分为：去掉一个最高分和一个最低分后其余8个分数的平均值。编写程序实现。
源代码：
#include <stdio.h>#include <string.h>#define maxn 11int main(){	int i,a[maxn]={0};	int sum,maxscore,minscore;	double average;	while(scanf("%d",&a[0])!=EOF)	{		for(i=1;i<10;i++)			scanf("%d",&a[i]);		maxscore=minscore=a[0];		sum=0;		for(i=0;i<10;i++)		{			sum+=a[i];			if(a[i]>maxscore)				maxscore=a[i];			if(a[i]<minscore)				minscore=a[i];		}		sum-=(maxscore+minscore);		average=sum*1.0/8;		printf("max=%d min=%d/n",maxscore,minscore);		printf("score=%.2lf/n",average);		memset(a,0,sizeof(a));                          //初始化数组	}	return 0;} 程序截图：
三、将真分数分解为埃及分数
        输入一个真分数，将该分数分解为n个（n>=1）埃及分数和的形式。
        分子是1的分数，叫单位分数。古代埃及人在进行分数运算时，只使用分子为1的分数。因此这种分数也叫做埃及分数。
        例如：8/11=1/2+1/5+1/55+1/110。
【分析】真分数分解为埃及分数之和的思路：
        （1）分数的分子与分母分别用a和b表示，变量c用来存储各个埃及分数的分母；
        （2）如果分母能够整除分子，可直接约减成一个埃及分数，此时埃及分数的分母c=b/a，分子为1，即直接将变量a赋值为1；
        （3）否则分数中一定包含一个分母为（b/a）+1的埃及分数（即可分解出一个分母为（b/a）+1的埃及分数，c=（b/a）+1）；
        （4）如果分子是1，表明已经是埃及分数，不用再分解，结束；
        （5）如果分子是3且分母是偶数，则可直接分解成两个埃及分数1/（b/2）和1/b，结束；
        （6）从分数中减去这个分母为（b/a）+1的埃及分数，回到步骤（2）重复上述过程。
源代码：
#include <stdio.h>int main(){	long int a,b,c;                   //a-分数分子 b-分数分母 c-各个埃及分数的分母	while(scanf("%ld/%ld",&a,&b)!=EOF)	{		while(1)		{			if(b%a!=0)                //若分子不能整除分母，则分解出一个分母为b/a+1的埃及分数				c=b/a+1;			else                      //否则，输出化简后的真分数(埃及分数) 			{				c=b/a;				a=1;				}			if(a==1)                  //a为1标志阶数 			{				printf("1/%ld/n",c);				break;				}			else				printf("1/%ld+",c);			a=a*c-b;                  //求出余数的分子 			b=b*c;                    //求出余数的分母			if(a==3 && b%2==0)        //若余数分子为3，分母为偶数，输出最后两个埃及分数			{				printf("1/%ld+1/%ld/n",b/2,b);				break;			}		}	}	return 0;}程序截图：
四、列出真分数序列
        按递增顺序依次列出所有分母为n，分子小于n的最简真分数
源代码：
法一：枚举分数的分子
#include <stdio.h>int main(){	int fz,fm,n;	int i,flag;	while(scanf("%d",&n)!=EOF)	{		fm=n;		for(fz=1;fz<fm;fz++)		{			flag=1;			for(i=2;i<=fm/2;i++)			{				if(fm%i==0 && fz%i==0)				{					flag=0;					break;				}			}			if(flag==1)				printf("%d/%d/n",fz,fm);		}	} 	return 0;}法二：结合辗转相除法思想求解（可降低算法复杂度）
#include <stdio.h>int main(){	int i,j,n;	int num1,num2;	while(scanf("%d",&n)!=EOF)	{		for(i=1;i<=n;i++)		{			num1=n;			num2=i;			while(num2!=0)                 //辗转相除法求最大公约数 			{				j=num1%num2;				num1=num2;				num2=j;				}			if(num1==1)                    //分子与分母的最大公约数为1时，该分数为最简真分数 				printf("%d/%d/n",i,n);		}	} 	return 0;}程序截图：
五、多项式之和的计算
        计算下列多项式的值：S=1+1/（1*2）+1/（1*2*3）+ … + 1/（1*2*3* … *50）
源代码：
#include <stdio.h>int main(){	int i,j,n;	double t,sum;	while(scanf("%d",&n)!=EOF)	{		sum=0;		for(i=1;i<=n;i++)		{			t=1;			for(j=1;j<=i;j++)        //注意精度问题，可以将阶乘形式的分母进行转化，计算				t*=(1.0/j);			sum+=t;		}		printf("%lf/n",sum);	}	return 0;}程序截图：