Исходное сообщение
"Нужна помощь при написании программы (псевдокод или C++)" Отправлено LSTemp, 23-Ноя-13 17:51
>[оверквотинг удален] >> "перебрать все" тут не катит .. ИМХО опять же. >> PS >> Есть вес каждой клетки матрицы, есть ограничение связей м/ду клетками (доступные движения >> ежа), задача набрать max. > Ок, посчитаю за вас. Количество комбинаций при n=10 и m=10 будет равно: > C_(n+m-2)_(n-1) = (n+m-2)!/((n-1)!*(n+m-2-n+1)!) = 18!/9!^2 = 48620 вариантов путей. > Что для современных процессоров не так и страшно (для учебной задачи, конечно > же), т.е. за 0.1 секунду на 1GHz проце выполнится даже в > худшем случае. Я не спорю, что в реальной программе брутфорс не > стоит делать. И тут надо понимать, чего от человека ждут. Несколько "но": - количество путей - это не колическтво команд для их поиска - поэтому не надо их вязать на частоту проца и делать выводы об 1-й секунде ) - при увеличении размера исходной матрицы (а такое ожидаемо - ибо по постановке задачи входные данные конфигурируются) количество операций при брут-форсе будет возрастать отнюдь не линейно. => Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать. >[оверквотинг удален] > Вообще это, насколько я понимаю, задача динамического программирования. Гуглится примерно > за 30 секунд, например тут вроде неплохо всё описано: http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&... > . Знаю, что не стоило давать решение, но с другой стороны, > who cares? Если человек хочет чему-то научиться -- он и так > сам попробует сделать или хотя бы по ссылке попробует разобраться что > к чему. Если нет -- то всегда есть куча других путей, > как не утруждать свой мозг :) Правда выгоняют таких до 2-го > курса во всех нормальных ВУЗов. > P.S. Автор, решите задачу самостоятельно, хотя бы самым простым способом. И только > после этого переходите по ссылке.

Ваше сообщение
Имя*:
EMail:	Для отправки новых сообщений в текущей нити на email укажите знак ! перед адресом, например, !user@host.ru (!! - не показывать email). Более тонкая настройка отправки ответов производится в профиле зарегистрированного участника форума.
Заголовок*:
Сообщение*:	>>[оверквотинг удален] >>> "перебрать все" тут не катит .. ИМХО опять же. >>> PS >>> Есть вес каждой клетки матрицы, есть ограничение связей м/ду клетками (доступные движения >>> ежа), задача набрать max. >> Ок, посчитаю за вас. Количество комбинаций при n=10 и m=10 будет равно: >> C_(n+m-2)_(n-1) = (n+m-2)!/((n-1)!*(n+m-2-n+1)!) = 18!/9!^2 = 48620 вариантов путей. >> Что для современных процессоров не так и страшно (для учебной задачи, конечно >> же), т.е. за 0.1 секунду на 1GHz проце выполнится даже в >> худшем случае. Я не спорю, что в реальной программе брутфорс не >> стоит делать. И тут надо понимать, чего от человека ждут. > Несколько "но": > - количество путей - это не колическтво команд для их поиска - > поэтому не надо их вязать на частоту проца и делать выводы > об 1-й секунде ) > - при увеличении размера исходной матрицы (а такое ожидаемо - ибо по > постановке задачи входные данные конфигурируются) количество операций при брут-форсе > будет возрастать отнюдь не линейно. > => > Брут-форс не выход для решения этой задачи (даже на сессии). Именно это > я и хотел сказать. >>[оверквотинг удален] >> Вообще это, насколько я понимаю, задача динамического программирования. Гуглится примерно >> за 30 секунд, например тут вроде неплохо всё описано: http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&chapterid=57 >> . Знаю, что не стоило давать решение, но с другой стороны, >> who cares? Если человек хочет чему-то научиться -- он и так >> сам попробует сделать или хотя бы по ссылке попробует разобраться что >> к чему. Если нет -- то всегда есть куча других путей, >> как не утруждать свой мозг :) Правда выгоняют таких до 2-го >> курса во всех нормальных ВУЗов. >> P.S. Автор, решите задачу самостоятельно, хотя бы самым простым способом. И только >> после этого переходите по ссылке.
	Введите код, изображенный на картинке: