2022 年 11 月 17 日

C, C++, Python, ZJ解題

a024: 最大公因數(GCD)

2022.11.17 PM 10:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=a024
出題者 : jiangsir
標籤 : 遞迴、迴圈、數學
難易度 : 3

解題想法 : 
GCD的虛擬碼如下 :
GCD(a,b){
 if b=0 then return a
 else return GCD(b,a%b)
}
詳細證明方式可以查看以下影片，說明的很清楚 :
https://www.youtube.com/watch?v=fGesPF3QA1U

若已了解GCD的運作方式，即可輕鬆的解決此題。

//C language
//solution link(含註解): 

#include<stdio.h>
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    if(a<b){
        int tmp=a;
        a=b;
        b=tmp;
    }
    printf("%d\n",gcd(a,b));
    return 0;
}

//C++ language
//solution link(含註解): 

#include<stdio.h>
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    if(a<b){
        int tmp=a;
        a=b;
        b=tmp;
    }
    printf("%d",gcd(a,b));
    return 0;
}

## Python language
## solution link(含註解): 

def gcd(a,b):
    if b==0: return a
    return gcd(b,a%b)
a,b=map(int,input().split())
if a<b: a,b=b,a 
print(gcd(a,b))

相關文章

發佈留言取消回覆