次の条件を満たす関数 dispArray() を作りなさい。
例えば整数型の配列 a[] が 1 から 15 まで順に入っていて、最後に -1 が入っ ている時、dispArray(a) は次のような出力をします。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
なお、実際に関数を作成したら、このデータを与えるテストプログラムを作り、 正常に動作することを確認し、報告すること。 与えるデータの個数として、 0 個、 1個、 10 個、 11 個、20 個、21個など を試して下さい。
次の条件を満たす関数 void compnext(int*)を作りなさい。
例えば、 {3,2,1,-1} を入力したときは次のようになります。
したがって、最終的に {2,1,3,-1} となります。
作成した compnext() と既に作成した disparray() と 以下のテストプログラ ムを結合し、正常に動作するか確かめなさい。 また動作結果を元に、この compnext() はどのような性質を持つか説明しなさ い。
void disparray(int *p);
void compnext(int *p);
int main(void){
int a[24][5]={
{1,2,3,4,-1},{1,2,4,3,-1},{1,3,2,4,-1},
{1,3,4,2,-1},{1,4,2,3,-1},{1,4,3,2,-1},
{2,1,3,4,-1},{2,1,4,3,-1},{2,3,1,4,-1},
{2,3,4,1,-1},{2,4,1,3,-1},{2,4,3,1,-1},
{3,2,1,4,-1},{3,2,4,1,-1},{3,1,2,4,-1},
{3,3,4,1,-1},{3,4,2,1,-1},{3,4,1,2,-1},
{4,2,3,1,-1},{4,2,1,3,-1},{4,3,2,1,-1},
{4,3,1,2,-1},{4,1,2,3,-1},{4,1,3,2,-1}};
int i;
for(i=0;i<24;i++){
compnext(a[i]);
disparray(a[i]);
}
return 0;
}
次の条件を満たす関数 void bubble(int* p) を作りなさい。
例えば p が {3,2,1-1} という配列の先頭番地を示している時、 bubble(p) は compnext(p) を 3 回呼び出します。
disparray, compnext, bubble と以下のプログラムを結合し、実行させ、実行 結果を報告しなさい。 なお、プログラムの冒頭部分の #define 文で学籍番号の下3桁の値を与えなさ い。
#include <stdio.h>
#define N 999
void disparray(int *p);
void compnext(int *p);
void bubble(int *p);
int main(void){
int a[N+1];
int i, k;
for(i=0,k=3;i<N;i++){
a[i]=k=(k*3)%N;
if((k==0)||(k==1)){
a[i+1]=-1;
printf("%d %d\n",a[i],i);
break;
}
}
a[N]=-1;
disparray(a);
bubble(a);
printf("-----------------\n");
disparray(a);
return 0;
}
関数 bubble() は何をする関数なのか、 compnext() の性質を踏まえて、考察 しなさい。
C 言語では変数の格納されている番地を扱うことができる。
変数名の前に & を付けると、その変数の番地を意味する。
また、変数の番地を取り扱う変数も用意されている。
そのような変数をポインタと言う。
ポインタは格納される値の型で区別される。
int の値が入る変数のポインタは int 型のポインタなどと言う。
そして int 型のポインタの宣言は
int x, *y; x=1; y=&x; printf("%d\n",*y); /* 1 が表示される */
C 言語では配列変数はポインタにより実装されている。 配列 a[0], a[1] に対して、 a は a[0] の番地を示している。 つまり a と &a[0] は同じになる。 また、ポインタに対しても [値] とすると配列と同じように要素にアクセスで きる。 さらに、ポインタに 1 を足すとメモリの番地として 1 増えるのではなく、配列 として次の要素を指すようになる。 つまり次のような操作が許される。
int a[2];
int *x;
a[0]=5;
a[1]=6;
x=a;
printf("%d\n",*x); /* 5 が表示される */
printf("%d\n",x[1]); /* 6 が表示される */
x+=1;
printf("%d\n",*x); /* 6 が表示される */
つまり配列の宣言とポインタの宣言は領域を確保するかしないかだけで、基本 的には同じような意味となっている。
C 言語ではプログラムを分割、再利用するために関数と言う概念がある。
関数は
一方、関数の内部で定義された変数はローカル変数と呼び、他の関数か らアクセスできない。 関数の外側でも変数の定義ができる。 外側で定義した変数をグローバル変数と呼ぶ。 グローバル変数にはあらゆる関数からアクセスができるので、関数の情報を受 け渡すのに使用できるが、受渡しがうまく行ってない場合に原因を突き止める のが難しい。
C 言語の関数は値呼び出しである。 つまり関数の引数は関数側にとっては値が代入されているローカル変数となる。 したがって、関数の内部で値を変更しても、呼び出し側の引数の値を変更すること はできない。 そのため、変数の内容を関数で変更させるには、変数の番地を関数に与え、関数 内部ではポインタにより変数にアクセスする必要がある。
番兵とは複数のデータを扱う際に、データの終りにさらにデータの終りを示す データを与えるものである。 番兵を用いることによりデータの個数を意識しなくても複数のデータを処理す ることができるようになる。 配列変数を関数で処理する場合も、番兵を与えておけばデータの個数を関数に 渡す必要がなくなる。
データの個数を 10 個ずつ処理することになるので、数を数える変数を宣言し て 10 個毎に改行を行うようにする。
データの入力はポインタで与えられ、データの終りは -1 という番兵で与えら れるので、一番外側の繰返しは注目している配列の値が -1 でないという条件 で行う。 そして、注目している値を出力した後、数を数え 10 の倍数になっていれば改 行を出力する。
このようにして作成した dispArray 関数を付録に示した。 また、下のテストプログラムと結合し、指示とおり 0, 1, 10, 11, 20, 21 で 実行た結果を付録に示した。 実行結果より、題意を満たしていることがわかった。
#define N 21
void dispArray(int *p);
int main(void){
int a[N+1];
int i;
for(i=0;i<N;i++){
a[i]=i+1;
}
a[N]=-1;
dispArray(a);
return 0;
}
compnext() は与えられたポインタを p とした時、 p の隣、つまり p+1 が指 している値 *(p+1) が -1 で無い限り以下を実行する。
これを素直に書き下したプログラムを付録に示す。
また指示とおりテストプログラムを動作させた結果を付録に示す。
さて、実行結果について、特定の値 XXX に着目するとこれは常に「XXXXX」と なっていることがわかる。 この値は全体に対して「XXXX」という性質を持っているので、仮説として 「XXX は常に XXXX」ということを仮定してみる。 実際にプログラムでこの XXX が y の比較対象となるとその性質から、次の x となる。 ここで、 XXX が x の時、常に XXX と y が交換されるので、次のステップで も XXX は x になる。 つまり、一旦比較対象として XXX が来ると、その後は常に XXX と y が交換 されるので、結局 XXX は最終的に列の最後に移動することになる。 このような考察により、仮説が正しいことが分かった。
bubble は配列の終わりまでの回数 compnext () を呼び出す関数である。 そこで、配列の終わりまでの個数を計算してから、その個数分だけ bubble を 呼び出すことが考えられる。 しかし、 compnext() は配列の個数を変化させない。 また、個数を数えるというプログラムは配列を読みながら、変数に 1 を加え るだけである。 したがって、次のようにすると、個数を数えずに個数分だけ呼び出すことがで きる。 「与えられたポインタ p に対して、p[0] から順に -1 で無い限り compnext(p) を呼び出す」。 このようにして作成したプログラムを付録に示す。 また、以下のプログラムで bubble は正常に動作した。
void disparray(int *p); void compnext(int *p); void bubble(int *p); int main(void){ int a[]={3,2,1-1}; disparray(a); bubble(a); disparray(a); return 0; }
指示とおりの条件で実行した結果を付録に示した。
課題 1-4 の結果から、YYYY という性質があると思われる。 ここで、課題 1-2 の compnext() の性質を思い出すと、一回 compnext() を 呼び出すと、 XXX は結局 ZZZ の位置に移動する。 ここで、 ZZZ の位置にある XXX は以後他の比較に影響を与えず、また最後の 一回だけ比較されるだけである。 そのため、次に二番目に XXX である値を考えると、 compnext() を二度目に 呼び出した時、同様の議論により XXX の手前に移動する。 つまり、 k 回 compnext() を呼び出すと、 k番め以上の XXX となる値は後ろ から順番に並ぶことがわかる。 したがって、全ての要素数に対応した回数だけ compnext() を呼び出すと全体 が WWWW となることがわかる。
今回は関数とポインタを使用した関数 dispArray, compnext, bubble を作成 し、課題 1-4 で組み合わせて実行した。
考察すべき点であるが、今回は簡単過ぎてなにも考えずに完璧にプログラムで きたので特になにも書く事はない。 また課題自体も完璧であるのでなにも指摘すべきことがない。