Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Тамика
Котовчанин
921 / 465 / 196
Регистрация: 16.02.2010
Сообщений: 3,284
Записей в блоге: 28
1

Количество маршрутов

06.02.2014, 11:58. Просмотров 864. Ответов 15
Метки нет (Все метки)

Доброе утро всем!
Есть задачка. На картинке показаны шесть квадратов и возможные маршруты их прохождения. НУжно посчитать количество возможных маршрутов для квадратов 20 на 20... ДУмаю через матрицу делать, то есть помечать пути единичками... Но как-то не могу нормально проработать далее. Помогите, пожалуйста, подсказкой, как можно решить эту задачу!
0
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2014, 11:58
Ответы с готовыми решениями:

Количество маршрутов с препятствиями
Здравствуйте, вот познаю основы динамического программирование и столкнулся с...

Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует
Здравствуйте! Имеем функцию на C++.Помогите исправить ошибки, чтобы выводился...

найти количество различных маршрутов, ведущих к спасению
Узник пытается бежать из замка, который состоит из MN квадратных комнат,...

Посчитать количество замкнутых маршрутов, проходящий ровно через четыре различных города
Задача E. Тетрациклофобия Имя входного файла: phobia.in Имя выходного файла:...

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату
Узник пытается бежать из замка, который состоит из MN квадратных комнат,...

15
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 14:15 2
Цитата Сообщение от Тамика Посмотреть сообщение
Помогите, пожалуйста, подсказкой, как можно решить эту задачу!
помогаю: проведите через узлы сетки диагонали с таким наклоном / и посчитайте поочередно для каждой диагонали (начиная с самой левой) сколькими способами можно добраться до каждого узла на этой диагонали со всех возможных узлов предыдущей диагонали, соблюдая правило обхода "вправо или вниз" (которое вы почему-то не указали в условии задачи). через некоторое время увидите закономерность.
1
mustimur
268 / 222 / 72
Регистрация: 22.11.2013
Сообщений: 837
Записей в блоге: 1
06.02.2014, 15:03 3
Тамика, А тут не квадратичная зависимость? 2х2=6 2х4=36.... Не проверял...
0
Тамика
Котовчанин
921 / 465 / 196
Регистрация: 16.02.2010
Сообщений: 3,284
Записей в блоге: 28
06.02.2014, 16:41  [ТС] 4
Цитата Сообщение от mustimur Посмотреть сообщение
Тамика, А тут не квадратичная зависимость? 2х2=6 2х4=36.... Не проверял...
... А что за квадратичная зависимость?..
0
mustimur
268 / 222 / 72
Регистрация: 22.11.2013
Сообщений: 837
Записей в блоге: 1
06.02.2014, 16:57 5
Цитата Сообщение от Тамика Посмотреть сообщение
... А что за квадратичная зависимость?..
Ну смотрите в квадрате 2х2 всего путей 6, то в прямоугольнике 2х4 сколько? вполне допуская что мин. 36 (ну или все равно есть какая-то регрессия пропорционально площади)
0
Тамика
Котовчанин
921 / 465 / 196
Регистрация: 16.02.2010
Сообщений: 3,284
Записей в блоге: 28
06.02.2014, 17:00  [ТС] 6
Может... Но немного странно. А если, к примеру, мы не знаем, что 6 путей. А просто есть квадрат 2 на 2. Как узнать тогда?
0
mustimur
268 / 222 / 72
Регистрация: 22.11.2013
Сообщений: 837
Записей в блоге: 1
06.02.2014, 17:11 7
Ну это анализ человека, а не машины...
0
Somebody
2801 / 1612 / 251
Регистрация: 03.12.2007
Сообщений: 4,215
Завершенные тесты: 3
06.02.2014, 18:13 8
n(x, y) = n(x - 1, y) + n(x, y - 1)
Ничего не напоминает?

Добавлено через 8 минут
И на всякий случай
Подсказка №2
Из x + y + 1 перемещений всегда x штук горизонтальных и y вертикальных
0
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 18:22 9
Тамика, вы поняли, что за закономерность то?
0
Тамика
Котовчанин
921 / 465 / 196
Регистрация: 16.02.2010
Сообщений: 3,284
Записей в блоге: 28
06.02.2014, 18:31  [ТС] 10
Цитата Сообщение от Somebody Посмотреть сообщение
n(x, y) = n(x - 1, y) + n(x, y - 1)
Ничего не напоминает?
Эм... А о чём должно?..

Добавлено через 1 минуту
Цитата Сообщение от ya_noob Посмотреть сообщение
Тамика, вы поняли, что за закономерность то?
Пока не очень... На работе сижу, потому смотрю когда время свободное...
0
Somebody
2801 / 1612 / 251
Регистрация: 03.12.2007
Сообщений: 4,215
Завершенные тесты: 3
06.02.2014, 18:31 11
Цитата Сообщение от Тамика Посмотреть сообщение
Эм... А о чём должно?..
О треугольнике Паскаля.
0
programina
2052 / 607 / 41
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
06.02.2014, 19:02 12
А вот такие варианты надо считать?
1
Изображения
 
Тамика
Котовчанин
921 / 465 / 196
Регистрация: 16.02.2010
Сообщений: 3,284
Записей в блоге: 28
06.02.2014, 19:03  [ТС] 13
Цитата Сообщение от programina Посмотреть сообщение
А вот такие варианты надо считать?
Не-а. Сглупила и не уточнила, что движение возможно только направо и вниз.
0
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 19:04 14
Цитата Сообщение от Somebody Посмотреть сообщение
О треугольнике Паскаля.
Ну вот, убили всю интригу
0
Xopecc
33 / 28 / 9
Регистрация: 13.09.2013
Сообщений: 250
06.02.2014, 19:34 15
Тамика, Возможно это вам поможет
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
06.02.2014, 19:41 16
Да тут пишется обычное двумерное ДП, и всё.Но или если извращаться, то запускаем DFS и считаем, сколько раз она достигла нужной клетки.
0
06.02.2014, 19:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2014, 19:41

Найти количество всевозможных маршрутов от города до города
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти...

Упорядочить номера маршрутов по возрастанию (структуры)
Помогите пожалуйста как упорядочить номера маршрутов по возрастанию?? ...

Выведение всех возможных маршрутов в неориентированном графе
Помогите пожалуйста составить программу для выведения всех возможных маршрутов...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru