Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 430
#1

Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков - C++

07.02.2011, 12:34. Просмотров 975. Ответов 8
Метки нет (Все метки)

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

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

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

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

Примеры
input.txt
3
output.txt
2

input.txt
6
output.txt
4

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

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
#include <fstream>
using namespace std;
 
short a[256][20];
short n, m = 0;
long x = 0;
 
short sum(short j)
{
    short s = 0;
    for(short i = 0; i < n; i++)
        s += a[i][j];
    return s;
}
short f()
{
    short s = 0;
    for(short j = 0; j < m; j++)
        s += sum(j);
    return s;
}
bool prov(short i, short j)
{
    bool z = true;
    for(short q = i; q < n; q++)
        if(a[q][j] == 1)
        {
            z = false;
            break;
        }
    return z;
}
void remiks(short j)
{
    for(short i = 0; i < n - 1; i++)
        if(a[i][j] == 2)
        {
            a[i][j] = 0;
            a[i + 1][j]++;
        }
    if(a[n][j] == 2)
    {
        a[n][j] = 0;
        a[0][j + 1]++;
    }
}
void main()
{
    ifstream f("input.txt");
    ofstream g("output.txt");
 
    f >> n;
 
    while(x < n)
    {
        m++;
        x += m;
        if(x > n)
            m--;
    }
 
    for(short j = 0; j < m; j++)
        for(short i = 0; i < n; i++)
            a[i][j] = 0;
 
    short p = m * n;
    bool z;
    x = 0;
 
    while(f() != p)
    {
        a[0][0]++;
 
        for(short j = 0; j < m; j++)
            remiks(j);
        if(f() == n)
        {
            z = true;
            for(short j = 0; j < m - 1; j++)
                if(sum(j) <= sum(j + 1))
                {
                    z = false;
                    break;
                }
            for(short j = 0; j < m; j++)
                if(prov(sum(j) + 1; j) == false)
                {
                    z = false;
                    break;
                }
            if(z == true)
                x++;
        }
    }
    g << x;
}
 Комментарий модератора 
Дублирование тем нарушает правила форума. Рекурсия, ошибка
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2011, 12:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков (C++):

Вычислить число лесенок, которое можно построить из N кубиков - C++
Объясните пожалуйста решение 16 задачи acmp . ru: Я нашёл только программу, а решение не понял. #include &lt;iostream&gt; #include...

Вычислить количество домов, которое можно построить на площади s1 - C++
Итак, у нас есть значение площади некоторого земельного участка, допустим s1. Еще есть значение площади, которую занимает 1 дом, например...

Сколько можно построить лестниц из кубиков? - C++
http://acm.timus.ru/problem.aspx?space=1&amp;num=1017 Вот такой вот код, рабочий, но все же гавнокод Вместо динамического программирования...

Количество плиток, которое можно уложить на заданную площадь - C++
Написать программу, вычисляющую количество плиток, которое можно уложить на заданную площадь Вводимые данные: а, b – размеры пола; ...

Как увеличить максимальное количество символов, которое можно ввести в консоль? - C++
Я использую функцию cin.getline(article, 9999);Как видите, количество символов для ввода стоит 9999, но на практике консоль принимает...

Структуры. Посчитать количество кубиков каждого цвета - C++
Надо ввести информацию о кубиках(цвет) и посчитать сколько есть кубиков каждого цвета. Написал код, но вместо количества выводит 0.#include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
07.02.2011, 20:09 #2
Wanee, Не у всех есть возможность запустить ваш код, однако многие бы могли помочь просто даже по описанию ошибки. Выкладывайте тексты ошибок.
0
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
07.02.2011, 20:14 #3
А как это у вас так получилось что на 86 строке стоит точка с запятой? (в if)
prov(sum(j) + 1; j == true - это что ещё значит?))
0
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 430
07.02.2011, 20:21  [ТС] #4
shocoladka, эт функция. У нее 2 параметра. а на выходе дает либо true либо false

Добавлено через 2 минуты
Ошибка была найдена. Просьба помочь отладить программу. Спасибо!
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
include <iostream>
using namespace std;
 
