Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Лесенка (олимпиадная задача)

Автор: yar11 2.12.2005 10:31

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


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

Автор: Malice 22.12.2005 15:21

Цитата(yar11 @ 2.12.2005 8:31) *

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


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

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


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

Автор: yar11 23.12.2005 12:02

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

Автор: Malice 23.12.2005 13:45

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

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

Автор: yar11 23.12.2005 14:26

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

Автор: Malice 23.12.2005 16:05

Цитата(yar11 @ 23.12.2005 12:26) *

5+4+3+2+1

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

Автор: tunyash 10.09.2010 18:49

Цитата(Malice @ 22.12.2005 11:21) *

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

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 9.01.2011 17:16

Эта тема давно в находилась в подвешенном состоянии и время от времени мозолила мне глаза. Таинственный гость tunyash сказал "А":

Цитата(tunyash @ 10.09.2010 14:49) *
решение, к сожалению, неправильное,
- но не сказал "Б".. И я, наконец, собрался и решил расставить точки над i smile.gif.
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 тупо в лоб, к сожалению, нельзя, требуется небольшая переделка..