Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий.
Требуется написать программу, вычисляющую число лесенок, которое можно построить из N кубиков.
Помогите с решением.


Вроде бы слышал, что задача считается классической, но она встретилась на районной олимпиаде по программированию для школьников.
Поэтому я ее поместил в данный раздел.

У меня вот так получилось:

readln (n);
c:=0;x:=0;
while x<n do begin
inc( с ); inc(x,c+1);
end;

c- соответственно, количество лесенок

Спасибо за ответ.
Но не мог бы ты сказать
почему решается именно так.
Теоритические предпосылки.
Или где про это можно почитать.
Заранее спасибо.

Где почитать не знаю, сам делал, а думалось примерно так:

Самый оптимальный вариант лесенки - когда кол-во отличается кубиков на 1. Из этого выходит, что оптимальные лесенки (минус 1 кубик-станет меньше лесенок, +1 - ничего не изменится) будут с количествами 1, (1+2), (1+2+3), (1+2+3+4) и. т.д. Исходя из кол-ва кубиков n в цикле я строю эту лесенку, начиная с верхнего ряда (с 1-цы), пока кубики не кончатся. х - текущее колво кубиков в лесенке.Вот, собственно, и все.

Положим из 10 кубиков можно построить
лесенки типа
9+1, 8+2, 7+3, 7+2+1, 6+4, 6+3+1,
5+4+3+2+1
По твоей программе получается ответ 4.
Может это не число лесенок а максимальное количество ступенек?

Здесь больше 10 Поэтому (1+2+3+4) - 4 лесенки

решение, к сожалению, неправильное, скажем из шести кубиков можно построить не 3, а 4 лесенки
5+1, 4+2, 3+2+1, 6+0
правильное решение рекуррентное.
n[i,j] = n[i][j-1]+n[i-j][j-1] - количество лесенок из i кубиков c основанием лестницы i и менее.
Первые три столбика (нулевой, первый и второй) заполним единичками, затем нулевую строчку - нулями.
а дальше сосчитаем остальное.
PROFIT

Эта тема давно в находилась в подвешенном состоянии и время от времени мозолила мне глаза. Таинственный гость tunyash сказал "А":
- но не сказал "Б".. И я, наконец, собрался и решил расставить точки над i .

type
  tInt= longint;
 
function Stairs(n,l: tInt): tInt;
begin
  Stairs:=byte(n=0);
  while l<n do begin
    Inc(l);
    Inc(Stairs,Stairs(n-l,l))
  end
end;
 
var
  n: tInt;
 
begin
  write('n = ');
  readln(n);
  writeln('total of ',Stairs(n,0),' stairs could be build');
  readln
end.

Прошу заметить: этот код в этом виде НЕ БУДЕТ работать под TurboPascal. Если кто-то все же хочет вкусить аромата старины - замените longint на integer (что, разумеется, уменьшит диапазон N). С longint диапазон N доходит примерно до 200. Использовать int64 тупо в лоб, к сожалению, нельзя, требуется небольшая переделка..