=…3=…1=…5=…2÷÷÷÷r15428140n1821542814gcdm70018215428第2部アルゴリズムとプログラムmnrmnr①②図2.3：ユークリッドの互除法のアルゴリズムの計算機向きの表現図2.1：電子計算機の基本構成図2.1に電子計算機の基本構成を示します。大多数の計算機では、計算機が実行できる命令に変換されたプログラムが主記憶装置に読み込まれ、この命令が順次、中央処理装置（Central Processing Unit: CPU）に取り出されて実行されます。このような方式をプログラム内蔵方式、この方式に従う計算機をフォンノイマン型計算機と呼びます。この方式を採用することにより、電子計算機はプログラムを書き換えるだけで様々な処理を実行できる万能機械になりました。有名なアルゴリズムに、ユークリッドの互除法があります。これは、ふたつの整数の最大公約数（ gcd ）を求める手順です。図2.2に示したように、ふたつの整数を割り算し、余りを求めます。次に除数を被除数に、余りを除数にして割り算を行い、余りを求めます。余りが0になったときの除数が最大公約数です。700と182の最大公約数をこの手順で求めると14になります。このアルゴリズムを計算機向きに表現すると図2.3のようになります。被除数と除数を記憶する記憶場所に m と n という名前（変数名）をつけ、CPUで割り算を実行して余りを r と言う名前の記憶場所に保存します（左図）。次に ① n に記憶されている数値を m に記憶した後、② r に記憶されている数値をnに記憶し、m÷nの割り算を実行して余りを r に記憶します。値を記憶場所に記憶させるこの操作のことを「代入」と言います。問題を解く手順のことをアルゴリズム（Algorithm）と言います。その語源は方程式の解き方などをまとめたアラビアの数学者アル＝フワーリズミーの名前です。アルゴリズムを計算機向きの言語で表現したものがプログラムです。主記憶装置中央処理装置(CPU)プログラム制御装置データ演算装置余りが０になったときの除数が最大公約数gcd図2.2：ユークリッドの互除法入力装置出力装置16代入m n CPU n r182 ÷ 154 =1...28 700 182 154700 ÷ 182 =3...154 700 182 154プログラム内蔵方式の計算機ユークリッドの互除法のアルゴリズム変数名主記憶装置（記憶場所）変数主記憶装置CPU変数（記憶場所）
元のページ ../index.html#16