情報基礎A 「Cプログラミング」（ステップ１・準備・アルゴリズム）

このステップの目標

• アルゴリズムとプログラムの関係と対応を理解する。

1. アルゴリズムを考え、それをプログラムとして表現する

Cプログラミングと全く関係無さそうな話題かもしれないが、ここで『炊飯器でご飯を炊く手順』を考えてみよう。 授業担当者の場合、ざっと以下のような感じになる：

ご飯を炊いたことの無い人に「ご飯、3合炊いといてね」といったアバウトな指示は全く意味が無いように、 コンピュータへの指示（コンピュータ・プログラム）も具体的かつ詳細に記述する必要がある。 このように、問題解決に向けての一連の処理や作業の手順をステップに分解し、具体的に記述したものをアルゴリズム（algorithm）と呼ぶ。

手順をどのくらい細かい手順にまで分解した上で、どのような語彙と文法を使ってアルゴリズムを記述する必要があるかは、もちろん、想定する機械（計算機）の機能によって変わる。 もし完全自動式の未来型の炊飯器があったら、その機械のための炊飯アルゴリズムは、『白米をn合を炊く』の１行で済んでしまうかもしれない。 一方、上に示したアルゴリズムは、現在普及している炊飯器を使い、人が作業することが暗に想定されている。

であるから、アルゴリズムを考える際には、我々がどれくらい賢い（あるいはおバカな）計算機システムを相手にしているのか を、あらかじめ想定しておく必要がある。 ここで我々が学ぼうとしているC言語は、プログラミング言語の中では「高水準言語」に分類されているものの、 コンピュータのハードウェアの設計と密接に関係した、かなり「低レベル」な操作を想定して設計されている。 そのため、Cでプログラミングする際に我々が考えなくてはならないアルゴリズムは、ハードウェア（CPU)の動作を直接・間接に反映したものとなる。

すると、きちんと手順（アルゴリズム）を記述するにはC言語の語彙や文法を把握しておかねばならない一方で、Cでプログラミングするためには、 まずアルゴリズムを考えなければならないことになって、これでは完全に循環論法である。 良い例えではないかもしれないが、作曲の際には楽器の特性を考慮しながら楽譜を書かなければならない一方で、楽器を演奏するには楽譜が必要である。 プログラミングの学習というのは、作曲法と演奏を同時に勉強するのとどこか似ているかもしれない。

その感じを掴んでおくために、具体的なCプログラミングに入る前に、C言語（を含む一般的なプログラム言語）を使って問題解決の自動化を行う際、 どれくらいの細かさでアルゴリズムを考える必要があるのか、トランプのカードを用いた簡単な例を使って、まずは頭の準備体操をしておきたい。

カードの並べ替え

テーブルにカードが２枚あって、それぞれ、aとbと書かれた枠内に置かれているとしよう。 その他に、tと書かれた枠がもうひとつあるとする。 そして、以下のルールに従ってカードを操作できるとしよう。

• カードはちょうど１枚分の大きさの枠内にしか置けない
• カードは１枚ずつ枠から枠に動かせる
• カードの上に別のカードを重ねると、下側のカードは「消えて」しまう（あるいは、上のカードとひっついて、１枚になってしまう）。

このとき、aとbのカードの場所を入れ替える手順を、「Cプログラミング流」に述べると、 以下のようになる（右側に、実際に動作するCコードの例も示した）：

#include <stdio.h>
main()
{
  int a,b,t ;
  a = 1 ;
  b = 2 ;
  t = a ;
  a = b ;
  b = t ;
  printf("a=%d\n",a);
  printf("b=%d\n",b);
}

上記のアルゴリズムを『aとbのカードを交換する』と一言で表しても、論理的に間違っているわけではないが、 一般的なコンピュータのハードウェアには「二つのデータを１回の工程で交換する」という機能が備わっていないので、 そのことを反映して、Cプログラミングでも、データをひとつずつ移動するステップにまで分解して考えなければならないのだ。

　練習：5枚のカードの並べ替え

(左から)一列に並んだ置き場所a,b,c,d,e上にそれぞれ置かれた5枚のカードの順序を反転させるアルゴリズムを、2枚のカードの交換の例に倣って、記述しなさい。 ただし、もう一箇所、仮置き場 t が用意されているとしなさい。

　解説:アルゴリズムの汎用化

『カードの並べ替え』を考えるときに、2枚の場合、3枚の場合、... といった具合に、与えられたカードの枚数ごとに手順を考えるのは明らかにスマートではない。 $N$ 枚($N$ は任意の自然数）のカードが並んでいる場合の手順を一般的に記述しておいて、枚数に応じて $N$ の値を「後から」設定できれば、はるかに融通が効く。

カードの並べ替えの場合、どんな規模($N$ の値)の問題にも対応できるようにアルゴリズムを記述するためには、カードの置き場所に a, b, c, ..という風に個別の名前を与えるやり方は破綻する（カードが1億枚あったら、1億通りの「地名」が必要になる）。 そのような場合は、「何番目の置き場所」という風に通し番号をつけて管理するほうが理にかなっている。例えば、カードの置き場所全体に $a$ という名前をつけて、1億番目の置き場所は $a_{100000000}$ とするのがわかりやすい。 さらに、置き場所の番号も、記号（変数）で指定できるようにして、$a_i$ といった風に添え字を使った記法を導入すると、記述の幅がうんと広がる（ここで $i$ は場所を表す自然数）。 例えば、$a_i$ の右隣は $a_{i+1}$ と指定できるし、左隣は$a_{i-1}$ 、一番右端の置き場所は $a_{N}$ である。こうすれば、どんな $N$ でも対応できるはずだ。

置き場所 a, b にそれぞれカードが置かれている場合、 すべてのカードを仮置き場 t に片付けるには、

と書けば事足りる。 一方、$N$ 枚のカードの場合、すべての置き場所についての移動を指示するには、上記の添字を使った記法を使って

などと書きたくなる。ところが、$\cdots$ のところは、人間が正しく察してくれることを想定した記法である。 つまり、添字の変化を表している $i=1,2,\cdots,$ の箇所は、意地悪に解釈すると、例えば、1, 2, 3, 5, 8, ... の場合なども含んでしまう。 こうした曖昧さを避けるには、起点、終点、そして「歩幅」まで、きちんと示しておく必要がある。 この場合、アルゴリズムの記述は以下のようにすれば良い：

　練習：N枚のカードの並べ替え

一列に並んだ$N$個の置き場所 $a_1, a_2, \cdots, a_N$にそれぞれ1枚ずつ計$N$枚のカードが置かれている。加えて、仮置き場 $t$ も使えるとする。 $N$枚のカードの順序を反転させるアルゴリズムを記述しなさい。

ここで、$i$番目の置き場所$a_i$とし、「反復過程」を含め

の様式で記述すること。

　練習：3枚のカードの整列

一列に並んだ置き場所（左から）a,b,c上に数値が書かれたカードが置かれている。カードの数値は全て異なるとしよう。 最初のカードの配置にかかわらず、最終的にカードの数値が左から小さい順になるよう整列させるアルゴリズムを、「ヒント」の2枚のカードの交換の例に倣って、記述しなさい。

　ヒント

　発展練習：カードの「山」の移動

ここまでは、「カードの上にカードは置けない（重ねたら、一番上のカードにまとまってしまう）」という状況設定を考えていた。 この練習課題では、このルールを変更して

• カードはちょうど１枚分の大きさの枠内にしか置けない
• カードの上に別のカードを重ねることができる。ただし、カードに書かれた数値が下のカードより小さくなければならない。
• カードは一番上のものを１枚ずつ枠から枠に動かせる

としてみよう。

三つの置き場所 a, b, cがあり、aに $N$ 枚のカードが積まれている。上記のルールに従い、カードに書かれた数値は、上から下に大きくなっている。 カードを1枚ずつ移動させて、このカードの山を aからcに移動する手順（アルゴリズム）を見つけなさい。

カードの枚数が $N=2$ のときをまず考え、$N=3, 4, 5$ と増やしてみなさい。

　ヒント

　解説: 「関数」を使ったアルゴリズムの記述

$x,y,z$という3つの置き場所があったときに、$x$に積まれた$n$枚のカードを$y$に移動する「行為」を $\textrm{move}(n,x,y,z)$ と記述してみよう。 ここで、$x,y,z$は変数で、$x$の内容は置き場所aであったり、置き場所bであったり・・、と変わり得る、と考える。 具体的には、例えば$n=2$のときは、

$\textrm{move}(2,x,y,z)$の内容:
　　$x \to z$
　　$x \to y$
　　$z \to y$

となるだろう。

$x$に$n$枚の山があったときは、上側の$n-1$枚をまず$z$に移動し、一番下のカードを$y$に移動後、$z$に積まれていた$n-1$枚を$y$に移せば良い。 その手順は

$\textrm{move}(n,x,y,z)$の内容:
　　$\textrm{move}(n-1,x,z,y)$
　　$x \to y$
　　$\textrm{move}(n-1,z,y,x)$

と記述することができる（moveの中の$x,y,z$の順序に注意）。

この、moveという「関数」を使うと、アルゴリズムは

のように表現することができる。このアルゴリズムをC言語に直訳したのが以下のコードである。

#include <stdio.h>

void move(int n, char x, char y, char z) {
    if (n==2) {
        printf("%c --> %c\n",x,z) ;
        printf("%c --> %c\n",x,y) ;
        printf("%c --> %c\n",z,y) ;
    } else {
        move(n-1,x,z,y) ;
        printf("%c --> %c\n",x,y) ;
        move(n-1,z,y,x) ;
    }
}

main()
{
    char a='a' ;
    char b='b' ;
    char c='c' ;

    move(4,a,c,b) ;
}

コンパイルして実行すると、4枚の場合の手順が画面に出力されるはずだ。プログラムの最後の辺りの"4"の値を変えれば、異なる枚数についても計算可能である。

この例では、「カードを移動する作業は・・・・をすることである」という風に、新しい語彙（ある種の動詞句）を定義することを通じてアルゴリズムが記述されている。 このように、手順の記述方法には、いくつかの流儀があって、そうした流儀に適したプログラミング言語が（C言語以外にも）沢山開発されている。