Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.10.2009, 16:13   #1
Airo
 
Регистрация: 12.10.2009
Сообщений: 4
По умолчанию Подскажите в какую сторону думать )

Вот незнаю в каком направлении мне думать Коды писать не обязательно, просто подскажите пожалуйста способ(сам алгоритм) или на что обратить внимание.. Вот условие:

Задана матрица натуральных чисел A(n, m), где n – количество строк, m – количество столбцов. За каждый проход через клетку (i, j) взимается штраф A(i, j). Необходимо минимизировать штраф и пройти из какой-либо клетки первой строки (приложение должно выбрать оптимальную стартовую ячейку) в любую клетку последней n-ой строки. При этом из текущей клетки можно перейти в любую из 3-х соседних ячеек в пределах матрицы, стоящих в стpоке с номеpом на 1-цу большем (можно двигаться вниз, вниз по диагонали влево, вниз по диагонали вправо).

(с ниже описанным я сам справлюсь, просто дал для примера)

Ввод из файла “input.txt”. В первой строке через пробел содержатся значения n и m (размеры матрицы), в последующих строках – сама матрица штрафов. Вывод в файл “output.txt”. В первой строке выходного файла содержится суммарный штраф по пути следования, во второй – последовательность набранных штрафов.
Примеры входных данных
input.txt
4 5
3 2 8 6 4
4 7 12 9 1
55 8 3 2 8
20 7 4 9 1

Соответствующие выходные данные
output.txt
8
4 1 2 1
Airo вне форума Ответить с цитированием
Старый 12.10.2009, 16:26   #2
ds.Dante
Старожил
 
Аватар для ds.Dante
 
Регистрация: 06.08.2009
Сообщений: 2,992
По умолчанию

Нужна рекурсия.

Должна быть глобальная переменная с минимальным штрафом. Рекурсивная функция принимает на входе текущую координату и запускает себя 3 раза. Если координата - последняя, то сравниваем получившийся штраф с минимальным.
ds.Dante вне форума Ответить с цитированием
Старый 12.10.2009, 17:07   #3
Airo
 
Регистрация: 12.10.2009
Сообщений: 4
По умолчанию