short a[256][20];
int n, m = 0;
long x = 0;
 
short sum(short j)
{
        short s = 0;
        for(short i = 0; i < n; i++)
                s += a[i][j];
        return s;
}
short func()
{
        short s = 0;
        for(short j = 0; j < m; j++)
                s += sum(j);
        return s;
}
bool prov(short i, short j)
{
        bool z = true;
        for(short q = i; q < n; q++)
                if(a[q][j] == 1)
                {
                        z = false;
                        break;
                }
                return z;
}
void remiks(short j)
{
        for(short i = 0; i < n - 1; i++)
                if(a[i][j] == 2)
                {
                        a[i][j] = 0;
                        a[i + 1][j]++;
                }
                if(a[n][j] == 2)
                {
                        a[n][j] = 0;
                        a[0][j + 1]++;
                }
}
void main()
{
        ifstream f("input.txt");
        ofstream g("output.txt");
 
        f >> n;
 
        while(x < n)
        {
                m++;
                x += m;
                if(x > n)
                        m--;
        }
 
        for(short j = 0; j < m; j++)
                for(short i = 0; i < n; i++)
                        a[i][j] = 0;
 
        short p = m * n;
        bool z;
        x = 0;
 
        while(func() != p)
        {
 
                a[0][0]++;
 
                for(short j = 0; j < m; j++)
                        remiks(j);
                if(func() == n)
                {
                    z = true;
                    for(short j = 0; j < m - 1; j++)
                        if(sum(j) <= sum(j + 1))
                        {
                            z = false;
                            break;
                        }
                        for(short j = 0; j < m; j++)
                            if(prov(sum(j)+1, j) == false)
                            {
                                z = false;
                                break;
                            }
                        if(z == true)
                            x++;
                }
        }
        g << x;
}
0
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
07.02.2011, 20:27 #5
я конечно могу чтото недопонять но обычно ставится , а не ;(перед j)

Добавлено через 4 минуты
а можно поподробнее условие задачи? например почему при 6 он должен вывести 4
1
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 430
07.02.2011, 20:32  [ТС] #6
shocoladka, точно вы правы

Добавлено через 2 минуты
ну допустим у нас 6 кубиков.
нам нужно вывести количество все возможных вариантов, тоесть количество лесенок которые можно собрать из этих кубиков.
6+0+0
5+1+0
4+2+0
3+2+1

Добавлено через 1 минуту
При этом учитывая правило. Что последующая ступень лесники меньше предыдущей
0
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
07.02.2011, 20:34 #7
а можно не корректировать вашу программу а написать свою)) уж больно там все перемудрено)
0
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 430
07.02.2011, 20:39  [ТС] #8
конечно. Буду очень признателен. Моя программа основана на двухмерных выборках. Она еще не работает. Ну даже если ее доделать она будет очень медленно работать. Если есть идей то конечно пишите
0
Beleaf
9 / 9 / 3
Регистрация: 14.04.2010
Сообщений: 99
09.02.2011, 19:15 #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <stdio.h>
using namespace std;
 
int t=0;
 
int sum(int x)
{
    t++;
    if (x < 1)
        return 0;
    return (x-sum(x-1));
}
 
int main()
{
    int x = 6, stairs;
    sum(x);
    cout << "You can build " << t << " stairs" << endl;
    system("PAUSE");
    return 0;
}
Вот пытался сделать заново, но ничего не получилось, просьба подправить этот код, чтобы корректно работал)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2011, 19:15
Привет! Вот еще темы с ответами:

Вычислить число лесенок, которое можно построить из N кубиков - Turbo Pascal
Помогите пожалуйста решить задачку!!! Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем...

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

Подсчитать число лесенок, которое можно построить из N кубиков - Pascal
Помогите решить плз Задача &quot;Лесенки&quot; Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков...

.NET 3.x Подсчитать число лесенок, которое можно построить из N кубиков - C#
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Лесенкой называется набор кубиков в один или несколько...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
09.02.2011, 19:15
Закрытая тема Создать тему
Опции темы

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