2D C 배열의 이전 "행"에서 값 가져 오기

Question

나는 1D 생명의 게임에 대해 (여기에 설명 된 규칙에 따라 Mathworld에 기초하여) 일하고 있습니다. 본질적으로, 각 세대는 0 또는 1의 행 (죽었거나 살아있다)으로 표현되고 차세대는 "규칙"명령 행 인수의 2 진 표현을 기반으로 작성됩니다.

예를 들어, 규칙 30은 00011110 (30은 2 진수)으로 바뀌며 이는 새 셀을 생성하거나 다음 세대에서 스스로를 죽일 비트 패턴을 결정하는 데 사용됩니다.

이것을 프로그래밍하려면 이전 행에서 규칙을 적용하기 위해 3 개의 그룹으로 비트에 액세스 할 수 있어야합니다. 행, 그때 세 및 그룹에 위의 행의 비트 봐야한다을 생성하기 위해

00000100000 #seed row 
11001011001 #generated from seed row 
........... 
11110010101 #n-th row, generated from n-1 row 

: 아래 샘플 이미지 (시작 행은 항상 중앙 1과 0의 대상이므로주의)입니다 규칙을 1/0, 라이브/다이 결정으로 적용하십시오.

기본적으로 3 비트 패턴과 규칙을 일치시키고 자손에 대해 0 또는 1을 인쇄 할 계획입니다. 이것은 일반적인 알 고입니다 :

if three_bit_pattern == 'xxx' && rule[x] == 0/1 {print 0/1} else {print 1/0} 

프로그램의 난 부분에서 이전 행의 내용에 액세스하는 데 어려움이 있습니다. 내 모든 시도는 쓰레기 나 잘못된 데이터를 산출합니다.

간단히 말해, 이전 행의 값을 3 비트 그룹으로 어떻게 액세스합니까? 나는이 훨씬 간단했다, 그래서

int i, j, k; 
int row = atoi(argv[1]) + 1; 
int col = 2 * atoi(argv[1]) + 1; 

int arr[col]; 
int output[col]; 

char rule[9]; //binary representation of rule (2^8 stores up to 255 + null term) 
int2binary(atoi(argv[2]), &rule, 10); 

for(i = 0; i < row; i++){ 
    for(j = 0; j < col; j++){ 
    if(i == 0){ 
     if(j == col/2) //print 1 in center of first row 
     arr[i] = 1;  
     else 
     arr[i] = 0; 
     printf("%d", arr[i]); 
    } 
    else{ 
     //output[i] = arr[i-1]; 
     output[i+1] = arr[i]; 
     output[i+2] = arr[i+1]; 
     output[i+3] = arr[i+2]; 
     printf("%s", output); 
    } 
    }//end inner for_loop 
    printf("\n"); 
}//end outer for_loop 

}

확인을 그냥합니다 (하나 이전의 열을 잡고 하나를 두 배열을해야 할 것입니다 :

행은 다음과 같이 생성됩니다 흐름). 내가 이해하지 못하는 것은 왜 출력 배열을 출력하면 쓰레기가 생기는 것입니까? output [i] = arr [i]가 유효한 표현식이 아닌가?

Answer 1

데이터 구조에 영향을 줄 수있는 입력 또는 출력을 지정하지 않았습니다. 예를 들어 계산할 때 인쇄 할 경우 두 행 또는 한 행만 유지하면됩니다. 모든 행을 배열로 유지할 계획 인 것 같습니다.

if(firstTime == 1){ 
     if(j == row-1) //print 1 in center of first row 
      arr[i][j] = 1;  
     else 
      arr[i][j] = 0; 
    } 

아마

if(i == 0){ 
     if(j == col/2) //print 1 in center of first row 
      arr[i][j] = 1;  
     else 
      arr[i][j] = 0; 
    } 

또는 뭔가 간단해야한다 : 초기 행의 논리 오류를 가지고있는 것처럼

는 것 같습니다.

다른 행을 생성하는 알고리즘은 그렇게 복잡하지 않습니다.

