第2講 試行錯誤法でヒント数0数独の解答を作る(1)
第7話 3次順列のトレース第1回
コード再掲
#include<iostream>
using namespace std;
void f(int s); //sは次元番号=部屋番号
int n; //次元数(部屋数)をキーボードから指定
int cn = 0; //順列を数える変数
int a[10];//大きめにとった
int main() {
  cout << "n = ";
  scanf_s("%d", &n); //キーボードからnの値を取得
  f(0);
  cout << "順列の場合の数は" << cn << "です。" << endl;
  cout << "プロジェクト成功" << endl;
  return(0);
}
void f(int s) {
  for (int i = 1; i < n + 1; i++) {
    if (s == 0) {
      a[s] = i;
    }
    if (s > 0) {
      for (int j = 0; j < s; j++) {
        if (i == a[j])goto tobi;
        a[s] = i;
      }  
    }
    if (s + 1 < n)f(s + 1); //1つ上の次元に飛翔(1つ奥の部屋に入室)
    if (s + 1 == n) { //一番奥の部屋に到達!
      for (int j = 0; j < n; j++) { //順列を表示
        cout << a[j] << " ";
      }
      cout << endl;
      cn++; //順列数をカウント
    }
 tobi:;
  }
}

では n = 3 の場合でトレースしてみましょう。

n = 3ですからnは3として記述します。

そして、皆さんはそれを参考にして

n = 4 の場合・n = 5 の場合でトレースしてください。


s = 0(f(0)の0)のとき0(茶色の)部屋にいます。
for (int i = 1; i < 3 + 1; i++) {
    if (s == 0) {
     a[s] = i;
    }
すなわち
for (int i = 1; i < 4; i++) {
    if (s == 0) {
     a[s] = i;
    }
によって1が入り a[0] = 1 となります。

    if (s > 0) {
      for (int j = 0; j < s; j++) {
        if (i == a[j])goto tobi;
        a[s] = i;
      }  
    }
s = 0ですから間の4行は実行されずに、
    if (s + 1 < 3)f(s + 1); //1つ上の次元に飛翔(1つ奥の部屋に入室)
s + 1は1なのでf(s + 1);が実行され1つ上の次元に飛翔して赤の部屋に移動して赤の部屋に入ります。
現在どの部屋にいるかを明確に掴んでください。
赤の部屋に入ったということはf(1)です。
すなわちs = 1です。
  for (int i = 1; i < 4; i++) {//赤の部屋のfor文最初の状態でi = 1です。
(本来はfor (int i = 1; i < n + 1; i++) )
  if (s == 0) {
      a[s] = i;
    }
    if (s > 0) {
      for (int j = 0; j < s; j++) {
        if (i == a[j])goto tobi;
        a[s] = i;
      }  
    }
ですから、
    if (s == 0) {
      a[s] = i;
    }
のa[s] = i;は実行されずに
    if (s > 0) {
      for (int j = 0; j < s; j++) {
        if (i == a[j])goto tobi;
        a[s] = i;
      }  
    }
に進み、
      for (int j = 0; j < s; j++) {

      for (int j = 0; j < 1; j++) {
でこのfor文は1回だけ実行され、
        if (i == a[j])goto tobi;

        if (1 == a[0])goto tobi;
a[0] = 1でしたから等号が成り立ち、

 tobi:;
に飛び
  for (int i = 1; i < 4; i++) {
の2回目でi = 2となります。
s = 1のために
    if (s == 0) {
      a[s] = i;
    }
は実行されずに
    if (s > 0) {
      for (int j = 0; j < 1; j++) {
        if (i == a[j])goto tobi;
        a[s] = i;
      }  
    }
に進み、for (int j = 0; j < 1; j++) {
        if (i == a[j])goto tobi;
        a[s] = i;
      }  
の第1回が実行され、i == a[j]は2 == a[0]すなわち2 == 1
となり等号が成立せずにif (i == a[j])goto tobi;は無視され、
        a[s] = i;
からa[1] = 2;

となります。部屋0と部屋1には異なる人が入ります。

ごめんなさい!疲れてしまったので続きは明日以降にします。



第6話へ 第8話へ

トップへ