Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
Octavarium
5 / 5 / 0
Регистрация: 12.02.2013
Сообщений: 233
1

ищу алгоритм поиска путей

19.04.2016, 10:15. Просмотров 820. Ответов 5
Метки нет (Все метки)

http://www.codewars.com/kata/paths-in-the-grid

Представим, что нам дают прямоугольник, составленный из квадратов. Нам нужно найти все пути из нижнего левого угла этого прямоугольника в верхний правый, двигаясь по граням квадратов вверх и вправо.

Чего-то конкретного ненагуглилось, уже сижу и сам придумываю. Подскажите, какой алгоритм нужно использовать?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.04.2016, 10:15
Ответы с готовыми решениями:

Алгоритм поиска путей
Привет. Ребята, такая тема, у меня есть граф, взвешенный, неориентированный, у...

Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей]
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой...

Алгоритм поиска
Привет всем.Вот тут задумался над алгоритмом поиска,смотрите я придумал такую...

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

Алгоритм поиска перестановок
помогите написать алгоритм поиска перестановок в числе, но не простой, а чтобы...

5
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
19.04.2016, 12:21 2
Ссылка нерабочая. Возможно, она доступна только Вам или только авторизованным пользователям.

Цитата Сообщение от Octavarium Посмотреть сообщение
Нам нужно найти все пути из нижнего левого угла этого прямоугольника в верхний правый, двигаясь по граням квадратов вверх и вправо.
Все пути или количество путей?
0
Octavarium
5 / 5 / 0
Регистрация: 12.02.2013
Сообщений: 233
19.04.2016, 12:28  [ТС] 3
Shamil1, количество путей
0
Миниатюры
ищу алгоритм поиска путей  
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
19.04.2016, 12:47 4
Лучший ответ Сообщение было отмечено Octavarium как решение

Решение

Строим "снизу вверх".

Создаём матрицу точек. Точек больше, чем клеток. Размер матрицы n+1 на m+1.
В каждую ячейку матрицы прописываем количество путей, ведущих в соответствующую точку.
Для начальной точки это 1. Для точек на левой и нижней границе - тоже 1. Для остальных точек это количество путей в точку снизу плюс количество путей в точку слева (то есть, количество способов попасть сюда снизу плюс количество способов попасть сюда слева).
Ответ будет в правой верхней ячейке.
1
Octavarium
5 / 5 / 0
Регистрация: 12.02.2013
Сообщений: 233
19.04.2016, 15:31  [ТС] 5
Shamil1, получилось, спасибо!

Добавлено через 2 часа 24 минуты
как только люди до такого додумываются
Javascript
1
2
3
4
5
6
function fact (n){
  return n ? fact(n-1) * n : 1;
}
function numberOfRoutes(m,n){
  return fact((m+n))/(fact(m)*fact(n));
}
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
19.04.2016, 17:23 6
Цитата Сообщение от Octavarium Посмотреть сообщение
как только люди до такого додумываются
Сравните алгоритм подсчёта путей с вычислением чисел в Треугольнике Паскаля.
Фактически, надо вычислить биноминальный коэффициент.
0
19.04.2016, 17:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.04.2016, 17:23

Алгоритм поиска ошибки.
Приветствую. :) Нужна помощь в составлении алгоритма поиска ошибки в...

Алгоритм поиска совпадений
Всем привет! Я веб-программист. Хочу сделать доброе дело, написать один...

Алгоритм поиска алгоритма
Здравствуйте! Хочу написать программу которая будет искать алгоритм который...


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

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

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