CONTENTS / BACK-PAGE / NEXT-PAGE

4.4 配列

 前節で、同じ処理を何回も繰り返し行なうことはプログラムにとって得意とすることであると学んだ。ここでは、同じ種類の大量のデータを容易に扱うために、配列と呼ばれる変数を導入する。

 いま、10個のデータ(例えば生徒の成績など)を扱うことを考えたとき、

int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10;
のような変数を宣言をし、これら個々の変数について個別の処理、例えば

	scanf("%d", &a1);
	scanf("%d", &a2);
		:
		:
	scanf("%d", &a10);
のように1つづつ記述しなければならない。これが100個,1000個のデータであったらどうであろうか。そこでこれらを番号付けした(添字を持った)変数として宣言し、扱いを容易にすることができる。これが配列変数である。配列は、ロッカーのように番号付けされており、下図のような概念である。

 配列宣言の一般形式は、

int a[n];
のようである。ここで、nは自然数であり配列要素の個数を表わす。C言語では配列の添字は0から始まるため、要素は、a[0], a[1], a[2], ... , a[n-1] のn個であり、この場合要素として a[n] は利用できないので注意しなければならない。配列は、1つの変数aにn個のデータを格納することができるものである。


例4−7

 20個の実数データを読み込み、合計を求めるプログラムをつくる。

考え方:

 個本的な考え方は、例4−5とほとんど同じである。与えられた実数データをa[0], a[1], a[2], ... , a[19]とすると、総和は次のような式で書ける。

      souwa = a[0] + a[1] + a[2] + ・・・・ + a[19]
 これをアルゴリズムで考える。
	1 souwa を0に初期化する
	2 20個のデータをaに読み込む
	3 i を0に初期化する
	4 souwa に a[i] の値を加える
	5 i の値に1を加える
	6 i の値が 19 より小さい時はステップ4へ、それ以外の時はステップ7へ
	7  データと souwa を出力

流れ図

プログラム4−7

/*  1 */  /*  Program 4-7                      */
/*  2 */  /*  20個のデータの合計を求める    */
/*  3 */  #include <stdio.h>
/*  4 */  main()
/*  5 */  {
/*  6 */      int i;
/*  7 */      float  souwa, a[20];
/*  8 */
/*  9 */      for (i = 0; i <= 19; i = i+1 )
/* 10 */          scanf("%f", &a[i]);
/* 11 */      for (souwa = 0, i = 0; i <= 19; i = i + 1)
/* 12 */          souwa = souwa + a[i];
/* 13 */
/* 14 */      for (i = 0; i <= 19; i = i + 1)
/* 15 */          if ( (i+1)%5 == 0 )
/* 16 */              printf(" %6f\n", a[i]);
/* 17 */          else
/* 18 */              printf(" %6f", a[i]);
/* 19 */      printf("\nGoukei = %f\n", souwa);
/* 20 */  }

実行例

1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10

 1.000000 2.000000 3.000000 4.000000 5.000000
 6.000000 7.000000 8.000000 9.000000 10.000000
 1.000000 2.000000 3.000000 4.000000 5.000000
 6.000000 7.000000 8.000000 9.000000 10.000000

Goukei = 110.000000

***解説***

7:配列aの宣言で、20個の実数要素を扱うことを意味する。
9−10:配列aにデータの読み込みである。配列の添字は0から始まるためfor文の初期値は i=0 で、終了条件は i<=19 になっている。&a[i]のiが0から19に変化し配列aにデータが読み込まれる。
12−13:合計を求めている。forの初期値として、souwa=0 と i=0 の2文があることに注意すること。for文は、 for(式1;式2;式3) 文;のスタイルをしていることは4−3(3)で学んだが、それぞれの式には複数の式がかくことができる。1つ目の;が来るまで式1(初期値の設定する文)をいくつも書くことができる。式2,式3についても同様である。
15−19:入力したデータの出力である。ここでは、データを横に5個出力したら改行するように細工されている。出力個数が5で割り切れたとき改行するようになっている。それが17−18:である。
20:合計の出力である。

*** 注意 ***

 上記解説12−13:でfor文の形式について解説したが、プログラム12−13:を次のように書くこともできる。

/* 12 */    for (souwa = 0, i = 1; i <= 19; souwa = souwa + a[i], i = i + 1)
/* 13 */        ;
これは、for(式1;式2;式3) 文; の文が省略された形になっており、C言語の文法として正しいものである。しかし、繰り返す内容が明記されたプログラム中の12−13:の形式を薦める。

 つぎは、文字の配列を使って文字列の操作を考えてみよう。


例4−8

 2組の文字列を入力し、英語の辞書引き順で先に出て来る文字列を出力するプログラムを作る。

考え方:

 文字列を頭からアルファベットを1つづつ比較し、辞書引き順を決める。

アルゴリズム:

  1. 2つの英単語をstring1,string2に入力する,
    同時に文字列の長さもカウントし、それぞれlen1,len2に代入する
  2. i ← 0に初期化
  3. 各文字列の先頭から1つづつアルファベットを比較し、 最初に異なったアルファベットの位置を捜しiに代入する
  4. string1[i] と string2[i] の大小を比べる ( writestr ← string1[i] - string2[i] )
  5. もし writestr < 0 ならば string1 を出力
       writestr >= 0 ならば string2 を出力

プログラム 4−8

/*  1 */  /*  Program 4-8        */
/*  2 */  /*  文字列の比較       */
/*  3 */
/*  4 */  #include <stdio.h>
/*  5 */
/*  6 */  main()
/*  7 */  {
/*  8 */      char string1[80], string2[80], c;
/*  9 */      int len1, len2, i, writestr;
/* 10 */
/* 11 */      len1 = 0;
/* 12 */      while((c = getchar()) != '\n')
/* 13 */      {
/* 14 */          string1[len1] = c;
/* 15 */          len1 = len1 + 1;
/* 16 */      }
/* 17 */      string1[len1] = '\0';
/* 18 */
/* 19 */      len2 = 0;
/* 20 */      while((c = getchar()) != '\n')
/* 21 */      {
/* 22 */          string2[len2] = c;
/* 23 */          len2 = len2 + 1;
/* 24 */      }
/* 25 */      string2[len2] = '\0';
/* 26 */
/* 27 */      for (i=0;(i<len1)&&(i<len2)&&(string1[i]==string2[i]);i=i+1)
/* 28 */          ;
/* 29 */
/* 30 */      writestr = string1[i] - string2[i];
/* 31 */
/* 32 */      if (writestr < 0)
/* 33 */          printf("%s\n", string1);
/* 34 */      else
/* 35 */          printf("%s\n", string2);
/* 36 */  }

実行例

program lecture lecture aiueo aiu aiu aiueo aiueo aiueo

***解説***

8:文字列のための配列の宣言で、最大80の長さの文字列まで対応している。
9:各文字列の長さを格納するための変数を、それぞれ len1,len2 とし、大小を比較した結果を格納するための変数として writestr を宣言する。
11−17: 1つめの文字列 string1の読み込みをすると同時に、文字列の長さを比較している。11:の getchar() は1つのキャラクタを読み込むためのライブラリ関数であり、読み込んだキャラクタを c の代入する。 while 文では、読み込んだキャラクタが改行記号(\n)になるまで、配列にキャラクタの格納と文字列の長さのカウントを繰り返す。17:では、文字列の最後に特殊なコード \0 を代入している。これについては後章で詳しく解説するが、文字列には必ず文字列の最後を表わすコード \0 がなくてはならないためこのような代入文をあえていれた。
18−25:2つめの文字列 string2 を読み込んでいる。1つめの文字列の読み込みとまったく同じである。
27−28:2つの文字列の先頭から順にキャラクタを比較し、最初に異なったキャラクタが現われた場所を捜している。繰り返しの条件には、それぞれの文字列の長さ以内でかつ同じキャラクタのあいだは、次のキャラクタを見るようにしている。つまり、(i が1つめの文字列の長さより小さく)かつ(i が2つめの文字列の長さより小さく)かつ(2つの文字列の i 番目のキャラクタが等しい) あいだは、for文を繰り返す( i を1増加する)。
30:最初に異なったキャラクタのコードの差を writestr に代入する。この値が負の時は、 string1 の方が辞書引き順で先に出現することになる。また、これは文字列の終端を示すコード \0 は、どのアルファベットよりもコードとして小さいという事実に基づいている。
31−35:writestr の値によって文字列の出力をコントロールしている。33,35:の printf ないの %s は文字列の出力をするための出力指令である。この場合は、配列の変数名だけ記述して、[ ]はつけなくてよい。もし %s と使わないのであれば、
    33:    for( i = 0; i < len1; i = i + 1)
                printf("%c", string1[i]);
としてもよい。
 プログラム4−8は文字列を操作するライブラリ関数を用いると、プログラムが非常に簡単になる。


プログラム4−8−2

/*  1 */  /*    Program  4-8-2                      */
/*  2 */  /*    文字列の比較  ライブラリ使用版  */
/*  3 */  /*                                        */
/*  4 */  #include <stdio.h>
/*  5 */  #include <string.h>
/*  6 */  main()
/*  7 */  {
/*  8 */      char string1[80], string2[80];
/*  9 */      int k;
/* 10 */
/* 11 */      printf("Input string1... ");
/* 12 */      gets( string1 );
/* 13 */      printf("Input string2... ");
/* 14 */      gets( string2 );
/* 15 */
/* 16 */      k = strcmp(string1, string2);
/* 17 */      if(k < 0 )
/* 18 */           puts(string1);
/* 19 */      else if(k < 0)
/* 20 */           puts( string2 );
/* 21 */  }
/* 22 */
/* 23 */

***解説***

11:文字列を入力するためのライブラリ関数である。改行コード(CR)が入力されるまでが、文字列の一部となる。改行コードは文字列には含まれない。 scanf("%s",string1); としてもよい。ただし、文字列にスペースやタブがいれられない。これらは区切り記号とみなされ、scanf の入力がそこで終わってしまう。また &string1 でないことに注意すること。これについては、後章のポインタのところで詳しく解説する。
15:2つの文字列を比較するライブラリ関数 strcomp を用いている。この場合 string1 のほうが辞書引き順で先であれば、関数として負の値を持つ。
18:文字列を出力するライブラリ関数である。11:で解説したことと同様に、scanf で扱えないキャラクタ(スペースやタブ)を出力できる。
 例4−7では、a[0], a[1], a[2], ... のように1次元の配列を扱ってき た。しかしある学校の成績の一覧表を扱うことを考えたときに、生徒1人に 対して英語,数学,国語,理科,社会,5科目の平均の6項目をデータとし て持ち、生徒が50名であればそれが50個必要となる。このとき、
float eng[50], mat[50], jap[50], sci[50], soc[50], ave[50];
のような変数の宣言をして、それぞれの配列の添字が生徒の番号と対応させ なければならない。i番目の生徒の平均点は  ave[i] = ( eng[i] + mat[i] + jap[i] + sci[i] + soc[i] ) / 5; として求めればよい。

 しかし配列を

