情報基礎A 「Cプログラミング」（ステップ１・準備）

このステップの目標

• Ｃによるプログラム作成に必要なソフト（TurtleEdit）について、作業内容の意味を把握しつつ、基本操作ができるようになる。
• アルゴリズムとプログラムの関係と対応を理解する。

0. 何故プログラミングを学ぶのか？

パソコンやスマフォにはOS(Operating System)というソフトウェアが入っていて、それ無しでは動かないし、しばしばそれをアップデートするよう「催促」されたりする。 さらに、便利に使うには、アプリ（application softwareの略）を追加でインストールしないといけなかったりする。 いわゆる情報機器以外でも、テレビなどの家電製品もその中身はコンピュータそのものであるし、 普段はあまり気にしないようなちょっとしたデバイスでさえ、不具合を解消するため、ときどきファームウェア(firmware)のアップデートが必要になったりもする。 今や、我々の暮らしのかなりの部分が、コンピュータープログラム（ソフトウェア）によって支えられているのは間違いない。

そういったソフトウェアは、もちろん、その道のプロ（あるいは、優秀なアマチュア）が開発しており、 どんなに自動車が好きでも、部品から車を自作することは（ほとんど）無いように、 ソフトやアプリは、誰かが作ったものをダウンロードしたり購入したりするのが当たり前である。 ところが、この「情報基礎」では、プログラミングの実習に一定の時間が割かれている。 このクラスの学生の多くは、将来その方面に進む可能性は少ないだろうに、全員がプログラミングを学習する意味（あるいは、教える側の意図）はどこにあるのだろう。

• 就職に有利だから？
  就職活動を行う際に、プログラミングの経験が有ったほうが入りやすい企業は（もちろん業種に依りますが）確かにあるだろう。
• 研究者になったとき必要だから？
  もちろん進む分野に依るけれども、実験データの解析、シミュレーションなどのために、本格的なプログラミングが要求される研究室も多いはずだ。 また、最近は、数理分野に限らず、「ビッグデータ」を活用した研究が注目されており、それを正しく解釈し、扱うための素養が要求されている （データ解析を「下請け」に依頼するにしても、ある程度の内容を知らなくては、適切な指示は出せないだろう）。
  また、既製のソフトウェアを購入して研究を行なう場合でも、科学技術系のソフトの多くは自由度を上げるために、「スクリプト」とか「マクロ」などと呼ばれるプログラムの動作環境を内蔵している場合が多いので、結局、プログラミングのスキルが必要になるケースも多い。
  事務系の仕事に就いたとしても、エクセルなどの「マクロ」（ＶＢＡ）は立派なプログラミング環境なので、知っておくと非常に役に立つはずだ。
• コンピュータの仕組みが分かるようになる？
  はい、でもあり、いいえ、でもある。ある程度実用的なプログラムの開発を行う際には、コンピュータの仕組みを知らないと「話にならない」ので、ソフト開発「だけ」勉強する といったやり方はあり得ない。
• 授業で習ったやり方は、他のシステムでも通用するのか？
  いいえ。大枠では、これから勉強する内容は所謂UNIX系のオペレーティングシステム(Linux)で動作している環境ではほぼそのまま使えるはずだ（例えばMacやAndroidはその裏側でUNIXが動作している）。しかし、Windowsパソコンなどではやり方がかなり異なるだろうし、AndroidやiPhone,iPadなどのプログラミング作法は、見かけ上は、ずいぶんと違っている。
  ただし、Ｃ言語の仕様そのものは国際的に標準化されているので、どこに行っても同じ。また、C言語で登場する様々な考え方（変数、式の計算、代入、条件分岐などなど）は、ほとんど全て、他のプログラミング言語にも通用する。Cを理解しておけば、別の言語の習得も格段に（本当に何十倍も！）早くなるだろう。

この授業の目的は「パソコンの使い方教室」ではないので、個別的な使い方ではなく、むしろプログラミングを通じて問題を抽象化して考えたり、論理的な思考を行う能力を養うことが大切。そして、その基本的な考え方は、WindowsでもMacでもスマートフォンでも、CでもJavaでも、皆同じだ。

加えて、是非ここで強調しておきたいのは、プログラミングは知的な「ゲーム」としても、とても面白く刺激的であるということだ。

1. コンピュータの基本的な動作

コンピュータは、記憶装置（メモリ）に書き込まれている数値（機械語命令）を順に読み込んで、それに対応した動作を延々と行うだけの、原理的には、いたって単純な機械だ。コンピュータが処理できるのは、おおざっぱに言って、以下のような単純な仕事だけである：

1. データ（数値）を外部装置に出力する
2. 外部装置からデータ（数値）を入力する
3. メモリーのデータ同士を演算（加減乗除など）して、その結果をメモリーにセットする（式の計算と代入）
4. 演算の結果によって（結果が０より大きいかどうか、など）、次に処理する命令を切り替える（条件分岐あるいは選択処理）
5. 機械語命令の決められた範囲を反復する（反復処理）
6. 機械語命令の決められた範囲に分岐して、そこが終わると、もとの場所から処理を再開する（サブルーチン処理）

