2

我正在开发 1D Game of Life（基于Mathworld中规定的规则）。本质上，每一代都表示为一行 0 或 1（死或活），并且下一代是基于“规则”命令行参数的二进制表示创建的。

例如，规则 30 变为 00011110（30 的二进制），这用于确定哪些位模式将产生新的单元格或在下一代中自行消亡。

为了对此进行编程，我需要能够访问前一行中的三个一组的位（以应用规则）。下面是一个示例图像（请注意，起始行始终为 0，中间为 1）：

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

为了生成一行，我必须以三个一组的方式查看上面一行中的位，然后将规则应用为 1/0，生死决定。

基本上我计划匹配 3 位模式和规则，并使用它为后代打印 0 或 1。这是一般算法：

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

我遇到困难的程序部分是访问前一行的内容。我所有的尝试都会产生垃圾或不正确的数据。

简而言之，我如何以三位为一组访问前一行的值？

行是这样创建的：

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] 不是一个有效的表达式吗？

4

1 回答 1

2

您尚未指定输入或输出，这可能会影响要使用的数据结构。例如，如果在计算它们时将它们打印出来，您可能只需要保留两行或什至只保留一行。看起来您打算将所有行保留在一个数组中。

看起来您在初始行中有一个逻辑错误：

    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<<(number from 1) with the rule to get result

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 是否是规则的一部分。如果是，请填写单元格。

我的另一个评论是你需要存储多少。如果你去输出，你只需要数组的一行（即只有一维）。遍历行时，可以将条目替换为下一行的值。唯一的困难是您需要以某种方式保留要替换的当前值以用于确定下一个单元格。

但是你可以保持这个值并用同样的技巧减少计算量：保持最后一个父编号；& it with 3 删除左父级；将其左移 1；| 它与右边的父母。这将为您提供当前的父编号。注意适当地处理数组的结尾条目，你就完成了。

另一个编辑：

首先实现以前的版本，但如果你真的想疯狂地节省空间，并且更加扭曲你的想法，请尝试将行存储为整数的位值，而不是 1 和 0 的数组。如果你想要一行比 long 中的位数更长，那么你需要一个整数数组来保存这些位，以及一些疯狂的位操作来处理两个这样的整数边界上的单元格。玩得开心！

于 2011-09-18T05:49:37.127 回答