float a[50][6];
のように2次元に宣言することもでる。概念的には、下図のようになる。

 この場合、 a[i][j]のiが生徒の番号で、jを0が英語,1が数学,2が国語,3が理科,4が社会,5が平均点と解釈してやれば、i番目の生徒の平均点は
	for( x = 0, j = 0; j < 5; j = j+1 )
	    x = x + a[i][j];
	a[i][6] = x;
のようにしてやれば、わさわざ5科目の変数を書かなくてもよくなる。こう することによって、もし7科目に増やしたい時には容易にプログラムを変更 することができる。


例4−9

 50人の生徒に対し、生徒の番号,英語,数学,国語,理科,社会,5科 目の平均を表に出力するプログラムを作成せよ。

考え方:

例5−7の合計を求めるプログラムを各生徒に対して行なえばよい。

流れ図

プログラム4−9

/*  1 */
/*  2 */  /*    Program 4-9         */
/*  3 */  /*   成績表の作成     */
/*  4 */  #include <stdio.h>
/*  5 */
/*  6 */  main()
/*  7 */  {
/*  8 */      int a[50][5], x;
/*  9 */      float heikin[50];
/* 10 */      int i, j;
/* 11 */
/* 12 */      for (i = 0;i < 50; i = i + 1)
/* 13 */          for (j = 0; j < 5; j = j+ 1)
/* 14 */              scanf("%d", &a[i][j]);
/* 15 */
/* 16 */      for (i = 0; i < 50; i = i + 1)
/* 17 */      {
/* 18 */          x = 0.0;
/* 19 */          for (j = 0; j < 5; j = j + 1)
/* 20 */              x = x + a[i][j];
/* 21 */          heikin[i] = (float)x / 5.0;
/* 22 */      }
/* 23 */
/* 24 */      for (i = 0; i < 50; i = i + 1)
/* 25 */      {
/* 26 */          printf ("%2d: ", i+1);
/* 27 */          for (j = 0; j < 5; j = j + 1)
/* 28 */              printf("%4d", a[i][j]);
/* 29 */          printf("%7.2f\n", heikin[i]);
/* 30 */      }
/* 31 */  }



 1:   80  75  93  53  65  73.20
 2:   62  32  45  65  78  56.40
 3:  100  90  79  85  89  88.60
 4:   75  69  84  90  77  79.00
 5:   78  45  32  65  89  61.80
        :
        :
        :

***解説***

8:成績データ50名,5科目分の配列を宣言する。
9:平均のデータを格納するために、実数が格納できるための配列の宣言をする。
12−14:成績データの読み込み。
16−22:各生徒に対し、5科目のデータを合計し、その平均を求めている。forの繰り返しが2重になっていることに注意せよ。16:では、生徒50名分を繰り返している。19:では、5科目のデータの合計を求めるために繰り返しを用いている。21:では、平均を求めている。ここで(float) とは、キャスト演算子と呼ばれ、整数型の変数xを一時的に実数(float)型に変換するためのC言語特有の演算子である。平均はデータとして実数であるのに対して、5科目の合計は整数であるため、代入の左辺と右辺の型を一致させる必要があるからである。型の異なった代入をするときによく用いられる演算子である。
24−29:5科目データと平均の出力をする。26:では、生徒の番号を出力している。printf 内の %2d は2桁右詰めでデータを出力するための、出力制御である。27−28:で5科目データの出力を行なっている。ここでは、%4d で4桁右詰めで出力をする。29:で平均を出力する。%7.2f は、7桁右詰めで小数点以下2桁の実数を出力するための制御である。7桁は、小数点も含まれているため、整数部分としては4桁になる。

演習問題

 20までの階段関数(フィボナッチ関数)を求めるプログラムを作れ。

ただし階段関数とは、

  f(0)=0
  f(1)=1
  f(2)=f(0)+f(1)=1
  f(3)=f(1)+f(2)=2
      :
      :
  f(20)=f(18)+f(19)

のように、一般的に

  f(n)=f(n−2)+f(n−1)
で表わされるものである。

 ヒントとしてf(0)とf(1)を与えておき、nを2から20まで繰り 返しf(n)を求める。


4.5 関数

 本章では処理の制御ということで、条件分岐,繰り返しを実現するための文法について学んできた。本節では処理の制御の最後として「関数」について学ぶ。

4.5.1 関数の考え方

関数と聞くと数学で

     f(x)=x^2+3x+4

のようなスタイルを思い浮かべるであろう。これはxが1の時f(x)の値は(1^2+3・1+4=)8で、xが2の時f(x)の値は(2^2+3・2+4=)14で、...のようにxに適当な数値を割り当てることによりf(x)の値を得ることができるものである。このfが関数名で=以下がfの内容になる。これと同様なことがCプログラムにも言える。scanf,printf,sqrt,gets,putsなどを考えてみよう。これらはみなCプログラムの関数であることは、すでに学んだ。例えば文字や数値の入出力を行ないたい時に、

     関数名( 書式 )

と記述する事により、容易に入出力を行なってきた。これは、あらかじめよく利用される機能をライブラリ関数としてCコンパイラが持っていて、利用者は関数の操作の詳細をまったく知らなくても括弧内の書式を知っているだけで使うことができた。4.4節のプログラム4−8と4−8−2の文字列の比較を考えてみると、4−8−2のようにstrcmp関数を呼んでやれば4−8のように長いプログラムを書かなくても済むことになる。また、比較する文字列を換えたい時には、プログラム4−8ではプログラムそのものを変更する必要があるが、プログラム4−8−2では書式中の文字列のみを変更してやれば簡単に結果が得られる。このように、書式が数学の関数の変数xに対応し、操作の詳細が=以下の数式に対応する。

 下記の図のように、大きなまとまった操作を一つの関数として定義し、それを呼び出すことによってプログラムの処理の流れを一時別な所に移しまたもとに戻すことができる。

