第１５講 関数の再帰的呼び出し
第３話 for文による順列作成の解説
お約束の通り、ここではfor文による３個順列作成の解説を行います。
そして、第４話以降で再帰的呼び出しの方の解説を３話から４話かけて解説していきます。
for文による３個順列作成のソースを再掲しましょう。
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
String^ w;
int i,j,k,l,h1,h2,s=0;
int a[3];
for(i=0;i<3;i++){
a[0]=i+1;
for(j=0;j<3;j++){
a[1]=j+1;
h1=1;
if(a[0]==a[1])h1=0;
if(h1==1){
for(k=0;k<3;k++){
a[2]=k+1;
h2=1;
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
}
}
}
}
w+=L"\n"+L"順列個数："+s.ToString();
label1->Text=w;
}
１行１行解説していきましょう。
String^ w;はlabel1のプロパティのTextに表示させるための文字変数wを用意しています。
２行目int i,j,k,l,h1,h2,s=0;では整数型の変数i,j,k,l,h1,h2,sを用意しています。
メモリ容量を節約するなら１バイト型のcharを使い、
char i,j,k,l,h1,h2,s=0;と宣言しても結構です。というのは、今回用意した変数はすべて６以下だからです。
char型では128までの整数を扱うことができるのです。
sは、順列総数を数えるための変数です。したがって、初期化s=0も同時に行っています。
順列の個数が増えると順列総数はあっという間に増えてしまいます（6個の順列ですでに総数は720で制限をオーバー）ので、
sだけはint型で宣言しておくのが無難です。
もちろんより大きな順列を扱うなら、sをlong型にしておかなければなりません。
というのは順列総数は階乗で増えていくためintの制限さえ簡単にオーバーしてしまうからです。
ですが、計算時間を考えれば15個程度の順列が限界です。
16個になると、１６！≒２１０００００００００＝210億（個）というべらぼうな数字になり、
さすがのコンピュータも苦戦することになります。
（後に挑戦することになる数独解答作成ソフトのおいては、
９の81乗＝1900000000000000000000000000000000000000000000000000000000000000000000
通り場合について探査しますので、世界随一のスーパコンピュータを使ってとしても、
すべての解答を宇宙年（宇宙の始まりから終わりまでの時間）以内に作り出すことはできないでしょう。）
i,j,k,lはループ文（for文）に使う変数です。
h1,h2はfor文において条件を満たしているかどうかの判定に使うための変数です。
３行目int a[3];では順列入れるための配列aを宣言しています。
3個の順列ですのでa[3]です。
次のfor文
for(i=0;i<3;i++){
a[0]=i+1;
・
・
・
}
では、a[0]に入れる数のループを行っています。具体的には、a[0]にa[1]=j+1;で1から3まで入れていっています。
2番目のfor文
for(j=0;j<3;j++){
a[1]=j+1;
h1=1;
if(a[0]==a[1])h1=0;
if(h1==1){
for(k=0;k<3;k++){
a[2]=k+1;
h2=1;
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
}
}
}
においては、a[1]の入力のループを行っています。a[1]=j+1;によってa[1]に1から3まで入力しています。
さて、皆さん、
h1=1;
if(a[0]==a[1])h1=0;
if(h1==1){
・
・
・
}
の18行ではいったい何をしているのでしょうか。
答えは、a[0]とa[1]の間に数字の重複がないかを調べているのです。
１１２のようなものは順列といいません。１３２のように数字に重複がないものを順列というからです。
重複してはいけないという禁止則に従うようにさせているのが、18行の役割なのです。
重複がなければh1は１、重複があればh1は０になるようにしてあります。
というのは1行目h1=1;でh1は1となっています。次のif文の条件a[0]==a[1]を満たさなければ何もされず、
1のままですが、条件を満たせばh1=0によって0となってしまいます。
つまりa[0]≠a[1]ならh1は1のままで、a[0]＝a[1]ならh1は0に変わります。
そして、h1が1のままならすなわちa[0]とa[1]の間に数字の重複がなければ、if文
if(h1==1){
・
・
・
}
が実行されます。
3番目のfor文
for(k=0;k<3;k++){
a[2]=k+1;
h2=1;
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
}
の役割は、もうお分かりですね。
というのは、
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
がなければ、2番目のif文と同一の構造をもっていることが分かります。
h1=1;
if(a[0]==a[1])h1=0;
が
h2=1;
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
に変わっていますが、基本は同じです。
h1=1;
if(a[0]==a[1])h1=0;
は
h1=1;
for(l=0;l<1;l++){
if(a[l]=a[1]){
h1=0;
break;
}
}
と変更しても変わりませんね。
つまり、2番目のfor文と3番目のfor文はまったく同一の構造をもていることが分かります。
では1番目だけ構造が違うのでしょうか。
答えはNOです。
1番目のfor文も
for(i=0;i<3;i++){
a[0]=i+1;
h0=1;
for(l=0;l<0;l++){
ｉｆ(a[l]==a[0]){
h0=0;
break;
}
ｉｆ(h0==1){
・
・
・
}
}
}
と書き換えても中身は変わりませんね。l=0;l<0は意味がないので、
for(l=0;l<0;l++)は実行されないからです。
（厳密にはここの説明には嘘があります。Visual BasicやTrubo C++においては、
最初からfor文の条件が矛盾していれば、そのfor文が実行されないのは真実です。
ところが、マイクロソフト系のC言語の場合は、for文の条件が矛盾していても、
1回は実行してしまうのです。
私が数独問題作成ソフトにおいて、思うような動作が選られなかった原因の一つとして、
Visual BasicとVisual C++の文法の微妙な違いにあった、と述べたことがあったのは、
この点を指しています。
同じC言語でありながら、for文に違いがあることは知っていましたが、
C言語から15年も離れていたので、この違いを忘れていたのです。
というわけでVisual C++の説明としては嘘があり、記述をもう少し工夫しなければなりませんが、
3つのfor文における構造の同一性の説明として後理解して頂ければと思います。）
2番目のfor文においては
h1=1;
for(l=0;l<1;l++){
if(a[l]=a[1]){
h1=0;
break;
}
}
1番目のfor文においては
for(i=0;i<3;i++){
a[0]=i+1;
h0=1;
for(l=0;l<0;l++){
ｉｆ(a[l]==a[0]){
h0=0;
break;
}
ｉｆ(h0==1){
・
・
・
}
}
}
としてもよいところそうしなかったのは、
a[0]においては、これが最初の数字なので重複の心配は最初からありませんし、
a[1]については、a[0]のみをチェックをすればよいからです。
ですが、3個より個数の多い順列の場合は、3番目以降のfor文の構造はまったく同じになることはお分かりになると思います。
というわけで、1番目,2番目のfor文と3番目以降ののfor文では一見違いがあるように見えながら、
本質的にはまったく同一の構造をもっているのです。
例えば、5つの順列の場合を考えれば
5つの枠の構造は同じです。つまり枠に入る数字は、他の枠に入る数字と重複してはいけないということです。
枠の構造の同一性があるので、各for文の構造も同一になります。
実はこのように構造が同一の場合、構造という言葉がわかりにくければ同じ操作を繰り返す場合、
for文ではなく、第3話以降で解説する関数の再帰的呼び出しという方法を使った方が良いのです。
数独の場合も
| 6 |
2 |
1 |
9 |
4 |
5 |
8 |
3 |
7 |
| 7 |
8 |
5 |
2 |
6 |
3 |
4 |
9 |
1 |
| 9 |
3 |
4 |
8 |
7 |
1 |
2 |
5 |
6 |
| 2 |
1 |
6 |
7 |
3 |
4 |
5 |
8 |
9 |
| 5 |
9 |
3 |
6 |
1 |
8 |
7 |
2 |
4 |
| 4 |
7 |
8 |
5 |
9 |
2 |
6 |
1 |
3 |
| 1 |
5 |
7 |
3 |
2 |
6 |
9 |
4 |
8 |
| 3 |
6 |
2 |
4 |
8 |
9 |
1 |
7 |
5 |
| 8 |
4 |
9 |
1 |
5 |
7 |
3 |
6 |
2 |
各セルがもっている属性は、まったく同じです。各セルは列と行とブロックに同じ数字が入ってはいけないというルール（構造）があります。
数独や魔方陣はまさに関数の再帰的呼び出しに向いているのです。
最後の部分
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
では、何をしているかと申しますと
a[0]、a[1]、a[2]のいずれにも重複がない場合に文字変数wに結果を代入しているのです。
ではトレースしてみましょう。
Ⅰ i=0の場合、
a[0]=i+1;により、a[0]=1となります。
ⅰ j=0のとき
a[1]=j+1;によって、a[1]=1となります。
すると、a[0]=a[1]ですから、if(a[0]==a[1])h1=0;によってh1=0です。
したがって、このときif文
if(h1==1){
for(k=0;k<3;k++){
a[2]=k+1;
h2=1;
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
}
}
は実行されず、次のループに入ります。
ⅱ j=1のとき、
a[1]=j+1;によって、a[1]=2となります。
すると、a[0]≠a[1]ですから、if(a[0]==a[1])h1=0;のh1=0は実行されず、h1=1のままで、if文
if(h1==1){
for(k=0;k<3;k++){
a[2]=k+1;
h2=1;
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
}
}
が実行されます。
(ｲ) k=0のとき、
a[2]=k+1;によって、a[2]=1となります。よって、a[0]=a[2]ですから
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
によって、h2=0となっていまい、if文
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
されません。
(ﾛ) k=1のとき、
a[2]=k+1;によって、a[2]=2となります。よって、a[1]=a[2]ですから
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
によって、h2=0となっていまい、if文
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
されません。
(ﾊ) k=2のとき、
a[2]=k+1;によって、a[2]=3となります。a[1]≠a[2]、a[1]≠a[2]ですから
for(l=0;l<2;l++){
if(a[l]==a[2]){
h2=0;
break;
}
}
でかき変えられることはなくh2=1のままで
if(h2==1){
w+=a[0].ToString()+L" "+a[1].ToString()+L"
"+a[2].ToString()+L"\n";
s++;
}
が実行され、ｗにはじめてw=1 2 3+L"\n"が代入されます。
トレースはまだ途中ですが、是非この後はご自分でされて下さい。
第１１講第６話へ 第１２講第1話へ 第１4講第10話へ 第15講第２話へ 第15講第４話へ
VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual
Basic入門基礎講座
