教科書案2 情報2 2章

アルゴリズムとデータ構造 §

プログラムを正しく作成し動かすには、それが実現しているアルゴリズ ムや、内部で使っているデータ構造についてについて、きちんと考える 必要がある。以下では、さまざまなアルゴリズムやそれらが用いるデー タ構造、アルゴリズムの計算量について学んで行こう。

アルゴリズムとその考え方 §

これまでに学んで来たように、コンピュータは、プログラムによって指 定された手順をその通りに実行する。ある問題を解く手順が、次のよう な性質を持つとき、それをアルゴリズムと呼ぶ。

• 有限個の処理で記述できている。

• 各処理にあいまいさがない。

• 必ず結果を出して終了する。

コンピュータのプログラムは、それを書き終わった時点でその大きさは 有限であり、各処理にあいまいさはない。これに加えて、必ず終了する ように書かれているプログラムは、アルゴリズムを実現しているものと 言える。

ただし、プログラムによっては必ず終了するとは限らない。たとえば、 OSのプログラムはいつまでも実行し続けるように作られているし、プロ グラムに間違いがあって同じ計算を限りなく繰り返す状態になってしま うこともある。そのようなプログラムはアルゴリズムには対応していな い。

アルゴリズムを記述するときは、直接プログラム言語でプログラムとし て書くと、細かい処理が書かれているため分かりにくくなりやすい。そ のため、アルゴリズムを記述するときは、もっと抽象化された(大観的 な書き方のできる)、人間に読みやすい記法を使うことが多い。

ここでは、アルゴリズムを記述する方法として疑似コードを用い る。疑似コードとは、JavaScriptなどのプログラミング言語に似ている が、構造や動作を普通の日本語に近い形で書き表したものである。

たとえば、既に学んだ「割算を使わずに整数が奇数か偶数か判定する」 プログラムを疑似コードで改めて考えてみよう。まず最初に、大まかな 流れが分かるような疑似コードを記述する。

 整数xを読み込む。
 {xが0以上の間、xから繰り返し2を引いていく。}
 {xが0かどうかに応じて、奇数か偶数かを出力。}

ここで、中かっこに囲まれた部分は、まだ概要を書いたレベルであるこ とを表している。次に、それぞれの部分をもっと具体的に書き直してい くと、プログラムに対応する疑似コードになる。ここで使っている書き 方では、代入は「←」で表し、等しいことは(普通に)「=」で表している。

 整数xを読み込む。
 x > 1 である間繰り返し、
   x ← x - 2。
 繰り返し終わり。
 もし x = 0 ならば、
   「xは偶数です」と出力する。
 そうでなければ、
   「xは奇数です」と出力する。
 枝分かれ終わり。

このように、最初は大まかに考えて記述し、次第に細かい部分まで正確 にしてゆく方法を段階的詳細化と呼び、アルゴリズムを考えると きに有効な方法である。

演習: 次のことを行うアルゴリズムを、疑似コードで記述してみよ。

• 正の整数xとyを読み込み、xがyで割り切れるかどうか判定する。 ただし、割り算演算と剰余演算を使わないこと。

• 正の整数xとyを読み込み、x×yを求める。ただし、乗算演算を使 わないこと。

繰り返しを含むアルゴリズム §

繰り返しを含んだアルゴリズムでは、先に述べた「永遠に同じ計算を繰 り返す」状態にならないように注意する必要がある。それには具体的に どのように考えればよいか学ぼう。

例として、2つの整数x、yの最大公約数を求めるアルゴリズムを取 り上げる。最大公約数とは何かについて確認しておこう。

• ある整数の約数とは、その整数を割り切ることができるような整 数をいう。

• 2つの整数の公約数とは、それらをともに割り切ることができる ような整数をいう。

• 最大公約数とは、公約数のうちでもっとも大きいものをいう。

たとえば、12の約数は「12、6、4、3、2、1」であり、18の約数は「18、 9、6、3、2、1」であるので、12と18の最大公約数は「6」ということに なる。

2つの整数の最大公約数を求めるアルゴリズムを、次のように考える。

 整数xを読み込む。
 整数yを読み込む。
 x ≠ y である間繰り返し、
   {xとyの大きい方から小さい方を引く}
 繰り返し終わり。
 xを出力する。

さらに、「xとyの大きい方から小さい方を引く」部分を具体化すること で、全体として次のようになる。

 整数xを読み込む。
 整数yを読み込む。
 x ≠ y である間繰り返し、
   もし x > y ならば、
     x ← x - y。
   そうでなければ、
     y ← y - x。
   枝分かれ終わり。
 繰り返し終わり。
 xを出力する。

