Как реализовать рекурсией n вложенных циклов с определенным условием?

@alekseja · Регистрация: 25.06.2017

Студворк — интернет-сервис помощи студентам

Здравствуйте! Не получается реализовать рекурсию для n вложенных циклов. Помогите пожалуйста, если это вообще возможно реализовать.

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
 switch(modules)
    {
    case 2:
        for(int i1=0; i1<pow(2.0,moduleArray[0].variableNumber);i1++)
            for(int i2=0; i2<pow(2.0,moduleArray[1].variableNumber);i2++)
            {
                sum=moduleArray[0].F[i1]+moduleArray[1].F[i1];if((maxMin && sum<=max) || (!maxMin && sum>=min)) continue;
                for(int j1=1;j1<rowsNumber;j1++)
                {
                    limit[j1]=moduleArray[0].L[i1][j1-1]+moduleArray[1].L[i1][j1-1];numberOfAdditionOperations+=1;
                }
                bool ok=true;
                for(int j=1;j<rowsNumber;j++)
                {
                    if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==1 && limit[j]<=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                    else
                        if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==0 && limit[j]>=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                        else
                            ok = false;
                }
                int k=0;
                if(ok)
                {
                    max=sum;
                    for(int j1=0;j1<moduleArray[0].variableNumber;j1++)
                    {
                        tempResultingVector[k]=moduleArray[0].vector[i1][j1];
                        k++;
                    }
                    for(int j1=0;j1<moduleArray[1].variableNumber;j1++)
                    {
                        tempResultingVector[k]=moduleArray[1].vector[i2][j1];
                        k++;
                    }
                }
            }
            break;
    case 3:
        for(int i1=0; i1<pow(2.0,moduleArray[0].variableNumber);i1++)
            for(int i2=0; i2<pow(2.0,moduleArray[1].variableNumber);i2++)
                for(int i3=0; i3<pow(2.0,moduleArray[2].variableNumber);i3++)
                {
                    sum=moduleArray[0].F[i1]+moduleArray[1].F[i2]+moduleArray[2].F[i2];if((maxMin && sum<=max) || (!maxMin && sum>=min)) continue;
                    for(int j1=1;j1<rowsNumber;j1++)
                    {
                        limit[j1]=moduleArray[0].L[i1][j1-1]+moduleArray[1].L[i2][j1-1]+moduleArray[2].L[i2][j1-1];numberOfAdditionOperations+=2;
                    }
                    bool ok=true;
                    for(int j=1;j<rowsNumber;j++)
                    {
                        if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==1 && limit[j]<=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                        else
                            if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==0 && limit[j]>=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                            else
                                ok = false;
                    }
                    int k=0;
                    if(ok)
                    {
                        max=sum;
                        for(int j1=0;j1<moduleArray[0].variableNumber;j1++)
                        {
                            tempResultingVector[k]=moduleArray[0].vector[i1][j1];
                            k++;
                        }
                        for(int j1=0;j1<moduleArray[1].variableNumber;j1++)
                        {
                            tempResultingVector[k]=moduleArray[1].vector[i2][j1];
                            k++;
                        }
                        for(int j1=0;j1<moduleArray[2].variableNumber;j1++)
                        {
                            tempResultingVector[k]=moduleArray[2].vector[i3][j1];
                            k++;
                        }
                    }
                }
                break;
//case n: 
//функция рекурсии
}

@alekseja · 23.07.2021, 19:36 **[ТС]**

Выше небольшие опечатки в индексах. У меня так и не получилось сделать рекурсию, поэтому написал "в лоб" варианты от 2 до 120 вложенных циклов. Код получился ужасный. И ограничение в 127 циклов и условий не дают сделать больше.

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
void GetTempResultVector1(Module* moduleArray,bool* tempResultingVector, int* massI)
{
    int k=0;
    int s=0;
    for(int j1=0;j1<moduleArray[0].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[0].vector[massI[s]][j1];
        k++;
    }
    s++;
    for(int j1=0;j1<moduleArray[1].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[1].vector[massI[s]][j1];
        k++;
    }
    s++;
}
void Array1(int modules,double* conditionalMatrix, Module* moduleArray,  int columnsNumber, int rowsNumber, double& max,double& min, bool maxMin,  long long& numberOfAdditionOperations, bool* tempResultingVector)
{
    double sum;
    double* limit = new double[rowsNumber];
    for(int i1=0; i1<pow(2.0,moduleArray[0].variableNumber);i1++)
        for(int i2=0; i2<pow(2.0,moduleArray[1].variableNumber);i2++)
        {
            sum=moduleArray[0].F[i1]+moduleArray[1].F[i2];
            if((maxMin && sum<=max) || (!maxMin && sum>=min)) continue;
            for(int j1=1;j1<rowsNumber;j1++)
            {
                limit[j1]=moduleArray[0].L[i1][j1-1]+moduleArray[1].L[i2][j1-1];numberOfAdditionOperations+=1;
            }
            bool ok=true;
            for(int j=1;j<rowsNumber;j++)
            {
                if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==1 && limit[j]<=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                else
                    if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==0 && limit[j]>=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                    else
                        ok = false;
            }
            int* massI = new int[modules];
            massI[0]=i1;massI[1]=i2;
            if(ok)
            {
                max=sum;
                GetTempResultVector1(moduleArray, tempResultingVector,massI);
            }
            delete[] massI;
        }
        delete[] limit;
}
void GetTempResultVector2(Module* moduleArray,bool* tempResultingVector, int* massI)
{
    int k=0;
    int s=0;
    for(int j1=0;j1<moduleArray[0].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[0].vector[massI[s]][j1];
        k++;
    }
    s++;
    for(int j1=0;j1<moduleArray[1].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[1].vector[massI[s]][j1];
        k++;
    }
    s++;
    for(int j1=0;j1<moduleArray[2].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[2].vector[massI[s]][j1];
        k++;
    }
    s++;
}
void Array2(int modules,double* conditionalMatrix, Module* moduleArray,  int columnsNumber, int rowsNumber, double& max,double& min, bool maxMin,  long long& numberOfAdditionOperations, bool* tempResultingVector)
{
    double sum;
    double* limit = new double[rowsNumber];
    for(int i1=0; i1<pow(2.0,moduleArray[0].variableNumber);i1++)
        for(int i2=0; i2<pow(2.0,moduleArray[1].variableNumber);i2++)
            for(int i3=0; i3<pow(2.0,moduleArray[2].variableNumber);i3++)
            {
                sum=moduleArray[0].F[i1]+moduleArray[1].F[i2]+moduleArray[2].F[i3];
                if((maxMin && sum<=max) || (!maxMin && sum>=min)) continue;
                for(int j1=1;j1<rowsNumber;j1++)
                {
                    limit[j1]=moduleArray[0].L[i1][j1-1]+moduleArray[1].L[i2][j1-1]+moduleArray[2].L[i3][j1-1];numberOfAdditionOperations+=2;
                }
                bool ok=true;
                for(int j=1;j<rowsNumber;j++)
                {
                    if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==1 && limit[j]<=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                    else
                        if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==0 && limit[j]>=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                        else
                            ok = false;
                }
                int* massI = new int[modules];
                massI[0]=i1;massI[1]=i2;massI[2]=i3;
                if(ok)
                {
                    max=sum;
                    GetTempResultVector2(moduleArray, tempResultingVector,massI);
                }
                delete[] massI;
            }
            delete[] limit;
}
void GetTempResultVector3(Module* moduleArray,bool* tempResultingVector, int* massI)
{
    int k=0;
    int s=0;
    for(int j1=0;j1<moduleArray[0].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[0].vector[massI[s]][j1];
        k++;
    }
    s++;
    for(int j1=0;j1<moduleArray[1].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[1].vector[massI[s]][j1];
        k++;
    }
    s++;
    for(int j1=0;j1<moduleArray[2].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[2].vector[massI[s]][j1];
        k++;
    }
    s++;
    for(int j1=0;j1<moduleArray[3].variableNumber;j1++)
    {
        tempResultingVector[k]=moduleArray[3].vector[massI[s]][j1];
        k++;
    }
    s++;
}
void GetResultArray(int modules,double* conditionalMatrix, Module* moduleArray,  int columnsNumber, int rowsNumber, double& max,double& min, bool maxMin,  long long& numberOfAdditionOperations, bool* tempResultingVector)
{
void GetResultArray(int modules,double* conditionalMatrix, Module* moduleArray,  int columnsNumber, int rowsNumber, double& max,double& min, bool maxMin,  long long& numberOfAdditionOperations, bool* tempResultingVector)
{
    switch(modules)
    {
    case 2:
        Array1( modules,conditionalMatrix, moduleArray, columnsNumber,rowsNumber, max,min,  maxMin,   numberOfAdditionOperations,  tempResultingVector);
        break;
    case 3:
        Array2( modules,conditionalMatrix, moduleArray, columnsNumber,rowsNumber, max,min,  maxMin,   numberOfAdditionOperations,  tempResultingVector);
        break;
...
         case 120:
                 Array119( modules,conditionalMatrix, moduleArray, columnsNumber,rowsNumber, max,min,  maxMin,   numberOfAdditionOperations,  tempResultingVector);
}

Вот код без опечаток. Но рекурсию реализовать так и не получилось.
Вообще это перебор для целевой функции и ограничений. Но, если в классическом переборе переменные умножаются на булевой вектор, то в этом случае мы делим набор переменных на n частей (ModuleArray). Например: система вида
7z1+5z2+6z3+1z4->max
6z1+9z2+4z3+1z4<=10
вместо zn мы перебираем {0,0,0,0},{0,0,0,1},{0,0,1,0} и так далее до нахождения наилучшего ответа.
А в моем варианте мы разбиваем, например, на 2 модуля, затем находим их суммы и ограничения, все забиваем в массив структуры ModuleArray для каждого модуля: F-суммы, L-ограничения, vector- вектор всех вариантов, variableNumber- количество переменных в модуле (в данном случае по 2 в каждой). Как выглядит первый модуль:
vector={0,0};{0,1};{1;0};{1;1}
F=0;5;7;12
L=0;9;6;15
variableNumber=2; (всего вариантов перебора 2^2 получается)
Второй модуль:
vector={0,0};{0,1};{1;0};{1;1}
F=0;1;6;7
L=0;1;4;5
variableNumber=2;
Когда все забито, переходим к коду, который я привел.
Для каждого набора z перебираем все возможные варианты. При этом складывая соответствующие суммы F между собой, получается sum. Если sum меньше либо равно, чем было, пропускаем этот вариант, а если больше, то проверяем сумму ограничений limit(ограничений может быть больше, чем одно). Если все в порядке, то запоминаем ответ.
Если переменных много, и мы разделили на множество модулей, то может понадобится множество циклов. Я написал 127 вариантов для каждого количества модулей, больше нельзя потому что с++ не разрешает больше циклов. Поэтому думал, что можно как-то сделать более универсальное решение благодаря рекурсии, тогда можно делить на большее количество модулей и будет больше циклов и кода меньше ( сейчас варианты от 2 до 120 занимают 55 тысяч строк.

@alekseja · 24.07.2021, 03:25 **[ТС]**

Я не могу понять как присвоить sum=moduleArray[0].F[i1]+moduleArray[1].F[i2]+moduleArray[2].F[i3]; в рекурсии. То же самое обстоит и с limit[j1]=moduleArray[0].L[i1][j1-1]+moduleArray[1].L[i2][j1-1]+moduleArray[2].L[i3][j1-1]; Это возможно?

@Kuzia domovenok · 24.07.2021, 21:31

мне не нравится это читать.
Почему так много букв?
почему всё в одной функции навалено?
почему двойка возводится в степень не оператором сдвига?
почему некоторые строки написаны по несколько выражений в одной строчке?
почему conditionalMatrix это не двумерный массив?
зачем всё так сложно в простой задаче (хоть я и не знаю условия)?

@alekseja · 24.07.2021, 22:44 **[ТС]**

Потому что это не идеальный код) А решение я нашел сам:

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
void ArrayN1(int modules,double* conditionalMatrix, Module* moduleArray,  int columnsNumber, int rowsNumber, double& max, double& min, bool maxMin,  long long& numberOfAdditionOperations, bool* tempResultingVector,double* limit, int cycle,int* i)
{
    double sum;
 
    if(cycle<modules)
        while(i[cycle]<pow(2.0,moduleArray[cycle].variableNumber))
        {
            if(cycle<modules-1)
                i[cycle+1]=0;
            if(cycle<modules)
                ArrayN1(modules, conditionalMatrix,moduleArray, columnsNumber, rowsNumber,max,min,maxMin,numberOfAdditionOperations,tempResultingVector,limit,cycle+1,i);
            if(cycle==modules-1)
            {
                sum=0;
                for(int k=0;k<modules;k++)
                {                   
                    {
                        sum+=moduleArray[k].F[i[k]];
                        numberOfAdditionOperations++;
                    }
                }
 
                if((maxMin && sum<=max) || (!maxMin && sum>=min)) 
                {i[cycle]++;
                continue; }
 
                for(int j1=1;j1<rowsNumber;j1++)
                    limit[j1]=0;
                for(int m=0;m<modules;m++)
                {
                    for(int j1=1;j1<rowsNumber;j1++)
                    {
 
                        limit[j1]+=moduleArray[m].L[i[m]][j1-1];
                        numberOfAdditionOperations++;
                    }
                }
                bool ok=true;
                for(int j=1;j<rowsNumber;j++)
                {
                    if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==1 && limit[j]<=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                    else
                        if(conditionalMatrix[(j)*columnsNumber+columnsNumber-2]==0 && limit[j]>=conditionalMatrix[(j)*columnsNumber+columnsNumber-1]) continue;
                        else
                            ok = false;
                }
 
                if(ok)
                {
                    max=sum;
                    min=sum;
                    GetTempResultVector2(moduleArray, tempResultingVector,i);
                }
 
                i[cycle]++;
            }
            else
                i[cycle]++;
        }
}

Добавлено через 15 минут
Использовал в рекурсии цикл while вместо for и завел массив i размером с число циклов и в нем хранил уже перебираемые переменные.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@alekseja 0 / 0 / 0 Регистрация: 25.06.2017 Сообщений: 8
	24.07.2021, 03:25 [ТС]
	Я не могу понять как присвоить sum=moduleArray[0].F[i1]+moduleArray[1].F[i2]+moduleArray[2].F[i3]; в рекурсии. То же самое обстоит и с limit[j1]=moduleArray[0].L[i1][j1-1]+moduleArray[1].L[i2][j1-1]+moduleArray[2].L[i3][j1-1]; Это возможно? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	24.07.2021, 21:31
	мне не нравится это читать. Почему так много букв? почему всё в одной функции навалено? почему двойка возводится в степень не оператором сдвига? почему некоторые строки написаны по несколько выражений в одной строчке? почему conditionalMatrix это не двумерный массив? зачем всё так сложно в простой задаче (хоть я и не знаю условия)? 0