Заголовок сообщения: как сделать рекрсивный алгоритм итерационным? Добавлено: 4 Октябрь 2005, 18:05:09
Привет.
Есть алгоритм основанный на рекурсии, он решает задачу схожую с задачей заполнения поля ходом коня, (заполняет матрицу числами от 1 до n, выбирая на каждом шаге координату случайным образом) как реализовать итерационный алгоритм решающий такую задачу, елси нужно помнить переменные всех предыдущих шагов. (без рекурсии). Спасибо.
Любая рекурсия штатно и бездумно раскрывается в итеративный алгоритм явным введением стека. Это уже не преподают в вузах?
_________________ We've got the big memory and the small memory. The small memory's to remember the small things and the big memory's to forget the big ones.
Crazy, эээ... я бы так не торопился, а сначала бы спросил у автора, какая именно задача решается. Может, там и не стеком нужно обходиться.
Для примера - часто попадается задачка такая, чтобы обойти дерево директорий и что-нибудь проделать со всеми файлами, которые найдутся по определенному признаку. Допустим что это PHP. Если делать просто opendir/readdir/closedir, не заботясь о порядке действий внутри функции - то глюков не оберешься. Функцию нужно организовать так, чтобы внутри цикла opendir/readdir/closedir не было ни одного рекурсивного вызова.
Ну то есть бывают ситуации, когда стеком не обойдешься.
А лучше просто рекурсивную функцию записать по-другому.
Crazy, эээ... я бы так не торопился, а сначала бы спросил у автора, какая именно задача решается. Может, там и не стеком нужно обходиться.
Между "нужно" и "можно" есть большая разница.
Цитата:
Ну то есть бывают ситуации, когда стеком не обойдешься.
Круто. А как оно выполняется в рекурсивном варианте? С помощью встроенного в процессор Magic Recursion Evaluator?
Был бы рад взглянуть на пример рекурсивной функции, которая для раскрытия в итеративную требует не только стека, но еще чего-то необычного. Раз уж упоминался PHP, то пусть это будет исходник на PHP.
Цитата:
А лучше просто рекурсивную функцию записать по-другому.
"Лучше" в отсутствие критерия оптимальности лишено смысла.
@TSV, проблема перевода неработающей рекурсивной функции в неработающую итеративную лично для меня не представляет практического интереса.
_________________ We've got the big memory and the small memory. The small memory's to remember the small things and the big memory's to forget the big ones.
Crazy, для меня тоже. Я просто эээ... припомнил случаи из практики, когда отвечал на вопросы по типу того, с которого началась тема. Самое интересное, что во всех случаях вместо переделывания рекурсивного алгоритма в итеративный правильным ответом было просто исправление рекурсивного алгоритма. Чтобы у кода рекурсивной функции корректно выполнялся reentrance. Некорректность может вызываться, например, обращением изнутри цикла в рекурсивной функции сразу и к внешним функциям, которые сохраняют state, и к собственно рекурсивным вызовам. Ну идея понятна.
Бывает ситуации и другого вида.
Когда рекурсивную функцию НУЖНО переводить в итеративную, но НЕЛЬЗЯ это делать с использованием стека ("рекурсия ручками"). Пару примеров вспомнил сходу. Привести?
Привет
Задача - заполнить матрицу буквами из имеющихся слов, для формирования венгерского кроссворда. Сейчас это делает рекурсивная функция: случайным образом выбирается из окружности на текущем шаге смещение (две координаты). Проверяется лежит эта ячейка в обл. матрицы и не заполнена еще, если удовлетв. помечает ее как заполненую, и вызывает себя с параметрами: новые координаты (i, j), и позиция -1. Если возвращается true возвращает true, если false проверяем есть ли свободные ячейки в окружности. Если да, сначала, если нет возвр. false. Пишу на ActionScript, при 5x5 не хватает времени выполнится скрипту и он зависает. Вы мне просто скажите, возможно решить такую задачу с использованием рек. функции вообще и во флеше в частн. (она ведь схожа с задачей о ходе коня...?)
Спасибо.
Когда рекурсивную функцию НУЖНО переводить в итеративную, но НЕЛЬЗЯ это делать с использованием стека ("рекурсия ручками"). Пару примеров вспомнил сходу. Привести?
Ты мои сообщения внимательно читаешь? Я вроде как совершенно недвусмысленно про это и спросил...
mssn, я бы, честно говоря, не стал решать такую задачу в онлайне. Проще базу нагенерить в оффлайне на 10000 штук и вытаскивать случайный. Абсолютно серьезно говорю!
Я бы разделил задачу. Подбором здесь явно ничего не добиться - на АС то стопроцентов... Группируем слова по количеству букв, отрабатываем комбинации из 2-3 слов, которые складываются в прямоугольники. Потом из них собираем квадрат 5 на 5. Это первое, что пришло голову. Поройся в сетке, может есть готовые алгоритмы.
Давно уже хотел это сюда закинуть, и наконец, решился. Был у меня в свое время курсовой, там надо было составлять сабжи. Сделал в лоб, но стало интересно, как подобные задачи решаются по уму. Что скажет общественность ?
Решение в лоб - это перебор в глубину с некоторой оптимизацией (отсечением заведомо неправильных вариантов: одинокая клетка, две одиноких клетки, etc).
ps. Венгерский кроссворд - это матрица MxN, заполненная буквами, образующими слова. Слово записывается начиная с некоторой клетки в произвольном направлении, по ходу дела направление может меняться. Двигаться по диагонали нельзя. Слова не пересекаются, т.е. одна клетка принадлежит только одному слову. Кроссворд считается составленным если все клетки заполнены, хотя иногда допускается не более K свободных клеток. Слов длиной <=4 не бывает. Кроме того, длины слов могут быть ограничены (Lmin,Lmax).
hint: Т.к. слова не пересекаются, можно обойтись генерацией только нумерованных цепочек, в которые уже на следующем этапе вписываются слова.
Уровень доступа: Вы не можете начинать темы. Вы не можете отвечать на сообщения. Вы не можете редактировать свои сообщения. Вы не можете удалять свои сообщения. Вы не можете добавлять вложения.
Новости дизайна |
Галереи |
О проекте |
RSS
Правила |
FAQ |
Поиск |
Наша команда |
Регистрация |
Вход
