プログラマ専用SNS ミクプラ

コード:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define true 1
#define false 0

int n=4;
double Y=-0.5;

int main(void)
{
	int mannaka=0;
	int x=pow(2,n); /*系列の長さ*/
	int y=pow(2,n-1);
	int kosuu=pow(2,pow(2,n-1)-n); /*系列の個数*/
	int weight[x][x];
	int igai[x][x];
	int l, k,i,j,q;
	int t=0;
	int p=0;
	int soukan[x];
	int g[x];
	float jiko[x]; /*相関値をいれる配列*/
	float f[x];
	float fmin=0.0;
	float fmax=0.0;
	int sift[x];

	printf("n=%d, 系列の長さ=%d, 系列の個数=%d\n",n,x,kosuu);

	/************** 道の生成を行なう*****************/

	for(l=0;l<x;l++) for(k=0;k<x;k++) weight[l][k] = false;

	j=2;
	for(i=1;i<y-1;i++){
		weight[i][j]=1;
		weight[i][j+1]=1;
		j=j+2;
	}

	j=2;
	for(i=y+1;i<x-1;i++){
		weight[i][j]=1;
		weight[i][j+1]=1;
		j=j+2;
	}

	weight[0][1]=1;;
	weight[y-1][x-1]=1;
	weight[y][0]=1;
	weight[x-1][x-2]=1;

	for(l=0;l<x;l++) for(k=0;k<x;k++) igai[l][k] = false;
	int ransu;
	int debruijn=0; /*系列の個数をカウントする変数*/
	int visited[x],current; /* visitedは訪れた所を,currentは現在値を示す変数*/
	int tour[x],length=0; /* tour は道順を、lengthは系列の長さを計る変数*/


	for(i=0;i<x;i++) visited[i] = false; /*初めはすべての点を訪れていないのでfalseにする*/

	current = 0; /*スタート地点を０とする*/
	tour[0]=0;


	while(debruijn<kosuu){

		for(j=0;j<x;j++){

			if(weight[current][j]==1 && visited[j] == false && j != y ){
				weight[current][j]=-1;
				current= j;
				visited[current]=true;
				j=0;
				length++;
				tour[length]=current;
			}else if(weight[current][y]==1 && length==x-2 && j==y && visited[y]== false){
				weight[current][j]=-1;
				current = y;
				visited[current]=true;
				j=0;
				length++;
				tour[length]=current;
				debruijn++;

				k=0;
				for(i=0;i<x;i++){
					if(0<=tour[i] && tour[i]<=y-1){
						soukan[k]=-1; /*自己相関関数を求めるために系列の0を-1にする処理*/
					}else if(y<=tour[i] && tour[i]<=x-1){
						soukan[k]=1;
					}
					k++;
				}

				for(k=0;k<x;k++) jiko[k]=0.0;

				for(i=0;i<x;i++){
					for(j=0;j<x;j++){
						jiko[i]=jiko[i]+soukan[j]*soukan[(j+i)%x]; /*ずれがiの時の相関値を計算*/
					}
					jiko[i]=jiko[i]/x;
				}

				f[0]=jiko[0];
				q=0;
				for(k=0;k<x;k++){
					if(jiko[k]!=f[q] && jiko[k]!=0.0){
						for(j=0;j<q+1;j++){
							if(f[j]==jiko[k]){
								break;
							}else if(j==q ){
								q++;
								f[q]=jiko[k];
							}
						}
					}
				}

				for(j=0;j<q+1;j++) g[j]=0;

				for(j=0;j<q+1;j++){
					for(k=0;k<x;k++){
						if(f[j]==jiko[k]){
							g[j]=g[j]+1;
						}
					}
				}

				for(j=0;j<q+1;j++){ /*worstcaseを求める*/
					if(fabs(f[j])>fabs(fmin) && f[j]<0.0){
						fmin=f[j];
					}else if(f[j]>fmax && f[j]!=1.00){
						fmax=f[j];
					}
				}

				for(i=0;i<x;i++){
					if(jiko[i]==Y){ /* 相関値Yが出てくる系列のみ表示する*/
						for(j=0;j<x;j++){
							if(0<=tour[j] && tour[j]<=y-1){
								ransu=0;
							}else if(y<=tour[j] && tour[j]<=x-1){
								ransu=1;
							}
							printf("%d->",ransu);
						}
						printf("%d]\n\n",tour[0]);


						for(k=0;k<t+1;k++){
							if(i==y){
								mannaka++;
								break;
							}else if(t==0 && i!=y){
								igai[k][0]=i;
								igai[k][1]++;
								t++;
								break;
							} else if(igai[k][0]==i && i!=y){
								igai[k][1]++;
								break;
							}else if(k==t && i!=y){
								igai[k][0]=i;
								igai[k][1]++;
								t++;
								break;
							}
						}

						for(i=0;i<x;i++){
							if(jiko[i]==Y){
								printf("%fが出てくるシフト時間は%d\n",Y,i);
							}
						}
						printf("\n");

						for(i=0;i<x;i++) printf("%f\n",jiko[i]); /* ずれがiの時の相関値を系列ごとに表示*/

						printf(" 相関値 個数\n");

						for(j=0;j<q+1;j++){
							printf("%15f %d\n",f[j],g[j]);
						}

						printf("現在までのworst case=%f,相関値のMAXは%f\n\n",fmin,fmax);

						break;
					}
				}
				break;
			}else if(j==x-1){ /*道がなくなった場合、別の道を探す時の関数*/

				p=0;

				while(p<1){
					length--;
					for(k=0;k<x;k++){

						if( weight[tour[length]][k]==1 && visited[k] == false && k!=y){
							visited[tour[length+1]]=false;
							j=0;
							p++;
						}else if(k==x-1 && p != 1){
							visited[tour[length+1]]=false;
							for(i=0;i<x;i++){
								if(weight[tour[length]][i]==true){
									weight[tour[length]][tour[length+1]]=1;
									break;
								}else if(i==x-1){
									for(j=0;j<x;j++) weight[tour[length]][j]=weight[tour[length]][j]*(-1);
								}
							}
						}

					}
				}
			}
			current=tour[length];
		}
	}
	printf("*********結果**********\n");
	printf("Rmax=%f\n",fmax);
	printf("Rmin=%f\n相関値%fが出てくるシフト時間は\n",fmin,Y);
	printf("真ん中%d %d個\n",y,mannaka);
	for(k=0;k<t;k++){
		printf("外側%d,%d %d個\n",igai[k][0],y+(y-(igai[k][0])),igai[k][1]);
	}
}