第１１講第６話へ 第１２講第1話へ 第１4講第10話へ 第15講第４話へ 第15講第６話へ
第１５講 関数の再帰的呼び出し
第５話 関数の再帰的呼び出しによる順列作成の解説その２
プログラム再掲
#pragma endregion
String^ w;
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^
e) {
w=L"";
s=0;
f(0);
w+=L"\n"+L"順列総数:"+s.ToString();
label1->Text=w;
}
void f(char g){
int i,j,k,h;
for(i=0;i<n;i++){
a[g]=i+1;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
if(h==1){
if(g<n-1){
f(g+1);
}
else{
for(k=0;k<n;k++)w+=a[k].ToString()+L"
";
w+=L"\n";
s++;
}
}
}
}
すべての順列
| １ | ２ | ３ |
| １ | ３ | ２ |
| ２ | １ | ３ |
| ２ | ３ | １ |
| ３ | １ | ２ |
| ３ | ２ | １ |
が完成するまでトレースしながら、gやi、j、kそしてhの働きを確認しましょう。
まず、f(0);によって、枠0の世界に飛びます。
| ０ | １ | ２ |
| １ | ２ | ３ |
| １ |
が枠0の世界です。つまり、void f(char g)のgは枠０，１，２のどの世界かを指定する変数です。
f(0)、f(1)、f(2)は同じ関数fでありながら、別の世界を対象にしているのです。
| ０ | １ | ２ |
| １ | ２ | ３ |
f(0)は、
| ０ |
| １ |
の世界です。この世界において、for文
for(i=0;i<n;i++){
a[g]=i+1;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
if(h==1){
if(g<n-1){
f(g+1);
}
else{
for(k=0;k<n;k++)w+=a[k].ToString()+L"
";
w+=L"\n";
s++;
}
}
}
}
が実行されるのです。
Ⅰ（g=0の世界） i=0のとき、
a[g]=i+1;によって、
| ０ |
| １ |
枠0に１が入ります。
現在g=0ですから、
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
は実行されません。
したがって、hは1のままで、if文
if(h==1){
if(g<n-1){
f(g+1);
}
else{
for(k=0;k<n;k++)w+=a[k].ToString()+L"
";
w+=L"\n";
s++;
}
}
}
が実行されます。g=0、n=3なので、if(g<n-1)はif(0<2)となり、
if(g<n-1){
f(g+1);
}
は実行されることになります。つまり、f(1)が実行され、
| ０ | １ | ２ |
| １ | ２ | ３ |
の
| １ |
| ２ |
の世界に飛びます。
この世界において、再びfor文
for(i=0;i<n;i++){
a[g]=i+1;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
if(h==1){
if(g<n-1){
f(g+1);
}
else{
for(k=0;k<n;k++)w+=a[k].ToString()+L"
";
w+=L"\n";
s++;
}
}
}
}
が実行されるのです。同じfor文でありながら、実行される世界が違うのです。
つまり、同じfor文ですが異なる次元の世界に住んでいるのです。
gによって次元が決められます。関数の再帰的呼び出しでは、異次元の世界を行ったり来たりしているのです。
f(g)はあちらこちらの世界を飛び回ります。
Ⅱ（g=1の世界）i=0のとき
a[g]=i+1;によって、
| ０ | １ | ２ |
| １ | １ | ３ |
となります。
1>0なのでif文
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
が実行されまが、a[1]=a[0]（＝１）なので、h=0になってしまい、if文
if(h==1){
if(g<n-1){
f(g+1);
}
else{
for(k=0;k<n;k++)w+=a[k].ToString()+L"
";
w+=L"\n";
s++;
}
}
}
は実行されず、for文の次のループになり、
| ０ | １ | ２ |
| １ | ２ | ３ |
となります。すると、a[1]≠a[0]（１と２）になり
今度はif文
if(h==1){
if(g<n-1){
f(g+1);
}
else{
for(k=0;k<n;k++)w+=a[k].ToString()+L"
";
w+=L"\n";
s++;
}
}
}
が実行されます。1<2よりif文
if(g<n-1){
f(g+1);
}
は実施され、g=3の世界すなわち
| ０ | １ | ２ |
| １ | ２ | ３ |
の
| ２ |
| ３ |
に飛翔します。
そして、ここでもfor文
for(i=0;i<n;i++){
a[g]=i+1;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(a[g]==a[j]){
h=0;
break;
}
}
}
if(h==1){
if(g<n-1){
f(g+1);
}
else{
for(k=0;k<n;k++)w+=a[k].ToString()+L"
";
w+=L"\n";
s++;
}
}
}
}
が実行されます。
第１１講第６話へ 第１２講第1話へ 第１4講第10話へ 第15講第４話へ 第15講第６話へ
VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual
Basic入門基礎講座
