|
|
NHK教育テレビの「ピタゴラスイッチ」という番組をご存知でしょうか。「ある物は，ある考え方で構成されている。その考え方はほかにも使われているから，そうした基本となる考え方を知ろう」という趣旨に基づいて，考え方や物の成り立ちを児童向けに教える，とても面白い番組です。児童向けなのに周りのプログラマたちはだいたい見ています（笑）。
この番組の制作には，「だんご3兄弟」の作詞者として著名な佐藤雅彦氏が参加しています。佐藤氏の著書「毎月新聞」（毎日新聞社）には，要約すると以下のようなエピソードが載っています。
――事務所のスタッフと話しているうちに「三角形の内角の和は180度になる」という話題になった。なぜそうなるか質問したが，「ただそう教わったから」というだけだった。そこで，三角形の図に補助線を引いたりして学校でやるように証明して見せたが「そういうことはお任せします」といわれて，興味すら示してもらえない。業を煮やして最後にはメモ用紙を三角形に切り出し，その頂点をちぎって角を合わせて見せた。我関せずの態度からうって変わって「ほんとだ！ 平らになっている！ 180度！」と叫んだ。――
本連載ではこれを狙います。アルゴリズムを構成している楽しい仕組みを紹介しながら，あなたに「おおっ」と言わせることが，本連載の最初の目的です。興味を持てたなら，アルゴリズムに関する文献や情報を抵抗なく読めるようになるはずです。アルゴリズムを使いこなしたり，作ることも無理なくできるようになるでしょう。これが真の目的なのですが…。でもまずはいろいろなアルゴリズムの面白いところを見て，楽しんでみましょう。
そもそもアルゴリズムってどんなもの？
アルゴリズムとはどんなものなのでしょうか。ふと気がつくと，私たちの身の周りにアルゴリズムはあふれています。「会社に行く」ためには，「支度する」→「家を出る」→「駅へ行く」→「電車に乗る」→「ゆられながら立っている」→「電車を降りる」→「会社に着く」という手順があります。「奥さんをなだめる」ためには「朝早く起きる」→「洗濯をする」→「食器を洗う」→「ゴミの日ならゴミを出す」→「朝食の支度をする」→「朝食ができたら奥さんにやさしく声をかけて起こす」という涙ぐましい努力が必要かもしれません。これらを「会社に行くアルゴリズム」「奥さんをなだめるアルゴリズム」と呼んでしまうとそれらしい気がしてきます。
こうした「目的を果たす」ための「手順」「順番」「流れ」がアルゴリズムと呼ばれているものの正体です。みなさんも「会社を休むアルゴリズム」「締め切りをなんとか延ばすアルゴリズム」など，いろいろ見つけてみてください。
30行でわかるプログラムの基本
こうして見つけたアルゴリズムをプログラムとして実現する場合は，プログラミングに使われているいろいろな「考え方」（パラダイムとも言います）を使って組み立てることになります。まずはこれを理解しましょう。
OS，メーラー，ブラウザなど，いろんなプログラムで加工されるものとして「データ」があります。ファイルだったり，プログラムの中に含んでいたり，データはいろいろなところにいろいろな形で存在します。これをプログラミングするときは，「変数」に入れてから使います。ある範囲の数値だけ扱える「整数型」や「実数型」のほかに，同じ種類の変数をいくつも集めた「配列」，違う種類の変数を集めた「構造体」，それら変数の位置だけを示す「ポインタ」などがあります。大きなデータは，小さな変数がいっぱい集まったものと考えます。
データを加工するには，変数と定数，あるいは変数同士を足したり引いたりする「演算」を行います。演算はプログラムで何度でもできるので，演算をする順番をソースコードに記述することになります。そうなると「データの内容によって演算方法や順番を変えたい」「配列が持つ要素を繰り返し加工したい」といった「処理の流れを変える」方法が欲しくなります。そのために用意されているのが，C言語のifやswitchによる「分岐」，forやwhileによる「繰り返し」といった「制御構造」です。
プログラムが大きくなってくると，人間が理解できる範囲を超えてきます。大きな処理は細かく分けて，「処理するデータを与えると加工されて戻ってくる」単純な目的を持つ「関数」をいっぱい作って一つのプログラムにします。関数をいっぱい作ると今度は「似たような関数が多くなる」といった不満が出てきます。オブジェクト指向では，いくつかの関数とデータをまとめた「クラス」が用意されました。クラスを使うと，よく似た処理をまとめて扱う「抽象化」がすんなりとできます。
「目的」と「処理の流れ」に注目してアルゴリズムを組み立てる
次に，プログラムにどんな「処理の流れ」があるのかを見てみましょう。例えばテキスト・エディタを作るとします。テキスト・エディタの目的は「文章を編集する」ことです。実際に使っているときのことを思い浮かべると，「テキスト・ファイルを開く」→「テキストを編集する」→「ファイルに保存する」という大ざっぱな流れがあることがわかります。「テキストを編集する」という部分では，「入力された文字を取得する」→「データとして格納する」→「画面に表示する」というように，さらに別の流れが見られます。
プログラムの中には，こうした「ある目的を果たす」ために「より小さな目的を果たす」処理が順番に実行される流れがあり，その小さな目的の処理の中には，さらに小さな目的の処理が連なった流れがあります。ここから考えると，私たちがプログラミングでアルゴリズムを作るときは，「目的を達するための小さな目的」を大ざっぱに考え，それを組み合わせて流れを作ることになります。次の段階でその小さな目的を実現するための流れを考え……と，細分化を繰り返してアルゴリズムを組み立てていくのです。
ある地点だけに注目して考える
何となくわかったところで，実践してみましょう。冒頭の「今号の問題」をご覧ください。比較的よく知られたパズル「ナンプレ」を解くプログラムを題材にしました。作成するプログラムの大ざっぱな流れとしては「問題を入力」→「解く」→「答えを出力」という形になります。
まずは，入力や出力のために盤面をデータとして表現する方法を考えましょう。縦横に数が並んでいるのですから，盤面のデータは「2次元配列」にしたくなります。nanpleTable[x][y]と縦横の位置を与えればそのマスの値が得られる仕組みです。そうすると，入力は「問題のマスに書かれた内容」，出力は「全部のマスが数字で埋められたもの」となります。ここをまず足場にします。
次に，問題の解き方を考えてみます。ルールを見ると各地点の関係がいろいろ絡んでいて頭がパニックするかもしれません。こんなときは，とりあえずほかの場所のことは忘れて，「ある地点だけに注目して」考えるのがポイントです。
私たちがナンプレを解くときは，一つのマス目に注目し，「そのマスを含む縦の列，横の列にない数字」「そのマスを含む3×3の範囲にない数字」などを考えて「空いているマスの数の候補を絞る」ことを最初に行います。数の候補が一つになったら数が確定したことになり，その数をマスに書き込みます。
プログラムでナンプレを解く場合も，同じような手順で処理を進めることができます。いずれも目的としては「空いているマスに何が入るかを決める」ということなので，「ある地点をまず見て，そこに入る数の候補を決める」というアルゴリズムにすればいいでしょう。先ほどの盤面データを使ってこの処理を実現することを考えると，x，yの位置を与えたときに数の候補を絞る処理を実行し，「確定した数」か「数の候補」を得る関数を作れば目的を達成できそうです。
