| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > !Задача! |
| Автор: Olmer 19.12.2003, 19:08 |
| Люди, помогите, пожалуйста решить задачу(на VB или Qbasic`e)!!!!!!!! Вот её условие: В прямоугольной таблице n строк и m столбцов (n и m) не превосходят 10. Подсчитать число возможных маршрутов перехода из левой верхней клетки в правую нижнюю, если разрешены перемещения только вниз и вправо и несколько клеток(но не начальная и не конечная) запрещены для посещения. Пример: Число строк 3 число столбцов 4 Число клеток, запрещенных для посещения 2 Их координаты: 1,4 3,2 Число маршрутов 6 Если кто сможет решить, то, Please, намыльте мне код!([email protected]) |
| Автор: Black_Star 20.12.2003, 02:14 |
| трудновато... Если бы надо было посчитать кратчайший маршрут, помог бы... |
| Автор: kostik_16 20.12.2003, 04:10 |
| Попробуй полным перебором! Каждый раз смещаясь на одну клетку в сторону от предвидужего маршрута, обходя недоступные клетки! Задача на графы! |
| Автор: maxim1000 20.12.2003, 11:17 |
| чтобы посчитать количество путей к заданной клетке, можно использовать следующий алгоритм: пусть f(x,y) - функция, которая вычисляет количество всевозможных путей к клетке (x,y) тогда: 1. f(0,0)=1 2. если клетка запрещена => f(x,y)=0 3. иначе => f(x,y)=f(x-1,y)+f(x,y-1) |
| Автор: cardinal 20.12.2003, 18:21 |
maxim1000, молоток!  Задача не на графы, а на рекурсию, которую так любят преподы. Лично я хотел идти от начальной точки  , но а в остальной идея та же. Сам понимаешь было бы не идеальное решение. У тебя можно кое что подправить, а так классно!1. f(1,1) = 1 2. если (клетка запрещена или x = 0 или y = 0) => f(x,y)=0 3. иначе => f(x,y)=f(x-1,y)+f(x,y-1) Должно работать. |
| Автор: maxim1000 21.12.2003, 12:43 |
| ну, это алгоритм записан рекурсивно, а для его реализации рекурсию можно обойти делаем двумерный массив, соответствующий таблице в каждую клетку записываем количество путей, по которым в нее можно прийти при этом используем информацию об уже обработанных клетках сначала можно будет проанализировать только одну клетку - начальную (будет 1) потом - ту, которая снизу (тоже будет 1) так заполнится первый столбец второй столбец: первая клетка - 1 каждая следующая клетка - верхняя + левая так по одному столбцу можно будет заполнить всю таблицу при заполнении последней клетки мы получим ответ |
| Автор: cardinal 21.12.2003, 16:08 | ||||
Поэтому заморачиваться не стоит и можно оставить рекурсию. Тем более, что не известен размер и
|
| Автор: maxim1000 22.12.2003, 14:02 | ||
просто идея пришла из другой области (распознавание речи с использованием динамического программирования), там была похожая ситуация, а время было критично но в данном конкретном случае полностью согласен |
| Автор: cardinal 22.12.2003, 20:42 |
| Я когда время критично пишу исключительно на ассемблере (ну и без рекурсии соответственно, тем более, что ее можно часто (но не всегда) очень красиво переделать в псевдо-рекурсию). |
| Автор: val 23.12.2003, 10:51 | ||
Да уж, динамическое программирование весьма гибкая штука, где уж его только не применяли... |
| Автор: Fedor 25.12.2003, 00:49 |
| Да.... Эта задача - одна из классических задач динамического программирования. |
| Автор: Bass_ 30.1.2004, 15:51 |
| а как создать генератор карт МТУ ?? |
| Автор: neutrino 18.2.2004, 12:32 |
| Вот на ум что пришло: Можно перемещаться только вверх и вправо? Хех, ну допустим есть поле m на n, то число маршрутов из (0,0) в (m-1, n-1) это ведь биномиальный коэффициент: (m+n - над - m) !!! Такое решение не требует рекурсии. Если есть какие-то места, которые нельзя посещять, то мы должны знать их "площадь" и тем же методом определить сколько разных ходов через них проходят, отнять их количество от общего и получатся все возможные ходы! Вот пример: 0 - ход возможен, 1 - препятствие: 00000000 00000000 00111000 00111000 00000000 сколько возможных ходов? Это поле 8 на 5, значит всего: (8+5 - над - 5) = 1287 площадь препятствия: 3 на 2, через него проходит (3+2 - над - 2) = 10 ходов. Значит всего: 1287-10=1277 !!! |