c - 从二维 C 数组中的前一个 "row"获取值

Question

我正在开发 1D 生命游戏(基于 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] 不是一个有效的表达式吗？

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) Bitwise & 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;

有一些明显的方法可以使这个过程更快。例如，根据前一列的父级和右上角的单元格构建此列的父级:& with 3, shift left, |与单元格内容。唯一丑陋的部分是分别处理第一列和最后一列。

根据评论进行编辑:

该算法在带有位操作的整数中有一些自然的实现，这就是“规则 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) 确定 parent 的模式数。

2) 确定 2^pattern 是否是规则的一部分。如果是，请填写单元格。

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

但是你可以保留这个值并使用相同的技巧减少计算量:保留最后一个父编号； & 它与 3 一起删除左父级；将它左移 1； |它与右边的 parent 。这为您提供了当前的 parent 号码。小心地适当处理数组的末尾条目，您就完成了。

另一个编辑:

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