第34講 ユークリッド互除法△ 
第1話 
ユークリッド互除法とは?

ユークリッド互除法とは、最大公約数を求める方法です。
例えば、(48,66)の最大公約数を求めるには、
66を48で割り余りを求めます。
余りは18です。
次に、48を18で割った余りを求めます。
48を18で割った余りは、12です。
次に18を12で割った余りを求めます。
それは6です。
次に12を6で割った余りを求めますが、余りは0です。
この余りを0にする割る数6が最大公約数というわけです。
o
交互に割っていきますから互除法です。

つまり、(a,b)の最大公約数を求めるには、
大きい方を小さい方で割ります。
そして、余りが0でない場合は、今割った割る数を余りで割ります。
そして、余りが0でないときはやはり今割った割る数(つまり一つ手前の余り)をその余りで求めます。
以降同じことを繰り返して、余りが0になるときの割る数が最大公約数というわけです。


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

問題 次の組の最大公約数を求めてください。
① (396,126)
② (72,100)
③ (180,588)







第33講第9話へ 第2話へ


戻る

VC++講義第1部へ
vb講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)