[an error occurred while processing this directive]
С рекурсией еще проще: Для каждой вершины вызываешь функцию заливки из данной.
(«Телесистемы»: Конференция «Микроконтроллеры и их применение»)
Отправлено
Дятковский Степан
22 апреля 2006 г. 19:18
В ответ на:
много памяти, хотелось бы с рекурсией, красиво...
отправлено -=DASM=- 22 апреля 2006 г. 19:03
Составить ответ
|||
Конференция
|||
Архив
Ответы
Да со стеком ты прав. То сообщение не до конца отправилось. Вот рекурсивный алгоритм:
—
Дятковский Степан
(22.04.2006 19:28
81.28.163.175
, 807 байт)
а это уже целая программа, а не простенькая функция
—
-=DASM=-
(22.04.2006 19:33
212.58.192.14
,
пустое
)
Ну, блин ) Поиск пути это не очень-то простое занятие. А вообще, то фунцию на С можно уложить в 40-50 строк + структуры вспомогательные еще строк 20. Просто глаза стращают, наверное ;-)
—
Дятковский Степан
(22.04.2006 19:37
81.28.163.175
,
пустое
)
что-то у меня тут не сколько рекурсия напрашивается (представляем бинарное дерево) сколько распаллеливание процессоров :-( То есть рекурсия идет вверх однобоко, а надо бы к кроне двигать горизонатльно, чтобы быстрее найти верный путь
—
-=DASM=-
(22.04.2006 19:50
212.58.192.14
,
пустое
)
я имел в виду - на какой платформе? МК? ПК? или что ?
—
Дятковский Степан
(22.04.2006 20:45
81.28.174.237
,
пустое
)
и МК и ПК.. какая разница... ну стека больше 30 кил все равно не хочу
—
-=DASM=-
(22.04.2006 20:57
212.58.192.14
,
пустое
)
Кроме волнового алгоритма поиска маршрута по графу больше ниче не могу предложеть. Если получится как-то по-другому, поделишься?
—
Дятковский Степан
(22.04.2006 21:14
81.28.187.169
,
пустое
)
по всем прикидкам мне подходит просто перебор вариантов =(
—
-=DASM=-
(23.04.2006 08:41
212.58.192.14
,
пустое
)
Построить цепь при помощи перебора? А как будешь перебирать? Там же граф..
—
Дятковский Степан
(23.04.2006 11:06
81.28.185.180
,
пустое
)
так а чего ? (+)
—
-=DASM=-
(23.04.2006 11:59
212.58.192.14
, 184 байт)
Для той задачи по-моему красивее некуда :-) 0 - это идти в одну сторону 1 - в другую. Так я понял ? Только надо знать максимально возможную длину маршрута. Но вообще красиво. Чего не нравится-то ?
—
Дятковский Степан
(23.04.2006 15:56
81.28.162.97
,
пустое
)
тепрь все нравится =)
—
-=DASM=-
(23.04.2006 16:47
212.58.192.14
,
пустое
)
Ну рекурсия - это просто поиск в глубину - отсюда кажущаяся однобокость. На самом деле она и "в стороны" ищет. Только к новой стороне она переходит только после того, как решит все со старой. Здесь это на самом деле немного стремно. На мой взгляд фронты очен неплохи. И распаралеливание на лицо. А на чем должен быть реализован поиск ?
—
Дятковский Степан
(22.04.2006 20:43
81.28.174.237
,
пустое
)
тут у меня ситуация осложняется что некоторые ветви тупиковые... да и цепь замкнута..
—
-=DASM=-
(22.04.2006 20:58
212.58.192.14
,
пустое
)
Если ветви тупиковые заливка из заданной вершины не будет происходить. Если цепь замкнута, то когда повторно вершина тоже не будет залита, по скольку условие оптимальности для такой заливки не будет выполняться - то есть в цикл алгоритм тоже не впадет.
—
Дятковский Степан
(23.04.2006 16:20
81.28.162.97
,
пустое
)
Все зависит от средней длины маршрута. Если маршрут не большой - то лучше рекурсию. Если происходит переполнение стека - можно делать с помощью фронтов. Максимальный размер фронта в случае приведенного графа будет 10-20 вершин.
—
Дятковский Степан
(22.04.2006 19:31
81.28.163.175
,
пустое
)
да понятно что все просто.. но не выходит каменный цыеток.. то тут грабли, то тут stack overflow, то находит только путь по одной стороне.... а функция явно строк 20 не более должна быть
—
-=DASM=-
(22.04.2006 19:21
212.58.192.14
,
пустое
)
Отправка ответа
Имя (обязательно):
Пароль:
E-mail:
NoIX ключ
:
Запомнить
Тема (обязательно):
Сообщение:
Ссылка на URL:
Название ссылки:
URL изображения:
Перейти к списку ответов
|||
Конференция
|||
Архив
|||
Главная страница
|||
Содержание
E-mail:
info@telesys.ru