Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
kravam
быдлокодер
1703 / 890 / 45
Регистрация: 04.06.2008
Сообщений: 5,489
#1

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

24.12.2011, 21:39. Просмотров 813. Ответов 5
Метки нет (Все метки)

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
1
Вложения
Тип файла: rar kombinatorika.rar (4.4 Кб, 23 просмотров)
Тип файла: rar VERYLONG.rar (3.8 Кб, 30 просмотров)
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2011, 21:39
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике (C++):

предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику - C++
Друзья! Ввиду возникшей необходимости мной был написан класс &quot;рекурсивный обход матрицы&quot;; Теперь задачи на такую тематику будут решаться...

Для чего заголовочный файл <iomanip>? - C++
#include &lt;iomanip&gt; для чего этот заголовочный файл? какие у него функции? и где можно прочитать про подключаемые файлы?спс!

Объявления классов в *.h, или почему просто не приписать заголовочный файл #include <QProgressBar>? - C++ Qt
Доброго времени суток. Не пойму почему Шлее в хэдерах объявляет классы следующим образом: #ifndef PROGRESS_H #define PROGRESS_H ...

Пара задач по комбинаторике - Комбинаторика
2 варианта решения : с помощью правила перемножения - на первое место можно поставить 6 цифр, на второе 5 и т.д. - 6*5*4*3=360 с...

Решение задач с применением булевых функций. Для каждой из функций заданных формулой составить: сднф и скнф - Логика и множества
http://www.cyberforum.ru/attachment.php?attachmentid=345772&amp;stc=1&amp;d=1387707019 Помогите пожалуйста любой пример на выбор завтра уже сдать...

Помогите создать заголовочный файл для Dll - Delphi
Всем добрый день. Есть некая библиотека, написанная на C++. Она компилится в DLL. Мне нужно написать на Delphi заголовочный файл для работы...

5
kravam
быдлокодер
1703 / 890 / 45
Регистрация: 04.06.2008
Сообщений: 5,489
24.12.2011, 21:43  [ТС] #2
В пункте в) надо читать:
Получение сочетаний из n по k без возврата и с учётом порядка

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

В пункте д) надо читать:
Получение сочетаний из n по k с возвратом и с учётом порядка
0
kravam
быдлокодер
1703 / 890 / 45
Регистрация: 04.06.2008
Сообщений: 5,489
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;
}
0
Вложения
Тип файла: rar kombinatorika.rar (4.4 Кб, 11 просмотров)
kazak
3050 / 2371 / 160
Регистрация: 11.03.2009
Сообщений: 5,436
Завершенные тесты: 1
05.03.2012, 02:07 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Задумка конечно интересная, но вот с названиями функций и классов нужно что-то делать.
3
kravam
быдлокодер
1703 / 890 / 45
Регистрация: 04.06.2008
Сообщений: 5,489
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, код не компилится, почему?

Вот я везде и понавставлял эти константные ссылки
0
Вложения
Тип файла: rar kombinatorika.rar (4.4 Кб, 10 просмотров)
Kuzia domovenok
2055 / 1900 / 174
Регистрация: 25.03.2012
Сообщений: 6,538
Записей в блоге: 1
28.03.2012, 23:11 #6
программа полезная, но имена в ней ржачные
Случайно не книгой Окулова вдохновлялся?
0
28.03.2012, 23:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.03.2012, 23:11
Привет! Вот еще темы с ответами:

Для чего нужен заголовочный файл conio.h ? - C++
&lt;conio.h&gt;. нам в институте говорили про такое. Я понимаю так,что если этот поток можно использовать без &lt;iostream&gt;. А то данный поток...

Какой заголовочный файл надо для функции ord() ? - C++
Всем привет... Тут такая напасть случилась забыл заголовочный файл(include &lt;???&gt;) для функции ord =)

Что такое заголовочный файл и для чего он нужен? - C++ Qt
Я только начинаю изучать Qt. И во всех книгах, которые я начинал читать, и во всех уроках в интернете пишут непонятные записи в этот...

Для подключения заголовочного файла graphics.H требуется заголовочный файл <sstream> - C (СИ)
Доброго времени суток! Для подключения заголовочного файла graphics.h требуется заголовочный файл &lt;sstream&gt;, но где его взять я не знаю....


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.