Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
06.02.2014, 11:58     Количество маршрутов #1
Доброе утро всем!
Есть задачка. На картинке показаны шесть квадратов и возможные маршруты их прохождения. НУжно посчитать количество возможных маршрутов для квадратов 20 на 20... ДУмаю через матрицу делать, то есть помечать пути единичками... Но как-то не могу нормально проработать далее. Помогите, пожалуйста, подсказкой, как можно решить эту задачу!
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2014, 11:58     Количество маршрутов
Посмотрите здесь:

найти количество различных маршрутов, ведущих к спасению C++
C++ Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату
Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует C++
C++ Количество маршрутов с препятствиями
C++ Определить количество выигрышей, количество проигрышей и количество ничьих данной команды
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 14:15     Количество маршрутов #2
Цитата Сообщение от Тамика Посмотреть сообщение
Помогите, пожалуйста, подсказкой, как можно решить эту задачу!
помогаю: проведите через узлы сетки диагонали с таким наклоном / и посчитайте поочередно для каждой диагонали (начиная с самой левой) сколькими способами можно добраться до каждого узла на этой диагонали со всех возможных узлов предыдущей диагонали, соблюдая правило обхода "вправо или вниз" (которое вы почему-то не указали в условии задачи). через некоторое время увидите закономерность.
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
06.02.2014, 15:03     Количество маршрутов #3
Тамика, А тут не квадратичная зависимость? 2х2=6 2х4=36.... Не проверял...
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
06.02.2014, 16:41  [ТС]     Количество маршрутов #4
Цитата Сообщение от mustimur Посмотреть сообщение
Тамика, А тут не квадратичная зависимость? 2х2=6 2х4=36.... Не проверял...
... А что за квадратичная зависимость?..
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
06.02.2014, 16:57     Количество маршрутов #5
Цитата Сообщение от Тамика Посмотреть сообщение
... А что за квадратичная зависимость?..
Ну смотрите в квадрате 2х2 всего путей 6, то в прямоугольнике 2х4 сколько? вполне допуская что мин. 36 (ну или все равно есть какая-то регрессия пропорционально площади)
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
06.02.2014, 17:00  [ТС]     Количество маршрутов #6
Может... Но немного странно. А если, к примеру, мы не знаем, что 6 путей. А просто есть квадрат 2 на 2. Как узнать тогда?
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
06.02.2014, 17:11     Количество маршрутов #7
Ну это анализ человека, а не машины...
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
06.02.2014, 18:13     Количество маршрутов #8
n(x, y) = n(x - 1, y) + n(x, y - 1)
Ничего не напоминает?

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

Добавлено через 1 минуту
Цитата Сообщение от ya_noob Посмотреть сообщение
Тамика, вы поняли, что за закономерность то?
Пока не очень... На работе сижу, потому смотрю когда время свободное...
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
06.02.2014, 18:31     Количество маршрутов #11
Цитата Сообщение от Тамика Посмотреть сообщение
Эм... А о чём должно?..
О треугольнике Паскаля.
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
06.02.2014, 19:02     Количество маршрутов #12
А вот такие варианты надо считать?
Изображения
 
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
06.02.2014, 19:03  [ТС]     Количество маршрутов #13
Цитата Сообщение от programina Посмотреть сообщение
А вот такие варианты надо считать?
Не-а. Сглупила и не уточнила, что движение возможно только направо и вниз.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 19:04     Количество маршрутов #14
Цитата Сообщение от Somebody Посмотреть сообщение
О треугольнике Паскаля.
Ну вот, убили всю интригу
Xopecc
33 / 28 / 2
Регистрация: 13.09.2013
Сообщений: 246
06.02.2014, 19:34     Количество маршрутов #15
Тамика, Возможно это вам поможет
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2014, 19:41     Количество маршрутов
Еще ссылки по теме:

В массиве записаны результаты N игр футбольной команды. Определить количество выигрышей, количество проигрышей и количество ничьих данной команды. C++
Вывести время отправления и номера маршрутов, проходящих через данный населенный пункт C++
Пользователь вводит строку. Определить количество букв (рус eng), количество цифр и количество остальных C++

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

Или воспользуйтесь поиском по форуму:
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
06.02.2014, 19:41     Количество маршрутов #16
Да тут пишется обычное двумерное ДП, и всё.Но или если извращаться, то запускаем DFS и считаем, сколько раз она достигла нужной клетки.
Yandex
Объявления
06.02.2014, 19:41     Количество маршрутов
Ответ Создать тему
Опции темы

Текущее время: 13:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru