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

[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

[yar11]

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

[Malice]

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

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

[yar11]

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

[Malice]

5+4+3+2+1

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

Сообщение отредактировано: Malice - 23.12.2005 12:07

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