Лесенка (олимпиадная задача) Опции

[yar11]

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


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

[Malice]

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

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

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

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

Сообщение отредактировано: Malice - 22.12.2005 11:22

[tunyash]

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

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

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

решение, к сожалению, неправильное, скажем из шести кубиков можно построить не 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

[Lapp]

Эта тема давно в находилась в подвешенном состоянии и время от времени мозолила мне глаза. Таинственный гость 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 тупо в лоб, к сожалению, нельзя, требуется небольшая переделка..