講義第11回：C言語 の基礎 --- 配列

配列

/* calculate_sum
 *
 * (C) J. Makino Version 1.0 Jan 26, 1997
 */
#include <stdio.h>

int  n ;
int  data[100];
int  i,sum;

void main()
{
    printf("How many numbers you want to input?");
    scanf("%d",&n);
    for (i=0;i<n;i++) scanf("%d",&data[i]);
    sum = 0;
    for (i=0;i<n;i++){
        sum += data[i];
        printf("data[%2d]=%5d, sum = %d\n", i,data[i],  sum);
    }
}

int  data[100] ;

配列の便利なところは、まず、変数宣言で int data0,data1,data2, .... data99 と書くよりずっと短くて済む（100万個変数が欲しかったら 大きな違いである）ということ、それから実行部も簡潔な繰り返しで書けると いうことである。特に大事なのは、番号（添字）に変数が使えるということで ある。このことのために、上のように、ループの中で配列の要素を順番に見る とか値をいれるとかいったことができる。

実行例

How many numbers you want to input?5
1
2
3
4
5
data[ 0]=    1, sum = 1
data[ 1]=    2, sum = 3
data[ 2]=    3, sum = 6
data[ 3]=    4, sum = 10
data[ 4]=    5, sum = 15

ソート

/* sort_data_from_file
 *
 * (C) J. Makino Version 1.0 Jan 26, 1997
 */
#include <stdio.h>

int n;
double data[100];
int   i,j;
double  work;

void main()
{
    for (i=0;scanf("%lf",&data[i])==1;i++);
    n =i;
    printf("Input data\n");
    for (i=0;i<n;i++) printf(" %5.2f",data[i]); printf("\n");
    for (i=0;i<n-1;i++){
        for (j=i+1;j<n;j++){
	    if (data[i] > data[j]){
                work = data[i];
                data[i] = data[j];
                data[j]= work;
	    }
	}
    }
    printf("Sorted data\n");
    for (i=0;i<n;i++) printf(" %5.2f",data[i]); printf("\n");
}

1. まず、一番小さい数を先頭に持ってくる。そのために、配列の2番 目の要素から最後の要素までを順に見て、それが先頭の値よりも小さければ2 つを入れ換える。

2. これで先頭にもっとも小さい数が来た。次に、2番目の位置に残りの 数の中で最小のものを持ってくる。これには、配列の3番 目の要素から最後の要素までを順に見て、それが2番目の値よりも小さければ2 つを入れ換える。

3. 以下、同様に、 N-1 番目まで順にやっていく。

simple_sort < sample.dat

注意 コンパイルして作るプログラムの名前には sort は使わな いこと。これは、この名前の別のプログラムがあらかじめ準備されていて、そ ちらが実行されてしまうからである。

なお、

    for (i=0;scanf("%lf",&data[i])==1;i++);

for ([0]初期化文; [1]条件; [3]文){[2]実行文 ; ...}

練習

1. 最初の、合計を求めるプログラムを配列を使わないで書き直して みよ。また、合計だけでなく平均と標準偏差をもとめるように拡 張せよ。配列を使わないで標準偏差を求めることはできるだろう か。

2. ソートのプログラムを手続きを使う形に書き直してみよ。メ インプログラムは手続きを呼 ぶだけの形になるようにすること。

3. ソートのプログラムについて、データの数を非常に大きくした時、実行時間がどうなるかを測定せよ。配列宣言の数字を大き くするのを忘れないこと。また理論上どうなるはずか考えてみよ。

4. （応用）適当な参考書または教科書を見て、クイックソート、マージソート、またはヒープソートのプログラムを作り、上でやったソートプログラムとの実行時間の違いについて考察せよ。

time simple_sort < sample.dat

0.040u 0.080s 0:00.56 21.4% 0+135k 2+0io 21pf+0w

再帰

もっとも簡単な例

/* factrial
 *
 * (C) J. Makino Version 1.0 Jan 26, 1997
 */
#include <stdio.h>
double factrial(double n)
{
    if (n <=1.0){
	return 1.0;
    }else{
	return  n*factrial(n-1);
    }
}

