Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.84/25: Рейтинг темы: голосов - 25, средняя оценка - 4.84
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
1

ЗАДАЧА №16 лесенка

23.01.2012, 15:22. Просмотров 4869. Ответов 6
Метки нет (Все метки)

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

как ее сделать? можете объяснить как сделать? (если кто то решил на паскале пришлите исхоник , если можете)
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.01.2012, 15:22
Ответы с готовыми решениями:

Задача "Лесенка". Как улучшить?
Здравствуйте! У меня задание: Коротышка шагает по целочисленному массиву. Шаг не велик, так что...

Лесенка
На каждой из n + 2 ступенек лестницы записано целое число, причем на первой и на последней...

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

Лесенка
Ограничение времени: 1 с Ограничение памяти: 64 M На каждой из N+2 ступенек лестницы записано...

6
20 / 13 / 1
Регистрация: 17.12.2010
Сообщений: 34
25.01.2012, 20:28 2
один цикл, в котором две строчки : увеличение этажа, вычитание этажа из кубиков.
0
3 / 3 / 0
Регистрация: 18.01.2012
Сообщений: 12
25.01.2012, 21:46 3
Цитата Сообщение от Cool-T Посмотреть сообщение
один цикл, в котором две строчки : увеличение этажа, вычитание этажа из кубиков.
этот прием не подходит под условия задачи. Это один элемент из множества. Представляет собой лесенку вида:
*
**
***
а вот такую:

*
***
******

или такую:

**
***
******
не отобразит
1
20 / 13 / 1
Регистрация: 17.12.2010
Сообщений: 34
25.01.2012, 22:20 4
Спасибо, я о другой лесенке вообще подумал. На том же сайте на днях делал)
0
Эксперт С++
3201 / 1728 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
26.01.2012, 09:52 5
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//////////////////////////////////////////////////////////////////////////////////////
//Лесенкой называется набор кубиков, в котором каждый более верхний слой 
//содержит кубиков меньше, чем предыдущий. Требуется написать программу, 
//вычисляющую число лесенок, которое можно построить из N кубиков.
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <limits>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef unsigned long long  T_int;
typedef std::vector<T_int>  T_row;
typedef std::vector<T_row>  T_matr;
//////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  successful_inc
    (
        T&  val,
        T   added_val        
    )
{
    bool  bool_res = val < std::numeric_limits<T>::max() - added_val;
 
    if(bool_res)
    {
        val += added_val;
    }
    return  bool_res;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  L
    (
        int     N,
        T_int&  res
    )
{
    bool    bool_res = false;
    T_matr  matr( N + 1, T_row(N + 1) );
 
    for(int  n = 1; n <= N; ++n)
    {
        for(int  max_summand = 1; max_summand <= n; ++max_summand)
        {
            if(max_summand == n)
            {
                matr[n][max_summand] = 1;
            }
            else
            {
                for(int  i = 1; i < max_summand; ++i)
                {
                    bool_res =  successful_inc
                                    (
                                        matr    [n]                 [max_summand],
                                        matr    [n - max_summand]   [i]
                                    );
 
                    if(!bool_res)
                    {
                        return  bool_res;
                    }
                }
            }
        }
    }
 
    res = 0;
 
    for(int  i = 1; i <= N; ++i)
    {
        bool_res =  successful_inc
                        (
                            res,
                            matr[N][i]
                        );
 
        if(!bool_res)
        {
            return  bool_res;
        }
    }
    return  bool_res;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));    
    
    for(;;)
    {
        int  n = 0;
        do
        {
            std::cout << "n = ";        
            std::cin >> n;        
        }while(n <= 0);
 
        T_int   res         =   0;
        bool    bool_res    =   L(n, res);
 
        if(bool_res)
        {
            std::cout << "res = "
                      << res
                      << std::endl
                      << std::endl;
        }
        else
        {
            std::cout   << "Значение n слишком велико."
                        << std::endl
                        << std::endl;
        }
    }
}
0
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
26.01.2012, 17:43  [ТС] 6
Mr.X, извините , конечно, но вы везде кидаете сови исходники, неужели, нельзя объяснить, потребуется меньше времени и все пойму, так как некоторые не знают с++, притом еще и с класами, я не вижу смысл в ваших исходниках
0
Эксперт Java
4058 / 3793 / 743
Регистрация: 18.05.2010
Сообщений: 9,330
Записей в блоге: 11
Завершенные тесты: 1
27.01.2012, 07:45 7
Проще всего решить задачу с помощью рекурсии.
Общий вид будет такой
Код
BuildLadder(count, max) {
   if (count ==0 || max==0)
      return;

    for (i=1; i<=count && i<=max; i++) {
        BuildLadder(count - i, i-1);
    }
}

count - кол-во доступных шариков.
max - насколько большим может быть следующий слой

условие выхода очевидно: когда не можем добавить новый слой
Код
if (count ==0 || max==0)
основной цикл будет перебирать длины очередного слоя, и вызывая себя рекурсивно:
Код
    for (int i=1; i<=count && i<=max; i++) {
        BuildLadder(count - i, i-1);
    }
я думаю тут все понятно:
i - сколько кубиков отведено на нижний слой,
значит остается count-i кубиков.
так как каждый слой должен быть меньше, то max = i-1

Моя обвязка на java

Java
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
        private static Stack<Integer> res = new Stack<Integer>();
        
        private static void outResult() {
            for (Integer i : res) {
                System.out.print(" " + i);
            }
            System.out.println();
        }
 
        private static void BuildLadder(int count, int max) {
            if (max==0 || count==0) {
                outResult();
                return;
            }
            
            for (int i=1; i<=count && i<=max; i++) {
                res.push(i);
                BuildLadder(count - i, i-1);
                res.pop();
            }
        }
 
        public static void main(String[] args) {
            BuildLadder(5, 5);
        }
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.01.2012, 07:45

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

Лесенка
Привет программисты!!! Подскажите пожалуйста код программы! Задача программы: при нажатии кнопки...

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

Лесенка из чисел
Нужно написать програму, которая принимает 1 аргумент - число от 1 до 9 (включительно) Программа...

Шифр «Лесенка»
К открытому тексту был применен шифр «Лесенка». Восстановите сообщение по шифрованному тексту...

Лесенка из цифр.
Не могу понять, что хочет преподаватель.Задание: Постройте лесенку вверх из цифр, отстоящих на три...

Лесенка из зведочек
Написать класс с методом рисующий лесенку из звездочек, высота равна ширине, и передается в метод в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.