Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
Раздел I (теоретический). Понятие множества
Можете ли вы представить, что натуральных чисел столько же, сколько и четных?! А точек на отрезке столько же, сколько и в квадрате? [ Рассказы о множествах. 3-е издание. – М.: МЦНМО, 2005. – 150 с.]
Положительные ответы на эти вопросы дает теория множеств.
Основные положения теории множеств впервые были разработаны:
- чешским математиком и философом Бернардом Больцано (1781-1848 г. г.), немецким математиком Рихардом Дедекиндом (1831-1916 г. г.), немецким математиком, профессором Галльского университета Георгом Кантором (1845-1918 г. г.).
Г. Кантор внес в теорию множеств (особенно бесконечных) наибольший вклад, поэтому теория множеств тесно связана с его именем.
Официально теория множеств была признана в 1897 году, когда Ж. Адамар и А. Гурвиц на международном конгрессе математиков в своих докладах привели многочисленные примеры применения теории множеств в различных разделах математики [ Основы дискретной математики. — М.: Высшая школа, 1986. — 311 с.].
Бернард Больцано (1781-1848) |
Рихард Дедекинд (1831-1916) |
Георг Кантор (1845-1918) |
Жак Адамар (1865-1963) |
Адольф Гурвиц (1859-1919) |
Итак, понятие множества является одним из фундаментальных понятий математики. Следуя Георгу Кантору, под множеством будем понимать совокупность объектов произвольной природы, которая рассматривается как единое целое. Объекты, входящие в состав множества, называются его элементами.
Это описание понятия множества нельзя считать логическим определением, а всего лишь пояснением. Понятие множества принимается как исходное, первичное, то есть не сводимое к другим понятиям.
Для обозначения множества общепринято использовать прописные (заглавные) буквы латинского алфавита: A, B, C, ... , X, Y, Z. Элементы же обозначаются строчными буквами: a, b, c, ...
Принадлежность элемента m множеству M обозначается так: m ? M, где знак ? является стилизацией первой буквы греческого слова ???? (есть, быть), знак непринадлежности – ?.
Приведем примеры множеств:
«из жизни»:- множество хищных животных; множество пальцев на руках у человека; множество планет Солнечной системы; множество карандашей;
- множество натуральных чисел; множество всех окружностей; множество (область) допустимых значений уравнения.
Множества бывают конечными, бесконечными и пустыми (
). Чтобы показать, что данное конечное множество состоит некоторого набора элементов, используют фигурные скобки для перечисления списка:
- M={январь, февраль, март, апрель, май, июнь, июль, август, сентябрь, октябрь, ноябрь, декабрь} – множество месяцев в году; C={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024} – множество степеней двойки от нулевой до 10-й.
В тех случаях, когда множество нельзя задать при помощи списка, для его элементов указывают характеристическое свойство. Характеристическое свойство – это такое свойство, которым обладает каждый элемент, принадлежащий множеству, и не обладает ни один элемент, который ему не принадлежит.
Примеры:
– множество четных чисел, т. е. таких, которые делятся на 2.
– множество степеней двойки от нулевой до 10-й;
– множество точек окружности.
Характеристическим свойством можно задавать как конечные, так и бесконечные множества.
Еще один способ задания множества называется порождающей процедурой. Такая процедура описывает способ получения новых элементов множества из уже полученных элементов по некоторому правилу.
Примеры:
; если 
, то 
– порождающая процедура для получения элементов множества четных чисел; 
; если 
, то 
– порождающая процедура для получения элементов множества степеней двойки. Над множествами (как и над другими математическими объектами) можно выполнять операции. С помощью операций из данных множеств можно получать новые множества.
Операция пересечения 
двух множеств А и В дает в результате множество, состоящее из тех и только тех элементов, которые принадлежат обоим множествам одновременно:
Объединением (суммой) 
множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А и В:
Разностью 
множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат множеству А и не принадлежат множеству В:
Пример:
Для множеств 
и 
найдем результаты рассмотренных операций.
Раздел II (практический). Класс в С++, реализующий работу с множеством (SET)
Цель: научиться при решении задач использовать контейнер set.
Задачи:
- изучить интерфейс класса set, рассмотреть классические примеры
- размещения нового элемента в множестве, поиска элемента, удаления элемента из множества, заполнения множества, вывода на экран элементов множества (в том числе, через итераторы),
Множество элементов set
Контейнер set позволяет организовать хранение множества элементов, обеспечивая следующую функциональность:
- добавить элемент в рассматриваемое множество, при этом исключая возможность появления дублей (insert); удалить элемент из множества (erase); узнать количество (различных) элементов в множестве (size); проверить, присутствует ли в множестве некоторый элемент (find).
Для подключения данного функционала необходимо использовать директиву препроцессора:
#include <set>
Познакомимся с интерфейсом set на примере фрагмента программы:
set<int> s; //описание множества целых чисел
for(int i=1; i<=100; i++) s. insert(i); // добавим сто
//первых натуральных чисел
s. insert(42); // ничего не произойдёт
// элемент 42 уже присутствует в множестве
int N=int(s. size()); // N будет равно 50
Такого понятия, как порядок элементов или индекс элемента, в set не существует. А раз уж у set нет понятия «индекс элемента», единственный способ просмотреть данные, содержащиеся в set, заключается в использовании итераторов.
Пример: вычисление суммы элементов множества S.
int r=0;
for(set<int>::const_iterator i = s. begin();
i!= s. end(); i++) r += (*i);
Однако, если предполагать возможные значения элементов, хранящихся в множестве, то можно использовать перебор таких значений и проверку их присутствия в множестве.
Основным преимуществом set перед vector является, несомненно, быстродействие. В основном это быстродействие проявляется при выполнении операции поиска. При добавлении операция поиска также неявно присутствует, потому как дубли в set не допускаются.
Метод set::find() имеет всего один аргумент. Возвращаемое им значение либо указывает на найденный элемент, либо равно итератору end() для данного экземпляра контейнера.
Пример:
for (int k=1; k<=100; k++)
if(s. find(k) != s. end()) cout<<k;
Для удаления элемента из set необходимо вызвать метод erase(), передав ему один параметр – элемент, который следует удалить, либо итератор, указывающий на удаляемый элемент.
Примеры:
s. erase(29);
s. erase(s. find(57));
Метод erase()имеет интервальную форму:
set<int>::iterator i1, i2;
i1 = s. find(10);
i2 = s. find(100);
//будет работать, если как 10, так и 100 //присутствуют в множестве
s. erase(i1, i2);
//при таком вызове будут удалены
//все элементы от 10 до 100 не включительно
Также, как и полагается контейнерам STL, у set есть интервальный конструктор:
int data[5]={5, 1, 4, 2, 3}; //объявлен и
//инициализирован массив
set<int> S(data, data+5);
Примеры программ
Пример 1. Основные возможности класса set
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
for(int i=1; i<=100; i++) s. insert(i);
s. insert(42);
cout<<"My set:"<<endl;
for (int k=1; k<=100; k++)
if(s. find(k) != s. end()) cout<<k<<",\t";
cout<<endl;
int N=int(s. size());
cout<<"N="<<N<<endl;
int r=0;
for(set<int>::const_iterator i = s. begin(); i!= s. end(); i++) r += (*i);
cout<<"summa="<<r<<endl;
s. erase(29);
s. erase(s. find(57));
cout<<"Delete 29 and 57:"<<endl;
for (int k=1; k<=100; k++)
if(s. find(k) != s. end()) cout<<k<<",\t";
cout<<endl;
set<int>::iterator i1, i2;
i1 = s. find(10);
i2 = s. find(100);
s. erase(i1, i2);
cout<<"Delete from 10 to 99:"<<endl;
for (int k=1; k<=100; k++)
if(s. find(k) != s. end()) cout<<k<<",\t";
cout<<endl;
return 0;
}
Результат работы программы:
Рисунок 1. Результат работы программы (создание множества, удаление элементов множества, просмотр элементов двумя способами)
Пример 2. Заполнение множества случайными символами
#include <stdio. h>
#include <set>
#include <stdlib. h>
#include <time. h>
using namespace std;
int main()
{
set<int> A;
int x;
srand(time(NULL));
int max_range=25;
printf("set A: \n");
for (int i=1;i<=10;i++)
{
x=97+rand()% max_range;
printf("%c ",x);//печатаем каждый генерируемый символ
A. insert(x);
}
printf("\n");
for(set<int>::const_iterator i=A. begin(); i!= A. end(); i++) printf("%c ",*i);
/*при выводе на экран содержимого множества А видим, что повторяющихся элементов в нем нет. Каждый символ входит в множество А ровно один раз*/
return 0;
}
Результат работы программы:
Рисунок 2. Формирование множества из символов
Пример 3. Реализация операции пересечения множеств
#include <stdio. h>
#include <set>
#include <stdlib. h>
#include <time. h>
using namespace std;
int main()
{
set<int> A, B,C;
int x;
srand(time(NULL));
int max_range=25;
printf("set A: \n");
for (int i=1;i<=20;i++)
{
x=97+rand()% max_range;
A. insert(x);
}
for(set<int>::const_iterator i=A. begin(); i!= A. end(); i++) printf("%c ",*i);
printf("\nset B: \n");
for (int i=1;i<=20;i++)
{
x=97+rand()% max_range;
B. insert(x);
}
for(set<int>::const_iterator i=B. begin(); i!=B. end(); i++) printf("%c ",*i);
for(set<int>::const_iterator i=A. begin(); i!=A. end(); i++) C. insert(*i);
for(set<int>::const_iterator i=B. begin(); i!=B. end(); i++) C. insert(*i);
for(set<int>::const_iterator i=C. begin(); i!=C. end(); i++)
{
char c=*i;
if (!(A. find(c)!=A. end() && B. find(c)!=B. end())) C. erase(c);
}
printf("\nset C: \n");
for(set<int>::const_iterator i=C. begin(); i!=C. end(); i++) printf("%c ",*i);
return 0;
}
Результат работы программы:
Рисунок 3. Множество 
Раздел 3. Самостоятельная работа
Предлагаемые здесь задачи являются контрольной работой №2 2017-2018 учебного года для учащихся 7-11 классов. Решите эти задачи, сформировав файлы отчета по каждой задаче в одном архиве, добавив в него также текстовый файл с информацией о вас:
- Фамилия, имя, класс, профиль класса (например: Голиков Василий, 9 кл., математический) Индекс, адрес места жительства, электронная почта (если есть), телефон (домашний или мобильный) Данные о школе (например: МБОУ №1 п. Бикин) Фамилия, И. О. учителя математики (например: учитель математики )
Электронную версию решения можно отправить на адрес электронной почты
Задания:
Для выполнения каждого задания написать программу на языке С/С++. В файл отчета включить формулировку задания, текст программы, скриншот консольного окна (результата выполнения программы).
Задать множество всех гласных букв английского алфавита (и строчных, и прописных) способом перечисления его элементов. Осуществить вывод на экран элементов множества, используя итераторы. Задать множество четных чисел от 40 до 80 с помощью характеристического свойства. Осуществить вывод на экран элементов множества, используя перебор возможных значений и проверку их присутствия в множестве. Задать множество степеней двойки от нулевой до 10-й с помощью порождающего правила. Осуществить вывод на экран элементов множества, используя итераторы. Реализовать операцию объединения двух множеств. Заполнение множеств осуществлять случайными символами (см. пример 3). Реализовать операцию разности для двух множеств. Заполнение множеств осуществлять случайными символами (см. пример 3).