これをJavaScriptプログラムに直すと次のようになる。

 x = parseInt(prompt('数1を入力してください。'));
 y = parseInt(prompt('数2を入力してください。'));
 while(x != y) {
   if(x > y) {
     x = x - y;
   } else {
     y = y - x;
   }
 }
 document.write('最大公約数は' + x + 'です。<br>');

計算の途中経過を観察したければ、whileの次の行に次のような行を 挿入することで、xとyの値の変化を表示させられる。

 document.write('x=' + x + ' y=' + y + '<br>');

たとえば、18と12についてこのアルゴリズムを実行すると、「18、12」 →(18から12を引く)→「6、12」→(12から6を引く)→「6、6」のように 進み、両方が等しくなって繰り返しを終わる。このとき、確かに最大公 約数「6」が求まっている。

なぜこの方法でうまく行くのだろうか? 整数XとYの最大公約数がLだと すると、XとYを次のように書き表せる。(ただし、AとBは1以外に共通の 約数を持たない。もし持ってしまうと、それをくくり出すことでLより 大きい公約数が求まるため、Lが最大公約数だということに矛盾する。)

 X = A × L
 Y = B × L

ここで、仮にXの方が大きいとすると、大きい方から小さい方を引くこ とで次のようになる。すなわち、大きい方から小さい方を引いても、両 者の最大公約数は変化しない。

 X - Y = (A - B) × L  →新しいX
 Y = B × L

さらに、次のような性質があることにも注意しよう。

• 毎回、大きい方から小さい方を引くのだから、XかYのどちらかは 前よりも小さくなる。

• 毎回、大きい方から小さい方を引くのだから、引いた結果が0以 下になることはない。

• したがって、繰り返しはいつかは終わる(整数が永遠に減りつづけて、 しかも0以下にならないということはあり得ないから)。

繰り返しが終わった時は上のAとBが等しく、しかもともに1になってい る(1より大きいなら、Lが最大公約数であることに矛盾する)。したがっ て、XおよびYがLに等しい。

このように、繰り返しを含むアルゴリズムは、次の2つのことがらに注 意をして構成するのがよい。

• 繰り返しの中で変化しないことは何かを確認する。(上の例では、 XとYの最大公約数は大きい方から小さい方を引いても変化しないという 性質がこれに相当した。)

• 繰り返しの中で何らかの一定方向の変化が起こることを確認する。 (上の例では、1回の繰り返しごとにXまたはYは必ず減るという性質がこ れに相当した。)

• 上記の変化の結果、必ず繰り返しが終了することを確認する。 (上の例では、XやYは減って行くが0以下にはならないという性質がこれ に相当した。)

演習: 次のJavaScriptプログラムは、乗算演算を使わずに整数xとyの積 を求めるものである(ただしx、yには正の整数を入力する必要がある)。 なぜこれでxとyの積が求められるのか説明してみなさい。

 x = parseInt(prompt('数1を入力してください。'));
 y = parseInt(prompt('数2を入力してください。'));
 result = 0;
 while(x > 0) {
   result = result + y;
   x = x - 1;
 }
 document.write('積は' + result + 'です。<br>');

2分探索による求解 §

繰り返しを含んだ汎用的なアルゴリズムの例として、2分探索によ る求解を学ぼう。関数f(x)について、等式「f(x) = 0」を満たすような xを求めることを求解と呼ぶ。2分探索が使えるためには、f(x)が次の条 件を満たす必要がある。

• f(l) < 0であるような値l、f(u) > 0 であるような値uがある (ただしl < u)。

• 区間[l,u]の範囲内の任意のa、bについて、a < b のとき常に f(a) < f(b)である。

たとえば、Aを正の数として、「f(x) = x*x - A」を考える。「f(x) = 0」になるのはx = √A のときだから、このf(x)に対して2分探索を行う ことで、Aの平方根を求めることができる。

上の条件について確認しよう。「f(0) = -A」だからlとしては0を用い ることができる。また、「f(A+1) = A*A + A + 1」だからuとしてはAを 用いることができる。そして、この2次関数のグラフを考えると、区間 [0,A]ではxが大きくなるほど値も大きくなる。

具体的に、2分探索探索で2の平方根を少数点以下5桁まで求めるアルゴ リズムの疑似コードを書くと、次のようになる。

 数値aを入力する。
 l ← 0。
 u ← a+1。
 u - l > 0.00001 である間繰り返し、
   h ← (l + u) / 2
   もし h*h - A > 0 ならば、
     u ← h。
   そうでなければ、
     l ← h。
   枝分かれ終わり。
 繰り返し終わり。
 lを出力する。

