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

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

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

Рекурсия, ошибка - C++

07.02.2011, 12:40. Просмотров 423. Ответов 6
Метки нет (Все метки)

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

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

Подскажите в чем ошибка в моей программе (рекурсия) - C++
Программа копирует строку t в конец строки s: вот код: #include&lt;iostream&gt; using namespace std; int i=0; string fn_strcat(string...

Рекурсия - C++
#include&lt;stdio.h&gt; void gg(int a,int b) { int i=0; if(a==20) return; printf(&quot;%d\n&quot;,a); printf(&quot;%d\n&quot;,b); gg(a+1,b-1); ...

Рекурсия - C++
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;time.h&gt; #include &lt;iostream&gt; int main() { int mass = {0}, ...

рекурсия - C++
Всем доброго времени суток. Есть рекурсивная функция выводящая числа от 15 до 10 по убыванию, как сделать чтоб выводило эти же числа но...

рекурсия в с++ ( ?: = if() else) - C++
Подскажите, пожалуйста, как сделать с помощью рекурсивной функции? int sum (int *arr, size_t size) { return size ? *arr + sum...

Рекурсия - C++
Не понимаю каков будет порядок действий в функции допустим когда(level =2). По тому как я понял работает рекурсия, когда начнется алгоритм...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
perimetral
1 / 1 / 0
Регистрация: 17.12.2010
Сообщений: 16
07.02.2011, 12:58 #2
Во-первых, при 6 кубиках будет 3 лесенки, а не 4. Во-вторых, в main() первый цикл while (в котором условие x<n) никогда не выполнится, ибо обе переменных изначально равны нулю. А т.к. в нем ты присваиваешь что-то m и x, то и второй цикл тоже не выполнится ни разу. Выполнится лишь третий (не вложенный во второй) цикл, ибо p тоже = 0. Это все, что заметил, пробежавшись.
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 430
07.02.2011, 13:04  [ТС] #3
perimetral, при 6 будет 4.
1)6 0 0
2)5 1 0
3)4 2 0
4)3 2 1

Добавлено через 41 секунду
Нам нужно найти не высоту лесенки, а количество все возможных вариантов
zulkis
682 / 609 / 38
Регистрация: 13.01.2011
Сообщений: 1,724
07.02.2011, 13:06 #4
perimetral,
ifstream f("input.txt");
f >> n;
Хм, вроде как раз тут он и заносит в переменную n свое число, так что с циклом на первый взгляд вроде ничего )
C++
1
2
short f();
ifstream f();
ничего не замечаешь ?*

Поправил код, дабы запустилось. На правильность работы не проверял:
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 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;
}
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 430
07.02.2011, 13:12  [ТС] #5
perimetral, я перед 1 циклом n считываю с файла. Это значение кубиков. Тоесть сколько мы имеем кубиков.
C++
1
f >> n;
Дальне я нахожу высоту таблицы
C++
1
2
3
4
5
6
7
        while(x < n)
        {
                m++;
                x += m;
                if(x > n)
                        m--;
        }
где m и есть высота
easybudda
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,603
07.02.2011, 15:19 #6
Цитата Сообщение от Wanee Посмотреть сообщение
Нам нужно найти не высоту лесенки, а количество все возможных вариантов
эх, жаль, а то бы всё просто было
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <math.h>
 
int main(void){
    int blocks, rows, used;
    
    while ( printf("\nBlocks: ") && scanf("%d", &blocks) == 1 && blocks > 0 ){
        rows = (int)((sqrt(1.0 + 8.0 * blocks) - 1) / 2);
        used = (rows + rows * rows) / 2;
        printf("%d rows and %d blocks left.\n", rows, blocks - used);
    }
    
    return 0;
}
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 430
07.02.2011, 15:51  [ТС] #7
easybudda, высоту лесенки ищет вот этот кусок кода
C++
1
2
3
4
5
6
7
        while(x < n)
        {
                m++;
                x += m;
                if(x > n)
                        m--;
        }
Добавлено через 26 минут
решить можно вот так:
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
#include <fstream>
using namespace std;
 
 
long stairs(int n, long l)
{
    long s = long(n == 0);
    while(l < n)
    {
        l++;
        s += stairs(n - l, l);
    }
    return s;
}
void main()
{
    long n;
 
    ofstream g("output.txt");
    ifstream f("input.txt");
 
    f >> n;
    g << stairs(n, 0);
}
но я не совсем уверен в этом решений
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2011, 15:51
Привет! Вот еще темы с ответами:

рекурсия - C++
#include &lt;iostream&gt; #include &lt;windows.h&gt; using namespace std; void someFunction ( int , int, int ); int main () { ...

Рекурсия - C++
Как переделать программу в рекурсию? char S='S', T='T', M={NULL}; int ST=5,i=0,j=0; int TS; void Per() { M=S; ...

Рекурсия - C++
Есть функция, в нее передается массив из n элементов. Функция находит минимальный элемент и считает сколько раз он встречается в массиве,...

Рекурсия - C++
не знаю как это сделать..помогите


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

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

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