Copyright (C) 2000 DaiichiGakushusha Corporation. All Rights Reserved.
連載 JavaScript入門講座
第2回 アルゴリズムの学習
エデュカーレNo.11 より
筑波大学大学院教授 久野 靖
今回は,繰り返しや配列の扱いを含んだアルゴリズムを取り上げます。
第1回 基本的なプログラム
第2回 アルゴリズムの学習
 <INDEX>
第3回ウェブページに動きをつける
 コンピュータで問題を解くときには,その手順を,入力や出力の指示まで含めてきちんと決める必要がある。問題を解く手順が,有限個の処理で記述でき,各処理にあいまいさがなく,必ず結果を出して終了するとき,その手順を「アルゴリズム」という。
 問題を解くためにプログラムを書いて動かす場合を考えてみよう。プログラムの長さは有限であり,各処理の動作は明確に定まっていて,答えを出して終了するように書く。つまり,アルゴリズムをコンピュータで実際に動かせる形に書きあらわしたものがプログラムになっており,両者は対応していると考えることができる *1
 すべてのアルゴリズムは,(1)順次実行,(2)枝分かれ,(3)繰り返し,の3つの構造を組み合わせて書きあらわせることが知られている。前回の講座で,順次実行(動作を1つずつ順に実行していくこと)と枝分かれ(条件に応じて動作を選択すること)のJavaScriptでの書き方は学んだので,今回は繰り返しを中心に学んでいく。

<script>
n = parseFloat(prompt('数を入力してください'));
tate = n; yoko = 1;
while(Math.abs(tate - yoko) > 0.000001) {
 yoko = 0.5 * (yoko + tate);
 tate = n / yoko;
<………………………………………………………………………………A
}
document.write(n + 'の平方根は' + tate + 'です。<br>');
</script>


結果画面(入力欄に数を打ち込んで,「OK」を選択。)
 1より大きい実数nの平方根√nの近似値を求めるアルゴリズムを考えてみよう。1つの方法として,縦の長さがn,横の長さが1,面積がnの長方形を,面積を一定に保ったまま,縦と横の長さを近づけていくことを考える。そうすると,縦と横の長さがほぼ等しくなったときには,それらの長さはほぼ√nになっているはずである。プログラム1は,この考え方によるアルゴリズムを,JavaScriptで書きあらわしたものになっている。
 1行目では,前回学んだように,変数nに数値を入力している。2行目では,上の考え方にもとづき,変数tateにnの値を,変数yokoに1を,それぞれ代入している。続いて「徐々に縦と横の長さを近づけていく」繰り返しに入る。

繰り返しの書き方
 JavaScriptでは,繰り返しは次の形であらわす。
   while(条件) {
      繰り返す命令…
    }
    ※ ←繰り返しの次の命令…

 条件として指定できるものは,枝分かれをあらわすifと同じである。また,繰り返す命令が何行かにわたってもよいこともifと同じである。実際の繰り返しの実行は次のようになる。
・まず「条件」を調べ,「はい」*2であれば先に進む。
・「繰り返す命令」を実行する。
・再度「条件」を調べ,「はい」であれば先に進む。
・「繰り返す命令」を実行する。
・再度「条件」を調べ,「はい」であれば先に進む。
・「繰り返す命令」を実行する。
  ……
 このようにして何回でも命令が繰り返されるが,条件を調べた結果が「いいえ」になったら,そこで繰り返しは終わり,その先(※の部分)から実行を続ける。

繰り返しの考え方
 プログラム1では,繰り返しの条件は
  Math.abs(tate − yoko) > 0.000001

となっていた。Math.abs(...)は「...の絶対値」をあらわす。つまり,縦と横の長さの絶対値の差が0.000001より大きい間(つまり「縦と横の長さが十分近くない」間),繰り返しが実行され続けることになる。
 次に,繰り返す命令は
  yoko = 0.5 * (yoko + tate);
 tate = n / yoko;

