2D C配列の前の「行」から値を取得する

Question

私は1Dゲームオブライフ（ここに記載されたルールに基づいてMathworldに基づいています）に取り組んでいます。本質的に、各世代は0または1の行（死んでいるか生きているか）で表され、次の世代は「ルール」コマンドライン引数のバイナリ表現に基づいて作成されます。

たとえば、ルール30は00011110（30の場合は2進数）に変わり、これを使用して、次の世代で新しいセルを生成するかどうかを決定します。

これをプログラムするには、前の行から（ルールを適用するために）3つのグループのビットにアクセスできる必要があります。次のサンプル画像（開始行が常に0の中央1であることに注意）である：

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

行を生成するために、私は、次の3つのグループに上記行からのビットを見て、必要がありますルールを1/0、生/死の決定として適用する。

基本的に3ビットのパターンとルールを一致させ、それを使って子孫に0または1のいずれかを印刷します。これは一般的なアルゴリズムです。

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

私が問題を抱えている部分は、前の行の内容にアクセスすることです。私の試みはすべてゴミや不正なデータをもたらす。

要するに、前の行の値に3ビットのグループでアクセスするにはどうすればよいですか？

行が次のように作成されますので、私はずっと簡単で、ちょうど2つのアレイ（以前のコラムを保持する1とのものを持っているつもりですこれを作った

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 

}

[OK]を現在）。なぜ私は理解していないのは、出力配列を印刷するとゴミが出るのですか？ output [i] = arr [i]は有効な式ではありませんか？

Answer 1

入力または出力が指定されていないため、使用するデータ構造に影響する可能性があります。たとえば、2行または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、left、|セルの内容で唯一の醜い部分は最初と最後の列を別々に扱います。 COMMENTに応じて

EDIT：

アルゴリズムは、「ルールXX」のアイデアはどこから来るのである、ビット演算と整数でいくつかの自然な実装を持っています。

現在のスペースの選択肢は、その上の3つのスペースによって決まります。これらには8つの可能性があります。これらは、8ビットのバイトに対応するものと考えることができます。

各ルールは、8つの可能性のセットから{0,1}のセットへの対応です。 2^8 = 256の可能な対応または規則があり、偶然に1バイトの可能な値の数と同じです。

ルールにラベルを付ける最も便利な方法は、現在のセルが親セルによって決定されたとおりに塗りつぶされる方法を正確に示す数字です。例えば、

ルール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がルールの一部かどうかを判定します。その場合は、セルを記入してください。

私が持っていたもう1つのコメントは、どれくらい保存する必要があるかということでした。出力する場合は、配列の行が1つだけ必要です（つまり、次元は1つだけです）。行をトラバースすると、次の行の値でエントリを置き換えることができます。唯一の難点は、置き換えようとしている現在の値を何らかの形で保持して、次のセルの決定に使用する必要があることです。

しかし、この値を保持して同じトリックで計算量を減らすことができます。最後の親の数を保持します。 &左の親を削除するには3を指定します。それを1だけ左にシフトする。 |それは右の親と一緒です。これにより、現在の親番号が得られます。アレイの最後のエントリを適切に処理するように注意してください。

ANOTHER EDIT：

整数の代わりに、配列のビット値として行を格納しようと、最初の以前のバージョンを実装していますが、実際にスペースを節約する上でクレイジー取得したい場合、さらにあなたの心をワープ1と0の行をビ​​ットの長さよりも長くしたい場合は、ビットを保持する整数の配列と、そのような2つの整数の境界にあるセルを扱うためのいくつかの狂ったビット操作が必要です。楽しむ！