求两个正整数的最大公约数

时间:2022-09-08 09:46:32

基本要求:从键盘输入两个整数,输出两个整数的最大公约数。用C或C++语言实现程序解决问题。

1.      程序风格良好(使用自定义注释模板)

2.      使用三种算法解决问题

3.      提供友好的输入输出,并进行输入数据的正确性验证

方法一:穷举法

穷举法,顾名思义,就是一个一个试,即遍历两个整数中较小的数到零的所有数,如果能够同时被两个整数整除,则这个数就为这两个数的最大公约数。

具体实现代码如下:

#include<stdio.h>
int main()
{
int m,n,k;
printf("请输入两个正整数:");
scanf("%d%d",&m,&n);
int GDC(int a,int b);//声明函数
k=GDC(m,n);
printf("%d和%d的最大公约数为:%d",m,n,k);
return 0;
}
int GDC(int a,int b)//定义一个函数用来求最大公约数
{
int i,q;
q=a>b?b:a;//将两个正整数中较小的数赋给q
for(i=q;i>0&&(b%i||a%i);i--);//遍历从q到0的所有数,如果能同时被两个正整数整除,则为两个数的最大公约数
return i;
}
方法二:相减法

相减法,即通过连续相减求得两个数的最大公约数。

如果a>b,则a=a-b;

如果a<b,则b=b-a;

如果a=b,则a和b均为最大公约数。

例如:a=27,b=15;

则27-15=12,15-12=3,12-3=9,9-3=6,6-3=3。则3位27和15的最大公约数。

具体实现代码如下:

#include<stdio.h>
int main()
{
int m,n,k;
printf("请输入两个正整数:");
scanf("%d%d",&m,&n);
int GDC(int a,int b);//声明函数
k=GDC(m,n);
printf("%d和%d的最大公约数为:%d",m,n,k);
return 0;
}
int GDC(int a,int b)//定义一个函数用来求最大公约数
{
while(a-b)//利用相减法求最大公约数
{
if(a>b)a=a-b;
elseb=b-a;
}
return a;
}
方法三:辗转相除法

辗转相除法,即利用连续相除来求最大公约数。

例:a=36,b=27

36%27=9,27%9=0。则9即为36和27的最大公约数。

具体实现代码如下:

#include<stdio.h>
int main()
{
int m,n,k;
printf("请输入两个正整数:");
scanf("%d%d",&m,&n);
int GDC(int a,int b);//声明函数
k=GDC(m,n);
printf("%d和%d的最大公约数为:%d",m,n,k);
return 0;
}
int GDC(int a,int b)//定义一个函数求最大公约数
{
int c;
while(b)//利用辗转相除法求最大公约数
{
c=a%b;
a=b;
b=c;
}
return a;
}
总结:

通过完成这次作业我学到了许多东西,自己原本只会用穷举法求两个数的最大公约数,通过这次作业,我也掌握了相减法和辗转相除法这两种方法。在以后学习过程中,我需要开拓自己的思维,,尝试着去用多种不同的方法来解决问题。