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

Рекурсия - C++

Восстановить пароль Регистрация
 
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
07.02.2011, 12:34     Рекурсия #1
Здраствуйте! У меня есть одна классическая задачка про Лесенку.

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

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

Добавлено через 4 минуты
а можно поподробнее условие задачи? например почему при 6 он должен вывести 4
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
07.02.2011, 20:32  [ТС]     Рекурсия #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     Рекурсия #7
а можно не корректировать вашу программу а написать свою)) уж больно там все перемудрено)
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
07.02.2011, 20:39  [ТС]     Рекурсия #8
конечно. Буду очень признателен. Моя программа основана на двухмерных выборках. Она еще не работает. Ну даже если ее доделать она будет очень медленно работать. Если есть идей то конечно пишите
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2011, 19:15     Рекурсия
Еще ссылки по теме:

Рекурсия C++
C++ Рекурсия
C++ Рекурсия

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

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

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