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

@comeTrue · Регистрация: 28.10.2012

Студворк — интернет-сервис помощи студентам

Привет.
Нужен код с++, который позволит вывести все комбинации цифр от 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;
}

И кучу ошибок, вплоть до крэша компилятора и необходимости перезапуска(из за переполнения стэка) Помогите найти ошибки или составить новый код.

Обязательно использование рекурсивной функции

@David Sylva · 28.10.2012, 11:29

Вот так можно выводить все комбинации

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 · 28.10.2012, 11:35 **[ТС]**

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

Croessmah · 28.10.2012, 11:35

Пожалуй соглашусь с comeTrue, ибо изначально неизвестно сколько знаков в числе

@comeTrue · 28.10.2012, 12:05 **[ТС]**

хотя бы подскажите, как сделать, чтобы тут стек не переполнялся

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 · 28.10.2012, 12:12

Сообщение от comeTrue

long int main

в какой книге так пишут?

@comeTrue · 28.10.2012, 18:46 **[ТС]**

Ни в какой. Это я запаниковал) не работает, все равно

Добавлено через 6 часов 6 минут
ап темы

@comeTrue · 29.10.2012, 20:44 **[ТС]**

Короче говоря, задачу я решил, если кому интересно [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);
}

Я молодец.

valeriikozlov · 30.10.2012, 05:47

Сообщение от 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);
    }
}

Новые блоги и статьи Все статьи Все блоги /
Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .	PowerShell Snippets iNNOKENTIY21 11.11.2025 Модуль PowerShell 5. 1+ : Snippets. psm1 У меня модуль расположен в пользовательской папке модулей, по умолчанию: \Documents\WindowsPowerShell\Modules\Snippets\ А в самом низу файла-профиля. . .	PowerShell и онлайн сервисы. Валюта (floatrates.com руб.) iNNOKENTIY21 11.11.2025 PowerShell функция floatrates-rub Примеры вызова: # Указанная валюта 'EUR' floatrates-rub -Code 'EUR' # Список имеющихся кодов валют floatrates-rub -Available function floatrates-rub {	PowerShell и онлайн сервисы. Погода (RP5.ru) iNNOKENTIY21 11.11.2025 PowerShell функция Get-WeatherRP5rss для получения погоды с сервиса RP5 Примеры вызова Get-WeatherRP5rss с указанием id 5484 — Москва (восток, Измайлово) и переносом строки:. . .
PowerShell и онлайн сервисы. Погода (wttr) iNNOKENTIY21 11.11.2025 PowerShell Функция для получения погоды с сервиса wttr Примеры вызова: Погода в городе Омск с прогнозом на день, можно изменить прогноз на более дней, для этого надо поменять запрос:. . .	PowerShell и онлайн сервисы. Валюта (ЦБР) iNNOKENTIY21 11.11.2025 # Получение курса валют function cbr (] $Valutes = @('USD', 'EUR', 'CNY')) { $url = 'https:/ / www. cbr-xml-daily. ru/ daily_json. js' $data = Invoke-RestMethod -Uri $url $esc = 27 . . .	И решил я переделать этот ноут в машину для распределенных вычислений Programma_Boinc 09.11.2025 И решил я переделать этот ноут в машину для распределенных вычислений Всем привет. А вот мой компьютер, переделанный из ноутбука. Был у меня ноут асус 2011 года. Со временем корпус превратился. . .	Мысли в слух kumehtar 07.11.2025 Заметил среди людей, что по-настоящему верная дружба бывает между теми, с кем нечего делить.	Новая зверюга volvo 07.11.2025 Подарок на Хеллоуин, и теперь у нас кроме Tuxedo Cat есть еще и щенок далматинца: Хочу еще Симбу взять, очень нравится. . .

@comeTrue 0 / 0 / 0 Регистрация: 28.10.2012 Сообщений: 10
	28.10.2012, 11:35 [ТС]
	Так выводятся не все возможные комбинации, протестив, увидел только 6. И тут не используется рекурсия, а без нее задача не примется. 0

Croessmah Неэпический 18144 / 10728 / 2066 Регистрация: 27.09.2012 Сообщений: 27,026 Записей в блоге: 1
	28.10.2012, 11:35
	Пожалуй соглашусь с comeTrue, ибо изначально неизвестно сколько знаков в числе 0

@comeTrue 0 / 0 / 0 Регистрация: 28.10.2012 Сообщений: 10
	28.10.2012, 18:46 [ТС]
	Ни в какой. Это я запаниковал) не работает, все равно Добавлено через 6 часов 6 минут ап темы 0