ユークリッドの互除法 - 版の履歴

2018年10月31日 (水) 03:06にimported>Administratorによる

2018-10-31T03:06:27Z

← 古い版		2018年10月31日 (水) 03:06時点における版
52行目:		52行目:
	* [[最大公約数]]		* [[最大公約数]]
	* [[最小公倍数]]		* [[最小公倍数]]

			[[category: アルゴリズム]]
			[[category: 算数]]

126.212.139.214: /* F#による実装例 */

2014-09-11T16:25:38Z

F#による実装例

← 古い版		2014年9月11日 (木) 16:25時点における版
42行目:		42行目:
	[[F Sharp\|F#]]で書くとこんな感じである。		[[F Sharp\|F#]]で書くとこんな感じである。
	F#は[[OCaml]]から派生した[[プログラミング言語]]なのでほとんど違いはない。		F#は[[OCaml]]から派生した[[プログラミング言語]]なのでほとんど違いはない。
	~~僅かな違いは~~[[除算]]が「mod」ではなく「%」なくらいである。		違いは[[除算]]の[[演算子]]が「mod」ではなく「%」なくらいである。
	<source lang="fsharp">		<source lang="fsharp">
	let rec gcd a = function		let rec gcd a = function

2014年9月11日 (木) 16:25に126.212.139.214による

2014-09-11T16:25:10Z

← 古い版		2014年9月11日 (木) 16:25時点における版
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>

imported>MikeCAT: とりあえず作成

2013-09-05T13:06:48Z

とりあえず作成

新規ページ

'''ユークリッドの互除法'''とは、2個の正の[[整数]]の[[最大公約数]]を比較的高速に求める[[アルゴリズム]]である。

==実装例==
===シンプルな実装===
<source lang="c">
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
</source>

===再帰を使わない実装===
<source lang="c">
int gcd(int a,int b) {
if(a<=0 || b<=0)return 0;
while(b>0) {
int t=a%b;
a=b;
b=t;
}
return a;
}
</source>

===[[Haskell]]による実装===
<source lang="haskell">
gcd a b = if b<=0 then a else gcd b (mod a b)
</source>

==関連項目==
* [[最大公約数]]
* [[最小公倍数]]