Как реализовать рекурсией n вложенных циклов с определенным условием? - Общие вопросы C/C++

aleksey95 · 20.07.2021, 08:40

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

Код:

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: 
//функция рекурсии
}

Алексей1153 · 20.07.2021, 18:36

aleksey95, расскажи словами, что должно делаться в этом коде

aleksey95 · 22.07.2021, 23:56

Это перебор для целевой функции и ограничений. Но, если в классическом переборе переменные умножаются на булевой вектор, то в этом случае мы делим набор переменных на 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 получается)
Когда все забито, переходим к коду, который я привел.
Для каждого набора z перебираем все возможные варианты. При этом складывая соответствующие суммы F между собой, получается sum. Если sum меньше либо равно, чем было, пропускаем этот вариант, а если больше, то проверяем сумму ограничений limit(ограничений может быть больше, чем одно). Если все в порядке, то запоминаем ответ.
Если переменных много, и мы разделили на множество модулей, то может понадобится множество циклов. Я написал 127 вариантов для каждого количества модулей, больше нельзя потому что с++ не разрешает больше циклов. Поэтому думал, что можно как-то сделать более универсальное решение благодаря рекурсии, тогда можно делить на большее количество модулей и будет больше циклов и кода меньше ( сейчас варианты от 2 до 127 занимают 55 тысяч строк.

BDA · 23.07.2021, 00:37

Кажется, в вашем коде опечатки в индексах есть, например, "sum=moduleArray[0].F[i1]+moduleArray[1].F[i1];" два раза i1. А в чем выгода от разделения на модули, если потом это всё обсчитывается кучей вложенных циклов?

aleksey95 · 23.07.2021, 19:25

Да, действительно, опечатка, я извиняюсь. Вот как я реализовал 120 циклов:

Код:

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);
}

Выгода в чем я не знаю) руководитель проводит работу и сказал мне это реализовать. Вот мучаюсь. Никак не получалось написать рекурсию, я тогда решил написать "в лоб". Я еще подумал, на самом деле можно выкрутиться опять же "в лоб" от ограничений в 127 массивов: просто сделать больше функций, но тогда код будет ужасный и занимать еще больше места. Когда реализовывал рекурсию, то пытался sum присвоить 0, а потом прибавлять соответствующие F, но это не заработало.

Алексей1153 · 23.07.2021, 19:44

Цитата:

Сообщение от aleksey95

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++)

я так понимаю, эти вложенные циклы - это полный перебор всех сочетаний членов всех уравнений системы?

//например, два уравнения, три члена в каждом

Код:

std::vector<std::vector<uint8_t>> enumerator={{0,0,0,},{0,0,1,}};

перебор сводится к перебору сочетаний единичек, то есть, по сути, представляем себе двоичное число 000001 и инкрементируем его до упора

когда будет удобный прототип перебора, можно (если вдруг понадобится оптимизация по скорости) перейти от двумерного вектора к битсету (std::bitset) или вообще к набору переменных типа uint64_t

а там потом и вовсе завернуть в шаблоны, чтобы сократить размеры портянки кода (чтобы не вручную портянку набивать, а предоставить это компилятору при инстанцировании шаблонов)

BDA · 23.07.2021, 19:50

Все GetTempResultVector можно заменить на один:

Код:

void GetTempResultVector(int modules, Module* moduleArray, bool* tempResultingVector, int* massI)
{
    int k = 0;
    for (int s = 0; s < modules; s++)
        for (int j1 = 0; j1 < moduleArray[s].variableNumber; j1++)
        {
            tempResultingVector[k] = moduleArray[s].vector[massI[s]][j1];
            k++;
        }
}

"int* massI = new int[modules];" делать один раз перед циклами, а освобождать после циклов, а внутри только заполнять индексами.

aleksey95 · 24.07.2021, 03:28

Я не могу понять как присвоить 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]; Это возможно? По сути задача создания рекурсии сводится к этому.

aleksey95 · 24.07.2021, 03:31

Цитата:

Сообщение от BDA

Все GetTempResultVector можно заменить на один:

Код:

void GetTempResultVector(int modules, Module* moduleArray, bool* tempResultingVector, int* massI)
{
    int k = 0;
    for (int s = 0; s < modules; s++)
        for (int j1 = 0; j1 < moduleArray[s].variableNumber; j1++)
        {
            tempResultingVector[k] = moduleArray[s].vector[massI[s]][j1];
            k++;
        }
}

"int* massI = new int[modules];" делать один раз перед циклами, а освобождать после циклов, а внутри только заполнять индексами.

Да, спасибо, я уже потом это понял и изменил, чтобы сократить размер. Код находится в процессе обработки еще)

aleksey95 · 24.07.2021, 03:45

Цитата:

Сообщение от Алексей1153

