Маленький тренажер для мозга :))

← →
Имя не скажу (2006-05-22 14:48) [0]

Здрасьте!
Хотел выставить на общее обозрение те задачи, которые не смог решить месяц назад на одной олимпиаде и с треском вылетел оттуда ((
Задача 1. Про ступеньки.
Мальчик может подниматься по ступенькам следующим образом: по одной, или перешагивая через одну ступеньку, или перешагивая через две ступеньки (три способа можно комбинировать как угодно образом).
Ну и дается нашей программе общее число ступенек, скажем, 18, и наша прога должна вычислить общее количество комбинаций.
Например, если дается 4 тогда комбинации такие:
1 1 1 1
1 2 1
1 1 2
2 1 1
2 2
1 3
3 1

Итак, общее число комбинаций: 7

ЗЫ: Остальные задачи напишу потом, а то уже вызывают )))

← →
Карелин Артем © (2006-05-22 14:50) [1]

> а то уже вызывают

В военкомат вызывают? Ждем-с с нетерпением через 2 года...

← →
Джо © (2006-05-22 14:53) [2]

> [1] Карелин Артем © (22.05.06 14:50)
>
> > а то уже вызывают
>
> В военкомат вызывают? Ждем-с с нетерпением через 2 года...

Это ж олимпиада.

← →
Cashmare © (2006-05-22 15:02) [3]

Джо © (22.05.06 14:53) [2]
> В военкомат вызывают? Ждем-с с нетерпением через 2 года...
Это ж олимпиада.

А там не важно. Там важнее:"А раз такой умный, так чего строем не ходишь?"

← →
jack128 © (2006-05-22 16:33) [4]

Имя не скажу (22.05.06 14:48)
а в чем проблема?? Вроде легкая задачка, простейшая рекурсия..

← →
MBo © (2006-05-22 17:52) [5]

или динамикой:

function CalcPathCount(const MaxStep, Len: Integer): Integer; var i, j, N, Curr: Integer; A: array of Integer; begin N := MaxStep + 1; SetLength(A, N); A[0] := 1; for i := 1 to Len do begin Curr := i mod N; for j := Min(0, i - MaxStep) mod N to (i - 1) mod N do Inc(A[Curr], A[j]); end; Result := A[Len mod N]; end;

← →
MBo © (2006-05-22 18:50) [6]

Зря я код [5] прямо в браузере писал :(

Вот так правильно:
function CalcPathCount(const MaxStep, Len: Integer): Integer; var i, j, N, Curr: Integer; A: array of Integer; begin N := MaxStep + 1; SetLength(A, N); A[0] := 1; for i := 1 to Len do begin Curr := i mod N; A[Curr] := 0; for j := 0 to Min(i, MaxStep) do if j <> Curr then Inc(A[Curr], A[j]); end; Result := A[Len mod N]; end;

← →
MBo © (2006-05-23 12:57) [7]

А на закуску решение за O(1) ;)
function PathCountUpTo3Steps(Len: Integer): Integer; var s33, O3, s19, s586: Double; begin s33 := 3 * Sqrt(33); O3 := 1 / 3; s19 := Power(19 + s33, O3) + Power(19 - s33, O3) + 1; s586 := Power(586 + 34 * s33, O3); Result := Round(3 * Power(O3 * s19, Len + 1) / (s586 - 2 + 4 / s586)); end;

← →
REA (2006-05-23 14:30) [8]

[7]!
решение не понял, но внушает... апроксимация какая то?

← →
MBo © (2006-05-23 14:49) [9]

>REA (23.05.06 14:30) [8]

Это формула для очередного члена ряда, похожего на ряд Фибоначчи, ( в котором не два предыдущих, а три предыдущих члена складываются), т.н. "трибоначчи"
http://mathworld.wolfram.com/TribonacciNumber.html

← →
McSimm © (2006-05-23 15:12) [10]

> Это формула для очередного члена ряда

Это мы все конечно понимаем, это нам товарищ доступно объяснил, тумбы там всякие, триббоначчи. Но цикл у ней где ?

:)

← →
Джо © (2006-05-23 15:14) [11]

Ну, слава богу, не я один не понял [7]...

>Но цикл у ней где ? :)
Цикл исключен решением линейного рекурсивного соотношения ;)

>Джо
Если интересно, могу немного пояснить.
Сам алгоритм [6] понятен?
Вот его более простая форма (с O(N) памяти):
function CalcPathCount(const MaxStep, Len: Integer): Integer; var Curr, Prev: Integer; A: array of Integer; begin SetLength(A, Len + 1); A[0] := 1; for Curr := 1 to Len do for Prev := Max(0, Curr - MaxStep) to Curr - 1 do Inc(A[Curr], A[Prev]); Result := A[Len] end;

Смысл такой - при максимальном шаге 3 на N-ю ступеньку мы можем попасть с N-1, N-2, N-3 ступеньки, так что количество путей на нее P(N) = P(N-1) + P(N-2) + P(N-3)
Подобные соотношения называются линейными рекурсивными, общий вид
F[N] = Sum(F[N-k]) с заданием нескольких начальных членов, и существуют математические методы решения таких соотношений.

Удалено модератором

Маленький тренажер для мозга :)) Найти похожие ветки