Лесенкой называется набор кубиков, в котором каждый более верхний слой
содержит кубиков меньше, чем предыдущий. Требуется написать программу,
вычисляющую число лесенок, которое можно построить из N кубиков.
Пример: для 6 кубиков можно сделать: 5-1, 4-2, 3-2-1.
Нет, не требуется. Во всяком случае, от нас.
Хочешь, чтобы тебе помогли - выкладывай, что сделал (тут проще всего рекурсией, для оптимизации можно кешировать результаты) .
Хочешь, чтобы сделали за тебя - предлагай деньги.
$a = 0;
for($i=n;$i>0;$i--)
{
$a+=$i;
}
print $a;
+++++++++++UPD
Не в том порядке написал
($a=+$i;) => ( $a+=$i;)
Реально на PHP? Это не очень алгоритмический язык, он затачивался под строки, но если очень надо, пишите…
Алгоритм примерно такой (самый простой в объяснении) :
Использовать матрицу A(M, N) - количество лесенок из N кубиков, когда в основании M.
По понятным причинам M < N, то есть матрица треугольная.
Первое значение A(1, 2) = 1.
Далее имея треугольник A(M, N) нужно конструировать A(i, N+1) i=1…N
Тут вложенный цикл, так как нужно перебрать по одному весь второй ряд от j=1…(N+1-i) накапливая количество:
-- если j >= i то пропускаем это j (это не лесенка)
-- иначе проверим, что осталось от k=(N+1-i)-j - это на 3ий и выше этажи
----k=0 - количество = количество + 1 (тут нельзя использовать A - лесенка низковата)
----k>0 - количество = количество + A(j, k+j)
A(i, N+1) = количество
ЗЫ
Допускаю, что где-то обсчитался, решал эту задачу более 10 лет назад.
Причём решал не через матрицу, а рекурсией, просто с матрицей проще отлаживать.
Но всё было как-то так.
ЗЗЫ
Это вообще-то олимпиадная школьная задачка.
Как вариант:
$a = 0;
for($i=n;$i>0;$i--)
{
$a=+$i
{
$1=40rub
}
print $a;
⇢