これをJavaScriptに直したものも示しておこう。

 a = parseInt(prompt('数を入力してください。'));
 l = 0;
 u = a + 1;
 while(u - l > 0.00001) {
   h = (l + u) / 2;
   if(h*h - a > 0) {
     u = h;
   } else {
     l = h;
   }
 }
 document.write(a + 'の平方根は' + l + 'です。<br>');

なぜこのアルゴリズムで根が求まるのだろう? 繰り返しに入る直前では、 解は区間[l,u]の中にある。そして、繰り返しの中ではlとuの中間点hを 求め、f(h) > 0 であればuをh、そうでなければlをhで置き換える。と いうことは、置き換えた後も解が区間[l,u]の中にあるという性質は維 持されている。そして、繰り返し1回ごとに区間の幅は半分ずつになる ので、いつかは0.00001以下になって繰り返しが終わり、その時も解は 区間[l,h]の中にある。言い替えれば、解が誤差0.00001以下で求まった ことになる。

このアルゴリズムに対する検討でも、前に延べた、(1)繰り返しの間変 わらないものに注意する、(2)繰り返しによる一定方向の変化に注意す る、(3)その一定方向の変化の結果として繰り返しが止まることに注意 する、という3点が重要となっていることを確認しよう。

ところで、この計算で平方根が「求まった」というのに抵抗がある人が いるかも知れない。おおよその近似値が分かるだけではないのか? しか し、コンピュータ上での少数点つき数の演算は有限の桁数で行われてい るので、常に近似値であると考えるのがよい。そもそも、多くの 数の平方根は無理数であり、何万桁計算してもそれで「ぴったり正確」 ということは無いのことも注意しておく。

演習: 次のようなJavaScriptプログラムを書いて動かせ。

• 数aを入力し、その立方根を計算する。

計数ループとfor文 §

アルゴリズムやプログラムで頻繁に出て来るパターンとして、数を順に 数えながらの繰り返しがある。たとえば、「与えられた整数Nの階乗を 求める」プログラムを考えよう。Nの階乗とは1からNまでの整数を順に 掛けたものであり、たとえば5の階乗であれば次のようになる。

 1 × 2 × 3 × 4 × 5 = 120 

階乗を計算するには、たとえばiという変数を用意しておき、それを1、 2、…、Nまで変化させながらその値までの積を用意してゆけばよい。 これを疑似コードにすると、次のようになる。

 nを入力する。
 fact ← 1。
 i ← 1。
 i ≦ n である間繰り返し、
   fact ← fact * i。
   i ← i + 1。
 繰り返し終わり。
 factを出力する。

この繰り返しは、変数で数を順に数えながら一定値まで繰り返すことか ら、計数ループとも呼ぶ。計数ループはよく使うため、もっと簡 単に次のような書き表し方をすることが多い。

 nを入力する。
 fact ← 1。
 iを1からnまで1ずつ増やしながら繰り返し、
   fact ← fact * i。
 繰り返し終わり。
 factを出力する。

この場合、繰り返し方として(1)最初の値、(2)繰り返しの条件、(3)幾 つずつ増やすか/減らすかをまとめて指定することになる。JavaScript でも、計数ループをこのように簡潔に書くための構文としてfor文 が用意されている。for文の形は次のようなものである。

 for(初期設定; 条件; 更新) {
   動作…
 }

ここで、「初期設定」は通常、数えるための変数を最初の値に設定する 代入を入れる。上の例では「i = 1」になるだろう。「条件」はwhileの 条件と同じで、この条件が成り立つ間繰り返すことを意味する。上の例 では「i <= n」になるだろう。「更新」は通常、数えるための変数を次 の値に進める代入を入れる。上の例では「i = i + 1」になるだろう。 なお、「更新」は繰り返し本体の動作が終わった後で実行され、更新に 続いて次の繰り返しを行うかどうかを「条件」に基づいて判断する。

for文を用いて上の疑似コードをJavaScriptに直したものを示す。

 n = parseInt(prompt('数を入力してください。'));
 fact = 1;
 for(i = 1; i <= n; i = i + 1) {
   fact = fact * i;
 }
 document.write(n + 'の階乗は' + fact + 'です。<br>');

演習: 次のようなJavaScriptプログラムを書いて動かせ。

