１０．素数・素数・偶数（の一部）方陣を作成するプログラム例
ここで紹介するプログラムは、９で説明した自己再帰によるプログラムであり、種の定義域は特殊領域に限られている。理論的には表題の魔方陣が作成可能であるが、実際上はパソコンの性能では４・５・７・８・９あたりが限界である。６が入っていないのは、特殊種による方法だからである。６方陣種は、特殊領域内においては、すべて非生産的であることはこのプログラムを走らせれば、１秒もかからず証明される。本質的には同じプログラムを２つ示しておく。このプログラムで骨格をなすのが関数ｔａｎｅの部分である。同一構造性から本質上はｔａｎｅは１つですむが、１つにするとスピードは著しく遅くなる。スピードが遅くても、プログラムの美的な観点からいうと１つにした方が、優れていると思うのでそれも示したわけだ。１番目のプログラムがｔａｎｅが１つの場合で、２番目の方は、少しずつ変えたｔａｎｅを４つ用意している。２番目の方がスピードは１０倍は早い。したがって、コンパイルは２番目のプログラムの方をされることをお勧めいたします。インデントはご自分でお取りください。
プログラム１
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 100
#define MAH 9
#define KRK 100
#define KR 30
char tane2(char dtr,char g,char n);
char tane4(char dtr,char g,char n);
void gousei(char s,char t,char n);
void ijhenkan(char g,char n);
void seisou(char n);
void seisoux(char d,char n);
unsigned int kai=0;
char hairetu[MAH][MAH];
char *x;
unsigned long int kn=0;
void main()
{
char n,m;
char ii;
int jj;
x=malloc(2*MAH*MAH);
clrscr();
gotoxy(1,1);
printf("何方陣について検索しますか。");
scanf("%d",&n);
seisoux(0,n);
for(jj=0;jj<n;jj++){
*(x+jj*MAH+jj)=jj+1;
*(x+jj*MAH+jj+MAH*MAH)=jj+1;
/*
gotoxy(2*j+1,2+j);
printf("%d",*(x+j*MAH+j));
gotoxy(2*j+1,3+j+n);
printf("%d",*(x+j*MAH+j+MAH*MAH));
*/
}
tane2(0,n,n);
seisou(n);
gotoxy(5,23);
printf(" 何かキーを入力してください。");
getchar();
getchar();
}
void gousei(char s,char t,char n)
{
static char y[MAH][MAH];
register int ii,jj;
char k,l;
char *a,*b;
char ken=1,iii,ij,ik;
for(ii=0;ii<n;ii++){
for(jj=0;jj<n;jj++){
y[ii][jj]=*(x+ii*MAH+jj+s*MAH*MAH)+n*(*(x+ii*MAH+jj+t*MAH*MAH)-1);
}
}
for(ii=0;ii<n;ii++)
for(jj=0;jj<n;jj++)
for(k=0;k<=ii;k++)
for(l=0;l<n;l++){
if((k==ii) &&
(l==jj))break;
if(y[ii][jj]==y[k][l]){
ken=0;
goto end;
}
}
end:
if(ken==1){
iii=kai%4;
kai++;
gotoxy(65,23);
printf("個数＝%d",kai);
for(ii=0;ii<n;ii++)
for(jj=0;jj<n;jj++){
ik=iii/2;
ij=iii%2;
gotoxy(3*jj+1+(n+1)*ik*3,ii+2+(n+1)*ij);
printf("%2d",y[ii][jj]);
}
}
}
void seisou(char n)
{
char ii,jj;
for(ii=0;ii<n;ii++)
for(jj=0;jj<n;jj++)
if(ii!=jj)
hairetu[ii][jj]=0;
else
hairetu[ii][jj]=1;
}
char tane2(char d,char g,char n)
{
char i,j,k,l,h,kaesu=0,w1,w2,ii;
if(n%2==0){
if(g<2*n){
i=g-n;
j=2*n-g-1;
}
else{
i=(g-2*n)/(n-2);
j=(g-2*n)%(n-2);
if(i<n-i-1){
if(j>=i)
j++;
if(j>=n-i-1)
j++;
}
if(n-i-1<i){
if(j>=n-i-1)
j++;
if(j>=i)
j++;
}
}
}
else{
if(g<2*n-1){
i=g-n;
j=n-i-1;
if(i>=j){
i++;
j--;
}
}
else if(g<(n+1)*n/2){
i=(g-2*n+1)/(n-2);
j=(g-2*n+1)%(n-2);
if(j>=i)
j++;
if(j>=n-i-1)
j++;
}
else if(g<(((n+1)/2+1)*n-1)){
i=(n+1)/2-1;
j=g-(n+1)*n/2;
if(i<=j)
j++;
}
else{
i=(g-2*n)/(n-2);
j=(g-2*n)%(n-2);
if(j>=n-i-1)
j++;
if(j>=i)
j++;
}
}
k=1;
if(d==1)
w1=*(x+i*MAH+j)-1;
while(k<n+1){
if(k==i+1 && k<n)k++;
if(k==i+1 && k==n)break;
if(k==j+1 && k<n)k++;
if(k==j+1 && k==n)break;
h=1;
w2=k-1;
*(x+i*MAH+j+d*MAH*MAH)=k;
/*
gotoxy(2*j+1,3+i+n);
printf("%d",*(x+i*MAH+j+d*MAH*MAH));
*/
if(i==n-j-1)
for(l=0;l<i;l++){
if(*(x+i*MAH+n-i-1+d*MAH*MAH)==*(x+l*MAH+n-1-l+d*MAH*MAH)){
h=0;
break;
}
}
if(h==1)
if(i>j && *(x+i*MAH+j+d*MAH*MAH)==*(x+i*MAH+i+d*MAH*MAH))h=0;
if(h==1)
if(i<j && *(x+i*MAH+j+d*MAH*MAH)==*(x+j*MAH+j+d*MAH*MAH))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j+d*MAH*MAH)==*(x+i*MAH+n-i-1+d*MAH*MAH))
h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j+d*MAH*MAH)==*(x+(n-j-1)*MAH+j+d*MAH*MAH))
h=0;
if(h==1)
for(l=0;l<i;l++){
if(*(x+i*MAH+j+d*MAH*MAH)==*(x+l*MAH+j+d*MAH*MAH)){
h=0;
break;
}
}
if(h==1)
for(l=0;l<j;l++){
if(*(x+i*MAH+j+d*MAH*MAH)==*(x+i*MAH+l+d*MAH*MAH)){
h=0;
break;
}
}
if(d==1 && h==1){
if(hairetu[w1][w2]==0){
hairetu[w1][w2]=1;
}
else
h=0;
}
if(h==1)
if(d==0)
if(g+1<n*n){
kaesu=tane2(d,g+1,n);
}
else{
seisou(n);
seisoux(1,n);
kn++;
gotoxy(65,22);
printf("syusuu=%ld",kn);
tane2(1,n,n);
}
else
if(g+1<n*n){
kaesu=tane2(d,g+1,n);
}
else{
gousei(0,1,n);
seisou(n);
}
if(h==1)
if(d==1 && kaesu==1){
h=0;
hairetu[w1][w2]=0;
}
else{
k++;
}
if(h==0)
k++;
}
if(h==1)
kaesu=0;
else
kaesu=1;
*(x+i*MAH+j+d*MAH*MAH)=0;
return(kaesu);
}
void seisoux(char d,char n)
{
char ii,jj;
for(ii=0;ii<n;ii++)
for(jj=0;jj<n;jj++)
if(ii!=jj)
*(x+ii*MAH+jj +MAH*MAH*d)=0;
}
プログラム２
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 100
#define MAH 14
#define KRK 100
#define KR 30
char tane1(register int g,char n);
char tane2(register int g,char n);
char tane3(register int g,char n);
char tane4(register int g,char n);
void gousei(char s,char t,char n);
void seisou(char n);
void seisoux(char d,char n);
unsigned int kai=0;
char hairetu[MAH][MAH];
char *x;
unsigned long int kn=0;
void main()
{
char n,m;
char i,ii;
int j;
x=malloc(2*MAH*MAH);
clrscr();
i=1;
gotoxy(1,1);
printf("何方陣について検索しますか。");
scanf("%d",&n);
seisoux(0,n);
for(j=0;j<n;j++){
*(x+j*MAH+j)=j+1;
*(x+j*MAH+j+MAH*MAH)=j+1;
/*
gotoxy(2*j+1,2+j);
printf("%d",*(x+j*MAH+j));
gotoxy(2*j+1,3+j+n);
printf("%d",*(x+j*MAH+j+MAH*MAH));
*/
}
if(n%2==0)
tane1(n,n);
else
tane3(n,n);
seisou(n);
gotoxy(5,23);
printf(" 何かキーを入力してください。");
getchar();
getchar();
}
void gousei(char s,char t,char n)
{
static char y[MAH][MAH];
register int i,j;
char k,l;
char *a,*b;
char ken=1,ii,ij,ik;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
y[i][j]=*(x+i*MAH+j+s*MAH*MAH)+n*(*(x+i*MAH+j+t*MAH*MAH)-1);
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<=i;k++)
for(l=0;l<n;l++){
if((k==i) && (l==j))break;
if(y[i][j]==y[k][l]){
ken=0;
goto end;
}
}
end:
if(ken==1){
ii=kai%4;
kai++;
gotoxy(65,23);
printf("個数＝%d",kai);
for(i=0;i<n;i++)
for(j=0;j<n;j++){
ik=ii/2;
ij=ii%2;
gotoxy(3*j+1+(n+1)*ik*3,i+2+(n+1)*ij);
printf("%2d",y[i][j]);
}
}
}
char tane1(register int g,char n)
{
register int ii,i,j,k,l,h,kaesu=0,kk,kkk;
if(g<2*n){
i=g-n;
j=2*n-g-1;
}
else{
i=(g-2*n)/(n-2);
j=(g-2*n)%(n-2);
if(i<n-i-1){
if(j>=i)
j++;
if(j>=n-i-1)
j++;
}
if(n-i-1<i){
if(j>=n-i-1)
j++;
if(j>=i)
j++;
}
}
k=1; kk=random(n);
while(k<n+1){
kkk=(kk+k-1)%n+1;
if(kkk==i+1 && k<n){
k++;
kkk=(kk+k-1)%n+1;
}
if(kkk==i+1 && k==n)break;
if(kkk==j+1 && k<n){
k++;
kkk=(kk+k-1)%n+1;
}
if(kkk==j+1 && k==n)break;
h=1;
*(x+i*MAH+j)=kkk;
/*
gotoxy(2*j+1,2+i);
printf("%d",*(x+i*MAH+j));
*/
if(i==n-j-1)
for(l=0;l<i;l++){
if(*(x+i*MAH+n-i-1)==*(x+l*MAH+n-1-l)){
h=0;
break;
}
}
if(h==1)
if(i>j && *(x+i*MAH+j)==*(x+i*MAH+i))h=0;
if(h==1)
if(i<j && *(x+i*MAH+j)==*(x+j*MAH+j))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j)==*(x+i*MAH+n-i-1))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j)==*(x+(n-j-1)*MAH+j))h=0;
if(h==1)
for(l=0;l<i;l++){
if(*(x+i*MAH+j)==*(x+l*MAH+j)){
h=0;
break;
}
}
if(h==1)
for(l=0;l<j;l++){
if(*(x+i*MAH+j)==*(x+i*MAH+l)){
h=0;
break;
}
}
if(h==1)
if(g+1<n*n){
kaesu=tane1(g+1,n);
}
else{
kn++;
gotoxy(50,23);
printf("種数＝%ld",kn);
seisou(n);
seisoux(1,n);
tane2(n,n);
}
k++;
}
if(h==1)
kaesu=0;
else
kaesu=1;
*(x+i*MAH+j)=0;
return(kaesu);
}
void seisou(char n)
{
char i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)
hairetu[i][j]=0;
else
hairetu[i][j]=1;
}
char tane2(register int g,char n)
{
register int i,j,k,kk,kkk,l,h,kaesu=0,w1,w2,ii;
if(g<2*n){
i=g-n;
j=2*n-g-1;
}
else{
i=(g-2*n)/(n-2);
j=(g-2*n)%(n-2);
if(i<n-i-1){
if(j>=i)
j++;
if(j>=n-i-1)
j++;
}
if(n-i-1<i){
if(j>=n-i-1)
j++;
if(j>=i)
j++;
}
}
k=1;
w1=*(x+i*MAH+j)-1; kk=random(n);
while(k<n+1){
kkk=(kk+k-1)%n+1;
if(kkk==i+1 && k<n){
k++;
kkk=(kk+k-1)%n+1;
}
if(kkk==i+1 && k==n)break;
if(kkk==j+1 && k<n){
k++;
kkk=(kk+k-1)%n+1;
}
if(kkk==j+1 && k==n)break;
h=1;
w2=kkk-1;
*(x+i*MAH+j+MAH*MAH)=kkk;
/*
gotoxy(2*j+1,3+i+n);
printf("%d",*(x+i*MAH+j+MAH*MAH));
*/
if(i==n-j-1)
for(l=0;l<i;l++){
if(*(x+i*MAH+n-i-1+MAH*MAH)==*(x+l*MAH+n-1-l+MAH*MAH)){
h=0;
break;
}
}
if(h==1)
if(i>j && *(x+i*MAH+j+MAH*MAH)==*(x+i*MAH+i+MAH*MAH))h=0;
if(h==1)
if(i<j && *(x+i*MAH+j+MAH*MAH)==*(x+j*MAH+j+MAH*MAH))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j+MAH*MAH)==*(x+i*MAH+n-i-1+MAH*MAH))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j+MAH*MAH)==*(x+(n-j-1)*MAH+j+MAH*MAH))h=0;
if(h==1)
for(l=0;l<i;l++){
if(*(x+i*MAH+j+MAH*MAH)==*(x+l*MAH+j+MAH*MAH)){
h=0;
break;
}
}
if(h==1)
for(l=0;l<j;l++){
if(*(x+i*MAH+j+MAH*MAH)==*(x+i*MAH+l+MAH*MAH)){
h=0;
break;
}
}
if(h==1){
if(hairetu[w1][w2]==0){
hairetu[w1][w2]=1;
}
else
h=0;
}
if(h==1)
if(g+1<n*n){
kaesu=tane2(g+1,n);
}
else{
gousei(0,1,n);
seisou(n);
}
if(h==1)
if(kaesu==1){
h=0;
hairetu[w1][w2]=0;
}
else{
break;
}
if(h==0)
k++;
}
if(h==1)
kaesu=0;
else
kaesu=1;
/*
*(x+i*MAH+j+MAH*MAH)=0;
*/
return(kaesu);
}
void seisoux(char d,char n)
{
char i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)
*(x+i*MAH+j+MAH*MAH*d)=0;
}
char tane3(register int g,char n)
{
register int ii,i,j,k,l,h,kaesu=0,kkk,kk,m;
m=n/2;
if(g<2*n-1){
i=g-n;
j=n-i-1;
if(i>=j){
i++;
j--;
}
}
else if(g<(n+1)*n/2){
i=(g-2*n+1)/(n-2);
j=(g-2*n+1)%(n-2);
if(j>=i)
j++;
if(j>=n-i-1)
j++;
}
else if(g<(((n+1)/2+1)*n-1)){
i=(n+1)/2-1;
j=g-(n+1)*n/2;
if(i<=j)
j++;
}
else{
i=(g-2*n)/(n-2);
j=(g-2*n)%(n-2);
if(j>=n-i-1)
j++;
if(j>=i)
j++;
}
k=1; kk=random(n);
while(k<n+1){
kkk=(kk+k-1)%n+1;
if(kkk==i+1 && k<n){
k++;
kkk=(kk+k-1)%n+1;
}
if(kkk==i+1 && k==n)break;
if(kkk==j+1 && k<n){
k++;
kkk=(kk+k-1)%n+1;
}
if(kkk==j+1 && k==n)break;
h=1;
*(x+i*MAH+j)=kkk;
/*
gotoxy(2*j+1,2+i);
printf("%d",*(x+i*MAH+j));
*/
if(i==n-j-1)
for(l=0;l<i;l++){
if(*(x+i*MAH+n-i-1)==*(x+l*MAH+n-1-l)){
h=0;
break;
}
}
if(h==1)
if(j==n-i-1 && *(x+i*MAH+j)==*(x+m*MAH+m))h=0;
if(h==1)
if(i>j && *(x+i*MAH+j)==*(x+i*MAH+i))h=0;
if(h==1)
if(i<j && *(x+i*MAH+j)==*(x+j*MAH+j))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j)==*(x+i*MAH+n-i-1))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j)==*(x+(n-j-1)*MAH+j))h=0;
if(h==1)
for(l=0;l<i;l++){
if(*(x+i*MAH+j)==*(x+l*MAH+j)){
h=0;
break;
}
}
if(h==1)
for(l=0;l<j;l++){
if(*(x+i*MAH+j)==*(x+i*MAH+l)){
h=0;
break;
}
}
if(h==1)
if(g+1<n*n){
kaesu=tane3(g+1,n);
}
else{
kn++;
gotoxy(50,23);
printf("種数＝%ld",kn);
seisou(n);
seisoux(1,n);
tane4(n,n);
}
k++;
}
if(h==1)
kaesu=0;
else
kaesu=1;
*(x+i*MAH+j)=0;
return(kaesu);
}
char tane4(register int g,char n)
{
register int i,j,k,l,h,kaesu=0,w1,w2,m,kk,kkk;
m=n/2;
if(g<2*n-1){
i=g-n;
j=n-i-1;
if(i>=j){
i++;
j--;
}
}
else if(g<(n+1)*n/2){
i=(g-2*n+1)/(n-2);
j=(g-2*n+1)%(n-2);
if(j>=i)
j++;
if(j>=n-i-1)
j++;
}
else if(g<(((n+1)/2+1)*n-1)){
i=(n+1)/2-1;
j=g-(n+1)*n/2;
if(i<=j)
j++;
}
else{
i=(g-2*n)/(n-2);
j=(g-2*n)%(n-2);
if(j>=n-i-1)
j++;
if(j>=i)
j++;
}
k=1;
w1=*(x+i*MAH+j)-1; kk=random(n);
while(k<n+1){
kkk=(kk+k-1)%n+1;
if(kkk==i+1 && k<n){
k++;
kkk=(kk+k-1)%n+1;
}
if(kkk==i+1 && k==n)break;
if(kkk==j+1 && k<n){
k++;
kkk=(kk+k-1)%n+1;
}
if(kkk==j+1 && k==n)break;
h=1;
w2=kkk-1;
*(x+i*MAH+j+MAH*MAH)=kkk;
/*
gotoxy(2*j+1,3+i+n);
printf("%d",*(x+i*MAH+j+MAH*MAH));
*/
if(i==n-j-1)
for(l=0;l<i;l++){
if(*(x+i*MAH+n-i-1+MAH*MAH)==*(x+l*MAH+n-1-l+MAH*MAH)){
h=0;
break;
}
}
if(h==1)
if(j==n-i-1 && *(x+i*MAH+j+MAH*MAH)==*(x+m*MAH+m+MAH*MAH))h=0;
if(h==1)
if(i>j && *(x+i*MAH+j+MAH*MAH)==*(x+i*MAH+i+MAH*MAH))h=0;
if(h==1)
if(i<j && *(x+i*MAH+j+MAH*MAH)==*(x+j*MAH+j+MAH*MAH))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j+MAH*MAH)==*(x+i*MAH+n-i-1+MAH*MAH))h=0;
if(h==1)
if(j<n-i-1 && *(x+i*MAH+j+MAH*MAH)==*(x+(n-j-1)*MAH+j+MAH*MAH))h=0;
if(h==1)
for(l=0;l<i;l++){
if(*(x+i*MAH+j+MAH*MAH)==*(x+l*MAH+j+MAH*MAH)){
h=0;
break;
}
}
if(h==1)
for(l=0;l<j;l++){
if(*(x+i*MAH+j+MAH*MAH)==*(x+i*MAH+l+MAH*MAH)){
h=0;
break;
}
}
if(h==1){
if(hairetu[w1][w2]==0){
hairetu[w1][w2]=1;
}
else
h=0;
}
if(h==1)
if(g+1<n*n){
kaesu=tane4(g+1,n);
if(kaesu==0)if(i==j)break;
}
else{
gousei(0,1,n);
seisou(n);
}
if(h==1)
if(kaesu==1){
h=0;
hairetu[w1][w2]=0;
}
else{
break;
}
if(h==0)
k++;
}
if(h==1)
kaesu=0;
else
kaesu=1;
/*
*(x+i*MAH+j+MAH*MAH)=0;
*/
return(kaesu);
}
|
|
|
|
|
|
|
|
|
|
|
|
