2

I'm working on a 1D Game of Life (based upon the rules set out here at Mathworld). Essentially, each generation is represented as a row of 0's or 1's (dead or alive) and the next generation is created based upon the binary representation of a "rule" command line argument.

たとえば、ルール 30 は 00011110 (30 のバイナリ) に変わり、これを使用して、新しいセルを生成するか、次の世代で消滅するビット パターンを決定します。

これをプログラムするには、前の行から (ルールを適用するために) 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 ビットのグループでアクセスするにはどうすればよいでしょうか?

行は次のように作成されます。

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

}

わかりましたので、これをかなり単純にして、2 つの配列 (前の列を保持するものと現在の列を保持するもの) を作成します。私が理解していないのは、なぜ出力配列を印刷するとガベージが生成されるのですか? output[i] = arr[i] は有効な式ではありませんか?

4

1 に答える 1

2

入力または出力を指定していないため、使用するデータ構造に影響を与える可能性があります。たとえば、計算中にそれらを印刷する場合、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) Bitwise & 1<<(number from 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;

これをより速くするいくつかの明らかな方法があります。たとえば、前の列の親と右上のセルに基づいて、この列の親を作成します: & with 3, shift left, | セルの内容で。唯一の醜い部分は、最初と最後の列を別々に処理することです。

コメントに応じて編集:

このアルゴリズムには、ビット操作を伴う整数での自然な実装がいくつかあります。これが「ルール XX」のアイデアの由来です。

基本的に、現在のスペースの選択は、その上の 3 つのスペースによって決定されます。これらには 8 つの可能性があります。これらは、1 バイトの 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 です。

セルを決定するアルゴリズムがより理にかなっていることを願っています。

１）親のパターン数を決定する。

2) 2^pattern がルールの一部であるかどうかを判断します。その場合は、セルに入力してください。

私が持っていた他のコメントは、どれだけ保存する必要があるかということでした. そのまま出力する場合、必要なのは配列の 1 行 (つまり、1 次元のみ) だけです。行をトラバースしながら、エントリを次の行の値に置き換えることができます。唯一の問題は、次のセルを決定する際に使用するために、置き換える現在の値を保持する必要があることです。

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

別の編集：

最初に以前のバージョンを実装しますが、スペースを節約することに本当に夢中になり、さらに心を歪めたい場合は、行を 1 と 0 の配列ではなく、整数のビット値として保存してみてください。long のビット数よりも長い行が必要な場合は、ビットを保持する整数の配列と、そのような 2 つの整数の境界にあるセルを処理するためのクレイジーなビット操作が必要です。楽しむ！

于 2011-09-18T05:49:37.127 に答える