第５話 Cプロジェクトにおける関数の再帰的使用
Cプロジェクトで
を実現するプログラム例
#include <stdio.h>
void f(int *x,int n,int g);
void h(int *x,int n);
int cn;
void main(){
int x[15],n;
cn=0;
printf("次順列を生成します");
scanf("%d",&n);
printf("\n");
f(x,n,0);
printf("%d次順列が%d個生成されました。",n,cn);
}
void f(int *x,int n,int g){
int i,j;
for(i=0;i<n;i++){
x[g]=i+1;
if(g>0){
for(j=0;j<g;j++){
if(x[g]==x[j])goto tobi;
}
}
if(g+1<n){
f(x,n,g+1);
}
else{
h(x,n);
cn++;
}
tobi:;
}
}
void h(int *x,int n){
int i;
for(i=0;i<n;i++){
printf("%d ",x[i]);
}
printf("\n");
}
参考ファイル１
では、２次元ポインタ（注※を参照して下さい）
int **x;
をmainで宣言して、**xの先頭アドレスxを
引数にして関数f送るという条件の下に、
参考ファイル２を基に魔方陣生成ソフトをCプロジェクトで作り、
２次元ポインタ(正確にはポインタへのポインタ)
もCとC++の間には違いがないことを確認しましょう。
ただし、
Cではcoutは使えませんから、
#include<iostream>
は必要ありません。
また、Cの場合は変数や配列は冒頭で宣言しなければなりませんので、
void main(){
int n;
printf("何次魔方陣を生成しますか？\n");
scanf("%d",&n);
int **x=(int **)malloc(sizeof(int)*n);
for(char i=0;i<n;i++)x[i]=(int *)malloc(sizeof(int)*n);
int *k=(int *)malloc(sizeof(int)*n*n);
printf("\n");
clock_t hj,ow; //clock_t型の宣言、プログラム開始時間を取得するための変数
hj=clock();
syokika(n,k);
printf("%d次魔方陣が%d個生成されました。",n,f(k,x,n,0,0));
ow=clock();
printf("魔方陣生成にかかった時間は%f\n",(double)(ow-hj)/1000);
}
だと、もちろんエラーします。
では順番を変えて
void main(){
int n;
clock_t hj,ow; //clock_t型の宣言、プログラム開始時間を取得するための変数
int **x=(int **)malloc(sizeof(int)*n);
for(char i=0;i<n;i++)x[i]=(int *)malloc(sizeof(int)*n);
int *k=(int *)malloc(sizeof(int)*n*n);
printf("何次魔方陣を生成しますか？\n");
scanf("%d",&n);
printf("\n");
hj=clock();
syokika(n,k);
printf("%d次魔方陣が%d個生成されました。",n,f(k,x,n,0,0));
ow=clock();
printf("魔方陣生成にかかった時間は%f\n",(double)(ow-hj)/1000);
}
ならどうでしょうか。
答えは、注※の下に。
※
正確にはポインタへのポインタといいます。
int *a;
で宣言したとき、aを変数*aへのポインタという、
が正しい説明ですが、
初心者を対象とする本講義では、
『へのポインタ』というわかりにくい表現は使いません。
int **a;
と宣言するときに*aが**aへのポインタであり、
aは*aへのポインタですから、
aをポインタへのポインタと呼ぶわけす。
ですが、ポインタへのポインタという表現は、
初心者にとってわかりにくいだけでなく、
VBA等でかなりのプログラミングができるようになった人にも
わかりにくい言い方です。
私は、aを*aのポインタ、*aを**aのポインタ
と表現します。
これでも大変わかりにくいかと思いますが、
変数**aのアドレスを入れる変数が*aであり、
その変数*aのアドレスを入れる変数がaというわけです。
int i;
int **a;
a=(int *)malloc(sizeof(int)*5);
for(i=0;i<10;i++)a[i]=(int *)malloc(sizeof(int)*6);
と宣言することは、
int a[5][6];
と宣言することと同じですから、
int **a;
と宣言するとき、
私はこれを２次元ポインタと呼ぶことにします。
答え
もちろんエラーします。
問題は、
int **x=(int **)malloc(sizeof(int)*n);
for(char i=0;i<n;i++)x[i]=(int *)malloc(sizeof(int)*n);
int *k=(int *)malloc(sizeof(int)*n*n);
printf("何次魔方陣を生成しますか？\n");
scanf("%d",&n);
のピンクの部分です。
というのは、
scanf("%d",&n);
の記述が後になっていますので、
nには値が代入されていないからです。
C++の場合は、変数･ポインタ・配列の宣言は、
途中でも出来ますので、
scanf("%d",&n);
int **x=(int **)malloc(sizeof(int)*n);
for(char i=0;i<n;i++)x[i]=(int *)malloc(sizeof(int)*n);
int *k=(int *)malloc(sizeof(int)*n*n);
として問題ないわけですが、
事前にnの値を代入できない以上、
グローバル配列のとき少し大きめにサイズを宣言したように
int **x=(int **)malloc(sizeof(int)*10);
for(char i=0;i<n;i++)x[i]=(int *)malloc(sizeof(int)*10);
int *k=(int *)malloc(sizeof(int)*100);
等とするしかありません。
（現在のやり方では、実際上は５次辺りが限界ですが、
将来的には改良して１０次魔方陣でも生成可能になりますので、
10としたわけです。
いろいろ工夫を重ねていくと、
２６次魔方陣当たりでも１秒に数百という単位で生成可能ですから、
10を30としても結構です。）
例えば、４次魔方陣などを算出するときには、
明らかに無駄なメモリーを確保しているわけですが、
Cではどうすることも出来ませんから、
妥協するしかないわけです。
第４話へ 第６話へ