Вот!.. ) Спасибо огромное за четкий ответ.. Жаль что я сам не додумался(( Еще раз спасибо!
Airo вне форума Ответить с цитированием
Старый 12.10.2009, 18:53   #4
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Рекурсия - зло. Запомните это.
В данной задаче нужно использовать ДП за О(n*m) (на матрице значений). Потом просто выбираем минимальное из значений в искомой строке матрицы за O(n).
По поводу вывода пути - самым оптималыным мне кажется массив указателей, но здесь есть разные мнения.
LeBron вне форума Ответить с цитированием
Старый 13.10.2009, 01:20   #5
Airo
 
Регистрация: 12.10.2009
Сообщений: 4
По умолчанию

LeBron, то что рекурсия зло я знаю. Но нахожу в ней самый оптимальный вариант для этой задачи.. Ибо твой путь решения я не совсем понимаю, не так я опытен в этом. Если не сложно, можешь объяснить? Мне было бы интересно знать еще один путь решения данной задачи. (хотяб поверхностно)
Airo вне форума Ответить с цитированием
Старый 13.10.2009, 08:51   #6
ds.Dante
Старожил
 
Аватар для ds.Dante
 
Регистрация: 06.08.2009
Сообщений: 2,992
По умолчанию

Цитата:
Сообщение от LeBron Посмотреть сообщение
Рекурсия - зло. Запомните это.
Можно поподробнее, почему?
ds.Dante вне форума Ответить с цитированием
Старый 13.10.2009, 17:10   #7
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Объясняю. При небольших ограничениях рекурсия, возможно, самый оптимальный варант для тех, кто ее любит и умеей быстро и качественно ею пользоватся. А для более-менее приличных ограничений - не прокатит. Мое решение (оптимальное) работает в пределах секунды и для ограничений 1000*1000. А рекурсия красиво и громко упадет. Первое - это само количество операций. Если говорить об неоптимизированной и простой для понимания функции, то вообще завал - каждая не крайняя ячейка (я так для себя клетку массива назвал, в рекурсии это как-то лучше звучит) первой строки порождает 3 функции, каждая из этих 3 порождает еще 3 во второй ячейке, и так далее. Понятно, что работать это будет дольше по времени, так как уже во втором ряду на обработку некрайних ячеек идет больше операций, чем при линейно организированном решении. Вообще, в ряду с большим номером на любую ячейку уйдет минимум 6 запросов - так как она будет вызвана из 2 клеток, верхней и верхней боковой (если не крайняя - таких боковых будет 2), а если еще и учесь, сколько раз эти клетки будут вызваны... Рост ведь ограничевается ниже экспоненицального только краями массива.
Второе - память. Мне жалко тот стек, который будет убит такой рекурсией.
Ее, конечно, можно оптимизировать. Подозреваю даже, что если оптимизировать в полупрерывный бэктрекинг, то будет укладыватся в оптимальные ограничения. Только вот это уже не будет чистая "голая" рекурсия, и сама задача построения такого алгоритма на порядок сложнее.
LeBron вне форума Ответить с цитированием
Старый 13.10.2009, 17:22   #8
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Теперь объясняю динамическое решение. Заводим еще 1 массив. Можно и на этом все делать, не юзая лишнюю память, но для начале лучше тренироватся делать такие стандартные задачи на динамику стандартным методом с заведением отдельного массива. Каждому элементу в массиве на входе будет отвечать в нашем новом массиве значение минимальной суммы, которую можно набрать, пройдя через эту клетку. Теперь начинаем заполнение. Понятно, что минимальные штрафы для клеток первой строки - это само значение этой ячейки массива. Для второй и последующих строк каждой ячейке присваиваем сумму ее значения в начальном массиве и минимального из значений тех ячеек массива сум, из которых можно перейти в эту ячейку. Потом просто в последней строке выбираем минимальное значение. Извлечение пути - с помощью массива указателей пути.
Пример:
3 2 8 6 4
6 9 14 13 5
61 17 12 7 13 - так, если не ошибаюсь (считал "на глаз") будут выглядеть 3 первые строки массива сум для инпута из примера.
LeBron вне форума Ответить с цитированием
Старый 13.10.2009, 18:50   #9
ds.Dante
Старожил
 
Аватар для ds.Dante
 
Регистрация: 06.08.2009
Сообщений: 2,992
По умолчанию

LeBron, такой вариант, вероятно, оптимальнее, но и значительно сложнее. После небольшой практики в 9-м классе я больше никогда не путался в рекурсии. А на счет стека - верно замечено.


:)
ds.Dante вне форума Ответить с цитированием
Старый 13.10.2009, 19:13   #10
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Эх... сложнее - это когда читаеш разбор задачи и не понимаеш в нем половины символов. Здесь десяток строк кода... И если человек собирается в будущем заниматся программированием дальше, то ему надо уметь решать такие базовые задачи, которые чаще выступают как подзадачи при решении натоящих задач, правильно. А рекурсия сдесь займет минимум 50-70 строк, так что не вопрос, что проще. Ну разве что, опять таки, говорить в очередной раз о "пародии на решение" - полном рекурсивом переборе, который загибается даже быстрее, чем кажется. Проверил програмно - уже при массиве 20*20 (ни об учебных 100*100, ни об соревновательных 1000*1000 речь не идет) на центральные элементы последней строки будет по 1155067303 запросов.
LeBron вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Подскажите чайнику(мне) какую прогу написать? BETONOMESHALKA Свободное общение 23 26.10.2011 12:27
Остановился в развитии, направьте в какую сторону идти дальше! iukash Свободное общение 43 02.09.2009 19:16
Подскажите, какую программу выбрать... Лена Брусникина Помощь студентам 0 19.06.2009 21:10
Подскажите пожалуйста какую функцию необходимо использовать... Андрю)(@ Паскаль, Turbo Pascal, PascalABC.NET 1 10.12.2008 00:03
Подскажите пожалуйста какую функцию необходимо использовать... Андрю)(@ Помощь студентам 1 09.12.2008 23:53