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

Не могу разобраться с отработкой рекурсивной функции - C++

Восстановить пароль Регистрация
 
Fafle
 Аватар для Fafle
34 / 34 / 4
Регистрация: 19.03.2010
Сообщений: 136
15.03.2011, 12:35     Не могу разобраться с отработкой рекурсивной функции #1
Доброго времени суток.
Имеется функция находящая в первом массиве количество повторения второго массива:
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
#include <iostream>
using namespace std;
int size, num = 0;
 
int fc(int* ar1, int* ar2, int size1, int size2) {
    for (int j = size2 - 1; j >= 0; j--) {
        for (int i = size1 - 1; i >= 0; i--) {
            if (ar1[i] == ar2[j]) {
                if (j == 0) {
                    num++;
                    fc(ar1, ar2, i, size);
                }
                fc(ar1, ar2, i, j);
            }
            fc(ar1, ar2, i, size);
        }
    }
return num;
}
 
int main() {
    const int size1 = 10;
    const int size2 = 2;
    size = size2;
    int ar1[size1] = {4, 3, 3, 4, 3, 3, 4, 3, 3, 4}, ar2[size2] = {3, 4};
    cout<<fc(ar1, ar2, size1, size2)<<endl;
}
Надеюсь не слишком большая белиберда и никто здесь мозг не сломает
А проблема в том что вроде все и найс, но есть одно "но", после отработки циклов и срабатывания return следующей итерацией идет, по не известной мне причине, вызов 13й строки, может кто подскажет что не так?
Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.03.2011, 12:35     Не могу разобраться с отработкой рекурсивной функции
Посмотрите здесь:

C++ Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
C++ Не могу разобраться с отработкой циклов
Функции и файлы! Для продвинутых, я не могу разобраться. C++
C++ не могу разобраться с функциями ( значение функции, заданной с помощью ряда)
C++ не могу разобраться в функции
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dexter
 Аватар для Dexter
284 / 144 / 16
Регистрация: 13.10.2009
Сообщений: 164
15.03.2011, 13:22     Не могу разобраться с отработкой рекурсивной функции #2
1) Циклы там ненужны совсем
2) Нету else, потому после прохода ифа оно и заходит в следующую функцию.

Должно выглядеть где-то так:

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
int fc(int* ar1, int* ar2, int size1, int size2) {
    int j = size2 - 1;
    int i = size1 - 1;
    if(size1==0||size2==0)return num;
    if (ar1[i] == ar2[j]) {
        if (j == 0) 
        {
            num++;
            for(int k=0;k<size1+size-1;k++)//Добавил вывод на экран чтобы посмотреть правильно ли считает
                printf("%i ",ar1[k]);
            printf("\n");
            for(int k=0;k<size;k++)
                printf("%i ",ar2[k]);
            printf("\n\n");
            fc(ar1, ar2, i, size);
        }
        else
        fc(ar1, ar2, i, j);
    }
    else
    fc(ar1, ar2, i, size);
 
    return num;
}
Fafle
 Аватар для Fafle
34 / 34 / 4
Регистрация: 19.03.2010
Сообщений: 136
15.03.2011, 17:36  [ТС]     Не могу разобраться с отработкой рекурсивной функции #3
Спасибо огромное, ошибку уяснил, осталось выяснить ошибку в алгоритме вычисления, но это уже я сам

Добавлено через 3 часа 59 минут
Собственно функция получилась вот такой:
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
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int size3, num = 0, size4;
 
int fc(int* ar1, int* ar2, int size1, int size2) {
 
    int i = size1 - 1;
    int j = size2 - 1;
    if ((i == 0) && (j == 1))
        i++;
    if (i < 0)
        return num;
    if (ar1[i] == ar2[j]) {
        if (j == 0) {
            cout << i << endl;
            num++;
            fc(ar1, ar2, i, size3);
        } else {
            fc(ar1, ar2, i, j);
        }
    } else {
        size4--;
        //        cout<<size4<<endl;
        i = size4;
        fc(ar1, ar2, i, size3);
    }
}
 
int main() {
    srand(time(NULL));
    const int size1 = 10;
    const int size2 = 3;
    size3 = size2;
    size4 = size1;
    int ar1[size1], ar2[size2];
    //    int ar1[size1]={11,11,11,12,12,11,11,11,12,11};
    //    int ar2[size2]={11,11, 11};
    for (int i = 0; i < size1; i++) {
        ar1[i] = rand() % 2 + 11;
        cout << ar1[i] << "\t";
    }
    cout << endl;
    for (int i = 0; i < size2; i++) {
        ar2[i] = rand() % 2 + 11;
        cout << ar2[i] << "\t";
    }
    cout << endl;
 
    cout << endl << fc(ar1, ar2, size1, size2) << endl;
}
Но мне кажется как то криво написано, в чем я ошибаюсь или как можно оптимизировать этот код?
Dexter
 Аватар для Dexter
284 / 144 / 16
Регистрация: 13.10.2009
Сообщений: 164
15.03.2011, 18:33     Не могу разобраться с отработкой рекурсивной функции #4
Ну я бы наверное так написал, чтобы уйти от этих глобальных констант, да и короче выходит:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int fc(int* ar1, int* ar2, int size1, int size2,int pos1,int pos2,int all) {
 
    int res=0;
    if(size2>size1)return 0;
    if(ar1[pos1-1]==ar2[pos2-1])
        if(pos2==1)
            return 1;
        else
            res+=fc(ar1,ar2,size1,size2,pos1-1,pos2-1,0);
    if(all)res+=fc(ar1,ar2,size1-1,size2,size1-1,size2,1);
    return res;
}
 
....
cout << endl << fc(ar1, ar2, size1, size2,size1,size2,1) << endl;
Конечно, переменных больше, но это уже что кому больше нравится.
Yandex
Объявления
15.03.2011, 18:33     Не могу разобраться с отработкой рекурсивной функции
Ответ Создать тему
Опции темы

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