 |
|
Модераторы: Daevaorn |
 
|
|
Конечный автомат вместо рекурсии 
| SABROG |
|
|||
 Hacker  Профиль Группа: Завсегдатай Сообщений: 2481 Регистрация: 18.9.2006 Репутация: 4 Всего: 91 |
Вопрос теоретический.
Предположим есть дерево основанное на указателях. По сути динамический список (list, array). Каждый элемент этого списка - указатель или объект содержащий ссылку на другие такие списки. Есть функция, которая должна обходить это дерево (как дерево файлов). Напрашивается естественное решение использовать рекурсию. Но хочется использовать Конечный Автомат для этой задачи, как более правильное и безопасное решение. Проблема в том, что я плохо понимаю как это работает. Можете мне это разжевать? |
|||
|
||||
Дата 1.6.2009, 18:05 (
Загрузка ...
| cardinal |
|
|||
 Инженер Профиль Группа: Экс. модератор Сообщений: 6003 Регистрация: 26.3.2002 Где: Германия Репутация: 2 Всего: 99 |
SABROG, если ты знаешь глубину (по крайней мере максимальное значение) дерева, то можешь использовать конечный автомат. Если не знаешь глубину, то без рекурсии не обойтись.
Рекурсия является точно таким же безопасным решением, если условия выхода из рекурсии правильно. А какое решение правильно это вообще непонятный вопрос. Оба решения правильны, если работают правильно. А то, что ты имеешь в виду это эффективность. Рекурсия зачастую работает медленнее (из-за стэка). -------------------- Немецкая оппозиция потребовала упростить натурализацию иммигрантов В моем блоге: Разные истории из жизни в Германии "Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие |
|||
|
||||
| SABROG |
|
|||
|
Hacker Профиль Группа: Завсегдатай Сообщений: 2481 Регистрация: 18.9.2006 Репутация: 4 Всего: 91 |
Максимальное значение что-то типа типа -1 или 4294967295, по размеру регистра. Этого, по идее, должно хватить. Главное при этом, чтобы от этого значения скорость или время выполнения цикла не зависило.
|
|||
|
||||
| GoldFinch |
|
|||
|
Профиль Группа: Завсегдатай Сообщений: 2141 Регистрация: 30.11.2008 Репутация: 15 Всего: 26 |
SABROG, если ты не знаешь как работает КА , то с чего ты решил что он подходит?
КА будет использовать свой стек в отличие от аппаратного при рекурсии, вот и вся разница. |
|||
|
||||
| mes |
|
|||
|
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
А почему КА не может использовать рекурсивные вызовы ?!  Это сообщение отредактировал(а) mes - 1.6.2009, 20:31 |
|||
|
||||
| SABROG |
|
|||
|
Hacker Профиль Группа: Завсегдатай Сообщений: 2481 Регистрация: 18.9.2006 Репутация: 4 Всего: 91 |
А почему КА не может скакать уровень за уровнем очищая при этом каждый раз результаты от предыдущего уровня?
|
|||
|
||||
| GoldFinch |
|
|||
|
Профиль Группа: Завсегдатай Сообщений: 2141 Регистрация: 30.11.2008 Репутация: 15 Всего: 26 |
mes, смотря какой КА и как он реализован %)
|
|||
|
||||
| mes |
|
||||
|
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
Что Вы подразумеваете под понятием "конечный автомат" ? Добавлено @ 22:03
 в этом то и дело, что рекурсивное перемещение по дереву и выполнение работы КА вполне могут использоваться в комплекте.поэтому чего добивается автор не вполне понятно.  Это сообщение отредактировал(а) mes - 1.6.2009, 22:04 |
||||
|
|||||
| SABROG |
|
|||
|
Hacker Профиль Группа: Завсегдатай Сообщений: 2481 Регистрация: 18.9.2006 Репутация: 4 Всего: 91 |
Цикл while с некоторым условием для выхода, а внутри цикла switch..case где выполняется разный код в зависимости от состояний  |
|||
|
||||
| mes |
|
||||
|
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
интересно а чем тогда по Вашему цикл по while правильней и безопасней рекурсивного цикла ? Это сообщение отредактировал(а) mes - 1.6.2009, 22:13 |
||||
|
|||||
| SABROG |
|
||||||
|
Hacker Профиль Группа: Завсегдатай Сообщений: 2481 Регистрация: 18.9.2006 Репутация: 4 Всего: 91 |
Стек не резиновый, а джампы могут быть бесконечные. |
||||||
|
|||||||
| GoldFinch |
|
|||
|
Профиль Группа: Завсегдатай Сообщений: 2141 Регистрация: 30.11.2008 Репутация: 15 Всего: 26 |
SABROG, у тя либо будет автомат с магазинной памятью - своим стеком
либо вложенные автоматы - та же рекурсия либо конечное число однотипных состояний и конечная глубина дерева |
|||
|
||||
| SABROG |
|
|||
|
Hacker Профиль Группа: Завсегдатай Сообщений: 2481 Регистрация: 18.9.2006 Репутация: 4 Всего: 91 |
А если представить, что есть некое громадное дерево настолько большое, что занимает тысячи серверов, как у гугля. Программа будет являться чем-то вроде клиента и её возможности ограниченны. Как решают подобные задачи? Рекурсия естественно уже не подходит. Это получается деревья надо как-то обрезать до некоторого уровня, обрабатывать кусок, затем обрезать следующий и так далее. |
|||
|
||||
| cardinal |
|
|||
|
Инженер Профиль Группа: Экс. модератор Сообщений: 6003 Регистрация: 26.3.2002 Где: Германия Репутация: 2 Всего: 99 |
SABROG, почитай и подумай над тем, что происходит вообще в рекурсии (во время вызова процедурой саму себя)
http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%...%81%D0%B8%D1%8F и поймешь как "обрезать" ее до некоторого уровня... -------------------- Немецкая оппозиция потребовала упростить натурализацию иммигрантов В моем блоге: Разные истории из жизни в Германии "Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие |
|||
|
||||
| mes |
|
|||
|
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
Но это никакого отношения к конечному автомату не имеет. Поэтому прежде всего необходимо перефразировать ту цель, которой добиваетесь, чтоб искать для нее решение. Иначе Вы и сами запутаетесь и других запутаете. Это сообщение отредактировал(а) mes - 3.6.2009, 09:26 |
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0619 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |