从前一“行”获取值二维 C 数组

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）按位& 1<<(number from 1) with therule 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 是否是规则的一部分。如果是这样，请填写该单元格。

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

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

另一个编辑：

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