アルゴリズム

■内容

■アルゴリズム

• アルゴリズムとは、ある問題を有限の時間で解決する手順のことです。この手順は、その手順に正確にしたがえばだれでもまったく同じ結果が得られるように記述されていなければなりません。

■アルゴリズムの記述方法

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

■アルゴリズムの基本構造

• アルゴリズムは、つぎの 3 つの基本構造の組み合わせで作ります。
  • 順次
  • 分岐
  • くり返し

■順次構造

• 順次構造は、処理が上から下に順番にならんでいる構造です。

  ・ 文1 ・ 文2 : ・ 文n
  文1; 文2; : 文n;

■例題

1. 変数 a と 変数 b を交換します。

   ・t ← a ・a ← b ・b ← t
   var t = a; a = b; b = t;

■分岐構造

■if-then 構造

• if-then 構造は、指定された条件式が成立する(式の結果が true )場合に処理を実行します。

  ▲ 条件式 ｜ ｜ 条件式の結果が true のときの処理 ｜ ▼
  if (条件式) { 条件式の結果が true のときの処理 }

■例題

1. 変数 a と 変数 b の小さい方を変数 a、大きいほうを変数 b にします。

   ○ 変数 t ▲ a > b ｜・t ← a ｜・a ← b ｜・b ← t ▼
   if (a > b) { var t = a; a = b; b = t; }

■実習

■if-then-else 構造

• if-then-else 構造は、指定された条件式が成立する(式の結果が true )か否か(式の結果が false )で、実行する処理を選択します。

  ▲ 条件式 ｜ ｜ 条件式の結果が true のときの処理 ＋ ｜ 条件式の結果が false のときの処理 ｜ ▼
  if (条件式) { 条件式の結果が true のときの処理 } else { 条件式の結果が false のときの処理 }

■例題

1. 変数 a の値の偶数 / 奇数を判定し、表示します。

   ▲ a が 2 で割り切れる ｜・"a は偶数" を表示 ＋ ｜・"a は奇数" を表示 ▼
   if (a % 2 == 0) { document.write("a は偶数"); } else { document.write("a は奇数"); }

■実習

■多分岐構造(ケース構造)

• 分岐構造の特殊なパターンで、多分岐構造(ケース構造)があります。

  ▲ 条件式1 ｜ ｜ 条件式1 の結果が true のときの処理 ｜ ＋ 条件式2 ｜ ｜ 条件式2 の結果が true のときの処理 ｜ ：　　　　： ｜ ＋ 条件式n ｜ ｜ 条件式n の結果が true のときの処理 ｜ ＋ ｜ ｜ すべての条件式の結果が false のときの処理 ｜ ▼

  if (条件式1) { 条件式1 の結果が true のときの処理 } else if (条件式2) { 条件式2 の結果が true のときの処理 : } else if (条件式n) { 条件式n の結果が true のときの処理 } else { すべての条件式の結果が false のときの処理 }

  上記のフローチャートは、以下のように書くこともできます。

■例題

1. 変数 a の値の正負零を判定し、表示します。

   ▲ a > 0 ｜・"a は正数" を表示 ｜ ＋a = 0 ｜・"a はゼロ" を表示 ｜ ＋ ｜・"a は負数" を表示 ▼
   if (a > 0) { document.write("a は正数"); } else if (a == 0) { document.write("a はゼロ"); } else { document.write("a は負数"); }

■実習

■繰返し構造

• 繰返し構造(反復構造)は、繰返し条件を満たしている間は、処理を実行します。

