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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Сформировать и распечатать квадратную матрицу http://www.cyberforum.ru/cpp-beginners/thread416587.html
Задача такая: Сформировать и распечатать квадратную матрицу А(n;n), так чтобы числа от 1 до n располагались по побочной диагонали. Кое-как сделал: #include <conio.h> #include <stdio.h> #include <stdlib.h> int main (void) { int **a, n; printf("Vvedite n="); scanf("%d", &n); a=(int**)calloc(n,sizeof(int*)); for (int k=0;k<n;k++)
C++ одномерный массив подсчитать количество не положительных, положительных, нулевых элементов массива В. тип элементов: действительные; Количество элементов:25 Элементы: от -50 до 50 http://www.cyberforum.ru/cpp-beginners/thread416586.html
C++ Матрица+консольное меню(С++)
Всем доброго времени суток. Помогите пожалуйста с заданием: Назовём допустимым преобразованием матрицы перестановку двух строк или двух столбцов. Дана действительная квадратная матрица порядка n. С помощью допустимых преобразований добиться того, чтобы один из элементов матрицы, обладающий наименьшим значением, распологался в левом нижнем углу матрицы. Ввод, решение, вывод, help должны...
C++ Задача о рюкзаке.требуется проверить, можно ли заполнить рюкзак полностью.Не знаю в чём ошибка...(
#include "stdafx.h" #include "conio.h" #include <iostream> using namespace std; int main(void) { int m, d; int sum, n, i, j, k, max, x; int go_back, good; printf ("Vvedite max massu: ");
C++ Одномерный массив http://www.cyberforum.ru/cpp-beginners/thread416579.html
Задание такое: В целочисленном массиве, сгенерированном случайным образом, найти количество пар соседних элементов, в которых предыдущий элемент кратен последующему. Сделал, вроде работает: #include <stdio.h> #include <conio.h> int main(void) { int i, n, n1, a, k=0; printf ("\n\n Vvedite chislo elementov v massive, ne bolshe 10 i ne menshe 2"); scanf ("%d", &n); if ((n>=2)&&(n<=10))
C++ Найти целые числа F(k-1) и F(k+1)-предыдущее и последующее числа Фибоначчи Дано целое число N (>1),являющееся числом Фибоначчи: N=Fk(катое).Найти целые числа F(k-1) и F(k+1)-предыдущее и последующее числа Фибоначчи подробнее

Показать сообщение отдельно
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,270
24.12.2011, 21:39     Предлагаю заголовочный файл с реализацией функций и классов, необходимых для решения задач по комбинаторике
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 просмотров)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 12:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru