使用Java或C在矩阵中存储1010

Question

我在一次采访中被问到这个问题（我无法回答）。我仍然渴望知道如何解决这个问题

我必须设计一个象棋棋盘一样的结构，在这里我必须存储1而不是黑色区域，0而不是白色区域，最多可以存储4行和4列。这个程序可以用C或java来解决。我知道这必须是一个简单的答案

有人能帮我吗？ 多谢各位

Answer 1

您可以使用位阵列并将4x4电路板存储在单个整数中

bin    hex
1010    A
0101    5
1010    A
0101    5

=>

int board = 0xA5A5;

您可以设置单元格中的值，该值由两个标记指定：i[0..3]和j[0..3]，其中：

int i = 1;
int j = 2;
board |= (1 << (i*4+j));

或使用以下命令清除单元格中的值：

board &= ~(1 << (i*4+j));

您可以通过以下方式发现单元格中的值：

printf("cell at (%d,%d) has value %d\n", i, j, (board >> (i*4)+j) & 1);

要用所需图案填充空白“结构”

board = 0;
for (i=0; i < 4; i++)
    for (j=0; j < 4; j++)
        if (!((i+j)%2))
            board |= (1 << (i*4+j));

SCCCE：

#include <stdio.h>
int main() {
    int i,j,board;

    for (i=0; i < 4; i++)
        for (j=0; j < 4; j++)
            if ((i+j)%2)
                board &= ~(1 << (i*4+j));
            else
                board |= (1 << (i*4+j));

    for (i=0; i < 4; i++) {
        for (j=0; j < 4; j++) {
            printf("%d ", (board >> (i*4+j)) & 1);
        }
        printf("\n");
    }
    return 0;
}

Answer 2

即使对于任意大小的阵列，该算法也不太困难：

首先，分配一个大小合适的2D数组。在某些语言中，您需要手动分配每一行。Java和C都可以为您做到这一点。Java:int[][] board = new int[w][h]

然后，对于每行、每列，计算单元格应为黑色还是白色：

• 将这两个索引相加，并取mod-2:(x+y)%2值
• 取模-2（奇偶校验）相当于取最低的位：(x+y)&1
• 也许这更容易理解，而且也是这样：x%2 ^ y%2或x&1 ^ y&1，其中^表示按位异或
• 或者，可以先进行异或运算，然后取最低的位：(x^y)%2或(x^y)&1
• 另一方面，平价之和将不起作用，因为这样您将在奇数位置上有2

这两种语言（以及所有其他类似c的语言）都支持经典的for循环：

for(int i = 0; i < size; i++)

i = 0发生在循环之前，是声明迭代变量的最佳位置i < size是在每次迭代之前计算的，如果它是falsy（0在C中，false在Java中），则迭代停止i++在每次迭代后计算

大多数语言将数组大小与数组一起存储。在C/C++中，必须单独存储数组大小，或者使用像^{}或^{}这样的智能数组。您还必须小心不要访问数组外部（Java抛出异常，但C/C++允许您写入随机内存片段-a great way to cause a remote program to misbehave）

C不允许您声明在编译时大小未知的数组。如果您想要这样做，您需要一个指向指针数组的指针（int**-不要忘记取消/分配每一行），或者扁平化数组（int*-内存效率更高，但需要执行board[x + w*y]来访问单元格）

当然，如果大小在编译时是已知的并且足够小，那么您可以使用数组文本并完成它int[][] board = new int[][]{{0,1,0,1}, {1,0,1,0}, {0,1,0,1}, {1,0,1,0}}

---

Java（省略的部分是供读者练习的）：

int[][] board = new int[h][w];
for(int x ...){
  for(int y ...){
    board[y][x] = (x+y)%2;
  }
}

为了进行比较，以下是Ruby：

board = Array.new(h) {|y|
  Array.new(w) {|x|
    (x+y)%2
  }
}
#or (this time inlined)
board = (0...h).map{|x| (0...w).map{|y| (x+y)%2 }}