|
我必须创建一个程序,以找到用y填充大小为x的正方形的所有可能方式.您放置一个占用2个空格的块,以完全填充.
问题是我不知道如何编码到可以记住每个正方形的位置的程度.我可以将它完全填充到董事会,甚至可能两次填充,但除此之外没有其他内容.我也知道我应该使用递归来解决这个问题.这是到目前为止我开始的代码.还有一种主要方法,我的初始偶/奇检查工作正常.这是我不知道的部分.
public void recurDomino(int row, int column) {
if (Board[2][x - 1] != false) {
} else if(Board[1][x-1]!=false)
{
}
else {
for (int n=0; n < x - 1; n ) {
Board[row][column] = true;
Board[row][column 1] = true;
column ;
counter ;
}
recurDomino(1, 0);
recurDomino(2, 0);
}
}
Thank you for any help you guys can give me.
******************* EDIT ****************************************
我还是有点困惑.我想出了这种算法,但是对于任何大于或等于2的值,我总是得到2.
public boolean tryHorizontal(int row , int col){
if( row < 0 || row >= array[0].length-1)
return false;
else
return true;
}
public boolean tryVertical(int row, int col){
if( col < 0 || col >= 2 )
return false;
else
return true;
}
public boolean tryRowCol(int row, int col){
if(this.tryHorizontal(row, col) && this.tryVertical(row, col)){
return true;
}
else
return false;
}
public int findWays(int row, int col){
int n = 0;
if( !this.tryRowCol(row, col))
return 0;
else
n = 1 this.findWays(row 1, col 1);
return n;
}
解决方法: 该递归解决方案实际上生成了通用MxN板的所有可能的平铺.它比您的程序要求更通用,因此并未进行优化以仅计算3xN板的平铺数量.
如果您只想计算数量,则可以使用dynamic programming techniques并更快地完成.同样,将行数固定为3实际上会使问题变得更加容易.但是,这种一般的生成解决方案应该是有启发性的.
public class Domino {
final int N;
final int M;
final char[][] board;
int count;
static final char EMPTY = 0;
Domino(int M, int N) {
this.M = M;
this.N = N;
board = new char[M][N]; // all EMPTY
this.count = 0;
generate(0, 0);
System.out.println(count);
}
void printBoard() {
String result = "";
for (char[] row : board) {
result = new String(row) "\n";
}
System.out.println(result);
}
void generate(int r, int c) {
//... see next code block
}
public static void main(String[] args) {
new Domino(6, 6);
}
}
这是肉和土豆：
void generate(int r, int c) {
// find next empty spot in column-major order
while (c < N && board[r][c] != EMPTY) {
if ( r == M) {
r = 0;
c ;
}
}
if (c == N) { // we're done!
count ;
printBoard();
return;
}
if (c < N - 1) {
board[r][c] = '<';
board[r][c 1] = '>';
generate(r, c);
board[r][c] = EMPTY;
board[r][c 1] = EMPTY;
}
if (r < M - 1 && board[r 1][c] == EMPTY) {
board[r][c] = 'A';
board[r 1][c] = 'V';
generate(r, c);
board[r][c] = EMPTY;
board[r 1][c] = EMPTY;
}
}
摘录自输出的最后几行,给出了生成板的示例以及最终计数.
//... omitted
AA<><>
VVAA<>
AAVV<>
VVAA<>
<>VVAA
<><>VV
//... omitted
6728
请注意,6728使用OEIS A004003签出.
您需要从此解决方案中学习一些知识：
>自己清理！这是递归解决方案中非常常见的模式,它修改了可变的共享数据.随便做您的事情,但是随便找到您留下的东西,其他人就可以做他们的事情.
>找出探索搜索空间的系统方法.在这种情况下,将多米诺骨牌放置在column-major order中,其左上角为参考点.
因此,希望您可以从中学到一些东西,并根据自己的家庭作业调整技巧.祝好运！
提示：如果您注释掉printBoard行,则可以在合理的时间内生成8×8的所有1300万张板.不过,仅计算数字而不必一一生成并计算它们肯定会快得多.
更新！
这是3xN电路板的递归生成器.它不使用共享的可变数组,而仅使用不可变的字符串.它使逻辑更简单(因为您没有弄乱,所以无需清理！),并使代码更具可读性(可见片段的放置位置和方式！).
因为我们固定在3行,所以如果我们只有3个相互递归的函数,则逻辑更加明确.
public class Domino3xN {
static int count = 0;
public static void main(String[] args) {
addRow1(8, "", "", "");
System.out.println(count);
}
static void addRow1(int N, String row1, String row2, String row3) {
if (row1.length() == N && row2.length() == N && row3.length() == N) {
count ; // found one!
System.out.format("%s%n%s%n%s%n%n", row1, row2, row3);
return;
}
if (row1.length() > row2.length()) { // not my turn!
addRow2(N, row1, row2, row3);
return;
}
if (row1.length() < N - 1)
addRow2(N, row1 "<>",
row2,
row3);
if (row2.length() == row1.length())
addRow3(N, row1 "A",
row2 "V",
row3);
}
static void addRow2(int N, String row1, String row2, String row3) {
if (row2.length() > row3.length()) { // not my turn!
addRow3(N, row1, row2, row3);
return;
}
if (row2.length() < N - 1)
addRow3(N, row1,
row2 "<>",
row3);
if (row3.length() == row2.length())
addRow1(N, row1,
row2 "A",
row3 "V");
}
static void addRow3(int N, String row1, String row2, String row3) {
if (row3.length() == row2.length()) { // not my turn!
addRow1(N, row1, row2, row3);
return;
}
if (row3.length() < N - 1)
addRow1(N, row1,
row2,
row3 "<>");
}
}
您不会经常看到这样的3个相互递归函数,因此这应该是有教育意义的. 来源：https://www./content-1-516351.html
|
