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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
05.02.2010, 09:40     Рекурсия от рекурсии #1
Люди, помогите! Я в с++ относительно недавно, в паскале-делфи никаких проблем не было. Значит мне нужно:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int pekypc()
{
    ...
    int pekypc()
    ...
}
 
int main()
{
    ...
    int pekypc()
    ...
}
Но когда я пишу в маине и начинаю пошагово смотреть результаты через вотч, он делает какую-то ересь а по самой функции не идет. Работую в c++ Builder(если это имеет значение)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2010, 09:40     Рекурсия от рекурсии
Посмотрите здесь:

рекурсии... C++
C++ С Использованием рекурсии!
C++ Рекурсии.
Вопрос по рекурсии C++
Корректировка в рекурсии C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
05.02.2010, 09:49     Рекурсия от рекурсии #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int pekypc()
{
    ...
    pekypc()
    ...
}
 
int main()
{
    ...
    pekypc()
    ...
}
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
05.02.2010, 10:03  [ТС]     Рекурсия от рекурсии #3
Ну в смысле да. Если интересно вот код:

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
int a[8];
int b[8][8];
int i,n,m,k,l1,l2,s,g,j;
 
int re(int &step)
{
    if(step==(n-1))
    {
        s++;
    }
    else
    {
        for(i=0;i<n;i++)
        {
            a[step]=i;
            g=0;
            for(j=0;j<step;j++)
            {
                if (b[j][step]==1)
                {
                    if (a[j]==a[i]) g++;
                }
                if (g==0)
                {
                    re(step+1);
                }
            }
        }
    }
    return 0;
}
 
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
 
int main()
{
    in >>n >>k >>m;
    if(m>0)
    {
        for(i=0;i<m;i++)
        {
            in >>l1 >>l2;
            b[l1-1][l2-1]++;
            b[l2-1][l1-1]++;
        }
    }
    for(i=0;i<n;i++)
    {
        a[i]=-1;
    }
    a[0]=0;
    s=0;
    re(0);
    s=s*k;
    out <<s;
    return 0;
}
задача такая: сделать гирлянду с n шариками и m цветами, в которые можно покрасить шарики, но так чтобы шарики, соединенные проводами, были окрашены в разные цвета.

Добавлено через 4 минуты
В вотче она почему-то на тесте:
4 4 6
1 2
1 3
1 4
2 3
2 4
3 4
с массивом а делает а[1]=3(?), a[2]=-1,a[3]=-1;a[4]=-1; s как и было, так нулем и осталась.

Добавлено через 1 минуту
Самого прохода по рекурсии в вотче я так и не видел
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
05.02.2010, 10:46     Рекурсия от рекурсии #4
C++
1
int re(int &step)
C++
1
int re(int step)
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
05.02.2010, 10:47  [ТС]     Рекурсия от рекурсии #5
пробовал x^8 через рекурсию сделать:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int x,step;
 
int pekypc(&step)
{
    if (step<3)
    {
        x*=x;
        pekypc(step+1);
    }
return x;
}
 
int main()
{
    cin >>x;
    pekypc(0);
    cout <<x;
}
Лажа получается

Добавлено через 57 секунд
Цитата Сообщение от accept Посмотреть сообщение
C++
1
int re(int &step)
C++
1
int re(int step)
И так и так делал
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
05.02.2010, 11:29     Рекурсия от рекурсии #6
в смысле заменить
C++
1
int re(int &step)
неправильно
когда
C++
1
pekypc(0)
Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
int pekypc(&step)
{
    if (step<3)
    {
        x*=x;
        pekypc(step+1);
    }
return x;
}
так тоже неправильно
C++ не поддерживает неявный int

Добавлено через 11 минут
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
 
int r(int x, int pow);
 
int main(void) /* C89 ANSI */
{
    
    printf("%d" "\n", r(3, 4));
    
    exit(EXIT_SUCCESS);
}
 
int r(int x, int pow)
{
    if (pow <= 0)
        return 1;
    return x*r(x, pow-1);
}
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
05.02.2010, 17:33  [ТС]     Рекурсия от рекурсии #7
Не совсем вкурил. Где у меня неявный int? Вместо нуля нужно сделать так, что ли?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int pekypc(int &step)
{
    ...
    pekypc(step+1);
    ....
}
 
int main()
{
    ...
    int x=0;
    pekypc(x)
    ...
}
так, что ли?

Добавлено через 28 минут
Фишка в том, что вместо нуля нужно написать переменную?

Добавлено через 1 час 20 минут
Никто вообще подобной темой не задавался? Никто qsort сам не писал в сишке?
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
05.02.2010, 18:06     Рекурсия от рекурсии #8
Цитата Сообщение от JKeeJ1e30 Посмотреть сообщение
Фишка в том, что вместо нуля нужно написать переменную?
да. т.к. в прототипе функции у тебя не константная ссылка.
Цитата Сообщение от JKeeJ1e30 Посмотреть сообщение
int pekypc(int &step)
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.02.2010, 02:30     Рекурсия от рекурсии #9
Цитата Сообщение от JKeeJ1e30
Никто qsort сам не писал в сишке?
в K & R есть упражнение
и на qsort и на bsearch
сначала дают основу, потом в упражнении задают доработать
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
06.02.2010, 13:42  [ТС]     Рекурсия от рекурсии #10
Так вроде че-то пошло. Один раз я видел как в вотче шла рекурсия. Нашел ошибку, кое-что заменил. Но после этого я опять перестал видеть как именно и что идет в вотче по рекурсии. Вот новый исходник проги:

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
#include <vcl.h>
#pragma hdrstop
#include <fstream> 
#include <cmath>
 
