递归问题
我在创建此递归方法时遇到问题。该方法需要将对象添加到堆栈。递归问题
备注: 这是一个路径查找器项目。
getNextBird()
民意调查来自鸟类物体内的鸟类队列。如果队列是空的,它将返回null;如果它不是空的,它会返回队列中的下一只鸟。
我根本无法使用任何循环。 (如果可以的话,本来很容易。) 堆栈中的最后一个元素必须是Bird“end”。但是,如果代码工作正常,它应该递归地完成。
我的问题是,有一个边界情况下,支票撞墙getNextBird
变为null(在这种情况下,对象鸟),我想从堆栈中弹出最新的对象。我将得到一个*错误或一个EmptyCollection错误。
private static boolean recurse(Stack<Bird> path, Bird current, Bird end)
{
Bird bird = null;
if (current != null) {
bird = current.getNextBird();
if (bird != null) {
path.push(current);
recurse(path, bird, end);
return true;
}
}
return false;
}
import java.util.Stack;
public class Solve2
{
public static void main(String [] args)
{
// create the maze to solve
Maze maze = new Maze();
// create a Stack of Bird objects named path here
Stack<Bird> path = new Stack<Bird>();
// call recursive method to solve the maze and print the path
recurse(path, maze.getStart(), maze.getEnd());
print(path);
}
private static boolean recurse(Stack<Bird> path, Bird current, Bird end)
{
Bird bird = null;
if (current != null) {
bird = current.getNextBird();
if (bird != null) {
path.push(current);
recurse(path, bird, end);
return true;
} else {
path.pop();
recurse(path, path.peek(), end);
return false;
}
}
return false;
}
private static void print(Stack<Bird> stack)
{
// write your code for recursively printing the stack here
System.out.println(stack.pop());
print(stack);
}
}
鸟类:
public class Bird
{
public static final int N = 0;
public static final int NE = 1;
public static final int E = 2;
public static final int SE = 3;
public static final int S = 4;
public static final int SW = 5;
public static final int W = 6;
public static final int NW = 7;
private static final String [] directions = {"N ", "NE", "E ", "SE", "S ", "SW", "W ", "NW"};
private String name;
private int direction;
private Queue<Bird> queue;
public Bird(int row, int column, int direction)
{
this.name = "Row/Column [" + row + "][" + column + "]";
this.direction = direction;
}
public void setBirdQueue(Queue<Bird> queue)
{
this.queue = queue;
}
public String toString()
{
return "Location: " + name + ", Direction: " + directions[direction];
}
public int getDirection()
{
return this.direction;
}
public Bird getNextBird()
{
// write code to return the next Bird from the queue or null if no Birds left.
return queue.poll();
}
}
进口java.util.LinkedList中; import java.util.Queue;
public class Maze
{
private Bird start;
private Bird end;
public Maze()
{
// construct the diagrammed maze
int MAX_ROW = 5;
int MAX_COL = 7;
Bird [][] maze = new Bird[MAX_ROW][MAX_COL];
// row 0
maze[0][0] = new Bird(0, 0, Bird.S);
maze[0][1] = new Bird(0, 1, Bird.SW);
maze[0][2] = new Bird(0, 2, Bird.S);
maze[0][3] = new Bird(0, 3, Bird.SE);
maze[0][4] = new Bird(0, 4, Bird.SW);
maze[0][5] = new Bird(0, 5, Bird.SW);
maze[0][6] = new Bird(0, 6, Bird.SW);
// row 1
maze[1][0] = new Bird(1, 0, Bird.S);
maze[1][1] = new Bird(1, 1, Bird.W);
maze[1][2] = new Bird(1, 2, Bird.SW);
maze[1][3] = new Bird(1, 3, Bird.S);
maze[1][4] = new Bird(1, 4, Bird.N);
maze[1][5] = new Bird(1, 5, Bird.S);
maze[1][6] = new Bird(1, 6, Bird.W);
// row 2
maze[2][0] = new Bird(2, 0, Bird.NE);
maze[2][1] = new Bird(2, 1, Bird.NW);
maze[2][2] = new Bird(2, 2, Bird.N);
maze[2][3] = new Bird(2, 3, Bird.W);
maze[2][4] = new Bird(2, 4, Bird.SE);
maze[2][5] = new Bird(2, 5, Bird.NE);
maze[2][6] = new Bird(2, 6, Bird.E);
// row 3
maze[3][0] = new Bird(3, 0, Bird.SE);
maze[3][1] = new Bird(3, 1, Bird.NE);
maze[3][2] = new Bird(3, 2, Bird.E);
maze[3][3] = new Bird(3, 3, Bird.NW);
maze[3][4] = new Bird(3, 4, Bird.NW);
maze[3][5] = new Bird(3, 5, Bird.E);
maze[3][6] = new Bird(3, 6, Bird.W);
// row 4
maze[4][0] = new Bird(4, 0, Bird.N);
maze[4][1] = new Bird(4, 1, Bird.NE);
maze[4][2] = new Bird(4, 2, Bird.N);
maze[4][3] = new Bird(4, 3, Bird.N);
maze[4][4] = new Bird(4, 4, Bird.NE);
maze[4][5] = new Bird(4, 5, Bird.W);
maze[4][6] = new Bird(4, 6, Bird.N);
start = maze[2][0];
end = maze[2][6];
// write your code here
/*snipped the logic for adding the birds in the queue, but I do know that this part is 100% functional on my end*/
}
public Bird getStart()
{
return this.start;
}
public Bird getEnd()
{
return this.end;
}
}
好了,有一件事我看到你已经通过在递归参数end
但从未使用过。
递归的一个关键是有一个控制语句这将导致递归中断和返回正确的事情或什么都没有。您随机返回true和false(或者可能存在逻辑),它不会为您的执行路径添加任何值。
所以,让我们做一个不同的方式:
- ,除非你需要它,让你有当您打印只弹出不要在压栈任何东西。你需要推入的第一只鸟是最后一只鸟匹配表达
(current == end)
。 - 如果这只鸟没有返回前一只鸟的东西,表明路径被阻塞。现在为了与此匹配,在步骤1中,如果
(current == end)
返回了前一只鸟的某个物体,表明找到了最后一只鸟,并将其连同第一只鸟中的每只鸟都传给它。
伪代码:
recursive(stack, current, end)
{
if(current == end){
stack.push(current); //push the final bird
return true; //indication that final is found
}
else if(current.getNext() != null){
result = recurse(stack, current.getNext(), end); //recurse
if(result == true)
stack.push(current); // using indication from the chain
return result;
}
return false;
}
这是真的,你是对的!但我的问题是我如何推进,并弹出堆栈。因为该方法中堆栈不应该变空,所以应该只删除不需要的鸟类物体。 –
是什么让鸟不需要? –
因此,如果鸟类队列中的下一只鸟(它位于每个鸟类物体内部,并且使用getNextBird调用),在没有达到最终鸟类的情况下变为null,则该特定鸟类物体将从堆栈中移除。此外,代码中使用的包装的键盘快捷键是什么? –
什么是禽流数据结构?以及你的输入数据是什么。也许你已经创建了某种循环,并且一次又一次地去同一只鸟?......如果你在中间添加System.out.println(鸟)会很有用。 – Rumoku
您能否提供堆栈跟踪和边界案例? –
@mst它不会一遍又一遍地循环同一只鸟。 –