アルゴリズムの設計と検証

指導者向けの公開補足

学習本文に加えて、指導の視点・背景・授業での確かめ方を示します。どなたでも読めます。

指導の焦点

手順を細かく書くことに加え、入力・出力・終了条件を確認する。「動いた一例」と、仕様を満たすことの説明は違う。

一歩踏み込んだ背景

実行時間の測定は端末や処理系に左右される。入力が増えたときの比較回数などを使うと、実装環境とは別の観点で手順を比べられる。

授業での確かめ方

同じ課題を二つの手順で解き、通常例・境界例・空の入力で試す。正解の値だけでなく、手順が終わる理由を説明させる。

制度・規格等は本文末尾の参考資料も確認してください。

JSFiddleでコードを試す

JSFiddleは、ブラウザーでHTML・CSS・JavaScriptを入力して実行できるサービスです。短い動作確認から始められます。

新しい編集画面を開きます。JavaScriptは通常のJavaScriptを選び、外部ライブラリは追加しません。
HTML欄にはページの本文、CSS欄には見た目、JavaScript欄には処理を書きます。HTML欄に<html>や<body>は不要です。JavaScript欄に<script>は付けません。
DOMを使う例では、JavaScriptの実行タイミングを「On Load」「On DOM Ready」または「No wrap - bottom of body」にします。
「Run」を押してResult欄を確認します。書き換えたら再びRunを押します。

console.logの結果は通常、ページではなく開発者ツールのコンソールに出ます。このサイトの計算例をResult欄で読みたいときは、HTML欄に次を入れます。

<pre id="output"></pre>

JavaScript欄には次を入れ、console.log(2 + 3);の行を、試したいコード一つに置き換えます。独立した例を複数まとめて貼らないでください。

{
  const output = document.getElementById("output");
  const console = {
    log(...values) {
      output.textContent += values.join(" ") + "\n";
    }
  };
  console.log(2 + 3);
}

Runを押すと「5」と表示されます。外側の波括弧の中だけで表示用のconsoleを用意しているため、ブラウザー本来のコンソールは変更しません。

HTMLとJavaScriptの両方を載せた実習例は、この表示用コードで囲まず、それぞれの欄へ分けて貼り付けます。保存・共有時は公開範囲を確認し、個人情報やパスワードを入力しないでください。コードは手元にも残しましょう。

NAS・GitHub・CodePenなど、作業環境の選び方

この単元でできるようになること

問題の入力、出力、前提を分けて書ける。
手順を順次・分岐・反復に整理して表せる。
トレースと境界のテストで、手順の正しさを検討できる。

問題を、計算可能な形にする

アルゴリズムは、問題を解くための明確な手順である。プログラムを書く前にも、文章、表、流れ図、疑似コードで表せる。使う言語が違っても、何を順番に調べるかという考え方は共通する。逆に、文法が正しくても手順が問題に合っていなければ、期待する結果にはならない。

架空の陶芸会で、できあがった作品を運ぶ箱の数を求めよう。一箱には作品を六個まで入れられ、作品は壊さず一個ずつ数える。空の箱は用意しない。入力を非負の整数の作品数、出力を必要な最小の箱数と決めれば、作品が零の場合も答えを定められる。

区分	今回決める内容	決めないと困ること
入力	作品の個数	重さなのか個数なのかが曖昧になる
前提	一箱六個、個数は非負の整数	小数個や負の値の扱いが不明になる
出力	必要な最小箱数	残り個数だけでは答えにならない
終了	すべての作品を箱へ割り当てた時点	いつ作業を終えるか分からない

大きな要求を小さな操作に分ける

まず「残っている作品があれば、箱を一つ使う」「残りを六個減らす」「残りが零になるまで続ける」と分解する。ただし最後の箱では六個未満しか残らないこともある。残りが負にならないよう、零と比較して更新する。

手順の骨組みは、初期値を設定する順次、残りを確かめる条件、箱を増やす操作の反復である。流れ図にするなら、開始から初期化へ進み、判断で「残りが正か」を問い、真なら処理して判断へ戻る。偽なら出力して終了する。図の矢印にも実行順の意味がある。

一般的な流れ図では、開始と終了を端子の記号、計算や代入を長方形、条件の判断をひし形、入出力を平行四辺形で表す。判断から出る矢印には真偽などの行き先を記す。記号を描くだけでなく、すべての枝がどこへつながるかを確認すれば、処理の抜けや戻り先の誤りを見つけられる。

let remaining = 20;
let boxes = 0;
while (remaining > 0) {
  remaining = Math.max(0, remaining - 6);
  boxes = boxes + 1;
}
console.log(boxes, remaining);

出力は 4 0 になる。箱数を増やす処理が反復の中にあるので、箱を使った回数と箱数が一致する。出力を反復の外へ置くことで、最終結果を一度だけ表示している。

トレース表で状態を追う

トレースとは、実行順に値の変化を追うことだ。頭の中で結果だけを予想するのではなく、更新前と更新後を区別して書く。更新の順番を入れ替えたときにも、違いを見つけやすい。

処理後	残り個数	箱数
初期状態	20	0
一回目	14	1
二回目	8	2
三回目	2	3
四回目	0	4

反復の後には、「すでに箱へ割り当てた作品と残りを合わせると元の作品になる」と考えられる。ただしこのコードは最後の箱の空きまでは記録しない。目的に必要な値だけを持つ設計になっている。

正しさと停止を別々に確かめる

この手順は、残りが正なら少なくとも一個を箱へ割り当て、残りを減らす。初めの個数は有限なので、やがて零になって停止する。一方、箱の定員を零に変えると残りが減らず、この停止の説明は成立しない。前提がアルゴリズムの正しさに関わっている。

最小の箱数であることも考えよう。最後以外の箱は六個入りであり、余りがあれば一箱を追加する。一箱減らすと全作品を収められない。単に停止しただけでなく、求めた出力の条件に合っていることを説明する必要がある。

テストは零個、一個、六個、七個を試すとよい。六個ちょうどで余分な箱を作らないか、その一つ先で追加できるかを確認できる。たくさんの大きな数を無作為に試すだけでは、境界の誤りを見逃すことがある。

別の手順と比べる

今回の問題は、作品数を六で割り、端数があれば切り上げる計算でも解ける。反復は作品数が増えるほど回数が増えるが、式なら箱数を直接求められる。一方、箱ごとの重量制限や壊れやすい作品の配置を扱うなら、単純な割り算だけでは足りない。

注意： 一つの入力で正しい答えが出ても、すべての入力で正しい証明にはならない。テストと、前提・途中の性質・停止の説明を組み合わせよう。現実の梱包の安全性を保証する教材でもない。

用語

用語	意味
アルゴリズム	問題を解くための明確な手順
前提条件	手順を使う前に満たすと決めた条件
トレース	実行順に処理と値の変化を追うこと
境界値	処理の選択などが変わる境目の値
停止条件	反復や処理を終えるための条件

確認問題

作品が零個なら、例の反復回数と出力はどうなるか。
作品が十三個のときのトレース表を作り、箱数が最小である理由を述べよう。
一箱の定員を変数にするなら、入力前にどのような条件を確かめるべきか。

問1の解答例を見る

反復は0回で、boxesとremainingの表示は0 0となる。最初からremaining > 0が偽なので、反復の中へ入らない。

問2の解答例を見る

（残り, 箱数）は開始時（13,0）、一回後（7,1）、二回後（1,2）、三回後（0,3）。一箱六個なので二箱では十二個までしか入らず、三箱が最小である。

問3の解答例を見る

一箱の定員が正の整数であることを確かめる。0や負の値では残りが減らず終了できない場合があり、個数を入れる定員に小数を許すかも仕様として決める。