• 繰返し構造の基本は上記のような考えですが、繰返し条件の位置、条件の意味(繰返し条件 / 終了条件)から、下記のように分類できます。
  整数を 1 から 10 まで順に表示する例を示します。

  なお、JavaScript では、while ループ、フローチャートでは、until ループが標準です。

  	繰返し条件(while ループ)	終了条件(until ループ)
  前判定	■ 繰返し条件式 ｜ ｜ 繰返し処理 ｜ ■	■▽ 終了条件式 ｜ ｜ 繰返し処理 ｜ ■
  	・i ← 1 ■ i <= 10 ｜・変数 i を表示 ｜・変数 i のカウントアップ ■ --- var i = 1; while (i <= 10) { document.write(i); i++; }	・i ← 1 ■▽ i > 10 ｜・変数 i を表示 ｜・変数 i のカウントアップ ■
  後判定	■ ｜ ｜ 繰返し処理 ｜ ■ 繰返し条件式	■ ｜ ｜ 繰返し処理 ｜ ■▽ 終了条件式
  	・i ← 1 ■ ｜・変数 i を表示 ｜・変数 i のカウントアップ ■ i <= 10 --- var i = 1; do { document.write(i); i++; } while (i <= 10);	・i ← 1 ■ ｜・変数 i を表示 ｜・変数 i のカウントアップ ■▽ i > 10

• とくに、前判定 while ループで、カウントアップするループの場合、つぎのように記述できます。

  ■ カウンター変数 = 初期値, 値1, 値2, ..., 値n ｜ ｜ 繰返し処理 ｜ ■
  ○ 整数型: i ■ i = 1, 2, 3, ..., 10 ｜・変数 i を表示 ■

■単純な繰返し

■例題

1. 整数 n の数だけ、星印(*)を横に並べるアルゴリズムです。

   ○ 整数型: i ■ i = 1, 2, 3, ..., n ｜・星印(*)を表示 ■
   □"StarPrint01.html" for (var i = 1; i <= n; i++) { document.write("*"); }

■実習

■繰返しのネスト

• 繰返し構造をネストさせて使うことができます。これを、多重ループといいます。ネストのレベルによって、n 重ループといいます。

■例題

1. 整数 n の数だけ、星印(*)を縦横(正方形)に並べるアルゴリズムです。

   ○ 整数型: i, j ■ i = 1, 2, 3, ..., n ｜■ j = 1, 2, 3, ..., n ｜｜・星印(*)を表示 ｜■ ｜・改行する ■
   □"StarPrint02.html" for (var i = 1; i <= n; i++) { for (var j = 1; j <= n; j++) { document.write("*"); } document.write("<br/>"); }

■実習

■基本的なアルゴリズム

■最小値･最大値

• 3 つの整数a, b, c のうち、最小値と最大値を変数 min, max に入れるアルゴリズムです。

  ○ 整数型: min = a ○ 整数型: max = a ▲ min > b ｜・min ← b ▼ ▲ min > c ｜・min ← c ▼ ▲ max < b ｜・max ← b ▼ ▲ max < c ｜・max ← c ▼
  □"MinMax01.html" var min = a; var max = a; if (min > b) { min = b; } if (min > c) { min = c; } if (max < b) { max = b; } if (max < c) { max = c; }

■合計の計算

• 1 から整数 n までの合計 s を計算するアルゴリズムです。

  ○ 整数型: s, i ・s ← 0 ■ i = 1, 2, ... n ｜・s ← s + i ■
  □"Sum01.html" var s = 0; for (var i = 1; i <= n; i++) { s = s + i; }

■ユークリッドの互除法

• ユークリッドの互除法は、最大公約数(GCD)を求める方法です。

• ユークリッドの互除法の原理は、つぎのとおりです。

   a と b の最大公約数を GCD(a, b) と表します。
   a > b > 0 とし、a を b で割ったときのあまりを r >= 0 とします。
   このとき次式が成立します。
  
       GCD(a, b) = GCD(b, r) 
  

• 2 つの正整数 a, b の最大公約数(GCD) を求めます。GCD は、b に求まります。

  ○ 整数型: r ・r ← a を b で割った余り ■ r != 0 ｜・a ← b ｜・b ← r ｜・r ← a を b で割った余り ■
  □"GCD01.html" var r; // 余り用の変数 while ((r = a % b) != 0) { a = b; b = r; }

