第12話 特殊種法の最適シード値実験コード
を実現するプログラム例
#include<iostream>
#include<ctime>
using namespace std;
int f1(int g,int m1[10][10],int m2[10][10],int a[10][10],int n,int* p,int* q,int cn);
int f2(int g,int m1[10][10],int m2[10][10],int a[10][10],int n,int* p,int* q,int cn);
void h(int m1[10][10],int m2[10][10],int n);
void zh(int n,int *p,int *q);
void sy(int m1[10][10],int m2[10][10],int a[10][10],int n);
void sy1(int m2[10][10],int a[10][10],int n);
clock_t hj,ow,rk,rkm=100000;
void main(){
int n=7;
int m1[10][10],m2[10][10],a[10][10],t=0;
int p[100],q[100];
zh(n,p,q);
for(int i=0;i<100;i++){
cout<<"i="<<i<<endl;
srand(i);
sy(m1,m2,a,n);
hj=clock();
cout<<n<<"次魔方陣種が"<<endl<<f1(0,m1,m2,a,n,p,q,0)<<"個できました。"<<endl;
ow=clock();
rk=ow-hj;
cout<<"魔方陣種生成にかかった時間は"<<(double)rk/1000<<"秒です。"<<endl;
if(rk<rkm){
rkm=rk;
cout<<"i="<<i<<" "<<(double)rkm/1000<<"秒"<<endl;
}
}
cout<<"プロジェクト終了"<<endl;
}
void sy(int m1[10][10],int n){
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
m1[i][j]=0;
}
}
void sy1(int m2[10][10],int a[10][10],int n){
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
m2[i][j]=0;
a[i][j]=0;
}
}
void zh(int n,int *p,int *q){
int i,j,cn;
int a[10][10];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=-1;
for(i=0;i<n;i++)a[i][i]=i;
cn=n;
for(i=0;i<n;i++){
if(a[i][n-1-i]==-1){
a[i][n-1-i]=cn;
cn++;
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(a[i][j]==-1){
a[i][j]=cn;
cn++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
p[a[i][j]]=j;
q[a[i][j]]=i;
}
}
}
int f1(int g,int m1[10][10],int m2[10][10],int a[10][10],int n,int* p,int* q,int cn){
ow=clock();
rk=ow-hj;
if(rk>rkm)return(cn);
int i,j,x,y,ht;
x=p[g];
y=q[g];
int ii,iii;
ii=rand()%n;
for(iii=0;iii<n;iii++){
ow=clock();
rk=ow-hj;
if(rk>rkm)return(cn);
i=(iii+ii)%n+1;
m1[y][x]=i;
if(g>0){
if(g<n){
for(j=0;j<g;j++){
if(m1[j][j]==m1[y][x])goto tobi;
}
}
}
if(x==n-1-y && x!=y){
for(j=0;j<y;j++){
if(m1[j][n-1-j]==m1[y][x])goto tobi;
}
if(m1[x][x]==m1[y][x])goto tobi;
if(m1[y][y]==m1[y][x])goto tobi;
if(n%2==1)if(m1[n/2][n/2]==m1[y][x])goto tobi;
}
if(x!=y && x!=n-1-y){
for(j=0;j<x;j++){
if(m1[y][j]==m1[y][x])goto tobi;
}
for(j=0;j<y;j++){
if(m1[j][x]==m1[y][x])goto tobi;
}
if(m1[y][y]==m1[y][x])goto tobi;
if(m1[x][x]==m1[y][x])goto tobi;
if(m1[y][n-1-y]==m1[y][x])goto tobi;
if(m1[n-1-x][x]==m1[y][x])goto tobi;
}
if(g+1<n*n){
cn=f1(g+1,m1,m2,a,n,p,q,cn);
ow=clock();
rk=ow-hj;
if(rk>rkm)return(cn);
if(cn==100)return(cn);
}
else{
sy1(m2,a,n);
cn=f2(0,m1,m2,a,n,p,q,cn);
rk=ow-hj;
if(rk>rkm)return(cn);
if(cn==100)return(cn);
}
tobi:;
}
return(cn);
}
int f2(int g,int m1[10][10],int m2[10][10],int a[10][10],int n,int* p,int* q,int cn){
ow=clock();
rk=ow-hj;
if(rk>rkm)return(cn);
int i,j,x,y,ht;
x=p[g];
y=q[g];
int ii,iii;
ii=rand()%n;
for(iii=0;iii<n;iii++){
ow=clock();
rk=ow-hj;
if(rk>rkm)return(cn);
i=(iii+ii)%n+1;
m2[y][x]=i;
ht=0;
if(a[m1[y][x]][m2[y][x]]==1)goto tobi;
ht=1;
a[m1[y][x]][m2[y][x]]=1;
if(g>0){
if(g<n){
for(j=0;j<g;j++){
if(m2[j][j]==m2[y][x])goto tobi;
}
}
}
if(x==n-1-y && x!=y){
for(j=0;j<y;j++){
if(m2[j][n-1-j]==m2[y][x])goto tobi;
}
if(m2[x][x]==m2[y][x])goto tobi;
if(m2[y][y]==m2[y][x])goto tobi;
if(n%2==1)if(m2[n/2][n/2]==m2[y][x])goto tobi;
}
if(x!=y && x!=n-1-y){
for(j=0;j<x;j++){
if(m2[y][j]==m2[y][x])goto tobi;
}
for(j=0;j<y;j++){
if(m2[j][x]==m2[y][x])goto tobi;
}
if(m2[y][y]==m2[y][x])goto tobi;
if(m2[x][x]==m2[y][x])goto tobi;
if(m2[y][n-1-y]==m2[y][x])goto tobi;
if(m2[n-1-x][x]==m2[y][x])goto tobi;
}
if(g+1<n*n){
cn=f2(g+1,m1,m2,a,n,p,q,cn);
rk=ow-hj;
if(rk>rkm)return(cn);
if(cn==100)return(cn);
}
else{
h(m1,m2,n);
cout<<endl<<endl;
rk=ow-hj;
if(rk>rkm)return(cn);
if(cn==100)return(cn);
cn++;
}
tobi:;
if(ht==1)a[m1[y][x]][m2[y][x]]=0;
}
return(cn);
}
void h(int m1[10][10],int m2[10][10],int n){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if((m1[i][j]-1)*n+m2[i][j]<10)cout<<"0"<<(m1[i][j]-1)*n+m2[i][j]<<" ";
if((m1[i][j]-1)*n+m2[i][j]>=10)cout<<(m1[i][j]-1)*n+m2[i][j]<<" ";
}
cout<<endl;
}
}
参考ダウンロード添付ファイル
さて、これで第24講は終了です。
第25講から第29講までは、ｎ進数の加減乗除（足し算・引き算・かけ算・割り算）を考えます。
第25講ではｎ進数の加法を、
第26講ではｎ進数の減法（引き算）を、
第27講ではｎ進数の乗法（かけ算）を、
第28・29講ではｎ進数の除法(割り算)を、
研究していきます。
ｎ進数の演算なんて興味ないよと、
お思いの方もいらっしゃるでしょうが、
そもそも、コンピュータは２進数、８進数、１６進数などによって処理をしています。
やがて、１２８ビットパソコンが普及していけば、
１２８進数でも処理されるようになるでしょう。
１６進数などが利用される理由は、
２進数と大変相性がよいからです。
そして、実はｎ進数の研究は、
巨大整数演算の基礎となるのです。
巨大整数の演算による巨大素数や巨大完全数（366桁の整数）
は、本講義第４部の主な主題になる予定です。
巨大整数の演算は・・・