図 関数呼び出しによる処理の移動

関数Aの呼び出しは何回も可能で、呼ばれるたびに処理が関数Aに移る。

 Cプログラムでは、ライブラリ関数以外に独自の関数を定義し利用する事ができる。プログラムの初めの部分でmain()と記述していたが、これは関数名mainで書式なしの関数を“{”以下に定義することを示している。これと同じ方法で独自の関数を定義することができる。

 関数をうまく使うことによりプログラムの各部の操作の詳細を隠し、プログラムの全容を明確にすることができるとともに見やすい分かりやすいプログラムを書くことができるようになる。関数は、2章で述べた構造化プログラミング(トップダウンプログラミング)が容易に実現させる一つの手段でもある。


4.5.2 関数による処理の移動

 簡単な例を用いての関数の考え方と処理の移動について理解しよう。

例4−10 2つの数値を読み込んで、平方和を戻す関数addsqrを定義せよ。

流れ図


プログラム4−10−1 関数に変数の値を直接渡す方法

/*  1 */  /*  Program 4-10-1  */
/*  2 */  /*  2数の平方和を計算する  */
/*  3 */  #include <stdio.h>
/*  4 */
/*  5 */  int addsqr(int x, int y);
/*  6 */
/*  7 */  main()
/*  8 */  {
/*  9 */      int a, b, c;
/* 10 */
/* 11 */      printf("a = ");
/* 12 */      scanf("%d", &a);
/* 13 */      printf("b = ");
/* 14 */      scanf("%d", &b);
/* 15 */      c = addsqr(a, b);
/* 16 */      printf("%d^2 + %d^2 = %d\n", a, b, c);
/* 17 */
/* 18 */  }  /*  End of main  */
/* 19 */
/* 20 */  int addsqr(int x, int y)
/* 21 */  {
/* 22 */      int d;
/* 23 */
/* 24 */      d = x * x + y * y;
/* 25 */      return (d);
/* 26 */
/* 27 */  }  /*  End of addsqr  */

実行例

a = 3 b = 5 3^2 + 5^2 = 34

***解説***

5:このプログラム内で利用する関数の宣言をする。ここでは、関数がどんなタイプ(どんな型の結果を戻してくるか)で、呼び出す時の名前とどんなタイプのデータを与えるかの書式のみを宣言する。この行は省略可能であるが、あらかじめこのように関数のヘッダ(関数定義の第1行目)を宣言しておくことにより、プログラムの作成のし易さやエラー発生の防止の役に立つために、書くことを薦める。
11−14:2つのデータの入力。
15:平方和の計算をする関数の呼び出しである。2つの値a,bを持って関数addsqrへ飛び、そこで計算した結果を持って戻ってきて、その値を変数cに代入している。この場合、cの型(int)とaddsqrの型(5:で宣言した型)が一致していなければならない。
16:結果の出力。
20:関数addsqrの定義の開始。5:と同じである。ただし、ここではこの後に関数の実体が定義されるため;を最後に付けてはならない。addsqrの型がintであり、int型のxとint型のyの2つ値を持って飛んできたことを意味する。関数を呼ぶところ(15:)と関数の定義(5:と20:)で型を一致させる必要がある。
22:関数addsqr内でのみ使える変数dの宣言。
24:平方和の計算結果を変数dに代入。
25:関数addsqrの値をしてdを持ち帰ることを意味するreturn文である。addsqrの値はint型であることを5:と20:で宣言しているため、dもint型でなくてはならない。

関数の一般形式は、

	戻り値の型 関数名( 仮引数の並び )
	{
	  変数の宣言;

	  実行文;

	  return 式;
	}
のようであり、いままで紹介してきたプログラムの形式と同じである。

 関数を使うと、プログラムの処理の流れを換えることが出来ることに気付くであろう。プログラム4−10−1では、

	7→8→9→10→11→12→13→14→15→16→17→18
	                     ↓↑
	     ←←←←←←←←←←←←←←←←  ←←←←←←←←←  
	    ↓                           ↑
	     → 20→21→22→23→24→25→26→27 →  
のように、15:から20:へ飛び、再び15:に戻って来る。 また、関数は何回も呼び出すことができ、17:に

/* 17 */ c = addsqr( c, a );
を加えると、cには c^2+a^2 の結果が代入される。入力されたa,bの値でcを表現すると、17:の処理が終了した時点ではcには (a^2+b^2)^2+a^2 の計算値が格納されていることになる。これは、2回のaddsqr関数が呼ばれたた結果である。

 上記関数addsqrのように、呼ばれる関数を呼ぶ関数のサブルーチンと呼ぶ。つまり、addsqrはmainのサブルーチンである。

 プログラム4−10−1では、2つの値を持ってサブルーチンに飛んでいった。つまり、a,bの値をx,yにコピーする形式をとっていた。この場合、aとx、bとyで記憶領域を2倍使ってしまうことになる。しかし、サブルチーンでx,yの値を更新してもメインのa,bにはなんら影響を与えないという利点はある。反対にサブルーチンで更新された値をメインにも繁栄したいことがある。そのために、値そのものを持ってサブルーチンに飛ぶのではなく、値が格納されている記憶領域の場所をもってサブルーチンに飛ぶ方法がある。プログラム4−10−2の格納領域(番地)を受け渡す方法の例である。

 番地呼び出しは、次章で予定しているポインタと深い関連があるので、ポインタを学んだ後にもう一度見返していただきたい。


プログラム4−10−2 関数に変数の番地を渡す方法

/*  1 */  /*  Program 4-10-2  */
/*  2 */  /*  2数の平方和を計算する  Ver 2  */
/*  3 */  #include <stdio.h>
/*  4 */
/*  5 */  int addsqr(int *x, int *y);
/*  6 */
/*  7 */  main()
/*  8 */  {
/*  9 */      int a, b, c;
/* 10 */
/* 11 */      printf("a = ");
/* 12 */      scanf("%d", &a);
/* 13 */      printf("b = ");
/* 14 */      scanf("%d", &b);
/* 15 */      c = addsqr(&a, &b);
/* 16 */      printf("%d^2 + %d^2 = %d\n", a, b, c);
/* 17 */
/* 18 */  }  /*  End of main  */
/* 19 */
/* 20 */  int addsqr(int *x, int *y)
/* 21 */  {
/* 22 */      int d;
/* 23 */
/* 24 */      d = (*x) * (*x) + (*y) * (*y);
/* 25 */      return (d);
/* 26 */
/* 27 */  }  /*  End of addsqr  */

実行例

a = 1 b = 5 1^2 + 5^2 = 26

***解説***

5:関数addsqrのヘッダの宣言。番地呼び出しされる場合の仮引数の前には、*を付ける必要がある。
15:addsqrの呼び出し。番地呼び出しのため、値が格納されている位置を渡すように、変数の前に&が付いている。scanfのパラメータにも&を付けることと同じように、&変数名で格納位置を示す。
24:平方和の計算をして、cに代入する。この関数内では、x,yは格納番地であるため、そこに格納されている値を参照するために、*x、*yのように*を付けることによって、参照ができる。*は、格納番地の指す内容を意味する。

**注意**

 必ずしも番地を受け渡す方法がよいのではなく、関数(サブルーチン)呼び出しには、2つの方法があることを示した。この例の場合は、16:でa,bの入力値を出力(参照)しているので、万一サブルーチンでx,yの値を壊すことがあってもmainではもとの値が壊れることがないので、値そのものを渡した方がよいであろう。

 24:を

/* 24 */ d = (*x) * (*x) + (*y) * (*y); *x = 1; *y = 2;
のように変更すると、16:の出力結果は、いつでも a=1, b=2 になってし まう。プログラム4−10−2では、24:を

/* 24 */ d = x * x + y * y; x = 1; y = 2;
のように変更しても、16:での出力結果は入力したa,bの値が出力される。






(演習問題:上記を試してみよ。)





次の例は、配列変数を引数にした場合である。単純変数を引数にした場合と多少扱いが異なるので注意すること。

例4−11 10個の数値を昇順に並べ換える関数sortnumberを定義せよ。

流れ図

 データの並べ換えには、単純選択ソートと呼ばれるアルゴリズムを採用する。このアルゴリズムは、以下のようである。

  1.  i←0
  2.  i← i+1
  3.  もし i>=データの最後の番号 ならば ステップ6へ
  4.  左からi+1番目のデータから順に右方向に最後までデータを見ていき、その中で最小のデータとi番目のデータとを交換する。
  5.  ステップ2へ
  6.  終わり

ソートの例

   4  10  1  9  5  2  7  3  8  6  の時

ステップ1,2,3,4を実行後

   1  10  4  9  5  2  7  3  8  6    ←1番目と3番目のデータが交換され、
                       この時点で一番左に最小のデータがくる
ステップ5,2,3,4を実行後

   1  2  4  9  5  10  7  3  8  6    ←2番目と6番目のデータが交換され、
                       この時点で左から2番目までが並べ換わっている
ステップ5,2,3,4を実行後

   1  2  3  9  5  10  7  4  8  6    ←3番目と8番目のデータが交換され、
                       この時点で左から3番目までが並べ換わっている
          :
          :
          :
   1  2  3  4  5  6  7  8  9  10    ←並べ換え終了。

プログラム4−11

/*  1 */  /*  Program 4-11  */
/*  2 */  /*  数値の並べ替え  */
/*  3 */  #include <stdio.h>
/*  4 */
/*  5 */  void sortnumber(int n, int s[]);
/*  6 */
/*  7 */  main()
/*  8 */  {
/*  9 */      int i,content, data[50];
/* 10 */
/* 11 */      content = 10;
/* 12 */      for (i = 0; i < content; i = i + 1)
/* 13 */      {
/* 14 */          printf("Input %2d number ", i + 1);
/* 15 */          scanf("%d", &data[i]);
/* 16 */      }
/* 17 */      for (i = 0; i < content; i = i + 1)
/* 18 */          printf(" %d", data[i]);
/* 19 */      printf("\n");
/* 20 */
/* 21 */      sortnumber(content, data);
/* 22 */
/* 23 */      for (i = 0; i < content; i = i + 1)
/* 24 */          printf(" %d", data[i]);
/* 25 */      printf("\n");
/* 26 */
/* 27 */  }  /*  End of main  */
/* 28 */
/* 29 */
/* 30 */  void sortnumber(int n, int s[])
/* 31 */  {
/* 32 */      int i, j, k, dummy;
/* 33 */
/* 34 */      for (i = 0; i < n; i = i + 1)
/* 35 */      {
/* 36 */          k = i;
/* 37 */          for (j = i+1; j < n; j = j + 1)
/* 38 */             if(s[j] < s[k])
/* 39 */                 k = j;
/* 40 */          dummy = s[i];
/* 41 */          s[i] = s[k];
/* 42 */          s[k] = dummy;
/* 43 */      }
/* 44 */  }  /*  End of sortnumber  */

実行例

Input 1 number 4 Input 2 number 10 Input 3 number 1 Input 4 number 9 Input 5 number 5 Input 6 number 2 Input 7 number 7 Input 8 number 3 Input 9 number 8 Input 10 number 6 4 10 1 9 5 2 7 3 8 6 1 2 3 4 5 6 7 8 9 10

***解説***

5:並べ換えする関数sortnumberのヘッダ部の宣言。データの個数nと並べ換えるデータsを仮引数として宣言し、これらを持って関数sortnumberへ飛ぶ。ここで、sの[]は、配列を意味している。sortnumber関数は、戻り値を持たない関数であるため、void型で宣言されている。
9:繰り返し作業のための変数i,並べ換えをする個数を格納する変数content,並べ換えのデータとして最大50個までを扱える配列変数dataの宣言。
11:並べ換えの個数を10個とする。こうすることにより、データの数が多くなったときには、9:の50と、ここの10を大きな数に変更してやれば、プログラム全体を修正しなくてもよくなる。この文がない場合は、プログラム中のcontentがすべて10になっており、10を50に変更しなければならない時は、すべての10を変更しなければならない。これは、手間がかかりミスを引き起こす原因となる。プログラムを書くときには、なるべく汎用性を持たせるようにするのが、コツである。
12−16:10個のデータを入力する。
17−19:入力したデータを出力する。
21:10個のデータを並べ換えるためのサブルーチンsortnumberを呼んでいる。sortnumberはvoid型であるために、プログラム4−10−1のように関数の結果を代入する必要がない。void型の関数は、関数というよりむしろ手続きと呼んだ方が適当であろう。
23−25:並べ換えたデータの出力。関数sortnumberは戻り値がないことを上で説明したが、なぜここで出力したデータが並べ換わっているのであろうか? それは配列変数を引数にした場合は、すべて番地呼び出しになるためである。このため、30:以降の配列s[]とdata[]は、同じ記憶領域を使っていることになっているので、値を戻す必要がない。
30:関数sortnumberのヘッダ部。配列の場合は、番地呼び出しでも変数の前に*が付かないことに注意する事。
34−43:単純選択ソートのアルゴリズムによりデータの並べ換えをする。

***注意***

 単純変数と配列変数を引数にする場合では、形式が異なっているので注意 が必要である。配列変数の場合は番地呼び出ししかないので、サブルーチン 内で引数データの更新を行なうときには注意をはらう必要がある。思わぬ所 でデータを壊すことがある。

 番地呼び出しとポインタ型(次回の予定)は、密接な関係があるためそこ でもう一度解説するので、ここではこの辺でやめにする。


4.5.3 関数による繰り返しの実現(再帰構造)

 関数を再帰的に呼ぶことによって、繰り返しの構造をつくることができる 。再帰とは、関数が自分自身を直接または間接に呼び出すことで、Cプログ ラムでも再帰が許されている。例えば、数学で f(n)=n! (nの階 乗) を考えよう。

	3の階乗は、 3! = 3×2×1
	5の階乗は、 5! = 5×4×3×2×1
	nの階乗は、 n! = n×(n−1)×(n−2)×・・・×2×1
のような計算式となる。一般に n!=n×(n−1)! であるから、関数fで定義しなおすと

	  f(n) = ┏ 1         :n=0の時
	         ┗ n×f(n−1)  :n>0の時
のように定義できる。この場合、nの階乗を定義するのに(n−1)!を使 っている。つまり再帰的な定義になっている。

 現在までにみなさんに解説した知識でnの階乗をもとめる関数をプログラ ムすることを考えると、for文などのループ(繰り返し)を使って、1か らnまで順次かけ算することになるであろう。これでも決して悪くないのだ が、もとの関数が再帰的に定義されていれば、Cプログラムも再帰的に書き たいと思うであろうし、問題とプログラムの考え方が一致しているので分か りやすい。例4−12で再帰的関数定義を理解しよう。


例4−12は、n!を再帰的に関数を定義せよ。

プログラム4−12

/*  1 */  /*  Program 4-12          */
/*  2 */  /*  n階乗を求める        */
/*  3 */
/*  4 */  #include <stdio.h>
/*  5 */
/*  6 */  int fact(int n);
/*  7 */
/*  8 */  main()
/*  9 */  {
/* 10 */      int a, b;
/* 11 */
/* 12 */      printf("a=");
/* 13 */      scanf("%d", &a);
/* 14 */
/* 15 */      b = fact(a);
/* 16 */
/* 17 */      printf("%d! = %d\n",a, b);
/* 18 */
/* 19 */  }
/* 20 */
/* 21 */  int fact(int n)
/* 22 */  {
/* 23 */      int dum;
/* 24 */
/* 25 */      if (n == 0)
/* 26 */          dum = 1;
/* 27 */      else
/* 28 */          dum = n * fact(n - 1);
/* 29 */
/* 30 */      return dum;
/* 31 */
/* 32 */  }  /*  End of fact  */

実行例

a=3 3! = 6 a=4 5! = 120

***解説***

6:階乗を求める関数factのヘッダ部の宣言。引数にはnを渡すようにする。
25:nの値が0の時とそれ以外の時に処理を分けている。
26:n=0の時の処理で、fact(0)の値として1を戻すようにしている。戻す値を一時的に変数dumに代入している。
27:n<>0の時の処理で、fact(n)の値として、n×fact(n−1)を戻すように、dumに代入する。ここで、fact(n−1)を呼んでいるので再帰的になっている。
30:関数factの値として、dumに代入された値を戻す。

変数dumを使わず、直接値を戻すこともできる。21−32:を以下のよ うに変更してもよい。

/* 21 */  int fact(int n)
/* 22 */  {
/* 23 */      if (n == 0)
/* 24 */          return  1;
/* 25 */      else
/* 26 */          return n * fact(n - 1);
/* 27 */
/* 28 */  }  /*  End of fact  */
 return文は、1つの関数の中に複数存在してもよい。


***注意***

 再帰的に定義する際には、一般項(一般式)と再帰の停止条件を考えれば、簡単にプログラムが書けるようになる。再帰の停止条件を誤ると再帰が無限に深く潜って行き、プログラムが終わらなくなることがあるので、気を付けること。

 数学的な関数を再帰的に定義する方法については理解していただけたと思うが、値を戻さない手続きについても再帰的に定義できることを示そう。例4−13は、誰もがこのよな発想でプログラムを書かないと思うが、あえて再帰的な関数(手続き)で繰り返しを実現できる簡単な例である。


例4−13

 配列データ逆順に出力する関数を再帰的に定義せよ。

プログラム4−13

/*  1 */  /* program 4-13          */
/*  2 */  /* 再帰による出力例      */
/*  3 */  #include <stdio.h>
/*  4 */
/*  5 */  void printrec( int n, int data[] );
/*  6 */
/*  7 */  main()
/*  8 */  {
/*  9 */       int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
/* 10 */       printrec( 9, data );
/* 11 */       printf("\n");
/* 12 */  }
/* 13 */
/* 14 */  void printrec( int n, int data[] )
/* 15 */  {
/* 16 */       if ( n >= 0 )
/* 17 */       {
/* 18 */           printf("%5d", data[n]);
/* 19 */           printrec( n-1, data );
/* 20 */       }
/* 21 */  }

実行例

10 9 8 7 6 5 4 3 2 1

***解説***

5:逆順に出力する関数(手続き)のヘッダ部の宣言。
9:出力するためのデータを格納する配列変数dataの宣言である。いままで学んだ形式とは多少異なっている。[]内に配列の要素の個数の記述がなく、代わりに=以下にデータが記述されている。これは、変数を宣言すると同時に、変数の初期化が可能であり、配列の場合は{}内にデータを記述するとその値で配列の内容が初期化されまた自動的に配列のサイズ(要素の大きさ)もデータの数に合わせて決定される。
10:データを逆順に出力する関数printrecを呼んでいる。データの数が10個であるため配列の最後の添字は9になっているので、引数に9を渡している。printrecは、配列dataの添字9以下を逆順に出力する関数と解釈する。
16:配列の添字が0以上の時に出力するようになっている。これが、再帰の停止条件になっている。
18:添字nのデータの出力。
19:添字n−1以下のdataの内容を逆順に出力する関数printrecを呼んでいる。ここが再帰的になっている。

 この例により、繰り返しが再帰関数により実現できることがわかって頂けたと思う。

 さらにもう少し難しい再帰的な手続きの例をあげよう。よく参考書などに取り上げられるハノイの塔と呼ばれる有名な再帰の例題である。


例4−14 ハノイの塔を解くプログラムを作れ。

 ハノイの塔の問題とは、以下の通りである。

 図のにように棒の立ったお皿A,B,C3つあり、初期状態としてAのお皿の上には大きさの異なる円盤がn個置かれている。この円盤は、いつでも大きいものが小さいもの上になることのないように置かれている。このとき、次のルールの従ってAの円盤をそのままの状態ですべてCへ移すことを考える。

ルール

1 1度に1つの円盤しか移動できない。
2 円盤は、つねにお皿の一番上からしか取ることができない。
3 自分より小さい円盤の上には、大きい円盤は置いてはいけない。

考え方

n個の円盤をAからCへ移すためには、

 。舛肪屬い討△覬瀏廚鮠紊らn−1個あらかじめBへ移動。
◆。舛琉貳峅爾肪屬い討△辰娠瀏廚鬘辰悵椶后
 Bに置いておいたn−1個の円盤をCへ移動。

 △鉢のあいだでは、Bに置いてあるn−1個の円盤をCに移すことを考えればよい。この時点のBの状態を先のAと考え、Bを先のAと考えてやれば、上記´↓の手順がそのまま利用できる。上記手順を関数的に記述してみよう。

n個の円盤をAからCへ移す: move( n, A to C, using B )

   n−1個の円盤をAからBへ移動 : move( n-1, A to B, using C )
   Aの一番下にあった(n番目の)円盤をCへ移す : 出力( n を A から C へ )
   n−1個の円盤をBからCへ移動 : move( n-1, B to C, using A )
 このように記述してみると、手続きが再帰的になっていることに気付くであろう。つまりこれらが再帰の一般式になっている。これに再帰の停止条件つまり、nが1の時の状況を考えればよい。

 1個の円盤をAからCへ移す: move( 1, A to C, using B )

  Aにある1つの円盤をCへ移す : 出力( 1 を A から C へ )


プログラム4−14

/*  1 */  /*  Program 4-14-1  */
/*  2 */  /*  ハノイの塔  */
/*  3 */
/*  4 */  #include <stdio.h>
/*  5 */
/*  6 */  void move(int n, char a, char b, char c);
/*  7 */
/*  8 */  main()
/*  9 */  {
/* 10 */      int n;
/* 11 */
/* 12 */      printf("How many saucers do You want? ");
/* 13 */      scanf("%d", &n);
/* 14 */
/* 15 */      move(n, 'A', 'B', 'C');
/* 16 */  }
/* 17 */
/* 18 */  void move(int n, char a, char b, char c)
/* 19 */  {
/* 20 */      if(n > 1)
/* 21 */          move(n - 1, a, c, b);
/* 22 */      printf("saucer %2d : %c -> %c\n", n, a, c);
/* 23 */      if(n > 1)
/* 24 */          move(n - 1, b, a, c);
/* 25 */  }

実行例

How many saucers do You want? 4 saucer 1 : A -> B saucer 2 : A -> C saucer 1 : B -> C saucer 3 : A -> B saucer 1 : C -> A saucer 2 : C -> B saucer 1 : A -> B saucer 4 : A -> C saucer 1 : B -> C saucer 2 : B -> A saucer 1 : C -> A saucer 3 : B -> C saucer 1 : A -> B saucer 2 : A -> C saucer 1 : B -> C

***解説***

6:再帰関数moveのヘッダ部の定義。引数に、円盤の数とどこからどこへどこを利用しての4つがある。これらは、値呼び出しである。
15:moveの呼び出し。
18−25:再帰関数の定義。再帰の停止条件として、20:と23:のif文で円盤の数が1以下になったときに再帰で潜らなくしている。上記解説の,21:,△22:,が24:に対応している。
 実行例の見方は、数字が円盤の番号(上から1番,2番,...)を示している。

例えば、 sourcer 1 : A -> B は、1番の円盤をお皿Aからお皿Bへ移動 させることを意味する。実行例を試してみると、動きがよく分かると思う。

 このように再帰的にプログラムするとややこし操作がエレガントに記述す ることができるようになる。逆にこのプログラムを再帰を使わないとすごく 難しくなるであろう。機会があれば、見せたいと思う。

 お皿の名前をA,B,Cのかわりに数字の1,2,3に置き換えるとプロ グラムはより短いステップになるので、参考までにプログラム4−14−2 に載せて置く。


プログラム4−14−2

/*  1 */  /*  Program 4-14-2        */
/*  2 */  /*  ハノイの塔   Ver. 2   */
/*  3 */
/*  4 */  #include <stdio.h>
/*  5 */
/*  6 */  void move(int n, int s, int d);
/*  7 */
/*  8 */  main()
/*  9 */  {
/* 10 */      int n;
/* 11 */
/* 12 */      printf("How many saucers do You want? ");
/* 13 */      scanf("%d", &n);
/* 14 */
/* 15 */      move(n, 1, 3);
/* 16 */  }
/* 17 */
/* 18 */  void move(int n, int s, int d)
/* 19 */  {
/* 20 */      if(n > 1)
/* 21 */          move(n - 1, s, 6 - s - d);
/* 22 */      printf("saucer %2d : %2d -> %2d\n", n, s, d);
/* 23 */      if(n > 1)
/* 24 */          move(n - 1, 6 - s - d, d);
/* 25 */  }

実行例

How Many Saucers Do You Want? 3 saucer 1 : 1 -> 3 saucer 2 : 1 -> 2 saucer 1 : 3 -> 2 saucer 3 : 1 -> 3 saucer 1 : 2 -> 1 saucer 2 : 2 -> 3 saucer 1 : 1 -> 3 How Many Saucers Do You Want? 5 saucer 1 : 1 -> 3 saucer 2 : 1 -> 2 saucer 1 : 3 -> 2 saucer 3 : 1 -> 3 saucer 1 : 2 -> 1 saucer 2 : 2 -> 3 saucer 1 : 1 -> 3 saucer 4 : 1 -> 2 saucer 1 : 3 -> 2 saucer 2 : 3 -> 1 saucer 1 : 2 -> 1 saucer 3 : 3 -> 2 saucer 1 : 1 -> 3 saucer 2 : 1 -> 2 saucer 1 : 3 -> 2 saucer 5 : 1 -> 3 saucer 1 : 2 -> 1 saucer 2 : 2 -> 3 saucer 1 : 1 -> 3 saucer 3 : 2 -> 1 saucer 1 : 3 -> 2 saucer 2 : 3 -> 1 saucer 1 : 2 -> 1 saucer 4 : 2 -> 3 saucer 1 : 1 -> 3 saucer 2 : 1 -> 2 saucer 1 : 3 -> 2 saucer 3 : 1 -> 3 saucer 1 : 2 -> 1 saucer 2 : 2 -> 3 saucer 1 : 1 -> 3

***解説***

15:関数moveの呼び出し。この場合は、n個の円盤をお皿1(A)からお皿3(C)へ移動させる手続きであると解釈すればよい。
18−25:move関数の定義。プログラム4−14−1では引数が4つであったのにたいして、今回は3つですんでいる。これは、円盤をどこからどこへがわかればどこを使ってというのは残りであることを利用しているからである。24:,26:で6−s−dという式が残りのお皿を算出している部分である。このような細工もプログラミングには必要とすることである。ただし、わかりやすさの面でいうとこのような細工はよくないのでは?

演習問題

 ユークリッドの互除法を用いて、2つの数の最大公約数を求めるプログラムを再帰的に定義せよ。ユークリッドの互除法については、以下の例で説明しよう。

	例 128と36の最大公約数を求める。
	 (128,36) → (36,128を36で割った余り)
	          → (36,20)
	          → (20,36を20で割った余り)
	          → (20,16)
	          → (16,20を16で割った余り)
	          → (16,4)
	          → (4,16を4で割った余り)
	          → (4,0)
	             ↑
	            この4が128と36の最大公約数

プログラミングのヒント

xとyの最大公約数を求める関数をgcd(x,y)とする。一般に

	gcd(x,y) = ┏ y         :r=0のとき
	           ┗ gcd(y,r)  :r>0のとき
	             ここで、y=(xをyで割った余り)とする
のような式が定義できる。


CONTENTS / BACK-PAGE / NEXT-PAGE