■ループ構造の表現

• フローチャートと擬似言語、JavaScript で、ループ構造の表現の違いがあります。上記のユークリッドの互除法の例では、フローチャートと擬似言語では、"r ← a を b で割った余り" は 2ヶ所あらわれていますが、JavaScript では、"r = a % b" は 1ヶ所のみです。

• これは、フローチャートや擬似言語では、条件式の中に代入文を入れることができないのに対して、JavaScript では入れることができる、という性質によります。

  ○ 整数型: r ・r ← a を b で割った余り ■ r != 0 ｜・a ← b ｜・b ← r ｜・r ← a を b で割った余り ■

  var r; // 余り用の変数 while ((r = a % b) != 0) { a = b; b = r; }

■配列を使ったアルゴリズム

• 配列 a の要素数を、N_a と記します。

■配列のコピー

■例題

1. 配列 a を、要素の正順に配列 b にコピーする。

   ○ 整数型: b[] ○ 整数型: i ■ i = 0, 1, ... Na - 1 ｜・b[i] ← a[i] ■
   □"Array31.html" // 要素の正順に配列 b にコピーする。 var b = new Array(a.length); for (var i = 0; i < a.length; i++) { b[i] = a[i]; }

2. 配列 a を、要素の逆順に配列 c にコピーする。

   ○ 整数型: c[] ○ 整数型: i ■ i = 0, 1, ... Na - 1 ｜・c[i] ← a[Na - 1 - i] ■
   □"Array31.html" // 要素の逆順に配列 c にコピーする。 var c = new Array(a.length); for (var i = 0; i < a.length; i++) { c[i] = a[a.length - 1 - i]; }

3. 配列 a を、要素をひとつずらして配列 d にコピーする。

   ○ 整数型: d[] ○ 整数型: i ■ i = 0, 1, ... Na - 1 ｜・d[i] ← a[(i + 1) を Naで割ったあまり] ■
   □"Array31.html" // 要素をひとつずらして配列 d にコピーする。 var d = new Array(a.length); for (var i = 0; i < a.length; i++) { d[i] = a[(i + 1) % a.length]; }

4. 配列 a の要素を逆にする。

   ○ 整数型: i ■ i = 0, 1, ... [Na / 2] ｜・a[i] と a[Na - 1 - i] とを交換する ■
   □"Array31.html" // 要素を逆にする。 var w; for (var i = 0; i < a.length / 2; i++) { w = a[i]; a[i] = a[a.length - 1 - i]; a[a.length - 1 - i] = w; }

5. 配列 a の要素をひとつずらす。このとき、作業用の変数をひとつ使用してもよい。

   ○ 整数型: w = a[0]; ○ 整数型: i ■ i = 0, 1, ... Na - 2 ｜・a[i] ← a[i + 1] ■ ・a[a.length - 1] ← w
   □"Array31.html" // 要素をひとつずらす。このとき、作業用の変数をひとつ使用してもよい。 w = a[0]; for (var i = 0; i < a.length - 1; i++) { a[i] = a[i + 1]; } a[a.length - 1] = w;

■要素数がわからない配列

■例題

1. 要素の最後に最大値が入っている整数型配列 b の最大値を除いた要素数を出力する関数 size() を作成してください。

   ○ 整数型: i ・i ← 0 ■ b[i] != 最大値 ｜・i のカウントアップ ■ ・変数 i の値を表示
   □"ElementSize01.html" function size(a) { var i; for (i = 0; a[i] != Number.MAX_VALUE; i++); return i; }

■探索

• 探索は、探索するデータの並びの中からキーとなる値を探すアルゴリズムです。

■線形探索

• 線形探索は、探索するデータの並びの中からキーとなる値を、先頭から最後まで単純に探索していくものです。逐次探索ともいいます。

■例題

1. 指定した整数 n が、配列 a の要素と一致しているか否かを検査し、一致する場合はそのときの添字を、一致しない場合は、-1 を戻す関数を作成してください。ただし、配列の要素は昇順に並んでいるとは限りません。

○ 整数型: i ■ i = 0, 1, ... Na - 1 ｜▲ a[i] = n ｜｜・添字 i を返す ｜▼ ■ ・値 -1 を返す
□"SequentialSearch.html" function search(a, n) { for (var i = 0; i < a.length; i++) { if (a[i] == n) { return i; } } return -1; }

■2 分探索

■例題

1. 指定した整数 n が、配列 a の要素と一致しているか否かを検査し、一致する場合はそのときの添字を、一致しない場合は、-1 を戻す関数を作成してください。ただし、配列の要素は昇順に並んでいます。

○ 整数型: l = 0, h = Na - 1, m ■ l <= h ｜・m ← [(l + h) / 2] ｜▲ a[m] < n ｜｜・l ← m + 1 ｜｜ ｜＋ a[m] > n ｜｜・h ← m - 1 ｜＋ ｜｜・変数 m を返す ｜▼ ■ ・値 -1 を返す
□"BinarySearch.html" function search(a, n) { var l = 0; var h = a.length - 1; var m; while (l <= h) { m = Math.floor((l + h) / 2); if (a[m] < n) { l = m + 1; } else if (a[m] > n) { h = m - 1; } else { return m; } } return -1; }

■コントロール・ブレーク

■例題

1. 昇順に並んでいる配列 a があります。配列 a の中の同じ要素の数をカウントし、その結果を配列で返す関数を作成してください。
   結果配列では、2つの要素がペアになり、最初の要素に、配列 a の値、そのつぎの要素に、その数を入れます。

○ 整数型: countValue[] ○ 整数型: count = 0 ○ 整数型: prevValue = a[0] ○ 整数型: i, j ・ j ← 0 ■ i = 0, 1, ... Na - 1 ｜▲ prevValue = a[i] ｜｜・count のカウントアップ ｜＋ ｜｜・countValue[j] ← prevValue ｜｜・countValue[j + 1] ← count ｜｜・j ← j + 2 ｜｜・count ← 1 ｜｜・prevValue ← a[i] ｜▼ ■ ・countValue[j] ← prevValue ・countValue[j + 1] ← count ・配列 countValue を返す
□"Count01.html" function count(a) { var countValue = new Array(); var prevValue = a[0]; var j = 0; var count = 0; for (var i = 0; i < a.length; i++) { if (prevValue == a[i]) { count++; } else { countValue[j] = prevValue; countValue[j + 1] = count; j = j + 2; count = 1; prevValue = a[i]; } } countValue[j] = prevValue; countValue[j + 1] = count; return countValue; }

2. 配列 a の各要素の降順の順位を配列で返す関数を作成してください。

○ 整数型: rank[] ○ 整数型: i, j ■ i = 0, 1, ... Na - 1 ｜・rank[i] ← 1 ｜■ j = 0, 1, ... Na - 1 ｜｜▲ a[j] > a[i] ｜｜｜・rank[i] のカウントアップ ｜｜▼ ｜■ ■ ・配列 rank を返す
□"Rank01.html" function rank(a) { var rank = new Array(a.length); for (var i = 0; i < a.length; i++) { rank[i] = 1; for (var j = 0; j < a.length; j++) { if (a[j] > a[i]) { rank[i]++; } } } return rank; }

■併合

■例題

1. 昇順に並んでいる2つの配列 a, b があります。配列 a と b をまとめて、新しい配列 c をつくる関数を作成してください。このとき、つぎのような条件を前提とします。
• 配列 a に同じ数値になる要素はありません。
• 配列 b に同じ数値になる要素はありません。
• 配列 a と b で同じ要素があったときは、片方だけを配列 c に追加します。
• 配列 a, b, c の最後の要素は数値の最大値です。