я так понимаю, эти вложенные циклы - это полный перебор всех сочетаний членов всех уравнений системы?

//например, два уравнения, три члена в каждом

Код:

std::vector<std::vector<uint8_t>> enumerator={{0,0,0,},{0,0,1,}};

перебор сводится к перебору сочетаний единичек, то есть, по сути, представляем себе двоичное число 000001 и инкрементируем его до упора

когда будет удобный прототип перебора, можно (если вдруг понадобится оптимизация по скорости) перейти от двумерного вектора к битсету (std::bitset) или вообще к набору переменных типа uint64_t

а там потом и вовсе завернуть в шаблоны, чтобы сократить размеры портянки кода (чтобы не вручную портянку набивать, а предоставить это компилятору при инстанцировании шаблонов)

модули я делал так:брал число, прибавлял единицу, переводил в двоичное число и получал суммы целевых функций и ограничений. Код, который я привел, уже имеет посчитанные вектора, целевые функции и ограничения. Самая главная оптимизация для меня - это возможность реализовать рекурсию. Я не могу понять как сделать присвоение sum без использования сложения. Также и с limit. То есть как записать эти выражения в рекурсию, если это возможно. Для немного другой задачи у меня это получилось, но там используются сложения, например:

Код:

sum=0;
			for(int k=0;k<modules;k++)
			{
				sum+=tempF[k][h1[k]];
				numberOfAdditionOperations++;
			}

А тут, видимо, нужно только присвоение, иначе происходит ошибка. А, может, и можно тоже использовать сложение, только я не понимаю как его реализовать в рекурсии для этой задачи.

20.07.2021, 18:36	#2
Алексей1153 фрилансер, препод. Участник клуба Регистрация: 11.10.2019 Сообщений: 1,043	aleksey95, расскажи словами, что должно делаться в этом коде https://programmersforum.ru/showthread.php?t=337821

23.07.2021, 00:37	#4
BDA МегаМодератор СуперМодератор Регистрация: 09.11.2010 Сообщений: 7,429	Кажется, в вашем коде опечатки в индексах есть, например, "sum=moduleArray[0].F[i1]+moduleArray[1].F[i1];" два раза i1. А в чем выгода от разделения на модули, если потом это всё обсчитывается кучей вложенных циклов? Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

23.07.2021, 19:50	#7
BDA МегаМодератор СуперМодератор Регистрация: 09.11.2010 Сообщений: 7,429	Все GetTempResultVector можно заменить на один: Код: `void GetTempResultVector(int modules, Module* moduleArray, bool* tempResultingVector, int* massI) { int k = 0; for (int s = 0; s < modules; s++) for (int j1 = 0; j1 < moduleArray[s].variableNumber; j1++) { tempResultingVector[k] = moduleArray[s].vector[massI[s]][j1]; k++; } }` "int* massI = new int[modules];" делать один раз перед циклами, а освобождать после циклов, а внутри только заполнять индексами. Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись ) Последний раз редактировалось BDA; 23.07.2021 в 19:53.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Выход из глубоко вложенных циклов	SAMOUCHKA	Общие вопросы C/C++	6	08.09.2013 21:00
Программа си ++ с использованием вложенных циклов.	misha.markov	Помощь студентам	0	08.11.2012 19:57
Программирование вложенных циклов	vanek1	Помощь студентам	2	28.11.2010 12:11
с использованием вложенных циклов	вкусняшка	Помощь студентам	4	31.03.2009 17:22
переменное число вложенных циклов	Evil Sun	Общие вопросы C/C++	4	31.03.2009 09:59

22.07.2021, 23:56	#3
aleksey95 Регистрация: 20.07.2021 Сообщений: 9	Это перебор для целевой функции и ограничений. Но, если в классическом переборе переменные умножаются на булевой вектор, то в этом случае мы делим набор переменных на 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 получается) Когда все забито, переходим к коду, который я привел. Для каждого набора z перебираем все возможные варианты. При этом складывая соответствующие суммы F между собой, получается sum. Если sum меньше либо равно, чем было, пропускаем этот вариант, а если больше, то проверяем сумму ограничений limit(ограничений может быть больше, чем одно). Если все в порядке, то запоминаем ответ. Если переменных много, и мы разделили на множество модулей, то может понадобится множество циклов. Я написал 127 вариантов для каждого количества модулей, больше нельзя потому что с++ не разрешает больше циклов. Поэтому думал, что можно как-то сделать более универсальное решение благодаря рекурсии, тогда можно делить на большее количество модулей и будет больше циклов и кода меньше ( сейчас варианты от 2 до 127 занимают 55 тысяч строк.

24.07.2021, 03:28	#8
aleksey95 Регистрация: 20.07.2021 Сообщений: 9	Я не могу понять как присвоить 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]; Это возможно? По сути задача создания рекурсии сводится к этому.