第9講 ユークリッド互除法

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

ユークリッド互除法とは、最大公約数を求める方法です。
公約数というのは、共通の約数のことです。
そして、約数とはその整数を割りきることの出来る数です。
ですから、ですから(18,12)の公約数は、
18も12も割り切ることの出来る数のことです。
1,2,3,6
が公約数です。
そして、最大の公約数(今の例では6)のことを最大公約数というのです。
ユークリッド互除法では次のようにして最大公約数を求めます。
例えば、(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)
A (72,100)
B (180,588)





第8講第9話へ
 第2話へ

004

eclipse c++ 入門
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
vc++講義へ
vba 2013 2010 2007 入門へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座へ
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座へ
専門用語なしの C言語 C++ 入門(Visual C++ 2010で学ぶ C言語 C++ 入門)
専門用語なしの excel vba マクロ 入門 2013 2010 2007 対応講義 第1部
eclipse java 入門へ
excel 2016 vba 入門第1部へ
本サイトトップへ