これらの処理を何万ステップも組み合わせると、画面に文字や画像を表示したり、数学関数を計算したり、意味のある動作を行わせることができるわけだ。ただ、それを数値（機械語; machine code）で記述するのはとても面倒で複雑なので、人間が分かりやすい記号で書かれたプログラム（ソースプログラム(source program)とかソースコード(source code)と呼ぶ）を、機械語に翻訳するシステムが開発された。それをコンパイラー(compiler)と呼ぶ。

こうした手順に対応して、C言語でのプログラム開発は、以下の３つの基本ステップで構成される：

1. 何々.c というファイルＣ言語のソースコードを作成する
2. cc （あるいはgcc）というコマンドをつかって、ソースコードをコンパイルする
3. a.outというファイルが新しく生成され、その中に機械語が格納されているので、それを（その中身の機械語コードを）実行する

ついでながら、実行する、は英語で execution である（死刑執行、という怖い意味もある）。Windowsのプログラム名の拡張子と使われている"exe"は、このことに由来する。

2. プログラム作成から実行までの流れ

では、ICL演習室の環境で上記の３ステップを行う具体的な方法を紹介しよう。

準備：実習用のソフト（TurtleEdit）を開く

画面左上の「アプリケーション」メニューをクリックし、「アクセサリー」または「プログラミング」の項目の中にあるTurtleEditを選んで起動する。 TurtleEditは情報基礎の実習用に開発されたソフトで、ソースプログラムの作成、コンパイル、実行をこのソフトを使って行うことができる。

ステップ１：ソースプログラムの作成

TurtleEditのウィンドウは上下の２つの区画に分かれている。その上側が、プログラムを記述するための区画で、 ワープロのようにCのプログラムをその中に記述する。

C言語のプログラムの記述法などはこれから勉強するとして、ここでは、TurtleEditの画面（上側の区画）に 以下のCプログラムをコピー＆ペーストしてみよう：

#include <stdio.h>

main()
{
  int year, month, day, year2, month2, dayofweek ;
  static char dow[][4] = {"Sun","Mon","Tue","Wed","Thu","Fri","Sat"} ;

  printf("Year ?: ") ;
  scanf("%d",&year) ;
  printf("Month ?: ") ;
  scanf("%d",&month) ;
  printf("Day ?: ") ;
  scanf("%d",&day) ;

  if (month==1 || month==2) { year2 = year - 1 ; month2 = month + 12 ;  }
  else { year2 = year ; month2 = month ; }
  dayofweek = (year2 + year2/4 - year2/100 + year2/400 + (13*month2+8)/5 + day) % 7 ;

  printf("%d/%d/%d is %s.\n",year,month,day,dow[dayofweek]) ;
}

コピー＆ペーストする際に、最初の # や、おしまいの } を選択し忘れないよう気をつけること。

プログラムを記述（コピー＆ペースト）したら、必ずその内容をファイルに保存しておく。 「ファイル」メニューの中の「保存」を選んで、自分の決めたディレクトリ（フォルダ）内にファイルを保存する。 その際、 ファイル名の拡張子は必ず .c にすること （拡張子cはそれがC言語のソースプログラムであることを表す）。 ここで、ファイル名はdow.cとしておこう。

ステップ２：コンパイル

保存したソースプログラムをコンパイルするには、TurtleEditのウィンドウ内のコンパイルボタンを押す。

もし、ソースプログラムに何かの不具合（エラー）があれば、TurtleEditの下側の区画にエラーメッセージが表示されるので、行番号を手がかりに、エラー箇所を見つけ、修正すること。

コンパイルが正常に終了すると、TurtleEditの下側の区画に「正常終了」と表示される。

コンパイルが成功した状態で、作業ディレクトリ確認ボタンを押すと、ソースプログラムの保存先の ディレクトリ名と、その中のファイルの一覧が表示される。現在作業中のファイル名（この場合はdow.cは赤字で 表示されている。 リストを注意深く眺めると、a.outというファイルも見つかるはずだ。 これがコンパイルによって生成された機械語のデータが格納されたファイルになる。

ステップ３：実行（および中断）

コンパイルされたプログラムを実行するには、TurtleEditの実行ボタンを押す。

このとき、もしも予期せぬ動作をした場合は中断ボタンを押せば、プログラムを強制終了することができる。

この例題プログラムは、西暦年、月、そして日をキーボードから入力するように求めてくる。 TurtleEditの下側の区画をマウスでクリックし、赤い四角いカーソルが出ている状態で、キーボードからそれぞれの項目を入力しEnterを押すと、 最後に、その日の曜日が出力されるはずだ。 例えば、あなたの誕生日は何曜日だろうか？。

　練習：実習のための専用のディレクトリを作成

今後の実習のために、各自のホームディレクトリの中に、Cのプログラムを保存するための専用ディレクトリを作成しておくこと。 ディレクトリ名は自由だが、日本語と空白文字（スペース）は使わないこと。 無難な名前の例としては、"c", "cprog", "c_examples", 等々。

亀場で練習：グラフィックスを描いてみる

「亀場」を使うため準備のページを開き、説明を手がかりに、「亀場」の画面に四角形を描けることを確認しなさい。

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

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(5,a,c,b) ;
}

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

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