1) 위 행의 요소를 사용하여 0에서 7까지의 숫자를 만듭니다.

2) 1 < < 비트 단위 & (규칙 포함) 1 수는

parent = 0; 
if(j>0 && arr[i-1][j-1]) parent = 4; 
if(arr[i-1][j]) parent += 2; 
if(j<col-1 && arr[i-1][j+1]) parent += 1; 

position = 1 << parent; 
arr[i][j] = (rule & position)?1:0; 

이 신속하게 몇 가지 확실한 방법이 있습니다 결과를 얻을 수 있습니다. 예 :이전 열의 부모 및 오른쪽 위의 셀을 기준으로이 열의 부모를 구성하십시오. & 3, 왼쪽으로 시프트, | 세포 내용물. 유일한 추악한 부분은 처음과 마지막 열을 개별적으로 처리하는 것입니다. 덧글에 대한 응답으로

편집 :

알고리즘은 "규칙 XX"아이디어의 출처 인 비트 연산과 정수의 일부 자연 구현이있다.

현재 공간에 대한 선택은 그 위의 세 공백에 의해 결정됩니다. 이것들에는 8 가지 가능성이 있습니다. 우리는 이것을 바이트의 8 비트에 해당한다고 생각할 수 있습니다.

각 규칙은 8 가지 가능성 집합과 집합 {0,1} 간의 대응 관계입니다. 2^8 = 256 개의 가능한 대응 또는 규칙이 있으며, 이는 우연히 한 바이트의 가능한 값의 수와 같습니다.

규칙에 레이블을 지정하는 가장 편리한 방법은 상위 셀이 결정한대로 현재 셀을 채우는 방법을 정확하게 나타내는 숫자입니다. 예를 들어,

규칙 30 :

30 = 16 + 8 + 4 + 2 = 2^4 + 2^3 + 2^2 + 2^1

따라서 규칙이 충전하는 셀 :

4 = 100 
3 = 011 
2 = 010 
1 = 001 

또 다른 예로, 이전 행을 복사하는 규칙은 무엇입니까? 상기 셀이 채워지면, 우리가 셀에 기입이 경우

하지만 인접 셀이 무엇이든 될 수

010 = 2 
011 = 3 
110 = 6 
111 = 7 

그래서 규칙 2^2 + 2^3 + 2^6 + 2^7 = 규칙 4 + 8 + 64 + 128 = 규칙 204.

세포를 결정하는 알고리즘이 더 좋았 으면 좋겠습니다.

1) 부모의 패턴 수를 결정하십시오.

2) 2^pattern이 규칙의 일부인지 확인하십시오. 그렇다면 셀을 채우십시오.

내가 갖고있는 다른 의견은 얼마나 저장할 필요가 있는지입니다. 이동하면서 출력하면 배열의 한 행 (한 차원 만 필요함) 만 있으면됩니다. 행을 탐색 할 때 항목을 다음 행의 값으로 바꿀 수 있습니다. 유일한 어려움은 대체 할 현재 값을 어떻게 든 유지하여 다음 셀을 결정하는 데 사용해야한다는 것입니다.

하지만이 값을 유지하고 같은 트릭으로 계산량을 줄일 수 있습니다. 마지막 상위 번호 유지. & 왼쪽 부모를 제거하려면 3을 입력하십시오. 왼쪽으로 1 시프트하십시오. | 오른쪽 부모와 함께. 이렇게하면 현재 상위 번호가 제공됩니다. 배열의 끝 항목을 적절하게 처리하면주의해야합니다.

ANOTHER 편집 :

먼저 이전 버전을 구현하지만, 당신이 정말로 공간을 절약에 미친하려는 경우, 더욱 마음을 워프, 비트 정수 값 대신 배열로 행을 저장하려고 1s 및 0s.행의 길이가 long의 비트 수보다 길어 지길 원한다면 비트를 보유하는 정수 배열과 두 개의 정수의 경계에있는 셀을 처리하는 미친 비트 조작이 필요합니다. 재미있어!