Задачка на комбинаторику

Решить нужно аналитически, без рекурсивных программ в лоб.

Но зачем? Какой размер реальной задачи?

без рекурсии с ходу вижу решение в O(H*W), но это не точно. :)

тег haskell потому что он нужен как раз для решения таких высосанных из пальца задачек

Возмём конкретный пример и 5-и точек про уровень.

Из 3-х средних позиций у нас 3 возможных пути (вниз, в лево, в право). Из 2-х крайних только 2 возможных пути (вниз и в сторону).

Итого: (5-2)×3 + 2×2 = 13 возможных перехода.

У нас 7 уровней. Последний уровень финальный, переходов из него уже не происходит. Отнимаем его.

Итого: ((W-2)×3 + 2×2) × (H-1))

С W=5 и H=7 у нас 78 возможных пути перемещения листика.

PS: Это если начинать из любой точки в верху стакана. Если ограничить только серединой, то нахождение решения оставляется в качестве домашнего задания.

Точки у стенок случаются с меньшей вероятностью, чем центральная.

От балды на глаз 63

По-моему ещё интереснее задача если начинать не с середины а с произвольной точки. Но кажется она сложнее.

По-моему тут надо посчитать P(x,y) - количество путей из точки (x0,0) до точки (x,y).

P(x,0) = (x==x0)
P(0,y>=1) = P(0,y-1) + P(1,y-1)
P(W-1,y>=1) = P(W-2,y-1) + P(W-1,y-1)
P(1<=x<=W-2,y>=1) = P(x-1,y-1)+P(x,y-1)+P(x+1,y-1)

Если x0=(W-1)/2 то можно дополнить подсказкой P(x,y)=P(W-1-x,y)

Надо как-то узнать (угадать?) выражение для P(x,y), удовлетворяющее этим уравнениям - собственно это и есть задача, а выше было условие в математическом виде.

Шлакоблокунь

А зачем листик в стакан опускать?

При W = inf – 3^H;
При W = 1 – 1(^H);
При W = 2 – 2^H;
При W = 3,4,5,6… – (2+x)^H;

Это полегче, чем самоизбегающая прогулка, поэтому, возможно, решаемо. Скорее всего – на цепях Маркова.

А, нет, даже легче.

При W = 3 – (3/7)*3^H + (4/7)*2^H;
При W = 5 – (9/13)*3^H + (4/13)*2^H;

Товарищи программисты, проверьте.

При W = n – ((3n-6)/(3n-2))*3^H + (4/(3n-2))*2^H;
Так, что ли?

А нет, ошибочка.

Там намного хуже распределение. Но это решается при большом желании.

При W = 3 – c*(2+sqrt(2))(1+sqrt(2))^n. Ну или около того.

При W = 5 – распределение [1/2, sqrt(3)/2, 1, sqrt(3)/2, 1/2], т.е. ~(1+sqrt(3))^n

Объяснишь как это посчитал? Что за методика?

сдаётся мне что это олимпиадная задача для 8-го класса школы :-) дети как-раз подобное проходят.

решается довольно просто, без зауми - кол-во связей между уровнями перемножается. То есть важны не сами по себе точки, а их связи/рёбра графа. Кол-во рёбер считается визуально на бумажке или в уме как прогрессия

Для 3:

Предположим, что на шаге n у нас [1,x,1].
Тогда на шаге n+1: [x+1,x+2,x+1].

x/1 = (x+2)/(x+1) => x = sqrt(2)

Рассмотрим сумму всех элементов.

(3x+4)/(x+2) = 1 + sqrt(2) – и его наша искомая константа роста.

Попробуй решить для 5 сам, если надо решение – пиши, распишу.

это листик чая, чтобы сделать напиток «чай»

https://www.linux.org.ru/tag/шлакоблокунь

Посмотри Ширяева, «Вероятность», 1-ую главу, случайное блуждание 2. Там подсчитывается число таких путей (для биномиальной схемы, но не суть). Принцип отражения какой-то (не помню уже), может удастся применить к стенкам.

Приснилась

Невежливо врать, обращаясь за помощью.

Ну собственно да, я вспомнил, подумал, очень правильную дал наводку.

Если биномиальная схема, стенка у стакана лишь одна, и листок падает из положения рядом со стенкой, и в положение рядом со стенкой, то решение – в доказательстве Леммы 1 из того параграфа.

Все эти ограничения легко расширяемы до твоего случая. Пожалуй самое нетривиальное ограничение – вторая стенка. Если не догадываешься как – рассмотри короткий стакан, в котором частица, дойдя до (например) левой стенки, не сможет успеть дойти до правой. Потом увеличь глубину, чтобы частица, дойдя до левой, успела дойти и до правой стенки (но не успела повторно до левой). И т.д. Так легко расширишь принцип отражения.

Ответ пишется сразу, но долго (трёхэтажные суммы), потом пару часов «отлаживается» (+-1 разнообразные повсюду).

Решить нужно аналитически, без рекурсивных программ в лоб.

А динамическим программированием считается?