StackOverflowError при запуске моего "Knight's Tour" (в остальном он почти закончен) - PullRequest
1 голос
/ 05 марта 2011

Я пытаюсь создать программу, которая проходит через все квадраты шахматной доски (размер на самом деле не имеет значения, но на данный момент это 6x6) с рыцарем, которая называется "Рыцарский тур" . вики .

Тур должен быть закрыт, что означает, что рыцарь на последней посещенной клетке может «атаковать» клетку, с которой он начал. Код отлично работает для некоторых квадратов, например, ввод 'traverse (1,1,1)' в main генерирует вывод, который показывает, что он не только проходит, но и возвращается к успешному переходу к цели. Однако, если бы я ввел 'traverse (1,0,0)' вместо этого, я получил бы StackOverflowError . Поскольку он иногда бывает успешным, отслеживание и прохождение, я знаю, что код работает, я просто не знаю, как избавиться от ошибок. Я предполагаю, что я делаю слишком много звонков, но я понятия не имею, как обойти это, есть много квадратов для посещения :) Код отредактирован, в основном потому, что учитель мог найти его, скажем, что я обманул.

1 Ответ

4 голосов
/ 05 марта 2011

Вы пытаетесь решить проблему экспоненциальной сложности с помощью рекурсии.Это не будет работать за пределами очень маленьких входов.Размер стека растет намного быстрее, чем размер проблемы.Для прохождения стека не понадобится очень большой размер задачи.

Вы не будете получать ошибки StackOverflowErrors.Вам нужно переосмыслить свой алгоритм на основе цикла, а не рекурсии.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...