LINUX.ORG.RU

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

 , , ,


0

3

Приснилась сегодня.

Есть стакан шириной W(нечетное) высотой H

ooooo
ooooo
ooooo
ooooo
ooooo
ooooo
ooooo

Из точки @ ([floor(W / 2), 0]) отпускают листик. Падать он может вниз или по диагоналям - #

oo@oo
o###o
ooooo
ooooo
ooooo
ooooo
ooooo

При этом не может пересечь края стакана. Те [x, y] -> [[x, y + 1], [min(x + 1, W - 1), y + 1], [max(x - 1, 0), y + 1]]

ooooo
o@ooo
###oo
ooooo
oooo@
@oo##
##ooo

Найти всевозможное количество путей из изначальной точки [floor(W / 2), 0] до дна.

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

★★★

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

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

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

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

yoghurt ★★★★★ ()

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

Virtuos86 ★★★★★ ()

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

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

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

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

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

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

beastie ★★★★★ ()
Ответ на: комментарий от beastie

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

beastie ★★★★★ ()
Ответ на: комментарий от beastie

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

tyakos ★★★ ()

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

По-моему тут надо посчитать 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), удовлетворяющее этим уравнениям - собственно это и есть задача, а выше было условие в математическом виде.

firkax ★★ ()

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

ashot ★★★★ ()

При 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;
Так, что ли?

tyakos ★★★ ()
Последнее исправление: tyakos (всего исправлений: 4)

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

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

MKuznetsov ★★★★★ ()
Ответ на: комментарий от bga_

Для 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 сам, если надо решение – пиши, распишу.

tyakos ★★★ ()
Последнее исправление: tyakos (всего исправлений: 1)

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

Приснилась

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

the1 ★★ ()
Ответ на: комментарий от the1

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

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

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

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

the1 ★★ ()

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

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

Waterlaz ★★★★★ ()
Для того чтобы оставить комментарий войдите или зарегистрируйтесь.