Stack Overflow，麻烦各位帮忙看看哪里出错了！

Question

private LinkedList<int[]> findStep(int lastStep){
LinkedList<int[]> stepList = new LinkedList<int[]>();
for(int i=0; i<stepNum; i++){
if(!allStep[findIndex(lastStep, i)]){
int step[] = new int[] {lastStep, i};
stepList.add(step);
}
}
return stepList;
}

private boolean takeStep(int lastStep, boolean side){
LinkedList<int[]> stepList = findStep(lastStep);
if(stepList.isEmpty()){
if(side)
return false;
else
return true;
}
else{
boolean result = false;
while(!stepList.isEmpty()){
int[] step = stepList.pop();
makeMove(step[0], step[1]);
result= takeStep(step[1], !side);
if(side){
if(result == true){
unMakeMove(step[0], step[1]);
return result;
}
}
else{
if(result == false){
unMakeMove(step[0], step[1]);
return result;
}
}
unMakeMove(step[0], step[1]);
}
return result;
}
}算法应该没问题，当stepNum比较小的时候运行结果都是对的，但当stepNum比较大的时候就会stack overflow了，达人们有什么建议么？

Answer 1

public class lastStand {
private int stepNum = 5;
private boolean[] allStep; public lastStand() {
} public static void main() {
lastStand anInstance = new lastStand();
anInstance.play();
} private void play() {
boolean result = false;
for (int i = 0; i < stepNum; i++) {
result = takeStep(i, true);
if (result == true)
break;
}
if (result == true)
System.out.println("P1 Win");
else
System.out.println("P2 Win");
} private void makeMove(int a, int b) {
allStep[findIndex(a, b)] = true;
} private void unMakeMove(int a, int b) {
allStep[findIndex(a, b)] = false;
} private int findIndex(int a, int b) {
if (a >= b)
return a * (a + 1) / 2 + b;
else
return b * (b + 1) / 2 + a;
} private LinkedList<int[]> findStep(int lastStep) {
LinkedList<int[]> stepList = new LinkedList<int[]>();
for (int i = 0; i < stepNum; i++) {
if (!allStep[findIndex(lastStep, i)]) {
int step[] = new int[] { lastStep, i };
stepList.add(step);
}
}
return stepList;
} private boolean takeStep(int lastStep, boolean side) {
LinkedList<int[]> stepList = findStep(lastStep);
if (stepList.isEmpty()) {
if (side)
return false;
else
return true;
} else {
boolean result = false;
while (!stepList.isEmpty()) {
int[] step = stepList.pop();
makeMove(step[0], step[1]);
result = takeStep(step[1], !side);
if (side) {
if (result == true) {
unMakeMove(step[0], step[1]);
return result;
}
} else {
if (result == false) {
unMakeMove(step[0], step[1]);
return result;
}
}
unMakeMove(step[0], step[1]);
}
return result;
}
}
}
回楼上，是寻路算法，每个step是从a走到b，a和b都是>=0和<stepNum，每个step必须是从前一个step的后一步开始，第一步是(ab)的话第二步就要从b开始，而且不可以重复也不可以置换，也就是说(ab)和(ba)是一样的，走过(ab)就不能再走(ba)了，找的是给出stepNum最后谁赢。现在的问题是当stepNum很大得时候就stack overflow了，小的时候就没问题，搞不懂啊，麻烦指教一下，谢谢！

Answer 2

boolean[] allStep;
不知道你这个变量是在何处开辟的空间。 private int findIndex(int a, int b) {
        if (a >= b)
            return a * (a + 1) / 2 + b;
        else
            return b * (b + 1) / 2 + a;
    }
