Question

java递归习题。完全没头绪，求帮忙。

考虑一组list（仅包含非负数），从list的第一个元素开始，目标是到达最后一个元素（最后一个元素永远为0），你可以向走或向右，你走几步取决于你的元素是几。你不能超出这个表格，也就是说你的初始位置在最左端，而且第一步只能向右。只能用递归的方法，这是开头public boolean isSolvable(int index, List<Integer> t),index指的是list中你所在的地方！
不能用sublist。。。。2.不能修改原List，但可以创造一个copy，然后对其修改。

这个是JUnit的测试CODE。
@Test
public void testIsSolvable() {
Integer[] s = {2, 3, 4, 4, 5, 4, 1, 6, 9, 0};
List<Integer> t = new ArrayList<Integer>(Arrays.asList(s));
boolean isSolvable = Lab7.isSolvable(0, t);
assertTrue("board " + t + " is solvable", isSolvable);
assertEquals("board has been modified", Arrays.asList(s), t);

Integer[] u = {1, 3, 9, 8, 3, 0};
t = new ArrayList<Integer>(Arrays.asList(u));
isSolvable = Lab7.isSolvable(0, t);
assertFalse("board " + t + " is not solvable", isSolvable);
assertEquals("board has been modified", Arrays.asList(u), t);
}
分不多，帮我写出代码的在加30分，谢谢！
junit的报错，wjm0506





Answer 1

public boolean isSolvable(int index, List<Integer> t){
boolean flag = false;

int i = t.get(index);

if(i == 0)
return true;
//向左走
if(index > i ){
index = index - i;
flag = this.isSolvable(index, t);
} 

if(!flag){ //向左没通
//向右走
if((index + i) < t.size()){
index = index + i;
flag = this.isSolvable(index, t);
}
}


return flag;
}
已经测试了，要打出路径在找我，目前是能通就返回true

 

反着就是一种可以通的路径。我写的只是让他找一条可行的就OK没有找出所有！

追问

为什么第11行和第18行的this都报错了。。。大神在解决一下,,,

追答

你不会是静态方法吧，贴下图我看看什么错，我这没问题的！贴qq我加你也行

追问

对，是静态的，对不起我给错题了，老师给我们的提示少加了个static，他给我code从public static boolean isSolvable(int index, List t)开始的，那请问这要这么做呢？能不能帮我写完整啦...

追答

this去掉。。。

追问

eclipse可以了，课JUnit通不过。。。

追答

没用JUnit测试我直接跑的数据，报什么错误

有点问题等会！！

{1, 3, 9, 8, 3, 0}这组数据2个3会死循环

追问

那要怎么修改呢？要添加什么code

追答

这方法定死了就传两个参数不好搞，我看看能不能有方法！能加参数么
可不可以在方法外加变量，有没有要求？

追问

发现了一个提示。前面英语超出字数范围+ this means that it will be very useful if you find a way to keep track of all of the visited elements thus far

如果移动到你曾经到达过的地方，那说明没有一个方法能成功。也就是说这对你很有用如果你找到一个方式去记录所有你曾到达的地方

追答

static List<Integer> t2 = new ArrayList<Integer>();
public static boolean isSolvable(int index, List<Integer> t){
boolean flag = false;

int i = t.get(index);

if(i == 0)
return true;
//向左走
if(index > i && !t2.contains(index)){
index = index - i;
t2.add(index);
flag = isSolvable(index, t);
} 

if(!flag){ //向左没通
//向右走
if((index + i) < t.size() && !t2.contains(index)){
index = index + i;
t2.add(index);
flag = isSolvable(index, t);
}
}


return flag;
}

追问

还是报错，不管怎样，谢谢你了，你能在看看是什么原因吗?实在做不出来就算了，分还是给你，谢谢！

追答

static List<Integer> t2 = new ArrayList<Integer>();加上了么我试了啊可以的

不行你把两个static 先去掉试下

Answer 2

boolean flag = true;
int size = t.size()/2;
if (index < size) {
index = t.get(index) + index;
if (index >= t.size()) flag = false;

} else {
index = index - t.get(index);
if (index < 0) flag = false;
}
if (index == (t.size() - 1)) return true;
if (flag) isSolvable(index,t);
return flag;

写了下，没验证，死循环的情况未考虑如何处理。

Answer 3

看看 怎么说的

追问

大神，求解答，还可以在加分啊。。。今晚能做出来么。。。