第５話 最大値排除繰り返し法自己再帰版その１コード解説
コード核心部分再掲
void g(int a,int *m){
int i;
h(0,a,m);
cout<<"並び替え後"<<endl;
i=0;
while(i<a){
if(m[i]<10)cout<<" "<<m[i]<<" ";
if(m[i]>=10)cout<<m[i]<<" ";
if(i>0 && (i+1)%25==0)cout<<endl;
i++;
}
cout<<endl;
}
void h(int x,int a,int *m){
int i,max,ik,w;
max=-1;
for(i=x;i<a;i++){
if(m[i]>max){
max=m[i];
ik=i;
}
}
w=m[x];
m[x]=m[ik];
m[ik]=w;
if(x+1<a-1)h(x+1,a,m);
}
解説
後に独立の講を設ける予定ですが、
for文・while文などのループ文はすべて関数の再帰的呼び出しでも実現できます。
ですから、２次元ループの第１次元目を関数の再帰的呼び出しにすることができるのは当然なのです。
そして、第２次元目も関数の再帰的呼び出しにしたのが前話コード例でした。
ただし、前話コード例には何か欠陥があってプログラムの実行速度が著しく落ちてしまっています。
void h(int x,int a,int *m);はaと*mの部分をグローバル変数にすれば、
void h(int x);と至ってシンプルなものになります。
グローバル変数やグローバル配列は、
メモリーを無駄遣いするので余り使わないようにすることが推奨されていますが、
私は初心者用の入門講義では使ってもよいと思います。
今は、どのパソコンも有り余るメモリーを積んでいますから、
今回組んだプログラムでは、搭載メモリーの１／１０００も使っていないでしょう。
１／１０００未満ならメモリーの節約云々はないでしょう。
むしろ、初心者にはvoid h(int x);とした方が関数の再帰的呼び出しの本質を理解できてよいと考えられます。
xはもちろん次元番号です。
すなわち、入れ子式人形の外側から数えて何番目かを示します。
ただし、一番外側の人形を０番目と数えます。
では、次元番号xは具体的には何を意味するのでしょう。
次元番号xが０のときは、最大値の検索対象はすべてのデータです。
次元番号xが１のときは、検索対象は次元番号０で検出された最大値を除いたデータが検索対象です。
次元番号xが２のときは、検索対象は次元番号０と次元番号１で検出された最大値を除いたデータが検索対象です。
つまり、次元番号が上がる度に検索対象は絞られていくのです。
まさに、入れ子式の人形に比喩がぴったりの例です。
次元番号が０ときはすべての人形が検索対象になり、
次元番号が１のときは一番外側の人形を除いた人形が検索対象になります。
そして、次元番号２のときは、外側から二つの人形を取り除いた残りの人形が検索対象になります。
もっともこの比喩の言い方ですと、検索してみないとどれが最も大きい人形＝一番外側の人形であるかわからないわけです。
検索によって、外側からx番目（実際には、x+1番目）であることがわかり検索対象から外されていくという過程を辿るわけです。
先に、今回の再帰的呼び出しの本質部分がh(0）とした方が理解できると申し上げた理由がお分かりでしょうか。
h(0,a,m);では余計な服飾品があって初心者にはどれが本質であるか理解しにくいと言えるでしょう。
やはり、現在売られいる書籍やネット上にある入門サイトは初心者の心情を理解していないと言えるでしょう。
本講義のようにグローバル変数を多用する書籍やサイトは見たことがありません。
理解するための核心部分を提示して、細かいことはいわないが初心者用の入門の絶対鉄則だと思います。
最初は、グローバル変数を使って理解が進んでから、
徐々にグローバル変数を使わないようにしていく、
これで十分ですね。
では、本話の課題です。今度は、昇順＝小さい順に並べるプログラムを考えてください。
尚、最初の予定では第２３講ではsetとsortによる並び替えでしたが、
これは第２４講に回し、次講では隣項交換繰り返し法と最大値排除法繰り返し法のマルチスレッド化を考えます。
シングルスレッドでは、軍配は最大値排除繰り返し法に上がっていますが、
マルチ化したときにどちらが勝つのでしょうか。
第４話へ 第６話へ
