第10講 関数の再帰的使用による魔方陣の自動生成
第１話 n次順列自動生成ソフトからグローバル変数を追放する
グローバル配列・変数を追放したソフトコード例
#include<stdio.h>
#include<stdlib.h> /malloc()を使うために必要
void f(int g,int n,int x[],int *cn);
int main() {
int n,x[25],*cn=(int *)malloc(sizeof(int));
printf("これはすべての順列を求めるソフトです。\n");
printf("何の順列を発生させるのかをaに入力してエンターして下さい。\n");
printf("n=");
scanf("%d", &n);
*cn = 0;
f(0,n,x,cn);
printf("生成された順列は%d個です。\n", *cn);
return(0);
}
void f(int g,int n,int x[],int *cn) {
int i, j, h;
for (i = 0; i<n; i++) {
if (g == 0)x[g] = i + 1;
h = 1;
if (g>0) {
for (j = 0; j<g; j++) {
if (x[j] == i + 1) {
h = 0;
break;
}
}
if (h == 1)x[g] = i + 1;
}
if (h == 1) {
if (g + 1< n) {
f(g + 1,n,x,cn);
}
else {
for (j = 0; j<n; j++)printf("%d ", x[j]);
printf("\n");
(*cn)++;
}
}
}
}
さて、魔方陣生成ソフト開発に入ります。
せっかく引数にしてグローバル変数をすべて追放しましたが、
シンプルにするためにもとのコード
#include<stdio.h>
void f(int g);
int x[25]; //将来５次魔方陣まで生成できるように25に変更
int n,cn;
int main() {
printf("これはすべての順列を求めるソフトです。\n");
printf("何の順列を発生させるのかをnに入力してエンターして下さい。\n");
printf("n=");
scanf("%d", &n);
cn=0;
f(0);
printf("生成された順列は%d個です。\n",cn);
return(0);
}
void f(int g){
int i,j,h;
for(i=0;i<n;i++){
if(g==0)x[g]=i+1;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(x[j]==i+1){
h=0;
break;
}
}
if(h==1)x[g]=i+1;
}
if(h==1){
if (g+1 < n){
f(g+1);
}
else{
for(j=0;j<n;j++)printf("%d ",x[j]);
printf("\n");
cn++;
}
}
}
}
に直して下さい。
引数が多いとf(g)とf(g + 1)の関係が見えにくくなるからです。
入れ子式人形の例えでいうと、
gは外側の人形、g + 1はその内側の人形になります。
最初の課題を出しましょう。
n次順列生成ソフトをn×n次順列生成ソフトに改め、
さらに、実行画面が
これはすべてのn次方陣を求めるソフトです。
何次の方陣を発生させるのかをnに入力し
エンターするとn次方陣がすべて生成されます。
n=2
1 2
3 4
1 2
4 3
1 3
2 4
1 3
4 2
1 4
2 3
1 4
3 2
2 1
3 4
2 1
4 3
2 3
1 4
2 3
4 1
2 4
1 3
2 4
3 1
3 1
2 4
3 1
4 2
3 2
1 4
3 2
4 1
3 4
1 2
3 4
2 1
4 1
2 3
4 1
3 2
4 2
1 3
4 2
3 1
4 3
1 2
4 3
2 1
生成された2次方陣は24個です
となるようにしてください。
1 2
3 4
のように順列を２次元に並べたものを２次方陣と名付けます。
ｎ次方陣のｎは正方形の一辺です。
ですから、３次方陣なら
1 2 3
4 5 6
7 8 9
がその一例となります。
尚、
int x[25]; //将来５次魔方陣まで生成できるように25に変更
ですからnの入力限界は5です。
（5は方陣の一辺で、
25はすべての数字の種類数です。
すなわち5×5です。）
もっとも第10講で開発する魔方陣自動生成ソフトでは、
４次魔方陣が限界ですが。
作成速度を１億倍程度にしないと５次には対応できません。
