Лесенка - динамическое программирование

@jds_07 · Регистрация: 12.03.2009

Студворк — интернет-сервис помощи студентам

Здраствуйте. У меня есть одна классическая задачка про Лесенку.

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

Входные данные
Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке.

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести число лесенок, которые можно построить из N кубиков.

Примеры
INPUT.TXT OUTPUT.TXT
3 2
6 4

Я решил эту задачку с помощью грубого перебора и проходит тесты. Но я слышал что есть и другое эффективное решение с помощью динамическое программирование. Помогите решить.

@odip · 19.08.2009, 19:21

INPUT.TXT OUTPUT.TXT
3 2
6 4

И где тут N, и как вообще разделить INPUT от OUTPUT ?

вычисляющую число лесенок, которое можно построить из N кубиков.

Может число различных лесенок ?
И по условию не очень понял - приведи все варианты лесенок которые собственно нужно посчитать.

@skvor · 19.08.2009, 19:32

Минимальное число кубиков в лесенке - 3. Следовательно Число_Лесенок=Число_Кубиков\3

Надо задачу уточнить.

А про "динамическое программирование", переспросите того, кто это вам сказа - шо он имел ввиду под данным термином.

@odip · 19.08.2009, 19:40

Минимальное число кубиков в лесенке - 3

Вообще-то минимальное число кубиков в лесенке - 1.

@skvor · 19.08.2009, 19:57

Сообщение от odip

Вообще-то минимальное число кубиков в лесенке - 1.

Ссылку на авторитетный источник по лесенкам в студию!

Я определял лесенку, как множество ступенек, для каждой из которых кроме первой, есть предыдущая, для непоследней - есть последующая.

@odip · 19.08.2009, 20:06

Ссылку на авторитетный источник по лесенкам в студию

Первый пост в теме !

Я определял лесенку

Мало чего ты там определил - почитай первый пост.
Скорее всего лесенка из одного слоя - нормальное явление, просто предельный случай в математике.

динамическое программирование

Есть такой метод и возможно он даже применим к данной задаче, если автор конечно уточнит в чем собственно задача состоит.
А то мы тут скоро станем гуру в лесенках и без автора

@Puporev · 19.08.2009, 20:13

Условие задачи.
http://informatics.mccme.ru/mo... pterid=211

@skvor · 19.08.2009, 20:49

Блин, опять лесенка не по ГОСТу.
Там точно и не сказано про лесенку из 1 слоя!
Но там сказано "сколько различных". Тут опять хрень - сколько вариантов существует, или сколько можно построить одновременно разных лесенок из заданного числа кубиков?

odip, тогда Вы, дайте пожалуйста ссылку на "динамическое программирование", только применимое к таким языкам как Паскакаль или Си

Видимо, было не "динамическое программирование", а алгоритмы с использованием "динамических структурх данных".
Но использование "динамических структур", один хрен, суть алгоритма не изменит, всё равно, если не математические формулы с факториалами, то остаётся поиск тупым перебором вариантов.

+1
Там наверно имелось ввиду, что разные лесенки, но содержащие ровно N кубиков.
Плюс есть подсказка - загнать всё в матрицу (лучше в вектор с целыми числами), после этого заниматься перегонкой единиц из одной ячейки в другие, при наличии возможности.

@odip · 19.08.2009, 20:59

Из 3 кубиков можно построить 2 лесенки.
Я так понимаю: 3 кубика в один этаж, 2 кубика и 1 кубик сверху.
Отсюда следует что 1 кубик, тоже лесенка.
Из 6 кубиков можно построить 4 лесенки.
6; 5,1; 4,2; 3,2,1;

дайте пожалуйста ссылку на "динамическое программирование"

http://ru.wikipedia.org/wiki/Д... ммирование

Добавлено через 1 минуту 18 секунд

Я решил эту задачку с помощью грубого перебора и проходит тесты.

Ну так решение выложи.

@Toxa33rus · 19.08.2009, 21:30

Я думаю решается рекурсией: берем все кубики и выкладываем в 1 слой (это раз), далее берем 1 кубик и кладем на верх (это два). А суть рекурсии в том что когда мы будем "отбирать" от первого ряда больше кубиков то мы не будем учитывать первый ряд а просто представим что из взятого надо построить опять же лесенку. Алгоритм похож на фибоначчи.

Code
1
2
3
4
5
6
7
8
9
10
функция Лесенок(кубиков)
  если кубиков меньше 3 вывод 1
  иначе
    ответ=1
    цикл от счетчик = 1 до (кубиков-1)/2
      ответ += Лесенок(счетчик)
    дальше
    вывод ответ
  конец если
конец функции

Это так, на вскидку. Удиалюсь если работает

Но мне кажется 80% кода правильное.

@skvor · 19.08.2009, 21:46

Сообщение от Toxa33rus

Но мне кажется 80% кода правильное.

Закон Мерфи - В каждой программе есть ошибка.
Поправка к закону Мерфи - Мерфи был ба-а-альшим оптимистом

@Toxa33rus · 19.08.2009, 22:05

Не по теме:

Закон главбуха: если баланс не сошелся - значит в балансе ошибка, если сошелся - ошибок как минимум две.

Я и так 20% (целых 2 строки) отвел под ошибки, куда уж больше.

@Puporev · 20.08.2009, 07:46

Я и так 20% (целых 2 строки) отвел под ошибки, куда уж больше.

Вот в эти 20 процентов Вы и попали. Проверил Ваш план действий, считает непонятно что.

@jds_07 · 20.08.2009, 09:30 **[ТС]**

Я вот так решил:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int c[101];
int cnt = 0;
 
void find(int num, int k, int len)
{
    for (int i = 2; i <= len - 1; ++i)
        if (c[i - 1] <= c[i])
            return;
    if (num == 0)
        cnt++;
    else
        for (int i = 1; i <= k; ++i)
            if (num - i >= 0) 
            {
                c[len] = i;
                find(num - i, i, len + 1);
            }
}
find(n, n, 1);

Это конечно перебор

@Toxa33rus · 20.08.2009, 11:27

Сообщение от Puporev

Проверил Ваш план действий, считает непонятно что.

Считает?

Вы мне льстите

Сейчас сам проверю чего там считает...

@Puporev · 20.08.2009, 11:50

Считает? Вы мне льстите

Считает, если немного поправить выход из рекурсии.

@Toxa33rus · 20.08.2009, 11:57

Visual Basic
1
2
3
4
5
6
7
8
Function L(k)
  L = 1
  If k > 2 Then
    For i = 1 To (k - 1) \ 2
      L = L + L(i)
    Next i
  End If
End Function

И почти правильно считает. Где-то немного недосчитывает при кубиках больше 5, но ошибка явно в паре символов где-то.

Добавлено через 57 секунд
подозреваю что тут: (k - 1) \ 2

Добавлено через 5 минут 20 секунд
Точно, так и есть. Понял в чем ошибка! Код считает что если первый ряд например из 5 кубиков то на него нельзя положить больше 4, хотя можно аж 6 (3-2-1).

@odip · 20.08.2009, 22:30

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

@Toxa33rus · 21.08.2009, 12:52

на мой взгляд я подошел к решению, но пока где-то ошибка (а куда же без них).

Visual Basic
1
2
3
4
5
6
7
8
9
10
Function L(k)
  L = 1
  If k > 2 Then
    Max = Sqr(2 * k + 0.25) - 0.5
    Max = IIf(Max = Int(Max), Int(Max), Int(Max) + 1)
    For i = k - 1 To Max Step -1
      L = L + L(k - i)
    Next i
  End If
End Function

Max = Sqr(2 * k + 0.25) - 0.5
Max = IIf(Max = Int(Max), Int(Max), Int(Max) + 1)
это можно убрать заменив на округление вверх вот этого: Sqr(2 * k + 0.25) - 0.5

Добавлено через 1 минуту 0 секунд
откуда эти непонятные цифры объясню позже

@chelovechek · 21.08.2009, 14:06

Зачем все так усложнять?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "stdio.h"
 
int Lesenka(int steps)
{
    if(steps == 0)return 0;
    if((steps == 1)||(steps == 2))return 1;
 
    int counter = 0, add = 2;
 
    do
    {
         counter += add; add++;
    }
    while(counter+add < steps);
 
    return add-1;
}
 
int main()
{
for(int i=0;i<30;i++)
{
    printf("%s%d%s%d\n","cubes: ",i,", lesenok: ",Lesenka(i));
}
getchar();
}

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@jds_07 28 / 27 / 11 Регистрация: 12.03.2009 Сообщений: 85

	Лесенка - динамическое программирование 19.08.2009, 09:48. Показов 30936. Ответов 51 Метки нет (Все метки) Здраствуйте. У меня есть одна классическая задачка про Лесенку. Лесенка Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий. Требуется написать программу, вычисляющую число лесенок, которое можно построить из N кубиков. Входные данные Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке. Выходные данные В выходной файл OUTPUT.TXT необходимо вывести число лесенок, которые можно построить из N кубиков. Примеры INPUT.TXT OUTPUT.TXT 3 2 6 4 Я решил эту задачку с помощью грубого перебора и проходит тесты. Но я слышал что есть и другое эффективное решение с помощью динамическое программирование. Помогите решить. 0

@skvor 640KB мне хватило на всё. 119 / 50 / 3 Регистрация: 07.06.2009 Сообщений: 442
	19.08.2009, 19:32
	Минимальное число кубиков в лесенке - 3. Следовательно Число_Лесенок=Число_Кубиков\3 Надо задачу уточнить. А про "динамическое программирование", переспросите того, кто это вам сказа - шо он имел ввиду под данным термином. 0

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	19.08.2009, 20:13
	Условие задачи. http://informatics.mccme.ru/mo... pterid=211 0

@skvor 640KB мне хватило на всё. 119 / 50 / 3 Регистрация: 07.06.2009 Сообщений: 442
	19.08.2009, 20:49
	Блин, опять лесенка не по ГОСТу. Там точно и не сказано про лесенку из 1 слоя! Но там сказано "сколько различных". Тут опять хрень - сколько вариантов существует, или сколько можно построить одновременно разных лесенок из заданного числа кубиков? odip, тогда Вы, дайте пожалуйста ссылку на "динамическое программирование", только применимое к таким языкам как Паскакаль или Си Видимо, было не "динамическое программирование", а алгоритмы с использованием "динамических структурх данных". Но использование "динамических структур", один хрен, суть алгоритма не изменит, всё равно, если не математические формулы с факториалами, то остаётся поиск тупым перебором вариантов. +1 Там наверно имелось ввиду, что разные лесенки, но содержащие ровно N кубиков. Плюс есть подсказка - загнать всё в матрицу (лучше в вектор с целыми числами), после этого заниматься перегонкой единиц из одной ячейки в другие, при наличии возможности. 0

@Toxa33rus 3920 / 921 / 125 Регистрация: 16.04.2009 Сообщений: 1,956
	19.08.2009, 22:05
	Не по теме: Закон главбуха: если баланс не сошелся - значит в балансе ошибка, если сошелся - ошибок как минимум две. Я и так 20% (целых 2 строки) отвел под ошибки, куда уж больше. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	20.08.2009, 22:30
	Я думаю делать нужно рекурсивный спуск, но ответы запоминать в кэше. Например если мы знаем что их трех кубиков можно сложить две лесенки, то это достаточно вычислить один раз, а далее везде где потребуется будем просто брать из кэша. 0