スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


--/--/--(--)/--:--:--:コメント(-)|トラックバック(-)

ユークリッドの互除法


皆さんは、ユーグリッドの互除法というものをご存知でしょうか?

この方法を使うと、
2つの自然数の最大公約数を求めることができます。

テストで大きな分数を計算する際に、地味に役に立ったりします。
いや、なかなか面白い。
(ほかにも用途はあるけど、高2のテストで役に立つのはこれくらい)

また、別の機会に紹介しますが、これでプログラムを組めたりします。


ではまず、説明。
これ以降文字数は、すべて自然数とさせていただきます。


その前に予備知識。


aをbで割った時、余りがc出るとします。
これを式にすると

a≡c(mod b)
と表します(=と≡間違えてる可能性がりますが、≡で行きます)


ユークリッドの互除法とは以下のもの。

2つの数、AとBがあります。
A≡C(mod B)
B≡D(mod C)
C≡E(mod D)



これを余りの部分が0になるまで繰り替えします。


少し日本語に翻訳すると、

2つの数、AとBがあります。
AをBで割るとC余ります。
この時点では、
Aは割られる数。
Bは割る数。
Cはあまり
という扱いになります。

そして、この、
BをCで割ると、新しいあまりDが出ます。
こうすると、今回は、
Bが割られる数。
Cが割る数。
Dがあまりになります。


さらに日本語にすると…

1回目は、普通に余りを出す。
2回目以降は、
前回の数を以下のように扱い、計算する。

前回の扱い今回の扱い
わられる数割られる数
余り割る数

これを余りが0になるまで繰り返します。



こうしていくと、自然数である限り、どんな数でも余りは0になります。
余りが0になるときの、割る数が2つの数の最大公約数です。

もし最後が
a≡0(mod 1)
となったら、2つの数の最大公約数は1なので、
実質なしと言ってもいいでしょう。

簡単にエクセルでイメージ図を作ってみました。
2011y05m17d_215843604.png
めんどくさいので、途中から雑になってますが、
最終的に正方形を作るようなイメージで。

とか、どこかのサイトには書いてあったような気がします。

実際にやってみた方が早いような気がしますが。

実例
2010と19980の最大公約数を求めよ
2010≡12(mod 1998)
1980≡6 (mod 12)
12=0 (mod 2)
よって、最大公約数は6



後半に行くにつれて、だいぶ雑になってますが、
気になったら、別のサイトとかで学んだ方がいいような気も……

これで理解できるならいいんだけど。

ちなみに、作ったプログラムで算出しましたから、これであっているはずです。

イメージさえつかめれば、自分でプログラム組めるはずだけど、
次回は、自分の作ったそのプログラムソースを公開して、しくみでも解説してみます。(誰得



裏話。
エクセルのやつで、制作ミスってストレスが( ゚Д゚)ってなっていたり、
a≡c(mod b)をa%b=cとか書きかけて、かなり大変だったという。
後半の日本語的文法や、まとめ方が適当なのは、集中力が切れたから。
2011/05/17(火)/22:14:24:コメント(0)|トラックバック(0)
コメントの際の注意。
・宣伝・同じ内容の連投は削除等の対象。
・質問等は、しっかり考えてから行ってください。
 聞けば何でも教えてくれるというのは間違いです。
・コメントの返信方法が確立していないので、返せない場合があります(´・ω・`)
・http://とhttps://が禁止ワードとなっています。
 コメント本文のURL入力は頭のhを抜くなり、なんなりしてください
name:

title:

Mail_address:

URL:

comment:

パスワード:

管理者にだけ表示を許可する
トラックバックURL

プロフィール

猫と馬

Author:猫と馬
相互リンク希望の方はこちらにコメしてください
閲覧推奨環境
現在不明

フリーエリア

blogram投票ボタン
fc2ブログランキング 人気ブログランキングへ

↑から買い物をしてくれると管理人が喜びます

カテゴリ

リンク

月別アーカイブ

リンク・記事の紹介(引用)について。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。