例题

设计交互程序，输入两个非０正整数a和b，输出它们最大的公约数。例如：输入10 2，输出5。输入7 3，输出1。

这里我们介绍两种求最大公约数的方法。试商法和欧几里的算法。

1.试商法

试商法就是从较小数开始，逐个试除两个数，能同时整除它们的最大数就是最大公约数。它的过程是这样的：

流程图

程序

#include<bits/stdc++.h> using namespace std; int main() { int a,b,x; cin>>a>>b; x = min(a,b); while(x>0){ if( a%x==0 && b%x==0 ){ cout<<x<<endl; break; } x=x-1; } return 0; }

a = int(input('a=')) b = int(input('b=')) x = min(a,b) while(x>0): if( a%x==0 and b%x==0): print(x) break x = x-1

x要同时被a和b两个数整除，这个逻辑关系就是“逻辑与”。

2.欧几里的算法

欧几里得算法就是用大数除以小数取余数，再用除数除以余数，重复到余数为 0，最后那个除数就是最大公约数。

我们通过一个例子来理解这个算法。求48和18的最大公约数。

48 ÷ 18 = 2 …… 12
18 ÷ 12 = 1 …… 6
12 ÷ 6 = 2 …… 0
余数为 0，最大公约数 = 6

流程图

把上面计算思路转换成流程图，它是这样的。

程序

#include<bits/stdc++.h> using namespace std; int main() { int a,b; cin>>a>>b; int x = max(a,b); int y = min(a,b); while(x%y!=0){ int t = x; x = y; y = t%x; } cout<<y<<endl; return 0; }

a = int(input('a=')) b = int(input('b=')) x = max(a,b) y = min(a,b) while( x%y!=0 ): t = x x = y y = t%x print(y)

练习

分别用试商法和欧几里的算法设计一个程序，求三个非0整数的最大公约数。

@程序设计