Harrix Блог

  • Списки статей
    • Все статьи
    • IT
    • Qt
    • C++
    • Сложение двух чисел
    • Web программированиe
    • FAQ
    • Latex
    • Установка программ
    • Мифы
    • Видео
    • Про фото
  • Проекты
  • Harrix.org
  • RSS
  • Контакты

Как реализовать переменное количество вложенных циклов в C++

Иногда возникает в программировании задача, когда надо реализовать переменное количество вложенных циклов, число которых неизвестно, неизвестно также количество повторений каждого цикла. Как быть? В статье предлагается способ с использованием одного лишь цикла, который имитирует множество вложенных циклов.

16.08.2013 Leave a Comment 2 933 просмотров

Иногда возникает в программировании задача, когда надо реализовать переменное количество вложенных циклов, число которых неизвестно, неизвестно также количество повторений каждого цикла. Как быть? В статье предлагается способ с использованием одного лишь цикла, который имитирует множество вложенных циклов.

Содержание

  • Идея
  • Подготовительные функции
  • Сама реализация

Идея

Количество итераций во множестве вложенных циклов равно произведению прогонов каждого вложенного цикла. Поэтому можно заменить все одним циклом с числом повторений равным этому произведению. Но в циклах важную роль играют индексы, которые меняются от итерации к итерации. Поэтому для имитации вложенности всех циклов надо для каждой итерации нашего одного цикла ставить в соответствие вектор индексов вложенных циклов. Вот этим и займемся.

У меня эта задача возникла при тестировании алгоритмов оптимизации, где множество параметров и их количество у алгоритмов может отличаться, а переписывать каждый раз код из-за разных внешних вложенных циклов не хотелось.

Подготовительные функции

Для реализации идеи вам потребуется две функции, которые приведены ниже:

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
template <class T> T HML_ProductOfElementsOfVector(T *VHML_Vector,int VHML_N)
{
/*
Функция вычисляет произведение элементов вектора.
Входные параметры:
VHML_Vector - указатель на исходный массив;
VHML_N - размер массива.
Возвращаемое значение:
Произведение элементов массива.
*/
T VHML_Result=1;
for (int i=0;i<VHML_N;i++)
    VHML_Result*=VHML_Vector[i];
 
return VHML_Result;
}
//---------------------------------------------------------------------------
void HML_MixedMultiLogicVectorOfFullSearch(int *VHML_Vector, int I, int *HowMuchInElements, int VHML_N)
{
/*
Функция генерирует определенный вектор k-значной логики, где каждый элемент может
принимать разное максимальное значение, в полном переборе вариантов.
Генерируется I вектор в этом полном переборе.
Входные параметры:
VHML_Vector - выходной вектор, в который записывается результат;
I - номер в массиве в полном переборе, начиная с нуля (от 0 и до произведения всех элементов массива HowMuchInElements - 1);
HowMuchInElements - сколько значений может принимать элемент в векторе. То есть элемент может быть 0 и HowMuchInElements[i] - 1;
VHML_N - количество элементов в массиве.
Возвращаемое значение:
Отсутствует.
*/
    int *CountInBlock = new int[VHML_N];
 
    int CountOfAllVariants = HML_ProductOfElementsOfVector(HowMuchInElements, VHML_N);
 
    CountInBlock[0] = CountOfAllVariants/HowMuchInElements[0];
 
    for (int i=1;i<VHML_N;i++)
        CountInBlock[i] = CountInBlock[i-1]/HowMuchInElements[i];
 
    for (int i=0;i<VHML_N;i++)
        VHML_Vector[i] = (I/CountInBlock[i])%HowMuchInElements[i];
 
    delete [] CountInBlock;
}

Сама реализация

Всё использование показано в примере:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    int N=4;//сколько параметров будет у алгоритма
 
    int *R=new int[N];//вектор числа повторений у циклов
    R[0]=3;//Число повторений у 1 цикла
    R[1]=3;//Число повторений у 2 цикла
    R[2]=3;//Число повторений у 3 цикла
    R[3]=2;//Число повторений у 4 цикла
 
    int M=HML_ProductOfElementsOfVector(R,N);//сколько итераций вообще будет
 
    int *P=new int[N];//вектор текущих значений индексов имитируемых вложенных циклов
 
    //основной цикл
    for (int i=0;i<M;i++)
    {
        HML_MixedMultiLogicVectorOfFullSearch(P, i, R, N);//теперь в P лежат нужные индексы
 
        //используем результат
    }
 
    delete[] R;
    delete[] P;

Если мы это запустим, то вектор P будет принимать значения:

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
P = 0 0 0 0
 
P = 0 0 0 1
 
P = 0 0 1 0
 
P = 0 0 1 1
 
P = 0 0 2 0
 
P = 0 0 2 1
 
P = 0 1 0 0
 
P = 0 1 0 1
 
P = 0 1 1 0
 
P = 0 1 1 1
 
P = 0 1 2 0
 
P = 0 1 2 1
 
P = 0 2 0 0
 
P = 0 2 0 1
 
P = 0 2 1 0
 
P = 0 2 1 1
 
P = 0 2 2 0
 
P = 0 2 2 1
 
P = 1 0 0 0
 
P = 1 0 0 1
 
P = 1 0 1 0
 
P = 1 0 1 1
 
P = 1 0 2 0
 
P = 1 0 2 1
 
P = 1 1 0 0
 
P = 1 1 0 1
 
P = 1 1 1 0
 
P = 1 1 1 1
 
P = 1 1 2 0
 
P = 1 1 2 1
 
P = 1 2 0 0
 
P = 1 2 0 1
 
P = 1 2 1 0
 
P = 1 2 1 1
 
P = 1 2 2 0
 
P = 1 2 2 1
 
P = 2 0 0 0
 
P = 2 0 0 1
 
P = 2 0 1 0
 
P = 2 0 1 1
 
P = 2 0 2 0
 
P = 2 0 2 1
 
P = 2 1 0 0
 
P = 2 1 0 1
 
P = 2 1 1 0
 
P = 2 1 1 1
 
P = 2 1 2 0
 
P = 2 1 2 1
 
P = 2 2 0 0
 
P = 2 2 0 1
 
P = 2 2 1 0
 
P = 2 2 1 1
 
P = 2 2 2 0
 
P = 2 2 2 1

То есть значения будут именно такими, какими были бы индексы во вложенных циклах. И все идет в том же порядке.


Статьи по теме:

  1. Сложение двух чисел в Qt 5.4.0 на C++ (консольное приложение)
  2. Сложение двух чисел в Qt 5.4.0 на C++

IT C++, Алгоритм

© 2014 Harrix