c - 二维数组 C 中的 bool 表

Question

我在创建以下数组时遇到一些困难。我的任务是使用递归来填充 2D 数组，其中 0 和 1 的所有可能组合按词法顺序进行 m 次。从数学上讲，有 2 ^ m 种组合。我的程序只是以相同的顺序 0 1 0 1 填充数组的前 3 行，然后只打印其余行 0 0 0 0。

示例米=4

0   0   0   0
0   0   0   1   
0   0   1   0   
0   0   1   1   
0   1   0   0   
0   1   0   1   
0   1   1   0   
0   1   1   1   
1   0   0   0   
1   0   0   1   
1   0   1   0   
1   0   1   1   
1   1   0   0   
1   1   0   1   
1   1   1   0   
1   1   1   1

这是到目前为止我的代码，如果有人可以纠正它并向我解释我做错了什么，我很感激，因为我自己无法发现错误

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

void *safeMalloc(int n) {
    void *p = malloc(n);
    if (p == NULL) {
        printf("Error: malloc(%d) failed. Out of memory?\n", n);
        exit(EXIT_FAILURE);
    }
    return p;
}


void combine(int** arrTF,int m,int n,int row,int col){
    if(m==0){
        if(row<pow(2,m)){
            row++;
            combine(arrTF,n,n,row,0);
        }else{
            return;
        }
    }else{
        arrTF[row][col]=0;
        col++;
        combine(arrTF,m-1,n,row,col);

        arrTF[row][col]=1;
        col++;
        combine(arrTF,m-1,n,row,col);
    }

}



int main(int argc, char *argv[]) {
    int m
    scanf("%d",&m);


    int** arrTF;

    arrTF = safeMalloc(pow(2,m)*sizeof(int *));
    for (int r=0; r < pow(2,m); r++) {
        arrTF[r] = safeMalloc(m*sizeof(int));
    }


    for(int i=0;i<pow(2,m);i++){
        for(int j=0;j<m;j++){
            arrTF[i][j]=0;
        }
    }

    combine(arrTF,m,m,0,0);

    for(int i=0;i<pow(2,m);i++){
        for(int j=0;j<m;j++){
            printf("%d ",arrTF[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Answer 1

您希望 0's 和 1's 的所有可能的 (2^m) 组合在 m 次中出现词汇顺序，并且您使用二维数组来存储结果。如果您只想打印 0's 和 1's 的所有可能组合，而不是将其存储在二维数组中并稍后打印数组，事情会非常简单。

将 0 和 1 的组合存储到 2D 数组有点棘手，因为每个组合都是 2D 数组的一个元素。您想要根据递归算法生成 0 和 1 的组合。因此，假设在某个阶段，如果您的算法生成组合 0010 ，并将其存储在二维数组的元素中。下一个组合将是 0011，递归算法只需将最后一个组合中的最后一个数字从 0 更改为 1 即可生成该组合(<强>0010)。

因此，这意味着每次生成组合时，您都需要将该组合复制到二维数组中的连续位置。例如如果在算法开始计算下一个组合之前 0010 存储在二维数组的索引 2 处，我们需要做两件事:

1. 将索引 2 的元素复制到索引 3
2. 增加行号，以便最后的组合完好无损

(假设这是二维数组)

|0|0|0|0| 索引 0

|0|0|0|1| 索引 1

|0|0|1|0| 索引 2 ---> 将其复制到其连续位置(即索引 3)

|0|0|1|1| 索引 3 ---> 最后一个组合(索引 2)且最后一位数字从 0 更改为 1

......

......

......

我们需要在生成每个组合后执行此操作。现在，我希望您能明白所犯的错误。

很少有值得遵循的实践:

1. 如果您想要分配内存并使用 0 对其进行初始化，请使用 calloc 而不是 malloc。

2. 对于同一输入一次又一次调用的任何数学函数，最好只调用一次并将结果存储在变量中，并在需要时使用该结果。

3. 不要包含程序中不需要的任何头文件。

4. 完成后，请确保释放程序中动态分配的内存。

我已在您的程序中进行了更正:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void *safeMalloc(size_t n, size_t size) {
    void *p = calloc(n, size);
    if (p == NULL) {
        printf("Error: calloc(%zu) failed. Out of memory!\n", n);
        exit(EXIT_FAILURE);
    }
    return p;
}

void deallocate(int ** ptr, int row) {
    for(int i = 0; i<row; i++)
            free(ptr[i]);
    free(ptr);
}

void combine(int **arrTF, int m, int max_col, int max_row) {
    static int row;
    if(m==0){
        int i;
        if (row<(max_row - 1))
        {
            for(i=0; i<max_col; i++)
                arrTF[row+1][i] = arrTF[row][i];
        }
        row++;
        return;
    } else {
        arrTF[row][max_col-m] = 0;
        combine(arrTF, m-1, max_col, max_row);

        arrTF[row][max_col-m] = 1;
        combine(arrTF, m-1, max_col, max_row);
    }
}

int main(int argc, char *argv[]) {
    int** arrTF;
    int m, max_row;

    printf ("Enter number: \n");
    scanf("%d", &m);

    max_row = pow(2, m);

    arrTF = safeMalloc(max_row, sizeof(int *));
    for (int r=0; r<max_row; r++) {
        arrTF[r] = safeMalloc(m, sizeof(int));
    }

    combine(arrTF, m, m, max_row);

    for(int i=0; i<max_row; i++) {
        for(int j=0; j<m; j++) {
            printf("%d ", arrTF[i][j]);
        }
        printf("\n");
    }
    deallocate(arrTF, max_row);
    return 0;
}

输出:

$ ./a.out
Enter number: 
2
0 0 
0 1 
1 0 
1 1 

$ ./a.out
4
0 0 0 0 
0 0 0 1 
0 0 1 0 
0 0 1 1 
0 1 0 0 
0 1 0 1 
0 1 1 0 
0 1 1 1 
1 0 0 0 
1 0 0 1 
1 0 1 0 
1 0 1 1 
1 1 0 0 
1 1 0 1 
1 1 1 0 
1 1 1 1 

希望这有帮助。