最長周期系列を生成するプログラミングについて

[Drink]

自分は今、11を禁止語にした最長周期系列を生成するプログラムを書くという課題に取り掛かっているのですが、お世辞にもプログラミングがうまいとは言えないので先輩に泣き付いて11を禁止していない場合のプログラムを教えてもらったのですが、そのアルゴリズムがどういう原理なのか教えてもらえずどう参考にしたらいいのかわかりません。
以下はその参考プログラムです。

#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[j]=1;
weight[j+1]=1;
j=j+2;
}

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

weight[x][x]や、注釈していないfor文やif文などの役割などがわからず、どうして答えが出てくるのかわかりません。
だれか解説してくれませんか？

[bitter_fox]

コードを載せる際はcodeタグで囲ってください。
詳しくはフォーラムルールをご覧ください。

コード:

#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]);
	}
}

自分は今、11を禁止語にした最長周期系列を生成するプログラムを書くという課題に取り掛かっているのですが、お世辞にもプログラミングがうまいとは言えないので先輩に泣き付いて11を禁止していない場合のプログラムを教えてもらったのですが、そのアルゴリズムがどういう原理なのか教えてもらえずどう参考にしたらいいのかわかりません。

「最長周期系列」や「11を禁止語」の説明が無くどういった目的を持ったプログラムかよく分からないので読み解きにくいです。
課題の内容を詳しくご説明ください。

[DRINK]

ご指摘ありがとうございます。
最長周期系列とは、nビットの線形01シフトレジスタがあるとして、その各状態を重複しないように表れるようにして初期状態に戻るなかで最も長い系列です。
n=1のとき、0→1→0で「01」
n=2のとき、00→01→11→10→00で「0011」
n=3のとき、000→001→010→101→011→111→110→100→000で「00010111」
　　　　　000→001→011→111→110→101→010→100→000で「00011101」
n=4のとき…
となります。
11を禁止語とはこの条件に、11が現れるのは禁止されるということです。この場合、系列の長さや表れる個数も小さくなるうえに、無視される状態が出てきます。
n=1のとき、0→1→0で「01」
n=2のとき、00→01→10→00で「001」
n=3のとき、000→001→010→100→000で「0001」、101は無視（101は系列に含むと010を重複させてしまうから）
n=4のとき…
といった具合です。

[beatle]

恐らく最長周期系列はM系列のことだと思います。
それから、お示しになられたコードはVisual C++ 2010ではコンパイルできませんね。C99のコードのようです。

多分ですが、授業などで最長周期系列の説明は受けているのですよね？
だとすれば、最長周期系列の生成のやり方は分かっているはずですから、その知識を頼りにプログラムを読んだら
アルゴリズムが分かるはずですね。先輩も授業で説明されたアルゴリズムをプログラムに落としているのではないでしょうか。

以下、最長周期系列やM系列をまったく知らない人になったつもりで書きます。

最長周期系列とは、nビットの線形01シフトレジスタがあるとして、その各状態を重複しないように表れるようにして初期状態に戻るなかで最も長い系列です。
n=1のとき、0→1→0で「01」
n=2のとき、00→01→11→10→00で「0011」
n=3のとき、000→001→010→101→011→111→110→100→000で「00010111」
　　　　　000→001→011→111→110→101→010→100→000で「00011101」

説明不足です。
000→001→010→101→011→111→110→100→000を作るやり方も、
その9つの3ビットデータから「00010111」を作るやり方も書かれていません。
「nビットの線形01シフトレジスタがあるとして」、その後どういう風にすれば具体的に9つの3ビットデータを得られるのか。
そこがミソですよね。

さらに

11を禁止語とはこの条件に、11が現れるのは禁止されるということです。

どこに11が現れてはいけないのですか？9つの3ビットデータの中ですか？
それとも、その3ビットデータから生成された8桁のデータの中ですか？

101は系列に含むと010を重複させてしまうから

の意味もわかりませんでした。

余談ですが、日本語でアルゴリズムを説明できないのにプログラムを書く、というやり方は相当難しいです。