第17講 ユークリッド互除法
第1話 ユークリッド互除法とは?
ユークリッド互除法とは、最大公約数を求める方法です。
例えば、(48,66)の最大公約数を求めるには、
66を48で割り余りを求めます。
余りは18です。
次に、48を18で割った余りを求めます。
48を18で割った余りは、12です。
次に18を12で割った余りを求めます。
それは6です。
次に12を6で割った余りを求めますが、余りは0です。
この余りを0にする割る数6が最大公約数というわけです。
つまり、(a,b)の最大公約数を求めるには、
大きい方を小さい方で割ります。
そして、余りが0でない場合は、今割った割る数を余りで割ります。
そして、余りが0でないときはやはり今割った割る数(つまり一つ手前の余り)をその余りで求めます。
以降同じことを繰り返して、余りが0になるときの割る数が最大公約数というわけです。

66÷48=1・・・18
48÷18=2・・・12
18÷12=1・・・6
12÷6=2 ・・・0
よって、(48,66)の最大公約数は6
割る数が割られる数になることを繰り返すので、
o
互除法です。

ユークリッド互除法は、
紀元前300年前に書かれた『ユークリッド原論』に記載されているそうです。
『ユークリッド原論』は、19世紀までは聖書の次ぎに読まれた世界のベストセラーです。


ではプログラミングに入る前に、
いくつか手計算で求め、
プログラムの神髄を掴んでください。
何度も述べてきましたが、
プログラムを組むために大切なことは、
自分が取り組む対象・事象の本質を掴むことです。
数独問題作成ソフトを作る場合には、数独を手で解いて数独の肝要な本質を把握する必要があります。
将棋ソフトなら、将棋を徹底的に指してどれがよい手で、どんな手が敗因になるのかを掴むことが必要です。
将棋の徹底研究なしに強い将棋ソフトは作れません。
(コンピュータ将棋選手権で優勝したことのあるBonanzaは、将棋の初心者が開発したそうですが、
これは例外です。基本的に、コンピュータ将棋選手権を制しているソフトを作っている人は将棋の上段者です。)
日産で最初にマイクロコンピュータによる自動車のエンジン自動制御を開発した人は、
車を愛し、自動車やそのエンジンの仕組みに精通していた人であるといいます。
エンジンの構造、燃焼の仕組みなどを知らずに、エネルギー効率のよい自動制御プログラムを組むことは出来ません。
燃費のよい制御プログラムを組むには、自動車のことをよく知っていなければならないのです。
プログラムを組む前に、事象の本質を研究して掴むことが必要です。

問題 
o
これを参考にして次の組の最大公約数を求めて下さい。
① (396,126)
② (72,100)
③ (180,588)



第16講第6話へ
 第2話へ

a

eclipse c++ 入門講義第1部へ

魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第1部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