Упорядоченные и частично-упорядоченные множества

Множества, основные определения.

Множеством называется совокупность некоторых элементов, объединенных каким-либо общим признаком. Элементами множества могут быть числа, фигуры, предметы, понятия и т.п.

Множества обозначаются прописными буквами, а элементы множество строчными буквами. Элементы множеств заключаются в фигурные скобки.

Если элемент x принадлежит множеству X, то записывают x ∈ Х (∈ — принадлежит).
Если множество А является частью множества В, то записывают А ⊂ В (⊂ — содержится).

1) Объединением множеств А и В называется множество, которое содержит только элементы из А и В по одному разу.

A = {1,2,5,7}

B = {2,5,9}

A U B = {1,2,5,7,9}

2) Вычитание

A \ B множество содержащие только элементы из A не входящие в множество B.

A \ B = {1,7}

2. Операции на множествах

Выражение операций на множествах друг через друга.

----

Упорядоченные и частично-упорядоченные множества.

Отношение порядка - это операция, позволяющая сравнить элементы множества по "меньше". Упорядоченные множества - множества + отношение порядка, для любой пары элементов отношения порядка

A = {5, 3, 2, 4, 7}

{A, <} = {2, 3, 4, 5, 7}

{A, >} = {7, 5, 4, 3, 2}

} - >

{A, } } = {7, 5, 4, 3, 2}

} = { i<=2i i<=2i+1

{ A, } } = {1, 3, 2, 7, 4}

Если отношение порядка подразумевает существование неравных элементов, то такое множество называется частично-упорядоченным множеством.

5. Одномерные массивы в С++

Одномерный массив — массив, с одним параметром, характеризующим количество элементов одномерного массива. Фактически одномерный массив — это массив, у которого может быть только одна строка, и n-е количество столбцов. Столбцы в одномерном массиве — это элементы массива. На рисунке 1 показана структура целочисленного одномерного массива a. Размер этого массива — 16 ячеек.

Рисунок 1 — Массивы в С++

Заметьте, что максимальный индекс одномерного массива a равен 15, но размер массива 16 ячеек, потому что нумерация ячеек массива всегда начинается с 0. Индекс ячейки – это целое неотрицательное число, по которому можно обращаться к каждой ячейке массива и выполнять какие-либо действия над ней (ячейкой).

где, int-целочисленный тип данных. а -имя одномерного массива;
16 — размер одномерного массива, 16 ячеек.

Всегда сразу после имени массива идут квадратные скобочки, в которых задаётся размер одномерного массива, этим массив и отличается от всех остальных переменных.

6. Двумерные массивы в С++

Объявление int A[n] создает в памяти одномерный массив: набор пронумерованных элементов, идущих в памяти последовательно. К каждому элементу массива можно обратиться, указав один индекс - номер этого элемента. Но можно создать и двумерный массив следующим образом: int A[n][m]. Данное объявление создает массив из n объектов, каждый из которых в свою очередь является массивом типа int [m]. Тогда A[i], где i принимает значения от 0 до n-1будет в свою очередь одним из n созданных обычных массивов, и обратиться к элементу с номером j в этом массиве можно через A[i][j].

Подобные объекты (массивы массивов) также называют двумерными массивами. Двумерные массивы можно представлять в виде квадратной таблицы, в которой первый индекс элемента означает номер строки, а второй индекс – номер столбца. Например, массив A[3][4] будет состоять из 12 элементов и его можно записать в виде

A[0][0] A[0][1] A[0][2] A[0][3]

A[1][0] A[1][1] A[1][2] A[1][3]

A[2][0] A[2][1] A[2][2] A[2][3]

Для считывания, вывода на экран и обработки двумерных массивов необходимо использовать вложенные циклы. Первый цикл – по первому индексу (то есть по всем строкам), второй цикл – по второму индексу, то есть по всем элементам в строках (столбцам). Например, вывести на экран двумерный массив в виде таблицы, разделяя элементы в строке одним пробелом можно следующим образом:

int A[n][m];

for (int i = 0; i < n; ++i)

{ // Выводим на экран строку i

for (int j = 0; j < m; ++j)

{

cout << A[i][j] << " ";

}

cout << endl;

// Строка завершается символом перехода на новую строку

}

А считать двумерный массив с клавиатуры можно при помощи еще более простого алгоритма (массив вводится по строкам, то есть в порядке, соответствующему первому примеру):

for (i = 0; i < n; ++i)

{

for (j = 0; j < m; ++j)

{

cin >> A[i][j];

}

7. Битовые операции в С++

8.
Элементы комбинаторики.

Перестановка - это упорядоченная выборка элементов множества S.

Сочетание - это неупорядоченная выборка элементов мн-ва S.

Элементы множества могут быть выбраны несколько раз, в зависимости от договоренности.

Пример:

S = {a,b,c}

Перестановки из 2-х с повторениями:

aa, ab, ac, bb, ba, bc, ca, cb, cc

Кол-во перестановок без повторений:

ab, ba, ac, ca, bc, cb

Сочетание без повторении:

ab, bc, ac.

Класс функции О()

К классу функции будем относить все функции, которые растут не быстрее чем

Больше ниче нет.:(

10. Смысл операции #include<>

11.
Типы данных С++

ИЛИ

Поиск по сайту: