Программа возврата Java для N queen: ошибка StackOverFlow
В настоящее время я прохожу онлайн-курс, который учит различным головоломкам программирования. Головоломкой этой недели была задача N-Queen, а представленный код был написан на Python. Это следующее:
питон
def can_be_extended_to_solution(perm):
i = len(perm) - 1
for j in range(i):
if i - j == abs(perm[i] - perm[j]):
return False
return True
def extend(perm, n):
if len(perm) == n:
print(perm)
exit()
for k in range(n):
if k not in perm:
perm.append(k)
if can_be_extended_to_solution(perm):
extend(perm, n)
perm.pop()
extend(perm = [], n = 25)
Поскольку я очень новичок в программировании и единственный язык, который я немного знаю, это Java, я переписал весь код на Java, чтобы попрактиковаться. Однако переписанный код вызывал ошибку StackOverFlow при выполнении. Это следующее:
Джава
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Please insert N in a N x N chessboard");
int n = scanner.nextInt();
ArrayList<Integer> perm = new ArrayList<>();
extend(perm, n);
scanner.close();
}
public static boolean can_be_extended_to_solution(ArrayList<Integer> perm) {
int i = perm.size() - 1;
int[] range = new int[i];
for (int k = 0; k < range.length; k++) {
range[k] = k;
}
for (int j : range) {
if (i - j == Math.abs(perm.get(i) - perm.get(j))) {
return false;
}
}
return true;
}
public static void extend(ArrayList<Integer> perm, int n) {
if (perm.size() == n) {
for(int i = 0; i < perm.size(); i++) {
System.out.println(perm.get(i));
return;
}
}
int[] range = new int[n];
for (int i = 0; i < range.length; i++) {
range[i] = i;
}
for (int k : range) {
if (perm.contains(k)) {
}
else {
perm.add(k);
}
if (can_be_extended_to_solution(perm)) {
extend(perm, n);
}
perm.remove(perm.size() - 1);
}
}
}
И это сообщение об ошибке в консоли Eclipse:
Please insert N in a N x N chessboard
7
Exception in thread "main" java.lang.StackOverflowError
at java.lang.Integer.equals(Unknown Source)
at java.util.ArrayList.indexOf(Unknown Source)
at java.util.ArrayList.contains(Unknown Source)
at test.extend(test.java:51) // if (perm.contains(k)) {
at test.extend(test.java:57) // extend(perm, n);
at test.extend(test.java:57)
at test.extend(test.java:57)
at test.extend(test.java:57)
at test.extend(test.java:57)
at test.extend(test.java:57)
Эти два кода кажутся мне похожими, и я не понимаю, почему мой код Java вызывает ошибку StackOverFlow, в то время как код Python вообще не сталкивается с проблемой.
Может ли кто-нибудь сказать мне, что не так в моем коде?
Спасибо за добрый комментарий, @Bhavin. Я заменил оператор return на System.exit(0), как вы предложили, но он все равно выдает ошибку SO. Я добавил печатное сообщение об ошибке в исходный вопрос, и я был бы очень признателен, если бы вы взглянули на него.
Обратитесь за помощью к этому прекрасному блогу отлаживать. Вы говорите, что «два кода кажутся мне похожими» — на чем вы это основываете? Где ваша попытка отследить выполнение сбойного кода, если не то и другое? Мы ожидаем, что вы добросовестно попытаетесь отладить свою проблему перед публикацией; поделитесь этой попыткой.
Ответы 1
Я почти уверен, что ошибка в обеих формах кода. Измените Python на это:
def can_be_extended_to_solution(perm):
i = len(perm) - 1
for j in range(i):
if i - j == abs(perm[i] - perm[j]):
return False
return True
def extend(perm, n):
if len(perm) == n:
print(perm)
exit()
for k in range(n):
if k not in perm:
perm.append(k)
if can_be_extended_to_solution(perm):
extend(perm, n)
perm.pop()
extend(perm = [], n = 25)
Что было не так, так это то, что вы видели, что некоторые k могут быть добавлены, затем звонили extend. Вы возвращались, пытались добавить k, обнаруживали, что perm все еще можно расширить, и снова вызывали `extend . Что произойдет в цикле, и тогда вы получите бесконечную рекурсию.
В новой версии вы выполняете рекурсию только тогда, когда добавляете что-то в perm.
Привет Юнён, добро пожаловать в SO. Одно отличие, которое я вижу, заключается в том, что в python при поиске решения вы выходите из всего кода (exit()), тогда как в Java вы просто возвращаетесь. Попробуйте заменить вернуть на Система.выход(0) в начале функции расширения внутри условия if. Причина, по которой вы получаете ошибку SO, заключается в том, что в случае возврата из функции вы все еще находитесь внутри цикла предыдущей функции (на один уровень выше), которая все еще будет продолжать выполнять итерацию и выполнять другие вызовы функций.