• 正の整数nとr(ただしn > r)を読み込み、nCr (n個の中から順番 を考えずにr個のものを取り出す組合せの数)を計算するプログラム。

配列を用いたアルゴリズム §

アルゴリズムの中には、一連の値が並んだものを取り扱うものが多数あ る。そのようなアルゴリズムを記述するために、多くのプログラミング 言語は、値の並びを扱うために配列と呼ばれる機能を備えている。

配列では、並んだ値が何番目のものかを表す指定を[ ]の中に書いて、 たとえばaが配列だとすると、a[0]、a[1]などのようにあらわす。配列 では、この番号をつけた一つひとつの要素に変数と同じように値を代入 したり、そこから値を取り出したりできる。

上の例のように、コンピュータでは番号は0からつけることが多い。し たがって、要素数(並んだ値の個数)が10であれば、a[0]、a[1]、…、 a[9]までの要素を使うことができる。

また、JavaScriptでは、配列もオブジェクトであり、要素数はlengthと いうプロパティに格納されている(つまり、配列aの要素数はa.lengthで 参照できる)。一般に、配列aで使える添字の範囲は0からa.length-1ま でということになる。

JavaScriptで配列を作り出す方法はいくつもあるが、代表的なものを説 明しておく。

• a = [4, 3, 1, 2]; --- 角かっこの中に値を「,」で区切って並 べると、並べた値をこの順に格納した要素を持つ配列が作り出される。

• a = new Array(5); --- 「new Array(個数)」という書き方で、 指定した個数の要素を持つ配列が作り出される。この時は、すべての要 素は、nullという、「まだ何も入っていない」ことを表す特別な値が格 納された状態になっている。上の例は「a = [null, null, null, null, null];」と同じことになる。

• a = 'This is a pen'.split(' '); --- 文字列のsplit()メソッ ドを使うと、文字列を指定した文字のあるところで切り分け、分けたそ れぞれの部分(文字列)を要素とする配列が作り出される。上の例は「a = ['This', 'is', 'a', 'pen'];」と同じことになる。

例として、数値の並びを配列に読み込み、その合計と平均を求めるアル ゴリズム考えよう。まず大まかな疑似コードを示す。

 {数値の並びを配列aに読み込む。}
 {変数totalに合計を求める。}
 {変数averageに平均を求める。}
 totalとaverageを出力する。

数値の並びを読み込むには、文字列を読み込んでsplit()で分けて配列 にし、それぞれの要素を数値に変換する。合計を求めるには、変数 totalを最初0にしておき、配列の要素を順に「足し込んで」行けばよい。 平均は合計を要素数で割れば求まる。これらをそれぞれ具体的にしたも のを次に示す。

 a ← 文字列を空白で区切って配列に読み込む。
 iを0からa.lengthの手前まで1ずつ増やしながら繰り返し、
   a[i] ← a[i]を数値にしたもの。
 繰り返しおわり。
 total ← 0。
 iを0からa.lengthの手前まで1ずつ増やしながら繰り返し、
   total ← total + a[i]。
 繰り返しおわり。
 average ← total / a.length。
 totalとaverageを出力する。

具体的になったので、この疑似コードをJavaScriptに直してみる。「あ る値の手前まで」の繰り返しには、for文で条件として「<」を使えばよ いことに注意。

 a = prompt('数を空白で区切って入力してください。').split(' ');
 for(i = 0; i < a.length; i = i + 1) {
   a[i] = parseFloat(a[i]);
 }
 total = 0;
 for(i = 0; i < a.length; i = i + 1) {
   a[i] = total + a[i];
 }
 average = total / a.length;
 document.write(a + 'の合計は' + total +
                '、平均は' + average + 'です。<br>');

演習: 配列を使って次のようなプログラムを作りなさい。

• 数値の並びを読み込み、最大値と最小値を出力する。

• 2つの数値の並びを読み込み、平均値が大きい方を出力する。

データ構造の工夫 §

プログラムの中で、どのようなデータをどのような形で保持しておくか ということがら全般をデータ構造とよぶ。データ構造を工夫する ことで、込み入ったアルゴリズムを簡単なものにしたり、時間の掛かる アルゴリズムを速くしたりできることがある。

例として、与えられた整数N未満の素数をすべて出力するアルゴリズム を考えてみる。なお、素数とは、1とその数自身以外では割り切れない ような数のことを言う。

アルゴリズムとして、素数の候補とする数kを2から順に用意して、それ が素数であるかどうか調べ、素数だったら打ち出すという方針のものを 作ってみる。その疑似コードは次のようになる。

 整数nを読み込む。
 kを2からnの手前まで1ずつ増やしながら繰り返し、
  {sosuにkが素数かどうかの判定結果を入れる。}
  もしsosuならば、kを出力する。
 繰り返しおわり。

