|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.07.2021, 08:40 | #1 |
Регистрация: 20.07.2021
Сообщений: 9
|
Как реализовать рекурсией n вложенных циклов с определенным условием?
Здравствуйте! Не получается реализовать рекурсию для n вложенных циклов. Помогите пожалуйста, если это вообще возможно реализовать.
Код:
Последний раз редактировалось aleksey95; 20.07.2021 в 18:11. |
20.07.2021, 18:36 | #2 |
фрилансер
Участник клуба
Регистрация: 11.10.2019
Сообщений: 1,010
|
aleksey95, расскажи словами, что должно делаться в этом коде
|
22.07.2021, 23:56 | #3 |
Регистрация: 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 тысяч строк. |
23.07.2021, 00:37 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,341
|
Кажется, в вашем коде опечатки в индексах есть, например, "sum=moduleArray[0].F[i1]+moduleArray[1].F[i1];" два раза i1. А в чем выгода от разделения на модули, если потом это всё обсчитывается кучей вложенных циклов?
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
23.07.2021, 19:25 | #5 |
Регистрация: 20.07.2021
Сообщений: 9
|
Да, действительно, опечатка, я извиняюсь. Вот как я реализовал 120 циклов:
Код:
|
23.07.2021, 19:44 | #6 | |
фрилансер
Участник клуба
Регистрация: 11.10.2019
Сообщений: 1,010
|
Цитата:
//например, два уравнения, три члена в каждом Код:
когда будет удобный прототип перебора, можно (если вдруг понадобится оптимизация по скорости) перейти от двумерного вектора к битсету (std::bitset) или вообще к набору переменных типа uint64_t а там потом и вовсе завернуть в шаблоны, чтобы сократить размеры портянки кода (чтобы не вручную портянку набивать, а предоставить это компилятору при инстанцировании шаблонов) |
|
23.07.2021, 19:50 | #7 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,341
|
Все GetTempResultVector можно заменить на один:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
Последний раз редактировалось BDA; 23.07.2021 в 19:53. |
24.07.2021, 03:28 | #8 |
Регистрация: 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]; Это возможно? По сути задача создания рекурсии сводится к этому.
|
24.07.2021, 03:31 | #9 | |
Регистрация: 20.07.2021
Сообщений: 9
|
Цитата:
|
|
24.07.2021, 03:45 | #10 | |
Регистрация: 20.07.2021
Сообщений: 9
|
Цитата:
Код:
Последний раз редактировалось aleksey95; 24.07.2021 в 03:48. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Выход из глубоко вложенных циклов | 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 |