拡張ユークリッド互除法
ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方法です。 これについては，ユークリッドの互除法の項で説明しました。ここでは，その発展系の一つで色々なところでよく使われている，拡張ユークリッド互除法について説明します。 ユークリッドの互除法は２つの自然数 x，y の最大公約数を効率的に計算する方法でした。 例えば，GCD(13,5) を計算するのに， 13=2*5+3 5=1*3+2 3=1*2+1 2=2*1 を求めて，GCD(13,5)=1 とするものでした。今の場合この計算は，全く自明で，互除法は不要な感じがします。しかし，少し視点を変えるとそうとも言えません。上の式のうち最後の項を除いて，それぞれ，移項すると， 13-2*5=3 5-1*3=2 3-1*2=1 が得られます。ここで，３行
拡張版ユークリッドの互除法
よくある問題 ところで問題です。29リットル入るバケツと17リットル入るバケツがあります。この2つのバケツを使って、別のバケツに1リットルの水を入れなさい。 頭の軟らかさを競うテレビ番組でおなじみですね。これが蚊取り線香になったり縄になったりしますが、すべて同じ問題です。この問題は頭の軟らかさは関係がありません。ユークリッドの互除法を知っているかどうかで決まります。知識の問題です。多くの場合、「頭のやわらかさ」というのは宣伝文句であり、そこにはなにがしかの法則・アルゴリズムが存在します。 この問題の本質は、以下の数式で表すことができます。 29x + 17y = 1 となる(x,y)の組を見つけること このとき、(x,y)のどちらかは必ず負です。当たり前ですが。 拡張版ユークリッドの互除法の実際 ちょっと気づいてほしいのですが、もし、この問題が正しいのならば、全ての数は 29 と 17 で
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
