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

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

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

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

07.02.2011, 12:34. Просмотров 903. Ответов 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;
}
 Комментарий модератора 
Дублирование тем нарушает правила форума. Рекурсия, ошибка
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2011, 12:34     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков
Посмотрите здесь:

C++ Найти количество кубиков каждого их перечисленных цветов и их суммарный объем.
C++ Найти: А) количество кубиков каждого из перечисленных цветов и их суммарный объем
Рекурсия(вычислить 1*2*3*...n+2*3*4*...(n-1)+3*4*5*(n-2)+...) C++
Количество плиток, которое можно уложить на заданную площадь C++
Структуры. Посчитать количество кубиков каждого цвета C++
Вычислить количество домов, которое можно построить на площади s1 C++
Сколько можно построить лестниц из кубиков? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
insideone
Модератор
Автор FAQ
3635 / 913 / 48
Регистрация: 10.01.2010
Сообщений: 2,460
07.02.2011, 20:09     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков #2
Wanee, Не у всех есть возможность запустить ваш код, однако многие бы могли помочь просто даже по описанию ошибки. Выкладывайте тексты ошибок.
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
07.02.2011, 20:14     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков #3
А как это у вас так получилось что на 86 строке стоит точка с запятой? (в if)
prov(sum(j) + 1; j == true - это что ещё значит?))
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
07.02.2011, 20:21  [ТС]     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков #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;
}
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
07.02.2011, 20:27     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков #5
я конечно могу чтото недопонять но обычно ставится , а не ;(перед j)

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

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

Добавлено через 1 минуту
При этом учитывая правило. Что последующая ступень лесники меньше предыдущей
shocoladka
7 / 7 / 0
Регистрация: 02.12.2010
Сообщений: 71
07.02.2011, 20:34     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков #7
а можно не корректировать вашу программу а написать свою)) уж больно там все перемудрено)
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
07.02.2011, 20:39  [ТС]     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков #8
конечно. Буду очень признателен. Моя программа основана на двухмерных выборках. Она еще не работает. Ну даже если ее доделать она будет очень медленно работать. Если есть идей то конечно пишите
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2011, 19:15     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков
Еще ссылки по теме:

C++ Структуры: посчитать количество кубиков указаного цвета и материала
Сформировать из данного числа другое число, которое содержит только четные цифры (рекурсия) C++
C++ Как увеличить максимальное количество символов, которое можно ввести в консоль?
C++ Наибольшее число, которое можно записать в переменную типа int
Вычислить число лесенок, которое можно построить из N кубиков C++

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

Или воспользуйтесь поиском по форуму:
Beleaf
9 / 9 / 3
Регистрация: 14.04.2010
Сообщений: 99
09.02.2011, 19:15     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков #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;
}
Вот пытался сделать заново, но ничего не получилось, просьба подправить этот код, чтобы корректно работал)
Yandex
Объявления
09.02.2011, 19:15     Рекурсия: вычислить количество лесенок, которое можно построить из N кубиков
Закрытая тема Создать тему
Опции темы

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