第６話 ｎ次順列の自動生成
を実現するコード例#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つ奥の部屋に入室）
if (s + 1 == n) { //一番奥の部屋に到達！
for (int j = 0; j < n; j++) { //順列を表示
cout << a[j] << " ";
}
cout << endl;
cn++; //順列数をカウント
}
tobi:;
}
}
なんだかさっぱりわからん！
と悲鳴を上げている人がたくさんいらっしゃると思います。
でも大丈夫ですよ。
次話で詳しく説明します。
驚くほど懇切丁寧に説明します。
コンピュータの動きを追うことをトレースと言います。
nが大きすぎるとトレースの分量が多すぎになりますので、
次話以降n = 3の場合でトレースをしていきます。
このプログラムをつかむ上で肝要なのはsを把握することです。
sは部屋番号です。
部屋番号と人番号を区別しなければなりません。
コードを再掲しますので、部屋と人を明確にわけてコードを読んでください。#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つ奥の部屋に入室）
if (s + 1 == n) { //一番奥の部屋に到達！
for (int j = 0; j < n; j++) { //順列を表示
cout << a[j] << " ";
}
cout << endl;
cn++; //順列数をカウント
}
tobi:;
}
}
第５話へ 第７話へ
トップへ