Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.78/9: Рейтинг темы: голосов - 9, средняя оценка - 4.78
 Аватар для Saym
5 / 5 / 4
Регистрация: 02.11.2014
Сообщений: 196

Генерирование размещений рекурсией

22.01.2017, 13:27. Показов 1990. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Задача: сгенерировать размещения (подсчитать их кол-во). m - макс. число элемента размещения, n - длина(размер) размещения. Условия: элементы должны располагаться по возрастанию, повторяющихся элементов быть не должно.

Это я сделал, но не с помощью рекурсии. Мне уже писали, что подобную задачу лучше решить, используя рекурсию. Но я не понимаю, как это сделать (все, что встречал - это вычисление факториала числа).

Как я понял, при вычислении факториала, функция "углубляется" (уходит дальше внутрь), а при достижении определенного значения, "движется" обратно.

Но ведь в моем случае функция не может только увеличить последнее число до макс. возможного, происходит также увеличение и других (слева стоящих чисел) и нужно будет снова возвращаться к последнему числу и снова его увеличивать.

Может быть есть ресурсы или книги (статьи), где нечто подобное расписано подробно?

программа:
Кликните здесь для просмотра всего текста
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
#pragma argsused
#include <iostream.h>
#include <conio.h>
 
class perestanovki
       {
        private:
        int i,j,n,max,fl,k,m[20];
 
        public:
        perestanovki ()
             {
             i=0;
             fl=0;
             k=1;  
             m[i]=1; 
             }
 
        void input();     
        void create_array(); 
        void out();     
        void plus_plus();   
        void swap();    
        void pusk();   
        };
 
void perestanovki::input  ()
       {
 
       cout<<"Vvedite razmer perestanovki: ";
       cin>>n;
 
       cout<<"Vvedite alfavit: ";
       cin>>max;
 
        //alаavit<razmer
       }
 
void perestanovki::create_array ()
      {
 
        for (j=i;j<n;j++)
           {
           m[j+1]=m[j]+1;
           }
 
           out();
      }
 
void perestanovki::out()
    {
 
     for (i=0;i<n;i++) cout<<m[i];
 
     cout<<" ("<<k<<")"<<endl;
     k++;
 
    }
 
void perestanovki::plus_plus()
    {
     while (m[n-1]!=max)
            {
             m[n-1]++;
             out();
            }
          
    }
 
void perestanovki::swap()
    {
     j=n-1;
     for (i=n-1;i>=0;i--) {if (m[i]>=(max-((n-1)-i)))
                                {
                                 j--;
                                }
                                }
 
     i=j;
     m[j]++;
 
     if (m[0]==(max-((n-1)-0))) {fl=1;out();}
 
    }
 
    void perestanovki::pusk ()
    {
 
      input();
 
      while (fl==0)
      {
      create_array();
      plus_plus();
      swap();
      }
    }
 
int main()
  {
 
   perestanovki a;
 
   a.pusk();
 
   getch();
 
  }
Миниатюры
Генерирование размещений рекурсией   Генерирование размещений рекурсией  
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
22.01.2017, 13:27
Ответы с готовыми решениями:

Генерирование размещений
Помогите пожалуйста с этой программой,а то очень надо, а как написать никак не пойму((Благодарю за помощь) Добавлено через 1 час 9...

Генерация размещений
Подскажите пожалуйста, как в коде можно записать генерацию размещений? Знаю, как подсчитать их количество, но не вывести сами размещения((

Генерация размещений
Составить компьютерную программу генерации всех размещений для заданных значений n и m в лексикографическом порядке. Программа должна...

4
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
22.01.2017, 13:30
Цитата Сообщение от Saym Посмотреть сообщение
или книги
Липский "Комбинаторика для программистов" Есть и поновее.
1
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.01.2017, 02:02
Лучший ответ Сообщение было отмечено Saym как решение

Решение

Вот вам рекурсия на рекурсии
C++
1
2
3
4
5
6
7
8
9
10
int a[50],n,m,c;
 
void s(int i) {if (i<n) {cout<<a[i]; s(i+1);} else cout<<" ("<<++c<<")\n";}
 
void f(int, int);
void l(int i, int k) {if (k<=m) {a[i]=k; f(i+1, k); l(i,k+1);}}
 
void f(int i, int j) {if (i==n) s(0); else l(i, j+1);}
 
int main() { cin>>n>>m; f(0, 0); }
1
 Аватар для Saym
5 / 5 / 4
Регистрация: 02.11.2014
Сообщений: 196
28.01.2017, 19:25  [ТС]
Спасибо большое!
У меня вопрос возник:
C++
1
void s(int i) {if (i<n) {cout<<a[i]; s(i+1);} else cout<<" ("<<++c<<")\n";}
Это рекурсивный вывод. После вывода всех элементов - вывод счетчика.
C++
1
void f(int, int);
Две функции f. Перегрузка функций? Не понял для чего эта функция, но без нее не компилируется)

C++
1
2
int main() { cin>>n>>m; f(0, 0); }
void f(int i, int j) {if (i==n) s(0); else l(i, j+1);}
На начальном этапе аргументы f будут равны 0.
Вижу вызов вывода. Как только i равен n - вывод массива.

C++
1
void l(int i, int k) {if (k<=m) {a[i]=k; f(i+1, k); l(i,k+1);}}
Могу разглядеть здесь заполнение массива). Пока пытаюсь осознать, что точно происходит в f и l.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
28.01.2017, 19:31
Цитата Сообщение от Saym Посмотреть сообщение
Не понял для чего эта функция
В нормальных языках она не нужна, здесь только из-за кривизны плюсового компилятора (препроцессора).
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
28.01.2017, 19:31
Помогаю со студенческими работами здесь

Число размещений с n по m
Написал программу на ассемблере, находит число размещений с n по m и записывает результат в eax. Вроде всё верно, так?) MASM MODEL...

Количество размещений
5 различных шаров распределяются по 4 ячейкам так, что в ячейку (ячейки различны) попадает любое количество шаров. Подсчитать количество...

число упорядоченных размещений
найти число упорядоченных размещений n различных объектов по m различным ящикам ( размещения, отличающиеся перестановками объектов внутри...

Вычислите число размещений из n по m
Вычислите число размещений из n по m.

Генерация размещений и перестановок
Алфавит языка состоит из трех символов {0,1,2}. Нужно сгенерировать все возможные варианты слов такого языка длиной 2 сивмола Пример...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru