第４話 隣項交換繰り返し法解説その２
今日は、
void f(int a,int *m){
int i;
i=0;
while(i<a){
m[i]=rand()%100;
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 g(int a,int *m){
char t=1;
int i,v,w,cn;
cn=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++;
}
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;
}
の部分を解説しましょう。
void f(int a,int *m){
int i;
i=0;
while(i<a){
m[i]=rand()%100;
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;
}
については解説は必要ありませんね。
１００未満の整数をランダムに発生させ、
それを配列（実際にはポインタ）に収納しています。
rand()は、１０万以内ぐらい(曖昧な言い方で済みません。正確にはわかりません。）
の０以上の整数をランダムに発生させます。
a%bはaをbで割った余りを求める式ですから、
rand()%100で１００未満の整数になります。
１００にしたとは特に理由はありません。
１０００でも１００００でも好きに設定してください。
このループはもちろんfor文で行ってもよいわけですが、
while文を学習したばかりですので、
復習のためwhile文にしてみました。
void g(int a,int *m){
char t=1;
int i,v,w,cn;
cn=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++;
}
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;
}
が今回の目玉、核となる部分です。
並び替えプログラムです。
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++;
}
はfor文でもできますが、
while文の方が向いていると言えます。
何故かと申しますと、
今回はプログラマーは、何回で終了するかは把握できません。
下限や終了回数がわかっているときは、
for文の方がわかりやすいわけですが、
下限・終了回数がわからないときは、
while文が向いていると言えます。
この隣項交換繰り返し法の終了はどういうときでしょうか。
４，９，３，８，１０
の場合
４，９，３，８，１０
９，４，３，８，１０
９，４，３，８，１０
９，４，３，８，１０
９，４，８，３，１０
９，４，８，３，１０
９，４，８，１０，３
１巡目が終わりです。
９，４，８，１０，３
９，４，８，１０，３
９，８，４，１０，３
９，８，４，１０，３
９，８，１０，４，３
９，８，１０，４，３
２巡目が終了しましたが、まだ降順になっていません。
３巡目に入ります。
９，８，１０，４，３
９，８，１０，４，３
９，１０，８，４，３
９，１０，８，４，３
９，１０，８，４，３
３巡目終了時にもまだ、降順になっていません。
９，１０，８，４，３
１０，９，８，４，３
１０，９，８，４，３
１０，９，８，４，３
１０，９，８，４，３
すべての隣項を比較したとき、
左の項が右の項より小さくないとき、
終了です。
つまり、隣項の交換が１回も行われないときに終了です。
vは交換回数を数えています。
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++;
}
新しいループに入るときvを０にセットしています。
１回でも交換が行われた場合、まだ降順になっていない可能性がありますので、
その場合にはループ処理を繰り返さないとなりません。
しかし、交換回数０なら降順すなわち大きい順に並んでいることになります。
さて、課題を出して今話を閉じましょう。
今回
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++;
}
をループ文で処理しましたが、
関数の再帰的呼び出しでもできます。
考えてみましょう。
第３話へ 第５話へ
