IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Лесенка (олимпиадная задача)
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской

Репутация: -  0  +


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


Вроде бы слышал, что задача считается классической, но она встретилась на районной олимпиаде по программированию для школьников.
Поэтому я ее поместил в данный раздел.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(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- соответственно, количество лесенок

Сообщение отредактировано: Malice -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской

Репутация: -  0  +


Спасибо за ответ.
Но не мог бы ты сказать
почему решается именно так.
Теоритические предпосылки.
Или где про это можно почитать.
Заранее спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


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

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


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской

Репутация: -  0  +


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


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


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

5+4+3+2+1

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

Сообщение отредактировано: Malice -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Цитата(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
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 18:48
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name