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

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

Восстановить пароль Регистрация
 
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
07.02.2011, 12:40     Рекурсия, ошибка #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:40     Рекурсия, ошибка
Посмотрите здесь:

Рекурсия C++
Рекурсия C++
C++ Рекурсия
Рекурсия C++
Рекурсия C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
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
 Аватар для zulkis
681 / 608 / 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
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
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
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2011, 15:51     Рекурсия, ошибка
Еще ссылки по теме:

C++ Рекурсия
C++ Рекурсия
Подскажите в чем ошибка в моей программе (рекурсия) C++

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

Или воспользуйтесь поиском по форуму:
Wanee
52 / 52 / 13
Регистрация: 02.02.2011
Сообщений: 428
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);
}
но я не совсем уверен в этом решений
Yandex
Объявления
07.02.2011, 15:51     Рекурсия, ошибка
Ответ Создать тему
Опции темы

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