辗转相除法求最大公约数,非goto

 1 #include<iostream>
 2 using namespace std;
 3 //不推荐用goto,当然用它更快
 4 //辗转相除法求两数的最大公约数
 5 int gcd(long int a,long int b){
 6     int x=a<b?a:b;
 7     //获得较小者,用来做循环的约束值
 8     
 9     for(int i=0;i<x;x++){
10         //循环
11       if(a>b){
12           int r=a%b;//取余数
13           if(r==0){//能否整除判断
14              return b;//可以便输出
15           }else{//否则进行下一轮的算法
16               a=b,b=r;
17           }
18       }else if(a<b){//下面一样
19           int r=b%a;
20           if(r==0){
21               return a;
22           }else{
23               b=a,a=r;
24           }
25       }else{//两数相等的,直接输出其中一个
26           return a;
27       }
28    }
29 }
30 
31 int main(){
32     int y=0;y=gcd(156,176);
33     cout<<"156和176的最大公约数是:"<<y;
34 
35     return 0;
36 }

 原理: 欧几里得,辗转相除法, a 和 b 的最大公约数,等于 a除b 后的余数和b的最大公约数。 a 除 b 余 c,b 和 c 的最大公约就是 a 和 b 的

如果您认为这篇文章还不错或者有所收获,您可以通过扫描一下下面的支付宝二维码 打赏我一杯咖啡【物质支持】,也可以点击右下角的【推荐】按钮【精神支持】,因为这两种支持都是我继续写作,分享的最大动力


辗转相除法求最大公约数,非goto
上一篇:jMeter 打开项目时遇到错误消息 CannotResolveClassException: com.blazemeter.jmeter.RandomCSVDataSetConfig


下一篇:实现一个网易云音乐的 BottomSheetDialog