这段，使得当你的 stepNum 过大时，传入的 a 参数很大，返回值又是 a 的平方级的。if (!allStep[findIndex(lastStep, i)]) {返回到这一行，可能就使得allStep 栈溢出了。更可能是在 allStep 定义的时候栈溢出的。若在函数体内声明的变量，尤其是数组，是进栈的，数组维度过大，将造成栈溢出。

Answer 3

回楼上，allStep是在play()里面初始空间的，不小心删了。
allStep = new boolean[findIndex(stepNum-1, stepNum-1)+1];
应该不会是在allStep定义的时候溢出，每次溢出都是在这一行
private LinkedList<int[]> findStep(int lastStep) {
        LinkedList<int[]> stepList = new LinkedList<int[]>();

Answer 4

算法复杂度似乎是O(n!)，而且是递归，这可了不得，随着N的增加，方法调用次数急剧增加。这不是你程序的错误，而是算法问题，不改算法不行。

Answer 5

呵呵。明白了。这个JAVA的 LinkedList 好像就是C系语言里面的 stack<>吧……我并不清楚JAVA对对像的维护是怎么样的。
但是C系语言的话，函数内声明的变量是要压栈的。
LinkedList <int[]> stepList = new LinkedList <int[]>(); 
觉得应该不会是这一行的问题。而是其它方面。
函数调用会压栈。
函数内变量声明会压栈。注意你的调用顺序。你在play里面定义这个allStep 开辟空间过大，压栈，然后调用takeStep，注意你传入的i参数是越传越大，
然后你在takeStep里面开了一个LinkedList ，然后你之后又调用findStep，注意你传入的lastStep也是越传越大，
注意你这整个的调用过程，一直在压栈压栈……
最后你再想在栈里面开辟空间stepList ，栈溢出。应该走了这样一个过程，造成了这样的问题。

Answer 6

复杂度没错，不过不是递归，是伪递归，使用循环实现的。所以方法是平行的。只不过，函数变量对栈的消耗太大了。C#在这方面就做得很好。像list这种东西，一律放到HEAP里面……

Answer 7

你为什么要把这个stepNum设很大呢？VC下可以设置函数的栈空间大小，
JAVA下就不知道了。实在不可以的话……我并不了解JAVA的堆栈使用方式。以你对JAVA的了解，想办法把内存的使用的大头放到堆里面，减轻栈的压力。在C#下几乎遇不到类似的问题……因为栈只维护对像的引用，对像的实体全部在堆里面……

Answer 8

我有一个疑问（我首先承认我还没有认真分析这个代码），
如果照你说的参数越传越大，那么这个算法就是发散的，那么在stepNum比较小的时候，为什么可以出结果，而不是也越算越大呢？（我再去研究一下代码，呵呵）。

Answer 9

我的简单理解就是，因为是发散的，所以对资源的消耗不收敛，stepNum小时，栈空间可以容纳，大了越了栈就完了。

Answer 10

^_^，我试了一下，算法复杂度过高了，远超过O(N!),我也不知道具体是多少，总之非常高，
看一下这个数字：
stepNum=4时，takeStep被调用77次。
stepNum=5时，takeStep被调用559次。
stepNum=6时，takeStep被调用169537次。
stepNum=7时，takeStep被调用2761238次。
这段代码是递归，而且递归的过于厉害了。
不过我还没有改进的头绪。楼主能够把需求说的再清楚些吗？

Answer 11

还有一个问题问楼主，我试了3,4,5,6,7，结果都是p1 win，
所以就更不明白你的规则了。8就已经跑不出来了。

Answer 12

takestep里面有while循环的takestep ，该循环的维度与findstep的返回量有关，但是由于findstep 里面的一个for 循环，使得这是一个与 sum(1:n)的正相关的复杂度，那么实际上while下来就应该是  o( (sum(1:n)) ! ) 的复杂度了。改算法吧……

Answer 13

谢楼上各位，看来只能改算法了。因为每次都是p1先走，双方都会用最优势的走法，目标是让对手没有step可以走，所以从0开始的时候p1是有优势的。实际输入的时候有可能已经走了几步，所以输入的时候除了stepNum外还有一个字符串来表示已经走了的step，例如"(0,0)(0,1)(1,2)"，这个已经走了的step是随机并合法的，所以就有了p2 win的可能，我这里只给出了当字符串为空的状况。