Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,213
Записей в блоге: 27
#1

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

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

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

Количество маршрутов с препятствиями - 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 до...

15
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 14:15 #2
Цитата Сообщение от Тамика Посмотреть сообщение
Помогите, пожалуйста, подсказкой, как можно решить эту задачу!
помогаю: проведите через узлы сетки диагонали с таким наклоном / и посчитайте поочередно для каждой диагонали (начиная с самой левой) сколькими способами можно добраться до каждого узла на этой диагонали со всех возможных узлов предыдущей диагонали, соблюдая правило обхода "вправо или вниз" (которое вы почему-то не указали в условии задачи). через некоторое время увидите закономерность.
1
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
06.02.2014, 15:03 #3
Тамика, А тут не квадратичная зависимость? 2х2=6 2х4=36.... Не проверял...
0
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,213
Записей в блоге: 27
06.02.2014, 16:41  [ТС] #4
Цитата Сообщение от mustimur Посмотреть сообщение
Тамика, А тут не квадратичная зависимость? 2х2=6 2х4=36.... Не проверял...
... А что за квадратичная зависимость?..
0
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
06.02.2014, 16:57 #5
Цитата Сообщение от Тамика Посмотреть сообщение
... А что за квадратичная зависимость?..
Ну смотрите в квадрате 2х2 всего путей 6, то в прямоугольнике 2х4 сколько? вполне допуская что мин. 36 (ну или все равно есть какая-то регрессия пропорционально площади)
0
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,213
Записей в блоге: 27
06.02.2014, 17:00  [ТС] #6
Может... Но немного странно. А если, к примеру, мы не знаем, что 6 путей. А просто есть квадрат 2 на 2. Как узнать тогда?
0
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
06.02.2014, 17:11 #7
Ну это анализ человека, а не машины...
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,200
Завершенные тесты: 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 вертикальных
0
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.02.2014, 18:22 #9
Тамика, вы поняли, что за закономерность то?
0
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,213
Записей в блоге: 27
06.02.2014, 18:31  [ТС] #10
Цитата Сообщение от Somebody Посмотреть сообщение
n(x, y) = n(x - 1, y) + n(x, y - 1)
Ничего не напоминает?
Эм... А о чём должно?..

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

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

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

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

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


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

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

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