Форум программистов
 
Регистрация на форуме тут, о проблемах пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Как купить рекламу на форуме


Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме 20000 рублей в месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.07.2021, 08:40   #1
aleksey95
 
Регистрация: 20.07.2021
Сообщений: 9
По умолчанию Как реализовать рекурсией n вложенных циклов с определенным условием?

Здравствуйте! Не получается реализовать рекурсию для 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: 
//функция рекурсии
}

Последний раз редактировалось aleksey95; 20.07.2021 в 18:11.
aleksey95 вне форума Ответить с цитированием
Старый 20.07.2021, 18:36   #2
Алексей1153
фрилансер
Форумчанин
 
Регистрация: 11.10.2019
Сообщений: 530
По умолчанию

aleksey95, расскажи словами, что должно делаться в этом коде
Алексей1153 вне форума Ответить с цитированием
Старый 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 тысяч строк.
aleksey95 вне форума Ответить с цитированием
Старый 23.07.2021, 00:37   #4
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 6,173
По умолчанию

Кажется, в вашем коде опечатки в индексах есть, например, "sum=moduleArray[0].F[i1]+moduleArray[1].F[i1];" два раза i1. А в чем выгода от разделения на модули, если потом это всё обсчитывается кучей вложенных циклов?
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Старый 23.07.2021, 19:25   #5
aleksey95
 
Регистрация: 20.07.2021
Сообщений: 9
По умолчанию

Да, действительно, опечатка, я извиняюсь. Вот как я реализовал 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, но это не заработало.
aleksey95 вне форума Ответить с цитированием
Старый 23.07.2021, 19:44   #6
Алексей1153
фрилансер
Форумчанин
 
Регистрация: 11.10.2019
Сообщений: 530
По умолчанию

Цитата:
Сообщение от 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

а там потом и вовсе завернуть в шаблоны, чтобы сократить размеры портянки кода (чтобы не вручную портянку набивать, а предоставить это компилятору при инстанцировании шаблонов)
Алексей1153 вне форума Ответить с цитированием
Старый 23.07.2021, 19:50   #7
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 6,173
По умолчанию

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

Цитата:
Сообщение от 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   #10
aleksey95
 
Регистрация: 20.07.2021
Сообщений: 9
По умолчанию

Цитата:
Сообщение от Алексей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++;
			}
А тут, видимо, нужно только присвоение, иначе происходит ошибка. А, может, и можно тоже использовать сложение, только я не понимаю как его реализовать в рекурсии для этой задачи.

Последний раз редактировалось aleksey95; 24.07.2021 в 03:48.
aleksey95 вне форума Ответить с цитированием
Ответ
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


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


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS