PR

 前回までの本連載では,Cプログラマからみたメモリーのイメージや,データが2進数として処理されているイメージについてなど,いかにもミクロな,コンピュータの内部に近い内容の話を進めてきました。これらはプログラムを作るうえで大事な基礎です。でも,メモリー上のデータのイメージだけを熱心に勉強しても,プログラムを作成することはできません。

 今回はメモリーの話はお休みにして,アルゴリズムの基礎について説明を進めていきます。まず最初に「アルゴリズム」という言葉の意味を確認しておきましょう。アルゴリズムとはJISの定義(JIS X 0001)でいうと,

「問題を解くものであって、明確に定義され、順序づけられた有限個の規則からなる集合」

となります。難しそうですね。問題を解決するためのプログラムの“手順”と考えましょう。

 例を挙げて説明します。テーブルの上にトランプをぶちまけて,ぐちゃぐちゃにしてから,クローバー,ハートなどの種類別に,エース(1)からキング(13)の順に並べ替えるとします。皆さんは別に何も考えずに無意識のうちに整理できてしまうでしょう。

 しかし,これをコンピュータにやらせたい場合,バラバラに記憶されている4種類の1から13の数値を読み出して,区分して並べ替えるプログラムを作らなくてはなりません。では,「どうやって並べ替えと分類をコンピュータに実行させれば,効率的か」を考えなけばいけませんね。「うーん」と頭をひねって考えた手順,つまり問題を解くための方法をアルゴリズムといいます。

 「こんな簡単なことを,プログラムを作ってイチイチ教えてやらないといけないなんて,コンピュータってなにもできないんだ」と思われる人もいるかもしれません。コンピュータは人間が考えて作ったプログラムを忠実に実行するだけの機械なのです。ですから,人間が知識と知恵を総動員してアルゴリズムを考えなければいけません。ちゃんとアルゴリズムを考えつき,それをプログラムの制御文として実装できれば人間にとっては大変な数の処理(たとえば,400種類の1から100の並べ替え)だって,コンピュータはわけもなく処理してくれます。

フローチャートで制御文を理解しよう

 アルゴリズムをC言語で実現するには,制御文という文を利用します。制御文はプログラムの流れを制御します。制御文がないとプログラムは上から順にコードを実行するだけで,望みのアルゴリズムを備えたプログラムを作成するのが困難です。

 制御文には,大きくわけて2種類あります。「繰り返し」と「条件分岐」です。繰り返しはある処理を何度も実行するもの,条件分岐は,ある処理を条件によって実行したりしなかったりするものです。考えてみると私たちの行動も,繰り返しと条件分岐によって成り立っていますね。100枚の封筒すべてに切手を貼る――などというのは代表的な“繰り返し”です。朝起きたら朝食を食べて会社に行き,会社で仕事をして,夜になったら家に戻って寝る――平日はこのような繰り返しを実行している方もいらっしゃるのではないでしょうか。C言語には,繰り返しを表す文が三つあります。(1)for文,(2)while文,(3)do while文――です。ここでは名前だけ覚えておいてください。

 また,日々の繰り返しの中で,我々はいつも条件判断をしています。今日の昼飯は豪勢に「うなぎ」にしようかとか,給料日前だから社員食堂のランチにしようなどという,どうでもいい判断から,転職しようか,それともやはり今の会社にとどまろうか,というシリアスなものまで,いつもある条件を判断して分岐しています。C言語では条件分岐はif文やswitch文で記述します。

 制御文の働きを一発で理解するにはフローチャート(流れ図)が役立ちます。「フローチャートなんて古いもの,今さら何にするんだ」って思われる方もいるかもしれません。確かにイベントドリブン*1のプログラムを表現したいときや,オブジェクト指向設計*2にフローチャートは役に立たないでしょう。でも,繰り返しや条件分岐を表現するときには,フローチャートは今でもベストな図解手法だと筆者は考えています。

 さて,少し昔話にお付き合いください。1983年,筆者は情報処理会社に就職しました。そこではホスト・コンピュータ*3によるバッチ処理*4が実行されていました。アメリカに追い付き,追い越せと開発された富士通やNECのホスト・コンピュータが,コンピュータ専用のマシン・ルームでうなりをあげていました。顧客から預かってきた紙の資料をデータに起こし,コンピュータに入力して処理します。処理の結果は紙の帳票に出力して顧客に届けます。日夜このような作業が繰り返されていました。

 プログラミング言語はCOBOL,一連のトランザクション・データとマスターのマッチングなどが主要なアルゴリズムでした*5。最初はフローチャートを書くことから,プログラミングが始まりました。プラスチック製のテンプレートを使って紙に丁寧に書いていくのです。詳細にフローチャートを書きあげると,頭の中でプログラムのイメージができ上がっていました。

 たった20年前のことですが,若い方には大昔の話のように感じられるかもしれませんね。でも基本的なアルゴリズムを考えるとき,フローチャートが役に立つことには変わりありません。今はWordやExcelでフローチャートが書けます。図1にフローチャートで使用する代表的な記号を示しました。記号を線でつなぎ処理を記述します。以下では制御文の動きをフローチャートとともに考えていきましょう。

図1●フローチャートで利用する代表的な記号
図1●フローチャートで利用する代表的な記号