素数かどうかの素朴な判定方法として、実際に2からk-1までの数で割っ てみて割り切れるかどうか調べることを考える。その部分の疑似コード は次のようになるだろう。

   sosu ← 真。
   iを2からkの手前まで1ずつ増やしながら繰り返し、
     もし k%i = 0 なら、
       sosu ← 偽。
       繰り返しを抜け出す。
     枝分かれおわり。
   繰り返しおわり。    

なお、\%は剰余演算子(割った余りを計算する演算子)である。また、k がiで割り切れた時には、もうkは素数でないと分かったので、それ以上 別の数で割ってみる必要がないので「繰り返しを抜け出す」という命令 で一番内側の(順番に割ってみる)繰り返しを終らせている。

また、sosuという変数には論理値(「はい」か「いいえ」かどちら かの値)を入れている。sosuは最初「真」(はい)だが、どれかの整数で 割り切れることが分かったら、そのとき「偽」(いいえ)を入れている。 そこで、最後まで来たときにまだ「真」が入っていれば、いちども割り 切れなかったのでkは素数だと分かる。逆に「偽」が入っていれば、い ずれかの整数で割り切れたのでkは素数ではない。

このような変数の使い方をフラグ(旗)と呼んでいる。つまり、最 初旗を立てておき、最後に旗を見て、立っていなかったら、(誰が降ろ したかは分からないとしても)誰かが旗を降ろしたことは分かる、とい う考え方を使っている。フラグもデータ構造の工夫の1つである。

この疑似コード全体をJavaScriptに直すと次のようになる。「繰り返し を抜け出す」命令は、JavaScriptでは「break;」という命令になる。

 n = parseInt(prompt('いくつ未満の素数を表示しますか。'));
 for(k = 2; k < n; k = k + 1) {
   sosu = true;
   for(i = 2; i < k; i = i + 1) {
     if(k % i == 0) { sosu = false; break; }
   }
   if(sosu) { document.write(k + ' '); }
 }

このプログラムを動かして、5秒間でいくつくらいまでの素数が表示で きるか調べておこう。

さて、kをさまざまな数で割ってみるときに、2からk-1までのすべての 数で割ってみなくても、k未満の素数で割って見れば十分だということ に注目しよう(たとえば、10で割り切れる数であれば、10の素因数であ る2や5でも割り切れるはずだから)。

そのため、素数と分かった数を打ち出すときに、その数を配列にも記憶 しておき、割ってみる時はこの記憶してある素数の配列にある数だけを 試すようにする。この考え方だと、「sosuにkが素数かどうかの判定結 果を入れる。」部分の疑似コードは次のようになるだろう(memoという 配列にこれまでに見つかった配列を順に入れてあるものと考える)。

   sosu ← 真。
   iを0からmemo.lengthの手前まで1ずつ増やしながら繰り返し、
     もし k%memo[i] = 0 なら、
       sosu ← 偽。
       繰り返しを抜け出す。
     枝分かれおわり。
   繰り返しおわり。    

もちろん、全体のアルゴリズムにも、「最初に空っぽ(大きさ0)の配列 memoを用意する」動作と、素数を打ち出す時に「素数を配列memoに追加 する」動作を増やす必要がある。配列aに要素を追加するのは、 「a.push(追加する値)」で行うことができる。全体をJavaScriptプログ ラムにしたものを次に示す。

 n = parseInt(prompt('いくつ未満の素数を表示しますか。'));
 memo = new Array(0);
 for(k = 2; k < n; k = k + 1) {
   sosu = true;
   for(i = 0; i < memo.length; i = i + 1) {
     if(k % memo[i] == 0) { sosu = false; break; }
   }
   if(sosu) { document.write(k + ' '); memo.push(k); }
 }

このプログラムを動かして、同じ5秒間でいくつ位の素数を表示できる か調べ、先のプログラムの場合と比較してみよう。同じ時間で、より多 くの素数が表示できるようになったはずである。つまり、「見つかった 素数を覚えておく配列」というデータ構造を工夫することで、プログラ ムの効率を高めることができたことになる。

演習: また別のアルゴリズムとして、「エラストテネスのふるい」と呼 ばれるものがある。その概要を以下に説明する。これをJavaScriptのプ ログラムとして完成させてみよ。

