「ユークリッドの互除法」の版間の差分
ナビゲーションに移動
検索に移動
imported>MikeCAT (とりあえず作成) |
|||
1行目: | 1行目: | ||
− | '''ユークリッドの互除法''' | + | '''ユークリッドの互除法'''([[英語]]: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); | |
} | } | ||
</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; | |
− | + | } | |
− | + | while (0 < b) { | |
− | + | int t = a % b; | |
− | + | a = b; | |
− | + | 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> | ||
2014年9月11日 (木) 16:25時点における版
ユークリッドの互除法(英語:euclidean algorithm)とは、2個の正の整数の最大公約数を比較的高速に求めるアルゴリズムである。
実装例
C言語
C言語によるシンプルな実装。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b,a%b);
}
C言語による再帰を使わない実装。
int gcd(int a, int b) {
if (a <= 0 || b <= 0) {
return 0;
}
while (0 < b) {
int t = a % b;
a = b;
b = t;
}
return a;
}
Haskellによる実装例
Haskellで書くとこんな感じである。
gcd a b = if b<=0 then a else gcd b (mod a b)
OCamlによる実装例
OCamlで書くとこんな感じである。
let rec gcd a = function
| 0 -> a
| b -> gcd b (a mod b);;
F#による実装例
F#で書くとこんな感じである。 F#はOCamlから派生したプログラミング言語なのでほとんど違いはない。 僅かな違いは除算が「mod」ではなく「%」なくらいである。
let rec gcd a = function
| 0 -> a
| b -> gcd b (a % b);;