У меня есть хорошее базовое понимание основ C ++, я также понимаю, как работает рекурсия. Я сталкивался с определенными проблемами, такими как классическая проблема восьми королев и решение судоку с возвратом.
Я понимаю, что я совершенно потерян, когда дело доходит до этого, я не могу думать о том, чтобы вернуться в стек рекурсии и начать заново, чтобы решить проблему. Это кажется легким с ручкой и бумагой, но когда дело доходит до написания кода для этого, я не понимаю, как начать атаковать эти проблемы.
Было бы полезно, если бы существовало учебное пособие, предназначенное для начинающих, чтобы вернуться назад, или если бы была хорошая книга, где это было описано. Если кто-то может пролить свет на эту тему или дать мне несколько ссылок на достойные ссылки, я был бы очень благодарен.
И да, я знаю, что это было бы проще в функциональных языках, но я бы хотел понять реализацию и в императивных языках.
Ответы:
При возврате вы не начинаете снова. Вместо этого вы перебираете все варианты в текущей ситуации.
Подумайте о поиске решения для лабиринта. В один момент, когда у вас есть два разных пути, вы сначала пробуете левый. Если левый не ведет вас к выходу, вы возвращаетесь к точке и пробуете другой путь. Вот как работает возврат. В 8 Q и других задачах, где можно использовать возвратный путь, запутанная часть находится в проблемной области - как детально детерминировать ваши варианты в данной ситуации.
РЕДАКТИРОВАТЬ : ниже приведен псевдокод, помогающий разобраться в возврате.
Для вопроса 8Q:
источник
Вы видели программу для бинарного дерева, верно? Это выглядит так:
Вот ваш ответ.
Вам на самом деле не нужно физическое дерево. Все, что вам нужно, это способ сделать ход, а затем отменить его, или сказать, выиграл ли вы, или сказать, если вы не можете пойти дальше.
источник
else{return walk(p->left)||walk(p->right));}
не нужно бросать для ожидаемого результата