int a[8];
int b[8][8];
int i,n,m,k,l1,l2,s,g,j;
 
int re(int step)
{
    int x;
    if(step==(n-1))
    {
        s++;
    }
    else
    {
        for(i=0;i<n;i++)
        {
            a[step]=i;
            g=0;
            for(j=0;j<step;j++)
            {
                if (b[j][step]==1)
                {
                    if (a[j]==a[i]) g++;
                }
            }
            if (g==0)
            {
                x=step;
                x++;
                re(x);
            }
        }
    }
    return s;
}
 
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
 
int main()
{
    in >>n >>k >>m;
    if(m>0)
    {
        for(i=0;i<m;i++)
        {
            in >>l1 >>l2;
            b[l1-1][l2-1]++;
            b[l2-1][l1-1]++;
        }
    }
    for(i=0;i<n;i++)
    {
        a[i]=-1;
    }
    a[0]=0;
    s=0;
    int step=0;
    re(step);
    s=s*k;
    out <<s;
    return 0;
}
Результат она стала выдавать более-менее приемлимый. Просто скажите мне, что нужно сделать чтобы я в вотче видел все проходы по рекурсии, все остальные блохи я сам выловлю

Добавлено через 2 часа 14 минут
Так как? Мне нужен вотч!!!!

Добавлено через 2 часа 5 минут
Так никто и не поможет?
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
06.02.2010, 15:55     Рекурсия от рекурсии #11
Цитата Сообщение от JKeeJ1e30 Посмотреть сообщение
Я лично не верю что за все эти годы которые существует с++ не было ни одного решения этой проблемы
волшебные слова: графы раскраска

Добавлено через 3 минуты
Цитата Сообщение от JKeeJ1e30 Посмотреть сообщение
Ты мораль мне читать будешь?
да
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
07.02.2010, 03:36     Рекурсия от рекурсии #12
Цитата Сообщение от JKeeJ1e30
Но после этого я опять перестал видеть как именно и что идет в вотче по рекурсии.
я рекурсию просматриваю через printf

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
int re(int step)
{
    int x;
    if(step==(n-1))
    {
        s++;
    }
    else
    {
        for(i=0;i<n;i++)
        {
            a[step]=i;
            g=0;
            for(j=0;j<step;j++)
            {
                if (b[j][step]==1)
                {
                    if (a[j]==a[i]) g++;
#ifdef 1
    printf(
        "a[i] = %d,"
        " a[j] = %d"
        " (i %d, j %d)"
        "\n",
        a[i],
        a[j],
        i,
        j
    ); 
#endif                
 
                }
            }
            if (g==0)
            {
                x=step;
                x++;
                re(x);
            }
        }
    }
    return s;
}
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
07.02.2010, 09:25  [ТС]     Рекурсия от рекурсии #13
accept, большущее спасибо
а всякие там "моралисты"...
ЗЫ: я как раз раскраску графа и пишу. Только там тайм лимит небольшой там можно по-старинке
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
07.02.2010, 11:30     Рекурсия от рекурсии #14
Цитата Сообщение от JKeeJ1e30 Посмотреть сообщение
сделать гирлянду с n шариками и m цветами, в которые можно покрасить шарики, но так чтобы шарики, соединенные проводами, были окрашены в разные цвета.
Если гирлянда линейная, то четные лампочки - один цвет, нечетные - второй. Если нелинейная, тогда примерно так
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
#include <iostream>
int main()
{
    setlocale(LC_ALL, "Russian");
    const int n(6);
    int i, j;
    int mi[n][n] = { 0, 1, 0, 1, 1, 0,
                         1, 0, 1, 1, 0, 0,
                         0, 1, 0, 1, 1, 1,
                         1, 1, 1, 0, 1, 0,
                         1, 0, 1, 1, 0, 1,
                         0, 0, 1, 0, 1, 0 };
 
    for(i = 0; i < n; ++i, std::cout<<std::endl)
        for(j = 0; j < n; ++j)
            std::cout<<mi[i][j]<<' ';
    int col[n];
    for(i = 0; i < n; ++i)
        col[i] = 1; 
    for(i = 0; i < n; ++i)
        for(j = i + 1; j < n - 1; ++j)
            if(mi[i][j] == 1 && col[j] == col[i])
                col[j] = col[i] + 1;
    int max = col[0];
    for(j = 1; j < n; ++j)
        if(max < col[j])
            max = col[j];
    std::cout<<"\nХроматическое число графа равно "<<max;
    fflush(stdin);
    std::cin.get();
    return 0;
}
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
07.02.2010, 12:11  [ТС]     Рекурсия от рекурсии #15
Спасибо большое я бы сам так сделал но нам сказано четко-решать перестановками Я бы сам так с большим удовольствием сделал бы

Добавлено через 40 секунд
А на перестановках если без рекурсии идти возникает тайм лимит

Добавлено через 24 минуты
Всем большущее спасибо(в том числе и Зиму(без сарказма)). Программа уже работает
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2010, 02:22     Рекурсия от рекурсии
Еще ссылки по теме:

Чем отличается хвостовая рекурсия от обычной рекурсии? C++
C++ Возврат рекурсии
Рекурсия без рекурсии C++

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

Или воспользуйтесь поиском по форуму:
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
08.02.2010, 02:22     Рекурсия от рекурсии #16
там я написал #ifdef 1, ошибся
надо #if 1
Yandex
Объявления
08.02.2010, 02:22     Рекурсия от рекурсии
Ответ Создать тему
Опции темы

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