MonoBook

「ユークリッドの互除法」の版間の差分

ビジュアルウィキテキスト
imported>MikeCAT
とりあえず作成
 
imported>Administrator
編集の要約なし
 
(他の1人の利用者による、間の2版が非表示)
1行目: 1行目:
'''ユークリッドの互除法'''とは、2個の正の[[整数]]の[[最大公約数]]を比較的高速に求める[[アルゴリズム]]である。
'''ユークリッドの互除法'''（[[英語]]：euclidean algorithm）とは、2個の正の[[整数]]の[[最大公約数]]を比較的高速に求める[[アルゴリズム]]である。


==実装例==
==実装例==
===シンプルな実装===
===C言語===
[[C言語]]によるシンプルな実装。
<source lang="c">
<source lang="c">
int gcd(int a,int b) {
int gcd(int a, int b) {
return b==0?a:gcd(b,a%b);
    return b == 0 ? a : gcd(b,a%b);
}
}
</source>
</source>


===再帰を使わない実装===
C言語による[[再帰]]を使わない実装。
<source lang="c">
<source lang="c">
int gcd(int a,int b) {
int gcd(int a, int b) {
if(a<=0 || b<=0)return 0;
    if (a <= 0 || b <= 0) {
while(b>0) {
        return 0;
int t=a%b;
    }
a=b;
    while (0 < b) {
b=t;
        int t = a % b;
}
        a = b;
return a;
        b = t;
    }
    return a;
}
}
</source>
</source>


===[[Haskell]]による実装===
===Haskellによる実装例===
[[Haskell]]で書くとこんな感じである。
<source lang="haskell">
<source lang="haskell">
gcd a b = if b<=0 then a else gcd b (mod a b)
gcd a b = if b<=0 then a else gcd b (mod a b)
</source>
===OCamlによる実装例===
[[OCaml]]で書くとこんな感じである。
<source lang="ocaml">
let rec gcd a = function
    | 0 -> a
    | b -> gcd b (a mod b);;
</source>
===F#による実装例===
[[F Sharp|F#]]で書くとこんな感じである。
F#は[[OCaml]]から派生した[[プログラミング言語]]なのでほとんど違いはない。
違いは[[除算]]の[[演算子]]が「mod」ではなく「%」なくらいである。
<source lang="fsharp">
let rec gcd a = function
    | 0 -> a
    | b -> gcd b (a % b);;
</source>
</source>


30行目: 52行目:
* [[最大公約数]]
* [[最大公約数]]
* [[最小公倍数]]
* [[最小公倍数]]
[[category: アルゴリズム]]
[[category: 算数]]
「https://monobook.org/wiki/ユークリッドの互除法」から取得