首页 / JAVA / 数组上的Java递归
数组上的Java递归
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数组上的Java递归,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4527字,纯文字阅读大概需要7分钟。
内容图文
![数组上的Java递归](/upload/InfoBanner/zyjiaocheng/688/64e3e946f3814e8b8304e1e592bf0a0e.jpg)
我必须创建一个程序,以找到用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个相互递归函数,因此这应该是有教育意义的.
内容总结
以上是互联网集市为您收集整理的数组上的Java递归全部内容,希望文章能够帮你解决数组上的Java递归所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。