void main()
{
    double n;
    printf("Enter n : ");
    scanf("%lf",&n);
    printf("N = %5.0f  N! = %20.13g\n", n,factrial(n) );
}

CやPascalのような「近代的」プログラミング言語では、この定義に従って素直にプログ ラムを書くことができる（これに対して、古いBASICなどではできない）。上の例では、まさに、 n が 1 なら 1 を返 し、それ以外では n*factrial(n-1)を返すというのが、 factrial(n)の中身になっている。 例えば factrial(5) を計算させるとすると、実際の計算は、以下のよ うな手順で進む。

factrial(5)
→5*factrial(4)
→5*(4*factrial(3))
→5*(4*(3*factrial(2)))
→5*(4*(3*(2*factrial(1))))
→5*(4*(3*(2*1)))
→5*(4*(3*2))
→5*(4*6)
→5*24
→120

練習

1. 階乗を計算する関数を、再帰を使わない形に書き直してみよ。
2. ある程度大きな数の階乗は正しく計算できない。計算できるのはい くつまでか。またそれより大きな数を入れた時にでる答えはどういう意味があ るか。
3. フィボナッチ数列$F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1を再 帰、再帰でないものの両方を使って書け。
4. 上のフィボナッチ数列について、n を大きくしていった時に計算の手間が どのように増えるかを、再帰の場合とそうでない場合のそれぞれについ て考察せよ。

お絵書き

/* tree
 *
 * (C) J. Makino Version 1.0 Jan 26, 1997
 */
#include <stdio.h>
#include <math.h>
#include </home/makino/text/xgraph.h>
#define PI  3.14159265358979
int gdriver, gmode;
double    x,y,vx,vy;

void tree(int n, int x, int y, double angle, double length)
{
    int x1, y1;
    if (n > 0){
	setcolor( n % 7 + 1);
	x1 = x + length*cos(angle);
	y1 = y - length*sin(angle);
	line(x,y,x1,y1);
	tree(n-1,x1,y1,angle + 0.25, length*0.7);
	tree(n-1,x1,y1,angle - 0.25, length*0.7);
    }

}

void main()
{
    char dumstr[100];
    initgraph(gdriver, gmode, "");
    cleardevice();
    tree(10, getmaxx()/2, getmaxy(), PI/2, getmaxy()/ 4);
  gets(dumstr); 
  gets(dumstr); 
  closegraph();
}

再帰を使うことで、角度、長さを変えて自分自身を呼び出すという形で簡潔に アルゴリズムが表現できている。

なお、このプログラムを打ち込んで、そのままコンパイルしようとしてもうま くできない。これは、三角関数(sin, cos) がどこにあるか指定されてい ないからである。これは以下のように, -lXtc -lX11 にさらに追加して指定する。

gcc tree.c -o tree -lXtc -lX11 -lm

練習

1. この木では、枝が2本ずつ出ているが、もっとたくさん出すにはどうすればい いだろうか？
2. この木は枝分かれが完全に規則的で不自然である。自然にするにはどうすれ ばいいだろうか？
   （ヒント：drand48() という関数を呼ぶと、0 から x まで の範囲の乱数 --- デタラメな数 --- を返す。これを使って枝分かれの長さ、 角度を変えて見よう)
3. 以下に示すようなフラクタル図形も、うえのプログラムと同じよう な考え方で作ることができる。どのようにすればいいかを考えて、 プログラムを作ってみよ。
   
   

レポート

• プログラム
• 実行結果
• 考察

makino-1@chianti.c.u-tokyo.ac.jp

1. 出力結果が画面に出たところで、 ~makino/bin/gfile というコマンド を実行する。これは、実行したウインドウとはべつのところで行 なうこと。
2. Enter file name: と聞いてくるので、名前をいれる。これは別にどん な名前でもいいが、例えば課題3の1 枚目ならkadai3-1 というように つけるのがいい。
3. しばらくすると、上の場合なら kadai3-1.uu というファイルができる ので、この中身をメイルにして送る。ただし、上に書いたように、こ れとプログラム、考察はまとめて1つのメイルで送ること。絵が何枚か ある場合も同じで、全体を1つのメイルでおくること。このためには mule の Insert-file (Ctrl-x i) などの機能を使う。

次回予告