Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
7 / 7 / 3
Регистрация: 27.05.2017
Сообщений: 89
Записей в блоге: 10
1

Множественные цикли

13.06.2017, 17:09. Показов 1630. Ответов 14

Author24 — интернет-сервис помощи студентам
Бывают простые ситуации, когда ты знаешь количество циклов, например, вот два цикла, один из которых вложен в другой:

C++
1
2
3
4
5
6
7
for (int i=0;i++;i<n){
 
     for (j=0;j++;j<n){
 
         //делаем что-то с массивов mas[i][j]
     } 
}
Но может возникнуть такая ситуация, когда количество вложенных циклов задаётся с помощью переменной n

Например,

for (int i1=0;i1++;i1<n){
//делаем что-то
for (int i2=0;i2++;i2<n) {
//делаем что-то
for (int i3=0;i3++;i3<n){
//делаем что-то
....
for (int in=0;in++;in<n){
//делаем что-то
}}...}

Как запустить такую вещь в C++? Не могу же написать для компилятора три точки: ... Он меня не поймёт.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.06.2017, 17:09
Ответы с готовыми решениями:

цикли
С помощью оператора WHILE напишите программу, вычисляющую сумму квадратов чисел от 1 до введенного...

с++ цикли
Помогите решить задачки буду очень благодарен я уверен есть ище добрие люди( Задача 3. Найти...

time в цикли while
есть цикл while(z==0) {...............................} как с помощью функции time() сделать так...

Lab4 цикли
Билет называется счастливым, если в его номере xyztuv (от 000000 до 999999) первые три цифры четные...

14
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
13.06.2017, 17:15 2
1. Пишешь с запасом 10 вложенных циклов, если на очередном уровне заходить глубже не надо - ставишь break.

2. Асиливаешь рекурсию и вертишь эти многомерные вложенные циклы как хотишь.
1
7 / 7 / 3
Регистрация: 27.05.2017
Сообщений: 89
Записей в блоге: 10
13.06.2017, 17:22  [ТС] 3
А если 100 циклов? Я же не могу написать сто циклов.

А как написать рекурсию?

Проблема в том, что вложенные циклы, то, что мы с ними делаем -- они влияют на другие циклы. Если тупо одно и то же запускать -- это не буде работать нормально. Идея в том, что работа каждого цикла будет немного отличаться:

скажем, есть задача вывести на экран все перестановки чисел от 0 до 4 из 5.

То есть вот первая перестановка:
0 1 2 3 4
Вот вторая
0 1 2 4 3
И так далее

Если писать рекурсию, то есть запускать одну и ту же функцию много раз -- не будет работать. А если написать множественные циклы -- то задача легко решиться.

Добавлено через 2 минуты
Я уверен, что в C++ должен быть механизм написать n вложенных циклов. Какая-то библиотеке или что-нибудь ещё
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
13.06.2017, 17:25 4
Цитата Сообщение от jvf Посмотреть сообщение
скажем, есть задача вывести на экран все перестановки чисел от 0 до 4 из 5.
Для данной задачи не нужны n-мерные вложенные циклы.
Цитата Сообщение от jvf Посмотреть сообщение
Я уверен, что в C++ должен быть механизм написать n вложенных циклов
Только если сгенерировать через какие-нибудь брутальные макросы.
Цитата Сообщение от jvf Посмотреть сообщение
Если писать рекурсию, то есть запускать одну и ту же функцию много раз -- не будет работать.
Почему же?
1
What a waste!
1608 / 1300 / 180
Регистрация: 21.04.2012
Сообщений: 2,729
13.06.2017, 17:27 5
Цитата Сообщение от jvf Посмотреть сообщение
Но может возникнуть такая ситуация, когда количество вложенных циклов задаётся с помощью переменной n
В общем случае, как уже написали, решается рекурсией. В определёных - можно уменьшить "глубину" вызовов функций + возможно дополнитеные структуры данных для промежуточных результатов.
1
7 / 7 / 3
Регистрация: 27.05.2017
Сообщений: 89
Записей в блоге: 10
13.06.2017, 17:30  [ТС] 6
Я не знаю, как написать все перестановки с помощью рекурсии. Вот мой вариант без рекурсии, но рабочий вариант для 3 циклов, а если циклов будет 100? :

Вот содержание файла INPUT.TXT

4 3
0 3 2 1
8 0 6 5
1 2 0 4
5 6 7 0
1 2 3 4

У нас есть элементы: 1, 2, 3, 4

И программа выводит на экран все перестановки чисел от 1 до 4.

Но я не знаю, как это написать с помощью рекурсии
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
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
 
using namespace std;
 
//int func(int i, int n, int k, int **mas)
//void ins (size_t rows, size_t columns, int matrix[rows][columns]){
 
int sum=0, sum_min=1000000;
 
 
 
 
int main(){
 
    //cout<<"Hello"<<endl;
 
    int n, k;
 
    ifstream fin("INPUT.TXT");
    ofstream fout("OUTPUT.TXT");
 
    //vector <int> *mas;
    
 
    fin >> n >> k;
    int temp;
 
    //int mas[n][k];
 
    vector<vector<int>> mas;
 
 
    for (int i=0;i<n;i++){
 
        vector <int> temp_m;
        for (int j=0;j<4; j++){
 
            fin>> temp;
            temp_m.push_back(temp);
 
        }
        mas.push_back(temp_m);
 
    }
 
    
    for (int i=0;i<n;i++){
 
        mas[i][i] = i+1;
    }
 
 
    for (int i=0;i<4;i++){
 
        for (int j=0;j<4;j++){
 
            cout<<mas[i][j]<<" ";
 
        }
        cout<<endl;
 
    }
    
 
    vector <int> pred;
    
    for (int j=0;j<k; j++){
 
            pred.push_back(-1);
 
        }
 
    
    
 
    
    cout<<endl;
    int sum, sum_min = 10000000;
 
    for (int i=0; i<4;i++){
 
        for (int j=0;j<4;j++){
 
            if (j==i){
                
                continue;
            
            }
            //cout<<mas[i][j]<<" ";
 
            for (int k=0;k<4;k++){
 
                if ((k==j) || (k==i)){
                    continue;
                }
 
                cout<<mas[i][i]<<" "<<mas[j][j]<<" "<<mas[k][k]<<" "<<endl;
                sum = mas[i][i]+mas[i][j]+mas[j][j]+mas[j][k]+mas[k][k];
 
                //cout<<"sum="<<sum<<endl;
            
                if (sum<sum_min){
                    sum_min = sum;
                    cout<<"sum_min="<<sum_min<<endl;
                }
            }
            cout<<endl;
 
        }
        cout<<endl;
 
    }
    
 
    //cout<<"sum_max="<<sum_min;
    //mas[0].push_back(10);
 
    //function(mas, n, k, pred);
    
 
    return 0;
}
Добавлено через 1 минуту
Вот что выводит программа:

1 2 3
sum_min=15
1 2 4

1 3 2
sum_min=10
1 3 4

1 4 2
1 4 3


2 1 3
2 1 4

2 3 1
2 3 4

2 4 1
2 4 3


3 1 2
3 1 4

3 2 1
3 2 4

3 4 1
3 4 2


4 1 2
4 1 3

4 2 1
4 2 3

4 3 1
4 3 2
0
What a waste!
1608 / 1300 / 180
Регистрация: 21.04.2012
Сообщений: 2,729
13.06.2017, 17:32 7
Цитата Сообщение от jvf Посмотреть сообщение
есть задача вывести на экран все перестановки чисел от 0 до 4 из 5.
Есть алгоритм, в стандартной библиотеке С++ например: http://en.cppreference.com/w/c... ermutation .
1
7 / 7 / 3
Регистрация: 27.05.2017
Сообщений: 89
Записей в блоге: 10
13.06.2017, 17:34  [ТС] 8
Я не хочу стандартный алгоритим, я хочу сам понять, как это написать с помощью рекурсии -- чтобы узнать язык C++ лучше.

Мне было бы интересно узнать, как это работает, как написать самому -- готовый алгоритм -- это важно, но хочется самому
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
13.06.2017, 17:38 9
Ну вот навскидку тупо в лоб без оптимизаций (меняй n и наслаждайся):
C++
1
2
3
4
5
6
7
8
9
10
11
const int n=5;
int a[n];
 
bool v(int j, int k) {for(int i=0; i<k; i++) if (a[i]==j) return true; return false;}
    
void f(int k) {
    if (k>=n) {for(int i=0; i<n; i++) cout<<a[i]<<' '; cout<<'\n';}
    else for(int i=0; i<n; i++) {if (v(i, k)) continue; a[k]=i; f(k+1);}
}
 
int main(){ f(0); }
1
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
13.06.2017, 17:44 10
Цитата Сообщение от jvf Посмотреть сообщение
Я не хочу стандартный алгоритим, я хочу сам понять, как это написать с помощью рекурсии -- чтобы узнать язык C++ лучше.
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
#include <iostream>
#include <clocale>
 
using namespace std;
 
// вывод множества на экран
void print(const int *A, const int size);
// функция перестановки двух чисел
void swap(int &, int &);
// функция генерации следующей перестановки
void next_perm(int k, int *A, const int size, int &counter);
 
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 4;
    int A[N]; // имеем множество A {1, ... N}
    int counter = 0; // счетчик числа перестановок
    for (int i = 0; i < N; i++) // заполняем множество
        A[i] = i + 1;
    next_perm(0, A, N, counter);
    cout << "Всего перестановок: " << counter << endl;
    return 0;
}
 
void print(const int *A, const int size)
{
    for (int i=0; i < size; i++)
        cout << A[i] << ' ';
    cout << endl;
}
 
void swap(int &x, int &y)
{
    int tmp = x;
    x = y;
    y = tmp;
}
 
void next_perm(int k, int *A, const int size, int &counter)
{
    // если заполнилось
    if (k == size)
    {
        print(A, size);
        counter++;
        return;
    }
 
    for(int i = k; i < size; i++)
    {
        swap(A[k], A[i]);
        next_perm(k + 1, A, size, counter); // следующая перестановка
        swap(A[k], A[i]);
    }
}
1
What a waste!
1608 / 1300 / 180
Регистрация: 21.04.2012
Сообщений: 2,729
13.06.2017, 17:50 11
Цитата Сообщение от jvf Посмотреть сообщение
я хочу сам понять
Например: https://en.wikipedia.org/wiki/Heap%27s_algorithm
1
Заблокирован
13.06.2017, 18:17 12
GNU
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 int count = 3; //число циклов
    int limit = 10; //циклы от 0 до limit
 
 
    int *length = new int[count] {};
    for (int k = 0; k < (float) std::pow(limit, count); k++) {
 
        //your cycles
        std::copy(length, length + count, std::ostream_iterator<int>(cout));
        cout << endl;
        //
 
        for (int i = 0; i < count; i++) {
            length[i]++;
            if (length[i] == limit) length[i] = 0;
            else break;
        }
 
    }
    delete[] length;
1
7 / 7 / 3
Регистрация: 27.05.2017
Сообщений: 89
Записей в блоге: 10
19.06.2017, 23:31  [ТС] 13
Честно говоря, я всё равно не понял логику этой рекурсии: много-много вызовов функции, сложно понять логику работы, что там происходит. Однако я написал свой вариант: он более медленный, но рабочий: без рекурсии.


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
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
 
using namespace std;
 
void print_mas(vector<int> mas){
 
    for (int i=0;i<mas.size();i++){
    
        cout<<mas[i]<<" ";
 
    }
    cout<<endl;
}
 
int change_mas(vector<int> &mas){
 
    int k=-1;
 
    for (int i=mas.size()-1;i>=0;i--){
 
        
        if (mas[i-1]<mas[i]){
            
 
            k = i-1;
            break;
        }
    
    }
 
    if(k==-1){
        cout<<"Конец сортировки"<<endl;
        return 0;
    }
 
    int razn;
    int min=99999999;
    int min_ind;
    
    for (int i=k+1;i<mas.size();i++){
 
        if (mas[i] > mas[k]){
 
            razn = mas[i]- mas[k];
 
            if (razn<min){
 
                min = razn;
                min_ind = i;
            }
 
        }
    }
 
 
    swap(mas[k], mas[min_ind]);
 
 
    for (int i = k+1;i<mas.size()-1;i++){
        
        for (int j=i+1;j<mas.size();j++){
 
            if (mas[i] > mas[j]){
                swap(mas[i], mas[j]);
            }
        }
 
    }
 
    print_mas(mas);
 
    return 1;
}
 
 
int main(){
 
    int n=3;
 
    vector <int> t;
 
 
    
    for (int i=0;i<n;i++){
 
        t.push_back(i+1);
        
    }
    
 
 
    print_mas(t);
 
    
    int p = -10;
    while (p!=0){
 
        p = change_mas(t);
 
    }
 
    
    return 0;
}
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
19.06.2017, 23:44 14
jvf, По поводу самой идеи множественных циклов хочу обратить твое внимание на смешанные системы счисления Грамотное их использование позволяет любое количество циклов уложить в два. Где-то на форуме я этот несложный фокус уже показывал. Найду - дам ссылку, но сам понимаешь, копать все свои посты - та еще работа...
А идея такая. Пусть у тебя вложенность - 3. Границы 4, 5, 6 (обработка матрицы A[4][5][6])
Представление числа от 0 до 4*5*6 - в системе счисления 4-5-6 дает индекс элемента этой матрицы.
Возможно, это не совсем то, что тебе нужно, но попробуй обратить внимание на этот прием.
1
7 / 7 / 3
Регистрация: 27.05.2017
Сообщений: 89
Записей в блоге: 10
20.06.2017, 00:32  [ТС] 15
Теперь мне надо написать более сложную программу: есть n чисел, берём из этих n чисел некое число k. Нужно написать все размещения из n по к.

Скажем, n=4, k=3
Тогда у нас будут другие числа:
1 2 3
1 2 4
1 3 4
и так далее.

Попробую тоже самостоятельно это написать без готового алгоритма.

Добавлено через 16 секунд
Теперь мне надо написать более сложную программу: есть n чисел, берём из этих n чисел некое число k. Нужно написать все размещения из n по к.

Скажем, n=4, k=3
Тогда у нас будут другие числа:
1 2 3
1 2 4
1 3 4
и так далее.

Попробую тоже самостоятельно это написать без готового алгоритма.

Добавлено через 1 минуту
Из Википедии:

В комбинаторике размещением (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов. В отличие от сочетаний, размещения учитывают порядок следования предметов.

Вот будет для меня интересная задача
0
20.06.2017, 00:32
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.06.2017, 00:32
Помогаю со студенческими работами здесь

Множественные ошибки в коде С++
#include &lt;iostream&gt; #include &lt;locale.h&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt; using namespace...

printf, множественные аргументы
void MyPrint(const char *message, ...) { * * printf(message, ...); // не вытаскивая просто...

Множественные условия выбора switch
В моем коде много case-ов я бы хотел их сократить путем логического умножения (case между собой...

множественные ошибки в простом проэкте
#include&lt;cmath&gt; #include&lt;iostream&gt; #include &lt;locale.h&gt; using namespace std; int main() {...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru