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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Тамика
Котовчанин
869 / 449 / 142
Регистрация: 16.02.2010
Сообщений: 2,899
Записей в блоге: 27
#1

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

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

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

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

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

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

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

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

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

Упорядочить номера маршрутов по возрастанию (структуры) - C++
Помогите пожалуйста как упорядочить номера маршрутов по возрастанию?? #include <iostream> #include <string.h> #include...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
201 / 145 / 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.... Не проверял...
Тамика
Котовчанин
869 / 449 / 142
Регистрация: 16.02.2010
Сообщений: 2,899
Записей в блоге: 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 (ну или все равно есть какая-то регрессия пропорционально площади)
Тамика
Котовчанин
869 / 449 / 142
Регистрация: 16.02.2010
Сообщений: 2,899
Записей в блоге: 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
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 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
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 18:22     Количество маршрутов #9
Тамика, вы поняли, что за закономерность то?
Тамика
Котовчанин
869 / 449 / 142
Регистрация: 16.02.2010
Сообщений: 2,899
Записей в блоге: 27
06.02.2014, 18:31  [ТС]     Количество маршрутов #10
Цитата Сообщение от Somebody Посмотреть сообщение
n(x, y) = n(x - 1, y) + n(x, y - 1)
Ничего не напоминает?
Эм... А о чём должно?..

Добавлено через 1 минуту
Цитата Сообщение от ya_noob Посмотреть сообщение
Тамика, вы поняли, что за закономерность то?
Пока не очень... На работе сижу, потому смотрю когда время свободное...
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
06.02.2014, 18:31     Количество маршрутов #11
Цитата Сообщение от Тамика Посмотреть сообщение
Эм... А о чём должно?..
О треугольнике Паскаля.
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
06.02.2014, 19:02     Количество маршрутов #12
А вот такие варианты надо считать?
Изображения
 
Тамика
Котовчанин
869 / 449 / 142
Регистрация: 16.02.2010
Сообщений: 2,899
Записей в блоге: 27
06.02.2014, 19:03  [ТС]     Количество маршрутов #13
Цитата Сообщение от programina Посмотреть сообщение
А вот такие варианты надо считать?
Не-а. Сглупила и не уточнила, что движение возможно только направо и вниз.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 19:04     Количество маршрутов #14
Цитата Сообщение от Somebody Посмотреть сообщение
О треугольнике Паскаля.
Ну вот, убили всю интригу
Xopecc
33 / 28 / 2
Регистрация: 13.09.2013
Сообщений: 250
06.02.2014, 19:34     Количество маршрутов #15
Тамика, Возможно это вам поможет
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2014, 19:41     Количество маршрутов
Еще ссылки по теме:

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

Поиск маршрутов выхода из лабиринта и запись карты с найденным маршрутом в файл - C++
Нужно провести поиск маршрутов выхода из лабиринта и запись карты с найденным маршрутом в файл solution.txt. Карта лабиринта содержится в...

Вывести время отправления и номера маршрутов, проходящих через данный населенный пункт - C++
Мне нужно написать программу: Создать массив, в котором записать информацию о маршрутах автобусов: номер маршрута, перечень населенных...

Определить количество выигрышей, количество проигрышей и количество ничьих данной команды - C++
Недавно начал изучать язык С++ и уже застопорился. Помогите пожалуйста решить. 2.В массиве записаны результаты N игр футбольной...

Количество букв в слове, количество предложений, самое длинное слово в предложении - C++
Как написать прогу, которая бы указывала количество букв в слове, вводимое пользователем, количество предложений, самое длинное слово в...


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

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

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