求两个整数的最大公约数

81 阅读 0 评论 54 点赞

我是靠谱客的博主悲凉黑米，最近开发中收集的这篇文章主要介绍求两个整数的最大公约数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

程序实现的功能：从键盘输入两个整数，输出两个整数的最大公约数。

基本思路：可采用辗转相除法，辗转相减法，穷举法对两个整数求最大公约数，并且要对负数、0单独考虑。

（1）可以先对负数求绝对值，转换成正数，再求最大公约数。

（2）如果输入的整数包含0，因为一个数与0的公约数为它本身，所以可以直接输出非0的数就是所求的最大公约数。

程序源代码：

/*
主要功能：求两个整数的最大公约数
作者：xxx
创建日期：2017.3.18
*/

#include<iostream>
#include<math.h>
using namespace std;
class GCD
{
private:
int a,b;
public:
void put_in(); //输入两个整数
void method_divide(); //辗转相除法求最大公约数
void method_subtract(); //辗转相减法求最大公约数
void method_illustrate(); //穷举法求最大公约数
void menu(); //打印菜单
int select; //select为是否退出系统的标记
};

void GCD::put_in() //输入两个整数
{
int flag=1; //flag用于判断循环是否执行
cout<<"请输入两个整数(以空格键隔开):"<<endl;
cin>>a>>b;
}

void GCD::method_divide() //辗转相除法
{
int c,temp;
if(b==0) //0不能做除数，当b==0时，交换a、b
{
temp=a;
a=b;
b=temp;
}
do
{
c=a%b;
if(c==0) //如果a能整除b,则两者的最大公约数为b的绝对值
cout<<"两者的最大公约数为:"<<abs(b)<<endl; //abs函数用于求绝对值
else
{
a=b; //b做新的除数
b=c; //c做新的被除数
}
}while(c!=0); //当a/b的余数是0时，跳出循环
}

void GCD::method_subtract() //辗转相减法
{
int d,temp;
int flag=1; //flag用于判断循环是否执行
if(a==0||b==0)
{
if(a==0)
cout<<a<<"和"<<b<<"的最大公约数为:"<<b<<endl;
else
cout<<a<<"和"<<b<<"的最大公约数为:"<<a<<endl;
}
else
{
if(a<0||b<0) //如果a<0或b<0,则对a、b求绝对值
{
a=abs(a);
b=abs(b);
}
if(a<b)
{
temp=a;
a=b;
b=temp; //大的数做被减数a，小的数做减数b
}
while(flag)
{
d=a-b;
if(b==d) //如果a是b的二倍，则a、b的最大公约数为b
{
cout<<"两者的最大公约数为:"<<b<<endl;
flag=0; //跳出循环
}
else
if(b>d) //如果减数b>差c
{
a=b; //减数b做新的被减数a
b=d; //差c做新的减数b
}
else
a=d; //如果差c>被减数b,则差c做新的被减数a，减数b不变
}
}
}

void GCD::method_illustrate() //穷举法
{
int i,t;
if(a<0||b<0) //如果a<0或b<0,则对a、b求绝对值
{
a=abs(a);
b=abs(b);
}
for(i=1;i<=a||i<=b;i++)
if(a%i==0&&b%i==0) //如果i能整除a且i能整除b
t=i; //t为能同时整除a、b的最大的数，即a、b的最大公约数
cout<<"两者的最大公约数为:"<<t<<endl;
}

void GCD::menu() //打印菜单，每种操作所对应的序号
{
cout<<endl;
cout<<"*********************************************************"<<endl;
cout<<"* *"<<endl;
cout<<"* 求最大公约数 *"<<endl;
cout<<"* *"<<endl;
cout<<"* 可选择的方法: *"<<endl;
cout<<"* 1.辗转相除法 *"<<endl;
cout<<"* 2.辗转相减法 *"<<endl;
cout<<"* 3.穷举法 *"<<endl;
cout<<"*********************************************************"<<endl;
cout<<"* *"<<endl;
cout<<"* 4.退出系统 *"<<endl;
cout<<"* *"<<endl;
cout<<"*********************************************************"<<endl;
}

int main()
{
int m;
GCD gcd; //定义类GCD的对象gcd
gcd.menu(); //先打印菜单
gcd.put_in(); //再输入两个整数a、b
gcd.select =1;
while(gcd.select)
{
cout<<"请输入您需要的操作所对应的序号(1--4)，按回车确认"<<endl;
do
{
cin>>m; //输入要选择的操作所对应的序号
switch(m)
{
case 1:
gcd.method_divide(); //辗转相除法
break;
case 2:
gcd.method_subtract(); //辗转相减法
break;
case 3:
gcd.method_illustrate(); //穷举法
break;
case 4:
gcd.select=0; //退出系统
break;
default:
cout<<"输入错误，请重新输入"<<endl;
}
}while(m!=1&&m!=2&&m!=3&&m!=4); //当所输入的值不在1--4之间时，重新输入
}
return 0;
}