• 1. 大きさn(最大の添字がn-1)の配列を用意する。最初はすべて の要素を「印がついていない状態」にしておく(JavaScriptであれば、 new Array(n)で作った配列はすべての要素にnullが入っていることを利 用するとよい)。

• 2. 候補となる数kを2から順にn-1まで1ずつ増やしながら、以下 を実行する。

• 3. もし配列の添字kのところに印がついていなければ、kは素数 なので出力し、続いてkの倍数のところすべてに印をつける(JavaScript で上の方法を使うなら、何でもnull以外の値を入れればよい)。

つまり、配列を順番に調べていくと、素数は「印のついていない次の要 素の番号」として見つかることになる。このアルゴリズムの特徴は、配 列をデータの入れ場所として使うのではなく、単に「k番目の場所に印 がついているかいないか」という形でだけ使うところにある。このよう に、データ構造にはとても多くの工夫のしかたが考えられる。

アルゴリズムと計算量 §

前節で「指定した数未満の素数を出力する」複数のアルゴリズムについ て取り上げ、アルゴリズムによって効率に違いがあることを学んだ。し かしそもそも、「アルゴリズムの速さを比較する」ことはできるのだろ うか?

たとえば2つのアルゴリズムを比較するとき、それらをプログラムに直 して動かせば、所要時間を測ることはできる。しかし、プログラムに直 す時の「腕前」や、測定に用いるコンピュータの「特性」などによって 片方のアルゴリズムが不利になったりするかも知れない。このため、ア ルゴリズム自身の性質に直接基づいた比較ができる方が望ましい。

実際には、このようにアルゴリズム自体の性質としての「速さ」を測る 基準として時間計算量(単に「計算量」と呼ぶこともある)が用い られる。これは、入力として与えられる量(たとえば素数の場合は指定 する数N)と、アルゴリズムが実行するステップの比例関係に基づいてい る。

上で比例関係と言ったが、実際のプログラムの実行時間が入力の量Nに 正比例する(実行時間をTとすると、「T = αN」のようになる)のはごく 単純なプログラムに限られ、ほとんどのプログラムではもっと高次の比 例になる。

たとえば、素数列挙の最初のアルゴリズムでは、N個の候補の数それぞ れについて、2からその数の1つ前までの数で割ってチェックするので、 チェックの回数はおおよそNの2乗に比例する。つまり、Nを2倍にすると プログラムの実行時間は4倍、Nを10倍にすると実行時間は100倍になる。

これに対し、2番目の(出て来た素数を記録しておいて素数だけで割って チェックする)アルゴリズムでは、素数の出現頻度がNの1/2乗程度に押 えられるため、プログラム全体として実行時間はNの1.5乗程度になる。 これは、Nを10倍にしたとき実行時間は30倍程度で済むことになり、1番 目のアルゴリズムよりだいぶ優っていると言える。

今度は例題として、「おつりの計算」を考えてみる。p円のおつりを、 できるだけ少ない枚数の硬貨で渡すにはいくらの硬貨を何枚使えばよい だろうか。

日本のように硬貨の種別が1円、5円、10円、50円、100円、500円となっ ている場合は、大きい金額の硬貨を使えるだけ使い、半端な分は次の金 額の硬貨を使えるだけ使い、…という方法で最も少ない枚数の使い方が 求められる。

しかし仮に、1円、10円、12円という3種類の硬貨がある国だったらどう だろうか。91円のおつりを返すのに、上の考え方だと、まず12円硬貨を できるだけ多く使って7枚で84円、残りは1円硬貨7枚で合計14枚になる。 しかし、12円硬貨を5枚、10円硬貨を3枚、1円硬貨1枚とすれば同じ91円 が9枚で渡せる。金額pを与えられた時、どのようにしたら最も少ない渡 し方が求められるだろうか。

1つの方法は、あらゆる場合をしらみ潰しに調べることである。合計p円 のおつりなのだから、1円硬貨は0〜p枚、10円硬貨は0〜p/10枚、12円硬 貨は0〜p/12枚使うはずである(端数は切捨て)。そこで、次のアルゴリ ズムが考えられる。

 整数pを入力する。
 maisuu ← p+1。
 kekka ← '';
 n1を1からpまで1ずつ増やしながら繰り返し、
   n10を1からp/10まで1ずつ増やしながら繰り返し、
     n12を1からp/12まで1ずつ増やしながら繰り返し、
       もし n1×1 + n10×10 + n12×12 = p
            かつ n1+n10+n12 < maisuu ならば、
          maisuu ← n1+n10+n12。
          kekka ← n1、n10、n12の値を文字列にしたもの。
       枝分かれおわり。
     繰り返しおわり。
   繰り返しおわり。
 繰り返しおわり。
 kekkaを出力。