のようになっていた。これは,縦と横の長さの平均を計算してそれを新たに横の長さとし,縦の長さは面積nと新たな横の長さから計算しなおすことを意味している。このようにすることで,縦と横の長さの差はこれまでより小さくなる。
 そして,繰り返しが終わった段階では,縦と横の長さの差は0.000001より小さいので,縦や横の長さと√nとの誤差はこの値未満になっている。そこで,いずれかの値(ここでは縦の長さの値)を結果として出力する。
 このように,繰り返しを含むプログラムは一般に,次のような考え方で構成するとよい。
・「解がまだ求まっていない間」という条件で繰り返す。
・繰り返しの中ではだんだん「解が求まった状態」に近づくように計算をおこなう。

途中経過の観察
 場合によっては,繰り返しの中での値の推移を観察したいこともある(たとえば,思うように解が求まらない場合など)。そのためには,繰り返しの途中に出力命令を挿入してみるとよい。
 プログラム1では,Aの部分に次の行を挿入することで,縦と横の長さが近づいていくようすを観察できる。
    document.write('縦=' + tate + ',横=' + 'yoko + '<br>');
 

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

結果画面(入力欄に数を打ち込んで,「OK」を選択。)
 アルゴリズムの中には,値の並びを扱うものが多くある。プログラミング言語にはこのために,「配列」とよばれる機能がそなわっている。ここでは,配列を使ったプログラムについて取り上げる。

配列とその要素
 配列とは,たくさんの値が並んだものを格納しておき,必要に応じて個々の値(配列の要素)を,参照したり書き換えたりできるような構造である。配列の要素を指定するときは,「何番目の要素であるか」の番号(添字)を指定する。
 JavaScriptでは,変数aが配列をあらわしているとき,それぞれの要素は,a[0],a[1],… のように[ ]の中に添字を指定してあらわす(a[i+1]などのように一般の計算式も指定できる)。また,配列の大きさ(要素の個数)はa.lengthで参照できる。添字は0からはじまるので,最大の添字の値はa.length-1ということになる。

配列の読みこみ
 JavaScriptで配列をつくり出す方法はいくつかあるが,その1つとして,文字列を特定の文字のあるところで切り分けて配列にする方法がある。たとえば
  a = 文字列.split(' ');

は,文字列を空白文字(' ')のところで分割して,その分割したものを並べた配列を変数aに代入する。文字列を入力して同様のことをするには,prompt()と組み合わせて,次のようにすればよい。
  a = prompt('値を空白で分けて入力').split(' ');

 この場合,たとえば「1 23 456」のように入力すると,変数aには長さ3の配列が代入され,a[0]は'1',a[1]は'23',a[2]は'456' という文字列が入った状態になる  *3

forによる繰り返し
 配列のデータは,0番目,1番目,…のように順番に繰り返しを使って処理することが多いので,そのような繰り返しを簡単に書けるようにしたforとよばれる形がある。
 for(変数 = 初期値; 変数 < 上限; ++変数) {
 繰り返す命令…
}

 これは次のwhileを使った繰り返しと同じ意味になるが,forを使った方が短く書けてわかりやすい。
 変数 = 初期値;
while(変数 < 上限) {
 繰り返す命令…
 ++変数;        ←変数を1増やすという意味
}

 どちらも,動作としては,変数をまず初期値に設定し,変数が上限より小さい間,「繰り返す命令」を実行しては変数を1増やす。たとえば,プログラム2にあるfor命令は,a.lengthが3だとすると,
 i = 0;
a[i] = parseFloat(a[i]);
i = 1;
a[i] = parseFloat(a[i]);
i = 2;
a[i] = parseFloat(a[i]);

と同じ動作になる(つまり,配列aのそれぞれの要素を文字列から数値に変換している)。このように,forを使うと,配列の要素を順に処理する動作が書きやすくなる。  

合計を求める
 配列の各要素に数値が入ったとして,その合計を求めるにはどうすればよいだろうか。それには,たとえばtotalという変数を用意して最初は0に設定し,次々に値を加えていけばよいと考える。たとえばa.lengthが3であれば
 total = 0;
total = total + a[0];  ←0番目の値までの合計
total = total + a[1];  ←1番目の値までの合計
total = total + a[2];  ←全要素の合計

のようにする。これを,forを使って書くと
 for(i = 0; i < a.length; ++i) {
 total = total + a[i];
}

のようになる。  上のように書いた方が分かりやすいのに,なぜ下のようにforを使って書くのだろうか。それは,こちらの方法なら要素の個数が何個であっても同じプログラムで動くからである。また,個数が決まっているとしても,1000,10000など数が多い場合は,足し算をずっと書き並べる方法は実質的に無理になる。  
<script>
n = parseFloat(prompt('いくつ未満の素数を計算しますか'));
for(x = 2; x < n; ++x) {
 sosu = true;
 for(i = 2; i < x; ++i) {
  if(x % i == 0) { sosu = false; }
 }
 if(sosu) { document.write(x + ' '); }
}
</script>
結果画面(入力欄に数を打ちこんで,「OK」を選択。)
 1より大きい整数で,1とその数自身でしか割り切れない数を「素数」という。「指定された数n未満の素数を求める」という問題を題材にして,アルゴリズムとプログラムについて考えてみよう。

アルゴリズムの考え方
 アルゴリズムを考えるときには,いきなりプログラムを書くより,そのあらすじを日本語などでプログラム風に記述することが多い。 これを「疑似コード」という。 また,そのときに,一度に細かいところまで考えるよりも,最初は大まかに考え,次第に細かいところまで検討していく方がよい。これを「段階的詳細化」という。プログラム(3)について,実際にやってみよう。 全体の考え方は次のようになるだろう(xは候補となる整数である)。
  nを読みこみ,n未満の素数を打ち出す: (※1)
    n ← 上限の数を読みこむ。
    xを2からnの手前まで変化させながら繰り返し,
      xが素数かどうか調べる。
      xが素数なら打ち出す。
    繰り返し終わり。
 では,整数xが素数かどうか調べるアルゴリズムはどうすればよいだろうか。 素数の定義を考えると,2からxの手前までの整数で実際に割ってみればよい。
    xが素数かどうか調べる: (※2)
      sosu ← true。
      iを2からxの手前まで変化させながら繰り返し,
        もし x % i == 0 なら sosu ← false。
    繰り返し終わり。
 「x % i」はxをiで割った余りを計算するので,余りが0なら割り切れたことになる。変数sosuは,最初はtrue(はい)だが,1回でも割り切れたらfalse(いいえ)を書きこむ。繰り返しが終わったとき変数sosuがtrueのままなら,どの数でも割り切れなかったことになるので,xは素数である。

プログラムの構造
 ※1,※2の2つの疑似コードを組み合わせてプログラムを完成させるには,※1に含まれる繰り返しの中に,※2の部分を埋めこむことになる。また,※2の疑似コードは,繰り返しの中に枝分かれ(もし〜ならば…)が含まれていることにも注意する。全体を1つのプログラムとして完成させたものが,プログラム3である。
 このようにプログラムでは,繰り返しや枝分かれなどの構造の中にさらに別の構造が埋めこまれる,という形がしばしばあらわれる。このような構造を一般に「入れ子構造」とよんでいる。

プログラムの改良
 プログラム(3)で,たとえば5秒間でいくつくらいまで素数がチェックできるか,試してみよう。プログラム3の素数列挙プログラムは,あまり高速でない。このプログラムの無駄な処理を減らすように改良する工夫として,次のものが考えられる。
・2以外の素数は,すべて奇数なので,2を最初に出力してしまい,あとは候補xとして3以上の奇数だけを調べる。
・割ってみる数iについても,3以上の奇数だけを試す。
・割ってみる数iの上限は,√xまででよい。
・内側の繰り返しは,xがiで割り切れたらすぐ終わりにする。
  これらの改良を施したときは,同じ時間でどれくらいまでチェックできるかを調べてみよう *4。