○ 整数型: c[] ○ 整数型: i = 0, j = 0, k = 0 ■ a[i] < 最大値 または b[j] < 最大値 ｜▲ a[i] < b[j] ｜｜・c[k] ← a[i] ｜｜・k のカウントアップ ｜｜・i のカウントアップ ｜｜ ｜＋ a[i] = b[j] ｜｜・c[k] ← a[i] ｜｜・k のカウントアップ ｜｜・i のカウントアップ ｜｜・j のカウントアップ ｜＋ ｜｜・c[k] ← b[j] ｜｜・k のカウントアップ ｜｜・j のカウントアップ ｜▼ ■ ・c[k] ← 最大値 ・配列 c を返す
□"Marge01.html" function marge(a, b) { var c = new Array(); var i = 0, j = 0, k = 0; while (a[i] < Number.MAX_VALUE || b[j] < Number.MAX_VALUE) { if (a[i] < b[j]) { c[k++] = a[i++]; } else if (a[i] == b[j]) { c[k++] = a[i++]; j++; } else { c[k++] = b[j++]; } } c[k] = Number.MAX_VALUE; return c; }

■整列

■バブル・ソート(交換ソート)

■選択ソート

■挿入ソート

■例題

1. 配列 a の要素を昇順に並べ替えて返す関数を作成してください。(例題は選択ソートです）

○ 整数型: i, j ■ i = 0, 1, ... Na - 2 ｜■ j = i + 1, i + 2, ... Na - 1 ｜｜▲ a[i] > a[j] ｜｜｜・a[i] と a[j] の値を交換 ｜｜▼ ｜■ ■ ・配列 a を返す
□"Sort01.html" function sort(a) { var n = a.length; for (var i = 0; i < n - 1; i++) { for (var j = i + 1; j < n; j++) { if (a[i] > a[j]) { var t = a[i]; a[i] = a[j]; a[j] = t; } } } return a; }

■クイック・ソート

■マージ･ソート

■文字列探索

■例題

1. 文字列 a の中の部分文字列 b のインデックスを返す関数を作成してください。

○ 整数型: i, j ■ i = 0, 1, ... (Na - Nb + 1) ｜■ j = 0, 1, ... Nb - 1 ｜｜▲ a[i + j] != b[j] ｜｜｜・ループから脱出 ｜｜▼ ｜■ ｜▲ j >= Nb ｜｜・ループから脱出 ｜▼ ■ ▲ j < Nb ｜・i ← -1 ▼ ・変数 i を返す
□"StringSearch01.html" function search(a, b) { var i, j; for (i = 0; i < a.length - b.length + 1; i++) { for (j = 0; j < b.length; j++) { if (a[i + j] != b[j]) { break; } } if (j >= b.length) { break; } } if (j < b.length) { i = -1; } return i; }

■グラフ･アルゴリズム

■その他

■例題 - エラトステネスのふるい

1. エラトステネスのふるいを利用して、指定された数 n までの素数を配列として戻す関数を作成してください。

   ○ 整数型: prime[n] ○ 整数型: primevalue[] ○ 整数型: i, j ・配列 prime の要素をすべて true にする ■ i = 2, 3, ... n - 1 ｜▲ prime[i] ← true ｜｜■ j = 2 * i, 2 * i + j, ... n - 1 ｜｜｜・prime[j] ← false ｜｜■ ｜▼ ■ ・j ← 0 ■ i = 2, 3, ... n - 1 ｜▲ prime[i] ← true ｜｜・primevalue[j] ← i ｜｜・j のカウントアップ ｜▼ ■ ・配列 primevalue を返す
   □"Eratosthenes.html" function eratosthenes(n) { var prime = new Array(n); // ふるい var primevalue = new Array(); // 素数配列(戻り値) for (var i = 0; i < n; i++) { prime[i] = true; } for (var i = 2; i < n; i++) { if (prime[i]) { for (var j = 2 * i ; j < n; j = j + i) { prime[j] = false; } } } var j = 0; for (var i = 2; i < n; i++) { if (prime[i]) { primevalue[j] = i; j++; } } return primevalue; }