第７話 隣項交換繰り返し法自己再帰版その２コード解説
コード再掲
void g(int a,int *m){
char t=1;
int i,cn;
cn=0;
while(t){
if(h(0,a,m)==0)t=0;
cn++;
}
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<<cn<<"巡目で並び替えに成功しました。"<<endl;
}
int h(int x,int a,int *m){
int w;
if(x+1<a-1){
if(m[x]<m[x+1]){
w=m[x];
m[x]=m[x+1];
m[x+1]=w;
return(h(x+1,a,m)+1);
}
else{
return(h(x+1,a,m));
}
}
else{
if(m[x]<m[x+1]){
w=m[x];
m[x]=m[x+1];
m[x+1]=w;
return(1);
}
else{
return(0);
}
}
}
解説
これはループ版
while(t){
v=0;
for(i=0;i<a-1;i++){
if(m[i]<m[i+1]){
w=m[i];
m[i]=m[i+1];
m[i+1]=w;
v++;
}
}
if(v==0)t=0;
cn++;
}
のピンクの部分を自己再帰版＝関数の再帰的呼び出し版にしたものです。
入れ子式の人形の比喩では、より内なる人形を求める旅、
自分探しを比喩にするなら、本当の自分を知るために一番奥深い自分への遡及の旅です。
一番奥深いとこまで遡及していって、その本質を探究しながら表皮の自分へと戻ってきます。
人は、いろいろな衣装をまとっています。
会社の営業では、とてもいい人で丁寧に接客します。
部下に対しては、厳しい上司であるかもしれません。
家では、すててこ一枚でだらしなくしていて娘から嫌われる父親であったりします。
あるいは妻の前では暴君だったり、弱い男だったりします。
しかし、どれも本当の自分ではありません。
衣装や仮面で自分を隠しています。
ですが、その仮面も自分と一心同体となっていて、
本当の姿は、自分にもわかりません。
偽りの衣装を一枚一枚とっていくことによってしか、
本当の自分が何であるかわかりません。
プログラミングの遡及は、何の遡及でしょうか。
一番外側の入れ子式人形は、初項と第２項の関係です。
そして、一番内側の人形は最後から２番目の項と末項の関係です。
それぞれの人形の役割は、右側の項の方が大きいときには、
隣項を交換することです。
隣項の交換回数を数えることも任務としていますが、
交換回数のカウントは、
一番奥の人形に到達してはじめて始まります。
一番内なる本質に到達してはじめてカウントを始めます。
一番内側の人形が隣項を交換したらなら交換回数を１とカウントし、
交換していないなら、０をカウントして、内側から２番目の人形に交換回数を返します。
内側から２番目の人形は、一番内側から返された交換回数に、
もし右側の項の方が大きければ隣項を交換した上で、
交換数に１加えて、内側から３番目の人形に返します。
交換していない場合は、内側の人形から返ってきた回数をそのまま外側の人形に返します。
以後同じことを繰り返していきます。
最後に一番外側の人形が値を返したとき、
交換回数が
if(h(0,a,m)==0)t=0;
ピンクの部分の値となります。
もし交換回数が０ならt=0となり、while文は終了となります。
そして、１以上ならt=1のままでwhile文は続きます。
以上で、隣項交換繰り返し法は終了としますが、
第1話で立てた仮説は、正しいことが証明されました。
何回実験してもデータ数より巡回数以下で並び替えを終了しているからです。
これでこの講を閉めて、最大値排除繰り返し法に入ることにしましょう。
第６話へ 第２２講第１話へ
