好的,基本上我的问题是,我有一个矩阵
010
101
111
只是随机的1和0 . 所以我有 rowcount
和 colcount
的数组,它们计算每行和每列中的数量 . 所以 rowcount
这是 {1,2,3}
而 colcount
是 {2,2,2}
. 现在在另一种方法中,我得到了数组 rowcount
和 colcount
,并且在该方法中,我应该创建一个具有 rowcount
和 colcount
中的计数的矩阵,但是结束矩阵可以是不同的 . 比原来的 . 我想我应该用尽所有的排列,直到矩阵工作 . 基本情况必须保持不变 .
注意:不能使用Math.random .
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;
}
public static void count(int[][] matrix, int[] rowcount, int[] colcount)
{
for(int x=0;x<matrix.length;x++)
for(int y=0;y<matrix[0].length;y++)
{
if(matrix[x][y]==1)
{
rowcount[x]++;
colcount[y]++;
}
}
}
2 回答
好的,您的问题和评论表明您走在正确的轨道上 . 代码本身有点乱,它显然经历了一些迭代 . 那不是很好,但没关系 .
我相信你是对的,你必须'exhaust'递归,直到你找到一个与现有列/行计数相匹配的新结果 . 所以,从逻辑上解决问题 . 首先,创建一个可以将矩阵与行/列计数进行比较的方法 . 你称之为'compare(...)' . 我假设你已经有了这种方法;-) . 这是标记递归结束的方法 . 当compare返回true时,您应该返回递归'stack' . 你不应该做
System.exit(...)
.因此,递归的基本规则,你需要一个输入,输出,一个包含退出条件检查的方法体,如果不满足条件,则需要一个递归调用....
您的问题有一个特定的问题,使事情复杂化 - 如果每次递归递归级别时输入矩阵都需要复制 . 或者,您需要“撤消”当您达到某个级别时所做的任何更改 . '撤消'方法更快(内存副本更少) .
因此,过程如下,以全零矩阵开始 . 为全零起点调用递归函数 .
这是它的调用方式,如果找到解决方案,
found
将成立 .与您的代码的区别在于
recur
现在返回boolean
.所以,我们的
recur
方法需要做:1 . 检查当前矩阵 - 如果匹配则返回true . 2.进行有意义的更改(在我们添加的限制内)3 . 递归检查更改(并添加其他更改) .您的方法没有输出,因此无法逃避递归 . 所以,添加一个(在这种情况下为布尔值) .
这可以工作的方式是我们从左上角开始,并尝试使用该位设置,并取消设置 . 对于每个部分(设置或未设置),我们递归测试下一位是否匹配设置或未设置,依此类推....:
上面的代码只是手写,它可能有bug等,但尝试一下 . 这里的教训是你需要测试你的志气,你需要一个策略....
好吧,我决定实现一个解决方案,但是不是Java(你实际上没有指定解决方案需要进入),我将使用Groovy(无论如何都是基于Java的)!我试图在可能的情况下使用Java语法,从这里推断Java代码并不难(但它更冗长!)
Note:
*生成随机位矩阵,不使用Math.random()
*我将我的矩阵存储在一个字符串中,即[[0,1],[1,0]] =“0110”
*我的解决方案非常依赖于将整数转换为/从BinaryStrings转换(这基本上就是你的矩阵!)
给出输出:
蛮力搜索逻辑: