[ 掲示板に戻る ]
記事No.28313に関するスレッドです
★ (No Subject) / わー
整数の問題です
(1)の青線のところがよく理解できません
(2)は互除法の使い方がわからずどういうふうに計算してるかわかりません。
解説よろしくお願いします。
No.28313 - 2014/08/18(Mon) 00:07:02
☆ Re: / angel
(2)から先に。
どこかで、互除法の具体的な説明を見ていないですか?

簡単に言うと、大小2数の組の中で、大を「大÷小の余り」に次々置き換えていくことで、最終的に最大公約数を求める方法です。

例えば、888,210 の2数であれば、
(888,210)→(210,48)→(48,18)→(18,12)→(12,6)→(6,0)
というような推移になります。
※まず、888÷210=4...48だから、888を48に置き換える
　次に、210÷48=4...18だから210を18に置き換える
　…という計算。
最終的に、一方が0になれば終了、もう片方の数 ( この例では6 ) が最大公約数です。実際、888=6×148,210=6×35ですから、ちゃんと合っています。
※割り算が割り切れれば、次は当然0が出てくるので、割り切れた所で止めても同じです。( 割り切った数が最大公約数 )

でまあ、なぜこんな方法が使えるかと言うと、この「置き換える」という操作をしても2数の最大公約数が変わらないこと、数がどんどん小さくなっていく ( だから必ず答えに辿り着ける ) こと、そういった性質を持つからです。
No.28315 - 2014/08/18(Mon) 04:25:26
☆ Re: / わー
ありがとうございます。
No.28316 - 2014/08/18(Mon) 16:19:50
☆ Re: / わー
ありがとうございます。理解できましたm(_ _)m
No.28317 - 2014/08/18(Mon) 16:20:22