0

这个程序的第一部分是随机生成一个维度在 2 到 6 之间的矩阵。然后我必须随机用 1 和 0 填充这个矩阵。使用这个矩阵，我制作了 2 个一维数组，其中包含每行和每列中 1 的数量。表示行号的矩阵的索引，以及表示计数的单元格中的数字。我制作了 2 个这样的数组：一个用于行数，一个用于列数。这是我的代码。

    public static void count(int[][] matrix, int[] rowcount, int[] colcount)
  {
     for(int x = 0; x < rowcount.length; x++)
        for(int y = 0; y < colcount.length; y++)
        {
           if (matrix[x][y] == 1)
           {
              rowcount[x] = rowcount[x] + 1;
              colcount[y] = colcount[y] + 1;
           }
        }
  }

现在我面临的问题是使用这些计数重新创建这个矩阵。通过重新创建，我的意思是只创建另一个满足一维数组计数的矩阵，没有必要生成这些计数源自的确切矩阵。 到目前为止，这是我的代码，我已经为这个程序工作了 2 天，但我找不到为所有情况生成矩阵的算法。

以下是方法

    public static void re_create(int[] rowcount, int[] colcount)
  {
     int[][] recreated = new int[rowcount.length][colcount.length];
     recur(recreated, rowcount, colcount, 0, 0);
  }
  private static void recur(int[][] m, int[] rowcount, int[] colcount, int r, int c) //recursive helper method
  {
     if(compare(m, rowcount, colcount))    //base case: if new matrix works
     {
        System.out.println();
        System.out.println("RECREATED");
        display(m, rowcount, colcount);    //we're done!
        System.exit(0);
     }
     else
     { 
        int[] temp_r = new int[m.length];
        int[] temp_c = new int[m[0].length];
        count(m, temp_r, temp_c);
        if(rowcount[r] > temp_r[r] && colcount[c] > temp_c[c])
           m[r][c] = 1;
        if(r+1 < m.length)
           recur(m,rowcount,colcount,r+1,c);
        if(rowcount[r] < temp_r[r] || colcount[c] < temp_c[c])
           m[r][c] = 0;
        if(c+1 < m[0].length)
           recur(m,rowcount,colcount,r,c+1);     
     }
  }
  private static boolean compare(int[][] m, int[] rowcount, int[] colcount)
  {
     int[] temp_r = new int[m.length];
     int[] temp_c = new int[m[0].length];
     count(m, temp_r, temp_c);

     for (int x = 0; x < temp_r.length; x++)
     {
        if(temp_r[x] != rowcount[x])
           return false;
     }

     for (int y = 0; y < temp_c.length; y++)
     {
        if(temp_c[y] != colcount[y])
           return false;
     }

     return true; 
  }

该程序来自学校，所以我已经给出了递归方法的方法头和基本情况，所以它们必须保持不变。其他的都是我写的。我只是找不到一个好的算法来生成这些矩阵。我认为我应该在矩阵中生成 1 和 0 的每一个排列，直到一个与基本情况匹配，但我不明白考虑到 recur 方法中的参数，这将如何工作。

4

2 回答 2

0

这是我想出的解决方案。对我来说似乎是正确的，但我没有提供很多测试数据。

public static void re_create(int[] rowcount, int[] colcount) {
    int[][] recreated = new int[rowcount.length][colcount.length];
    for (int y = 0; y < rowcount.length; y++) {
        for (int x = 0; x < colcount.length; x++) {
            if (rowcount[y] > 0 && colcount[x] > 0) {
                recreated[x][y] = 1;
                rowcount[y]--;
                colcount[x]--;
            } else {
                recreated[x][y] = 0;
            }
        }
        if (rowcount[y] != 0) {
            throw new IllegalArgumentException("Impossible! y = " + y);
        }
    }
    for (int x = 0; x < colcount.length; x++) {
        if (colcount[x] != 0) {
            throw new IllegalArgumentException("Impossible! x = " + x);
        }
    }
    System.out.println(Arrays.deepToString(recreated));
}
于 2013-06-26T15:51:03.167 回答
0

没有适用于所有情况的解决方案。考虑：

0 1 0 0 | 1    0 0 1 0 | 1
1 0 1 0 | 2    0 1 0 1 | 2
0 1 0 1 | 2    1 0 1 0 | 2
0 0 1 0 | 1    0 1 0 0 | 1
-------        -------
1 2 2 1        1 2 2 1
于 2013-06-26T15:10:05.820 回答