Форум программистов, компьютерный форум CyberForum.ru

Произвольное количество вложенных циклов + рекурсия - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.60
comeTrue
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 10
28.10.2012, 11:14     Произвольное количество вложенных циклов + рекурсия #1
Привет.
Нужен код с++, который позволит вывести все комбинации цифр от 1 до k в n-значном числе:
допустим,
ввод n=2, k=3, вывод:

Кликните здесь для просмотра всего текста
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3


ввод 3,3, вывод

Кликните здесь для просмотра всего текста
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3


В интернетах нашел такой вот параграф:

6.5. Произвольное количество вложенных циклов

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

Для примера напишем процедуру, печатающую все возможные сочетания из k чисел от 1 до n (). Числа, входящие в каждое сочетание, будем печатать в порядке возрастания. Сочетания из двух чисел (k=2) печатаются так:

Pascal
1
2
3
for i1 := 1 to n do
  for i2 := i1 + 1 to n do
    writeln(i1, ' ', i2);
Сочетания из трех чисел (k=3) так:
Pascal
1
2
3
4
for i1 := 1 to n do
  for i2 := i1 + 1 to n do
    for i3 := i2 + 1 to n do
      writeln(i1, ' ', i2, ' ', i3);
Однако, если количество чисел в сочетании задается переменной, то придется прибегнуть к рекурсии.

Pascal
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
procedure Combinations(
  n, k: integer; 
  //Массив, в котором будем формировать сочетания
  var Indexes: array of integer;
  //Счетчик глубины рекурсии
  d: integer);
var
  i, i_min: integer;
  s: string;
begin
  if d < k then
  begin
    if d = 0 then
      i_min := 1
    else
      i_min := Indexes[d-1] + 1;
    for i := i_min to n do
    begin
      Indexes[d] := i;
      Combinations(n, k, Indexes, d+1);
    end;
  end
  else
  begin
    for i := 0 to k-1 do
      write(Indexes[i], ' ');
    writeln;
  end;
end;
В попытках перевести все на c++ получил:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int d=0;
int ind[1000]={0};
 
void comb(int n, int k)
{int i=0,i_min=0;
if (d<k) 
        {if (d==0) i_min=1; else i_min=ind[d-1]+1;
         for (i=i_min; i<n;i++){ind[d]=i; comb(n,k); d++;}}
else {for(i=0;i<n;i++) cout<<ind[i]<<' '; cout<<endl;}}
    
long int main(){
int n,k;
cin>>n>>k;
comb(n,k);
system("pause");
return 0;
}
И кучу ошибок, вплоть до крэша компилятора и необходимости перезапуска(из за переполнения стэка) Помогите найти ошибки или составить новый код.

Обязательно использование рекурсивной функции
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.10.2012, 11:14     Произвольное количество вложенных циклов + рекурсия
Посмотрите здесь:

Сотня вложенных циклов C++
C++ Использование цикла while и вложенных циклов
Программирование вложенных циклов C++
C++ Приоритеты вложенных циклов
как сделать неизвестное количество вложенных циклов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
28.10.2012, 11:29     Произвольное количество вложенных циклов + рекурсия #2
Вот так можно выводить все комбинации
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
 
 
int main () 
{
  int myints[] = {1,2,3};
  std::sort (myints,myints+3);
 
  do 
  {
    std::cout << myints[0] << " " << myints[1] << " " << myints[2] << std::endl;
  } while ( std::next_permutation (myints,myints+3) );
 
  return 0;
}
comeTrue
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 10
28.10.2012, 11:35  [ТС]     Произвольное количество вложенных циклов + рекурсия #3
Так выводятся не все возможные комбинации, протестив, увидел только 6. И тут не используется рекурсия, а без нее задача не примется.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
28.10.2012, 11:35     Произвольное количество вложенных циклов + рекурсия #4
Пожалуй соглашусь с comeTrue, ибо изначально неизвестно сколько знаков в числе
comeTrue
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 10
28.10.2012, 12:05  [ТС]     Произвольное количество вложенных циклов + рекурсия #5
хотя бы подскажите, как сделать, чтобы тут стек не переполнялся

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int d=0;
int ind[1000]={0};
 
void comb(int n, int k)
{int i=0,i_min=0;
if (d<k) 
        {if (d==0) i_min=1; else i_min=ind[d-1]+1;
         for (i=i_min; i<n;i++){ind[d]=i; comb(n,k); d++;}}
else {for(i=0;i<n;i++) cout<<ind[i]<<' '; cout<<endl;}}
    
long int main(){
int n,k;
cin>>n>>k;
comb(n,k);
system("pause");
return 0;
}
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
28.10.2012, 12:12     Произвольное количество вложенных циклов + рекурсия #6
Цитата Сообщение от comeTrue Посмотреть сообщение
long int main
в какой книге так пишут?
comeTrue
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 10
28.10.2012, 18:46  [ТС]     Произвольное количество вложенных циклов + рекурсия #7
Ни в какой. Это я запаниковал) не работает, все равно

Добавлено через 6 часов 6 минут
ап темы
comeTrue
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 10
29.10.2012, 20:44  [ТС]     Произвольное количество вложенных циклов + рекурсия #8
Короче говоря, задачу я решил, если кому интересно [nobody cares**]

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
#include <iostream>
using namespace std;
int c=1;
int ind[100];
int i=1;
int asd=1;
 
void comb(int n, int k);
int main(){
for (int j=0;j<100;j++) ind[j]=1;
int n,k;
cin>>n>>k;
 
for (int j=1;j<=n;j++) asd=asd*k;
for (i=1;i<=n;i++) cout<<ind[i-1]<<' '; cout<<endl; c++;
comb(n,k);
system("pause");
return 0;
}
void comb(int n, int k)
{for (i=n-1;i>=1;i--) if ((ind[i]<k) && (ind[i-1]<k)) {ind[i]++; break;}
else if (ind[i-1]<k) {ind[i]=1; ind[i-1]++; break;}
else if ((ind[i-1]==k)&&(ind[i]==k)) {if (i-1!=0) {ind[i-2]++; ind[i-1]=1; ind[i]=1; break;}}
else if (ind[i-1]==k) {ind[i]++; break;}
 
for (i=1;i<=n;i++) cout<<ind[i-1]<<' ';
cout<<endl;
c++;
if (c==asd+1) return; else comb(n,k);
}
Я молодец.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.10.2012, 05:47     Произвольное количество вложенных циклов + рекурсия
Еще ссылки по теме:

Программированиие алгоритмов со структурой вложенных циклов C++
Распараллеливание вложенных циклов с AMP C++
Упрощение вложенных циклов C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.10.2012, 05:47     Произвольное количество вложенных циклов + рекурсия #9
Цитата Сообщение от comeTrue Посмотреть сообщение
Я молодец.
Точно молодец. В качестве награды вариант решения:
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
#include <iostream>
using namespace std;
 
int ind[100]; 
void comb(int n, int k, int t);
int main(){
int n,k;
cin>>n>>k;
comb(n,k,0);
system("pause");
return 0;
}
void comb(int n, int k, int t)
{
    if(t==n)
    {
        for(int i=0; i<n; i++)
            cout<<ind[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=1; i<=k; i++)
    {
        ind[t]=i;
        comb(n, k, t+1);
    }
}
Yandex
Объявления
30.10.2012, 05:47     Произвольное количество вложенных циклов + рекурсия
Ответ Создать тему
Опции темы

Текущее время: 08:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru