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

Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике - C++

Восстановить пароль Регистрация
 
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
24.12.2011, 21:39     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике #1
kombinatorika.h

Этот заголовочный файл подключается для работы с комбинаторикой. В нём определены и реализованы функциии классы для работы с ней. (Для работы с этим файлом необходимо подключиь также файл VERYLONG.h (большие числа, я его также выкладываю, сам скачал откуда-то))

kombinatorika.h условно можно разбить на две части

1)Разные количества- то есть набор функций, каждая из которых возвращающих число типа Verylong (суть строку символов), вот эти функции:

Функция возвращает факториал числа n
C++
1
Verylong _fact(int n);
Возвращает количество сочетаний из n по k без возврата и без учёта порядка
C++
1
Verylong  C_s_i_n_p_k_b_v_i_b_u_p (int n, int k);
Возвращает количество сочетаний из n по k без возврата и с учётом порядка
C++
1
Verylong  C_s_i_n_p_k_b_v_i_s_u_p (int n, int k);
Возвращает количество сочетаний из n по k с возвратом и без учёта порядка
C++
1
Verylong  C_s_i_n_p_k_s_v_i_b_u_p (int n, int k);
Возвращает количество сочетаний из n по k с возвратом и с учётом порядка
C++
1
Verylong  C_s_i_n_p_k_s_v_i_s_u_p (int n, int k);
Возвращает количество перестановок
C++
1
Verylong  C_perestanovok (int n);
Возвращает количество вариантов разбиения камней на кучки
C++
1
Verylong  C_v_r_k_n_k (int kamni, int kuchki);
Ну тут всё понятно, кроме последнего, чё значит разбиение камней на кучки, я скажу ниже, а пока пример использования:

C++
1
2
3
4
5
6
7
8
9
10
#include "kombinatorika.h"
#include <windows.h>
int main () {
 SetConsoleCP (1251);
 SetConsoleOutputCP (1251);
 printf ("тестируем количество сочетаний из n по k без возврата и без учёта порядка\n");
 cout<< "C_s_i_n_p_k_s_v_i_s_u_p (10, 5)= "<< C_s_i_n_p_k_s_v_i_s_u_p (10, 5)<< endl;
 getchar ();
 return 0;
}
И вывод:

Bash
1
2
тестируем количество сочетаний из n по k без возврата и без учёта порядка
C_s_i_n_p_k_s_v_i_s_u_p (10, 5)= 100000
В этих функциях защиты от дураков нет, надо вручную следить, чтобы n было больше
либо равно k ну и за остальными требованиями тоже


+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


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

a)
C++
1
P_p
получение перестановок

конструкторы
C++
1
2
P_s (int);
P_s (t<T, t_>&);
то есть если ты инициализируешь элемент типа P_s числом типа int, вот так:
C++
1
P_s (5);
то результаты будут: очередной вектор-перестановка чисел от 0 до 4-х включительно.

Если ты инициализируешь элемент типа P_s контейнером vector, list или deque, вот так:
C++
1
2
3
4
5
list<int> lis;
lis.push_back (23);
lis.push_back (61);
lis.push_back (99);
P_p<int, list > P_p_l(lis);
то очередная перестановка чисел 23, 61 и 99 будет возвращена в виде соответствующего контейнера. То есть если вторым параметром шаблона идёт list, то контейнер-очередная_перестановка тоже будет иметь тип list


функции:

C++
1
bool och_rez ();
Показывает, есть ли очередная перестановка и если есть, возвращает true, иначе false

C++
1
t<T, t_> rez ();
Вот эта функция и возвращает очередную перестановку абы какую (в смысле неотсортированную)

Пример использования:

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
#include "kombinatorika.h"
#include <windows.h>
#include <iterator>
#include <deque>
 
int main () {
 SetConsoleCP (1251);
 SetConsoleOutputCP (1251);
 
 printf ("тестируем P_p, работаем со списком\n");
 list<int> lis;
 lis.push_back (23);
 lis.push_back (61);
 lis.push_back (99);
 lis.push_back (12);
 P_p<int, list > P_p_l(lis);
 
 while (P_p_l.och_rez ()) {
  lis= P_p_l.rez();
  copy(lis.begin(), lis.end(), std::ostream_iterator<int>(std::cout, " "));
  cout<< endl;
 }
 
 getchar ();
 return 0;
}
вывод:
Bash
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
тестируем P_p, работаем со списком
23 61 99 12
23 61 12 99
23 99 61 12
23 99 12 61
23 12 61 99
23 12 99 61
61 23 99 12
61 23 12 99
61 99 23 12
61 99 12 23
61 12 23 99
61 12 99 23
99 23 61 12
99 23 12 61
99 61 23 12
99 61 12 23
99 12 23 61
99 12 61 23
12 23 61 99
12 23 99 61
12 61 23 99
12 61 99 23
12 99 23 61
12 99 61 23
Две очень важных детали, касающиеся всех классов, начинающихся с буквы P (всех "получений")
Во-первых каждую очередную корректную перестановку (включая и первую) мождно получить только после вызова och_rez () (должно возвратиться true, что продемонстрировано в текущем примере)
Во-вторых после того, как och_rez () вернёт false, это будет означать, что все перестановки перебраны
и все дальнейшие её вызовы будут возвращать false, а все дальнейшие вызовы rez() будут возвращать последнюю корректную перестановку
Эти же два правила касаются и всех последующих классов




б)
C++
1
P_s_i_n_p_k_b_v_i_b_u_p
Получение сочетаний из n по k без возврата и без учёта порядка

конструкторы
C++
1
P_s_i_n_p_k_b_v_i_b_u_p (t<T, t_>& prom, int k);
если использован этот конструктор, то будут возврщаться сочетания k элементов контейнера prom

C++
1
P_s_i_n_p_k_b_v_i_b_u_p (int n, int k);
если исползовать этот конструктор, то будут возвращаться перестановки k элементов;
тип контейнера будет определяться при вызове rez(); а изначально он инициализирутся элементами
0, 1, 2, 3...k

C++
1
bool och_rez ();
Показывает, есть ли очередное сочетание если есть, возвращает true, иначе false

C++
1
t<T, t_> rez ();
Эта функция и возвращает очередное сочетание;
Если был вызван констркутор P_s_i_n_p_k_b_v_i_b_u_p (int n, int k), то сочетания будут
отсортированными

C++
1
t<T, t_> rez (SORT);
Эта функция возвращает очередное отсортированное сочетание




в)
C++
1
P_s_i_n_p_k_b_v_i_s_u_p
Получение сочетаний из n по k без возврата и без учёта порядка

конструкторы
C++
1
P_s_i_n_p_k_b_v_i_s_u_p (t<T, t_>& prom, int k);
если использован этот конструктор, то будут возврщаться сочетания k элементов контейнера prom

C++
1
P_s_i_n_p_k_b_v_i_s_u_p (int n, int k);
если исползовать этот конструктор, то будут возвращаться перестановки k элементов;
тип контейнера будет определяться при вызове rez(); а изначально он инициализирутся элементами
0, 1, 2, 3...k

C++
1
bool och_rez ();
Показывает, есть ли очередное сочетание если есть, возвращает true, иначе false

C++
1
t<T, t_> rez ();
Эта функция и возвращает очередное сочетание;

C++
1
t<T, t_> rez (SORT);
Эта функция возвращает очередное отсортированное сочетание. Но, как вы сами понимаете, мало смысла в том, чтобы использовать эту функцию





г)
C++
1
P_s_i_n_p_k_s_v_i_b_u_p
Получение сочетаний из n по k без возврата и без учёта порядка

конструкторы
C++
1
P_s_i_n_p_k_s_v_i_b_u_p (t<T, t_>& prom, int k);
если использован этот конструктор, то будут возврщаться сочетания k элементов контейнера prom

C++
1
P_s_i_n_p_k_s_v_i_b_u_p (int n, int k);
если исползовать этот конструктор, то будут возвращаться перестановки k элементов;
тип контейнера будет определяться при вызове rez(); а изначально он инициализирутся элементами
0, 1, 2, 3...k

C++
1
bool och_rez ();
Показывает, есть ли очередное сочетание если есть, возвращает true, иначе false

C++
1
t<T, t_> rez ();
Эта функция и возвращает очередное сочетание;
Если был вызван констркутор P_s_i_n_p_k_s_v_i_b_u_p (int n, int k), то сочетания будут
отсортированными

C++
1
t<T, t_> rez (SORT);
Эта функция возвращает очередное отсортированное сочетание




д)
C++
1
P_s_i_n_p_k_s_v_i_s_u_p
Получение сочетаний из n по k без возврата и без учёта порядка

конструкторы
C++
1
P_s_i_n_p_k_s_v_i_s_u_p (t<T, t_>& prom, int k);
если использован этот конструктор, то будут возврщаться сочетания k элементов контейнера prom

C++
1
P_s_i_n_p_k_s_v_i_s_u_p (int n, int k);
если исползовать этот конструктор, то будут возвращаться перестановки k элементов;
тип контейнера будет определяться при вызове rez(); а изначально он инициализирутся элементами
0, 1, 2, 3...k

C++
1
bool och_rez ();
Показывает, есть ли очередное сочетание если есть, возвращает true, иначе false

C++
1
t<T, t_> rez ();
Эта функция и возвращает очередное сочетание;
Если был вызван констркутор P_s_i_n_p_k_s_v_i_s_u_p (int n, int k), то сочетания будут
отсортированными

C++
1
t<T, t_> rez (SORT);
Эта функция возвращает очередное отсортированное сочетание
Но как вы сами понимаете, особого смысла здесь вызывать эту функцию нет.



e)
C++
1
P_k_i_k
получение камней и кучек. О чём речь, допустим имеем 5 камней и три кучки. Тогда вот как
эти 5 камней можно разложить по трём кучкам:

Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
0 0 5
0 1 4
0 2 3
0 3 2
0 4 1
0 5 0
1 0 4
1 1 3
1 2 2
1 3 1
1 4 0
2 0 3
2 1 2
2 2 1
2 3 0
3 0 2
3 1 1
3 2 0
4 0 1
4 1 0
5 0 0
Вот собсно задача этого класса и получить такие вот последовательности

конструктор:
C++
1
P_k_i_k (int kamni, int kuchki);
Показывает, есть ли очередной вариант разложенгия камней по кучкам
C++
1
bool och_rez ();

C++
1
t<T, t_> rez ();
Эта функция и возвращает очередной вариант разбиения камней на кучки;





////////////////

В этих классах есть небольшая тык скыть защита от дурака, то есть если к примеру
конструктор P_s_i_n_p_k_b_v_i_b_u_p будет инициализирован значениями 5 и 7 (5< 7)
то будет выведена соответствующая надпись, но программа не прервётся и дальнейшие её действия не определены. Код распространяется по лицензии GPL
Вложения
Тип файла: rar kombinatorika.rar (4.4 Кб, 21 просмотров)
Тип файла: rar VERYLONG.rar (3.8 Кб, 28 просмотров)
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2011, 21:39     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике
Посмотрите здесь:

Для чего нужен заголовочный файл conio.h ? C++
C++ Использование оператора for для решения задач
C++ предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику
Какой заголовочный файл надо для функции ord() ? C++
C++ Материал для решения задач
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
24.12.2011, 21:43  [ТС]     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике #2
В пункте в) надо читать:
Получение сочетаний из n по k без возврата и с учётом порядка

В пункте г) надо читать:
Получение сочетаний из n по k с возвратом и без учёта порядка

В пункте д) надо читать:
Получение сочетаний из n по k с возвратом и с учётом порядка
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
05.03.2012, 01:37  [ТС]     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике #3
В файл kombinatorika.h внсены изменения:
поле
C++
1
vector<int> index;
класса P_s
Было определено как
C++
1
vector<T, t_> index;
Исправил; поскольку всё-таки индексы это индексы и пусть они будут просто int; в противном случае класс не работал с авторскими типами типа
C++
1
2
3
4
class cl {
 char x;
 char y;
}
Вложения
Тип файла: rar kombinatorika.rar (4.4 Кб, 11 просмотров)
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
05.03.2012, 02:07     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Задумка конечно интересная, но вот с названиями функций и классов нужно что-то делать.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
28.03.2012, 23:04  [ТС]     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике #5
Внёс очередные усовершенствования в классы, а именно:

Конструкторы классов не принимали (не компилилось) в качестве параметров объекты, возвращённые из функции, например:

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <kombinatorika.h>
 
vector <int> f () {
 vector<int> kazhdoe_pole;
 return kazhdoe_pole ;
} 
 
 
int main () {
 P_s_i_n_p_k_b_v_i_b_u_p<int, vector> P_s_i_n_p_k_b_v_i_b_u_p_ (f(), 4);
 return 0;
}
Не сработало бы. А потому не сработало бы, что конструктор:
P_s_i_n_p_k_b_v_i_b_u_p (t<T, t_>& prom, int x):P_s<T, t, t_>(prom, x){;};

А по идее он должен принимать константную ссылку, то есть:
P_s_i_n_p_k_b_v_i_b_u_p (const t<T, t_>& prom, int x):P_s<T, t, t_>(prom, x){;};

тут подробнее, если чё:
Есть объект типа T, но если вместо него подставить вызов функции, возвращающей T, код не компилится, почему?

Вот я везде и понавставлял эти константные ссылки
Вложения
Тип файла: rar kombinatorika.rar (4.4 Кб, 10 просмотров)
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
28.03.2012, 23:11     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике #6
программа полезная, но имена в ней ржачные
Случайно не книгой Окулова вдохновлялся?
Yandex
Объявления
28.03.2012, 23:11     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике
Ответ Создать тему
Опции темы

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