Помогите с разбором задачи на рекурсию

106
09 июня 2021, 19:20

Между городом A и гоордом B проложена единственная дорога, на которой построено N остановочных пунктов. Обычный автобусный маршрут из A в B предусматривает остановки на каждом из оборудованных пунктов. Экспрессный маршрут пропускает некоторые (не менее одного) остановочные пункты, но ни один экспрессный маршрут не пропускает более двух пунктов подряд. Сколько различных экспрессных маршрутов можно организовать между городами A и B? Два маршрута считаются различными, если множества остановочных пунктов, которые они пропускают, различны. 1 <= N <= 70.

Решение такое: Пусть D(n) число всех маршрутов (обычных и экспрессных), соединяющих города A и B при условии n промежуточных остановок. Тогда ответ равен D(n) - 1. Рекуррентное соотношение для нахождения D(n): D(n) = D(n-1) + D(n-2) + D(n - 3). Обьясните пожалуйста, откуда взялась эта формула, по рекурсии задач не решал, так что максимально по-простому.

Answer 1

Как можно попасть на последнюю (n-ю) остановку? Приехав с предпоследней (n-1)-ой, с (n-2)-й, пропустив одну, или с (n-3)-й, пропустив две.

Вот и получается, что число возможных маршрутов складывается из D(n-1), D(n-2), D(n-3).

Как найти D(n-1)? Да по аналогии, как сумму D(n-2), D(n-3), D(n-4).

Применяя такие правила к каждой, можно получить рекурсивное решение.

Стоит отметить, что простая реализация неэффективна, т.к. одни и те же значения рассчитываются многократно. Поэтому с указанными ограничениями (N=70) при использовании рекурсии нужно запоминать посчитанные значения в массиве.

Кроме того, есть ещё более продвинутые методы расчёта, о них можно почитать в статьях о числах Фибоначчи (в данном случае т.н. числа трибоначчи)

READ ALSO
c++ if в switch с использованием string
c++

c++ if в switch с использованием string

if string обработать может, а switch не можетно использовать if, как-то не красиво

 94
Как передать значение datepicker?
jQuery

Как передать значение datepicker?

Не могу передать значение инпута datepciker, как это можно реализовать? https://cdnjscloudflare

 116
Не работает jquery код
jQuery

Не работает jquery код

Надо чтобы при клике на div с классом "next" ему присваивался класс "next_a", а "next" удалялсяИ соответственно при клике на "next_a" присваивался класс...

 110
Динамические точки в строчке
HTML

Динамические точки в строчке

Есть вот такой макет:

 132