このアルゴリズムでは、n1が1円硬貨の枚数、n10が10円硬貨の枚数、 n12が12円硬貨の枚数をそれぞれ表している。そして、これらのあらゆ る組合せを調べるには、n1のあらゆる場合を用意する計数ループを作り、 その中にn10のあらゆる場合を用意する計数ループを作り、さらにその 中にn12のあらゆる場合を用意する計数ループを作る。

そしてループの一番内側では、(1)そのn1、n10、n12の組合せがp円になっ ていて、なおかつ(2)合計の枚数がこれまでの最小の枚数maisuuより小 さいならば、maisuuの値を更新し、n1、n10、n12の組合せをkekkaに覚 えておく。maisuuは最初は十分大きな値としてp+1にしておく。これで、 すべての繰り返しが終った後では、kekkaに最少枚数の組合せが記録さ れていることになる。

これをJavaScriptプログラムに直すと次のようになる。条件の「〜か つ〜」は、JavaScriptでは「＆＆」で表すことができる。

 p = parseInt(prompt('合計金額を入力'));
 maisuu = p+1; kekka = '???';
 for(n1 = 0; n1 <= p; n1 = n1 + 1) {
   for(n10 = 0; n10 <= p/10; n10 = n10 + 1) {
     for(n12 = 0; n12 <= p/12; n12 = n12 + 1) {
       if(n1*1 + n10*10 + n12*12 == p && n1 + n10 + n12 < maisuu) {
         maisuu = n1 + n10 + n12;
         kekka = '1*' + n1 + ' 10*' + n10 + ' 12*' + n12;
       }
     }
   }
 }
 document.write(p + 'の分け方: ' + kekka + '<br>');

さて、このプログラムで確かに最も少ない枚数は正しく求まるが、少し 金額pを大きくすると極めて時間が掛かるはずである。このアルゴリズ ムの計算量を概算で考えてみよう。p回実行するループの中にp/10回実 行するループがあり、その中にp/12回実行するループがあるのだから、 ループの一番内側は1/120×p×p×p回実行される。つまり実行時間はお おむねpの3乗に比例することになる。このため、pを10倍にすると、実 行時間は1000倍になってしまう。

どうしたらこれを改良できるだろうか。そもそも、10円硬貨と12円硬貨 の枚数が決まったら、1円硬貨の枚数は残った半端の金額から計算でき るはずである。したがって、あらゆる場合を作り出すのはn10とn12だけ でよい。この考え方で手直ししたアルゴリズムは次のようになる。

 整数pを入力する。
 maisuu ← p+1。
 kekka ← '';
 n10を1からp/10まで1ずつ増やしながら繰り返し、
   n12を1からp/12まで1ずつ増やしながら繰り返し、
     n1 ← p - (n10×10 + n12×12)。
     もし n1 ≧ 0 かつ n1+n10+n12 < maisuu ならば、
        maisuu ← n1+n10+n12。
        kekka ← n1、n10、n12の値を文字列にしたもの。
     枝分かれおわり。
   繰り返しおわり。
 繰り返しおわり。
 kekkaを出力。

このアルゴリズムでは、ループの内側でn10とn12の値に基づいてn1の値 を計算している。ただし、n10とn12が大きすぎるとn1が負の値になるの で、そのような場合は合計p円にできないため除外し、あとは先のアル ゴリズムと同様にして最も少ない枚数の場合を記録する。このアルゴリ ズムをJavaScriptにしたものを次に示す。

 p = parseInt(prompt('合計金額を入力'));
 maisuu = p+1;
 kekka = '';
 for(n10 = 0; n10 <= p/10; n10 = n10 + 1) {
   for(n12 = 0; n12 <= p/12; n12 = n12 + 1) {
     n1 = p - (n10*10 + n12*12);
     if(n1 >= 0 && n1 + n10 + n12 < maisuu) {
       maisuu = n1 + n10 + n12;
       kekka = '1*' + n1 + ' 10*' + n10 + ' 12*' + n12;
     }
   }
 }
 document.write(p + 'の分け方: ' + kekka + '<br>');

このアルゴリズムの計算量を先程と同様に考えると、計算時間はpの2乗 に比例することがわかる。実際に実行させてみても、先のプログラムよ りかなり速くなったことが感じられるはずである。

しかし、このような「しらみ潰し」によるアルゴリズムは、選択する要 素が増えると急激に計算量も多くなる。たとえばここの例では硬貨の種 類数が3だったが、一般に硬貨の種類数がcだとすると、計算量はpのc乗 (改良前のバージョン)ないしpのc-1乗(改良後のバージョン)になる。こ のため種類数が5〜6以上になると、このアルゴリズムでは実用的な時間 では終わらなくなる。

別の方法として、表(つまり配列)を使って合計金額が1〜p円の場合をす べて系統的に求めることで、結果的にp円の場合の最少枚数の組合せを 求めるアルゴリズムについて見てみよう。この方法の基本的なアイデア は次のようなものである。

合計が1円〜i-1円までの場合について表が完成されている状態で、これ をもとにi円の場合の最少枚数になる組合せを求めるには、次の3つのう ちで枚数が最少になる場合はどれかを考えて、表のi円のところに記入 すればよい。

• i-1円の最少枚数の場合に、1円硬貨を1枚追加する。

• i-10円の最少枚数の場合に、10円硬貨を1枚追加する。

• i-12円の最少枚数の場合に、12円硬貨を1枚追加する。

ただし、細かい場合として、次の2点も注意する。

• i-10等が0以下の時は、その場合は考慮しない。

• iがちょうどコインの金額のときは(1枚というのは最少枚数に決 まっているので)無条件にそのコイン1枚の場合を表に記入する。

これらを合わせたアルゴリズムの疑似コードを示す。こんどはmaisuuや kekkaが配列になることに注意。また、コインの金額も配列coinにデー タとして格納する。これにより、この配列を変更するだけでさまざまな コインの種別に対応できる。

 coin ← [1, 10, 12]。
 整数pを入力する。
 maisuu ← 大きさp+1の配列。
 kekka ← 大きさp+1の配列。
 iを1からpまで1ずつ増やしながら繰り返し、
   kを1からcoin.lengthの手前まで増やしながら繰り返し、
     もし coin[k] = i なら、
       maisuu[i] ← 1。kekka[i] ← 「coin[k]のみ」を表す文字列。
     そうでなくて もし coin[k] < i なら、
       もし maisuu[i] = null
           または maisuu[i] > maisuu[i-coin[k]]+1 なら、
         maisuu[i] ← maisuu[i-coin[k]] + 1。
         kekka[i] ← kekka[i-coin[k]]にcoin[k]を追加した文字列。
       枝分かれおわり。
     枝分かれおわり。
   繰り返しおわり。
 繰り返しおわり。
 kekka[p]を出力。

一番内側の「もし」が少し込み入っているが、まだmaisuu[i]に何も記 入されていなければ最初の値なのでとにかく記入し、何か記入されてい ればその記入されている値より少ない枚数で合計i円が作れる場合だけ 記入する、という形になっていて、これにより「枚数が最少になる場合」 が記入される。

このアルゴリズムをJavaScriptに直したものを次に示す。JavaScriptで は条件の「〜または〜」は「||」で表す。

 coin = [1, 10, 12];
 p = parseInt(prompt('合計金額を入力'));
 maisuu = new Array(p+1); kekka = new Array(p+1);
 for(i = 1; i <= p; i = i + 1) {
   for(k = 0; k < coin.length; k = k + 1) {
     if(coin[k] == i) {
       maisuu[i] = 1; kekka[i] = coin[k];
     } else if(coin[k] < i) {
       if(maisuu[i] == null || maisuu[i] > maisuu[i-coin[k]]+1) {
         maisuu[i] = maisuu[i-coin[k]] + 1;
         kekka[i] = kekka[i-coin[k]] + ' ' + coin[k];
       }
     }
   }
 }
 document.write(p + 'の分け方: ' + kekka[p] + '<br>');

このプログラムでも(表示方法は少し違うが)先のものと同じ結果が求め られるが、実行時間は大幅に少ない。アルゴリズムの計算量を考えると、 こちらは実行時間がpの1乗に比例するからである(コインの種類数をc とした一般の場合でも、実行時間はp×cに比例するだけで済む)。

このように、アルゴリズムを工夫することで、劇的に計算時間を短くで きる場合があることは覚えておきたい。一方で、これまでに多くの研究 がなされてきたにも関わらず、高速なアルゴリズムが発見されていない ような種類の問題も多数あることは注意しておく。

演習: 上のプログラムでは、p円までのすべての場合の最少枚数を順次 すべて計算している。プログラムを手直しして最後にすべての場合の結 果を表示させてチェックしてみよ。また、コインの種類を変えたり、もっ と増やして試してみよ。