Множини

Множини

Множина – основне математичне поняття.

            У Паскалі розглядаються тільки скінченні множини, що складаються не більш ніж з 256 різних елементів. Всі елементи мають бути значеннями одного порядкового типу (це типи Byte і Char або діапазон чи перелік значень з урахуванням допустимої кількості елементів).

            У Паскалі елементи множини беруть у квадратні дужки. Множина може не мати елементів, тобто бути порожньою, тоді її зображають так [ ].

            У квадратних дужках можуть знаходитися допустимі вирази зі змінними, наприклад, [i, j] – множина, що містить значення змінних i, j типу Byte. Порядок перерахування елементів ролі не грає і кожний елемент враховується тільки один раз, тому множина [1, 7, 3] еквівалентно [3, 1, 7]. Запис типу [5..5]  відповідає множині [5] , а [9..0] - порожній множині.

            Після задання типу множини сукупність значень відповідної змінної множинного типу визначається автоматично. У неї входять всі можливі підмножини, що є довільними комбінаціями значень.

            Змінну множинного типу описують так:

1 спосіб

type IntSet = set of 1..3;

var m: IntSet;

2 спосіб

var m: set of 1..3;

      c: set of char;

      y: set of (a,b,c);

      z: set of ‘a’..’f’;

Змінні множини m можуть набувати значень: [1, 2, 3],  [1, 2], [1, 3], [2, 3], [1], [2], [З], [].

Змінні множини b:Set of Boolean можуть мати значення: [true, false], [true], [false], [].

Змінній m задамо значення [1, 2] за допомогою оператора присвоєння: m:= [1, 2];

           

Набір операцій над множинами у Паскалі:

А = В     (Множини А і В збігаються)

А <>  В    (Множини А і В не збігаються)

А >= В  (Всі елементи множини В належать множині А)

А <= В  (Всі елементи множини А належать множині В)

х in А    (Значення х є того ж  типу, що і елементи множини А і належить множині А)

А + В    (Об’єднання множин А і В)

А * В    (Перетин множин А і В)

А - В     (Різниця множин А і В)

            Перші п’ять операцій у таблиці – це операції відношення. Вони повертають логічне значення true або false. Останні три операції утворюють нові множини. Операнди повинні бути одного типу.

            Є дві спеціальні процедури для роботи з одиночними елементами множини: include(А, x) і exclude(А, х), які відповідно включають або виключають елемент х з множини А.

            Множини зберігаються у пам’яті дуже компактно: кожне значення типу множини представляється лише одним бітом. У пам’ять комп’ютера заноситься 1 або 0 залежно від того, містить множина цей елемент чи ні. Наприклад, опишемо змінну var m: set of 1..5; то якщо m:= [1, 3]; то у пам'яті множина буде представлена так 10100, якщо M := []; тоді - 00000.

Д/З

1. Ввести рядок з цифр та малих латинських літер. Визначити, яких букв – голосних (a, e, i, o, u) чи приголосних – більше в цьому тексті.

2. var x,y,z:set of  8..100;

Змінній x присвоїти множину всіх цілих чисел від 8 до 100, змінній y – множину всіх простих чисел із цього діапазону, а змінній z – множину всіх складених чисел з цього діапазону.

3.  Ввести рядок. В алфавітному порядку надрукувати (по одному разу) всі малі англійські голосні літери (a, e, i, o, u), що входять в цей текст.

4.  Дано текст із малих латинських літер, який закінчується крапкою. Надрукувати:

a) перші входження букв у текст, зберігаючи їх початковий взаємний порядок;

b) всі літери, що входять в текст не менше ніж два рази;

c) всі літери, що входять в текст по одному разу.

Комбінований тип

Комбінований тип

1. Задано список з 30 учнів, для кожного вказані такі дані: прізвище, ім’я, вага, зріст, адреса (record з назви вулиці, номерів будинку та квартири)  та  10 оцінок.  Знайти

            а) середню вагу учнів;

            б) максимальний зріст учнів;

            в) прізвище та ім’я учня з максимальним зростом;

г) кількість учнів класу з ім’ям Андрій;

д) прізвища та імена учнів, прізвища яких починаються на ‘А’.

program pr1;

type Pupil = record

                                  Surname, Name: string[20];

                                   Vaga:integer;

   Zrist: real;

   Adress:record

                  Street:string[15];

                  House, flat:integer

                end;

                                   Marks: array [1..10] of 1..12;

                        end;

var klass: array[1..30] of Pupil;

      I,j:integer;

Begin

{ Вводимо дані }

  for i := 1 to 30 do

  begin

     writeln('Введіть прізвище');

     readln(Klass[i].Surname);

     writeln('Введіть імя');

     readln(Klass[i].Name);

     writeln('Введіть вагу');

     readln(Klass[i].Vaga);

     writeln('Введіть зріст');

     readln(Klass[i].Zrist);

     writeln('Введіть адресу');

     readln(Klass[i].Adress.Street);

     readln(Klass[i].Adress.House, Klass[i].Adress.Flat);

     for j:=1 to 10 do

      begin

      writeln('Введіть оцінку');

           readln(Klass[i].Marks[j]);

     end;

  end;

{Використаємо оператор приєднання для вводу }

      for i:=1 to 30 do  

          with klass[i] of

               begin

                    readln(Surname);

                    readln(Name);

                      readln(Vaga, Zrist);

                    readln(Adress.Street);

                      readln(Adress.House, Adress.Flat);

                    for j:=1 to 10 do  readln(Marks[j]);

               end;

{ а) Знайти середню вагу школярів }

  SerVaga := 0;     

  for i := 1 to 30 do

    SerVaga:= SerVaga+Klass[i].Vaga;

SerVaga:= SerVaga /30;

writeln(SerVaga);

{ б) Знайти максимальний зріст }

  MaxZrist := 0;          {Описати змінну MaxZrist }

  for i := 1 to 30 do

     if Klass[i].Zrist> MaxZrist then MaxZrist := Klass[i].Zrist;

  writeln(MaxZrist);

{ г) Знайти кількість щколярів на ім'я Андрій }

  NameCount := 0;

  for i := 1 to 30 do

     if Klass[i].Name = 'Андрій' then NameCount:= NameCount+1;

  writeln(NameCount);

{ д) Вивести прізвища та імена школярів, у яких прізвище починається на літеру ‘А’ }

  for i := 1 to 30 do

      if Klass[i].SurName[1] =’A then writeln(Klass[i].Surname ,' ',Klass[i].Name);

    

-------------------------------------------------------------------------------------------------------------------

Продовжуємо цю задачу

{ Знайти  кількість щколярів, у яких середня оцінка не менша 8 і не більша 10}

Count := 0;

for i := 1 to 30 do

begin

    MarkSum := 0;

    for j := 1 to 10 do

        MarkSum:=MarkSum+Klass[i].Marks[j];          { inc(MarkSum,Klass[i].Marks[j]) }

    AvgMark := MarkSum/10;

    if (AvgMark >= 8) and (AvgMark <= 10) then

        Inc(Count);

  end;

  writeln(Count);

{ Вивести прізвища та імена школярів, у яких найменша оцінка 10 }

  for i := 1 to 30 do

  begin

    MinMark := 13;

    for j := 1 to 10 do

        if Klass[i].Marks[j] < MinMark then MinMark := Klass[i].Marks[j];

    if MinMark = 10 then

        writeln(Klass[i].Surname ,' ',Klass[i].Name);

  end;

end.    {Кінець програми}

Д/з №1

1. Знайти кількість учнів з вагою більше середньої.
2. Вивести прізвища та імена учнів, прізвища яких починаються на літери ‘Бо’.
3. Знайти кількість учнів, які проживають по вулицях Петлюри та Садова.
4. Вивести прізвища учнів, які проживають у будинках  та квартирах з парними номерами

Д/з №2 (виконати ті завдання, що не встигли на уроці)

Знайти

1. Середнє арифметичне значення оцінок кожного учня.
2. Максимальну оцінку кожного учня.
3. Середнє арифметичне оцінок по кожному предмету.
4. Максимальну оцінку по кожному предмету.
5. Вивести прізвища та імена учнів, у яких всі оцінки не менші 10 балів.
6. Вивести прізвища учнів, які мають оцінки не нижче 8 балів та прізвища яких починаються з літер Б або В.
7. обчислити середній бал класу і вивести список учнів, які мають середній бал вищий  за середній бал класу;
8. Вивести дані про учня, який найкраще вчиться.
9. Вивести дані учня з ім’ям Андрій, який найкраще вчиться.

Обмежений тип

Д/з. (Використовуємо оператор case)

1. Ввести число обмеженого типу ( від 1 до 20). Якщо число від 1 до 12, то вивести назву відповідної пори року, інакше вивести повідомлення про помилку.

2. Ввести число обмеженого типу ( від -10 до 10). Якщо число -10 або 10, то обчислити крадрат цього число і куб, якщо число рівне -9,-8,-7,-6,-5,-4,-3,-2,-1,0, то обчислити модуль цього число, при всіх інших значеннях обчислити корінь квадратний з числа, та збільшити число на 5.

11клас. С++ Для Ярослава

+           Л Е К Ц І Я   6

1. ШАБЛОНЫ

Шаблоны позволяют определять функции, которые могут работать с разными типами данных. Шаблоны определяются следующим образом:

template <class идентификатор> определение функции;

template <typename идентификатор> определение функции;

Оба определения идентичны. Можно использовать как ключевое слово class, так и typename.

Например, в С можно создать перегруженную функцию вычисления модуля abs:

int abs(int n)

{

return n < 0 ? -n : n;

}

double abs(double n)

{

return n < 0 ? -n : n;

}

Используя шаблон, можно создать единственное определение, которое будет автоматически обрабатывать любой тип данных:

#include <stdio.h>

template <class T> T abs(T n)

{

return n < 0 ? -n : n;

}

void main (void)

{

  double d = abs(-4.55);

  int i = abs(-7);

  printf("%lf %d\n",d,i);

}

Следующий шаблон вычисляет максимум двух чисел:

template <class Type> Type max (Type a, Type b)

{

  return (a > b ? a : b);

}

Переменная Type может принимать любой тип. При вызове функции можно указывать явно тип, с которым она будет работать:

имя функции <тип> (параметры)

Функцию max можно вызвать следующим образом:

int i = max<int>(7,76);

Разнотиповые аргументы передавать функции max запрещается. Можно определить шаблон функции , которая может принимать разнотиповые приводимые аргументы:

template <class Type1, class Type2> Type1 max (Type1 a, Type2 b)

{

  return (a > b ? a : b);

}

Тогда функцию max можно вызвать одним из следующих способов:

int i = max(7,76);

int i = max<int,long>(7,76);

2. ИМЕНОВАННЫЕ ОБЛАСТИ    namespace

Именованные области (namespace) позволяют объединять глобальные классы, объекты, функции под одним именем. Другими словами они позволяют разбивать глобальное пространство на области, в каждой из которых действуют свои объекты.

Определяются именованные области следующим образом:

namespace <идентификатор>

{

   <тело именованной области>

}

Тело именованной области может содержать множество классов, объектов и функций. Например:

namespace ivan

{

   int a,b;

}

Для доступа к элементам именованной области извне используется оператор расширения видимости :: . Например, для доступа к переменной a следует написать: ivan::a. Следующая программа создает две именованные области, каждая из которых содержит переменную. Переменные и функции из разных именованных областей могут иметь одинаковые имена.

#include <iostream.h>

namespace first

{

  int var = 5;

}

namespace second

{

  double var = 3.1416;

}

void main (void)

{

  cout << first::var << endl;

  cout << second::var << endl;

}

using namespace

Директива using позволяет ассоциировать текущее глобальное пространство объектов с именованной областью. После выполнения команды

using namespace <идентификатор>

можно напрямую иметь доступ ко всем объектам и функциям именованной области.

#include <iostream.h>

namespace first

{

  int var = 5;

}

namespace second

{

  double var = 3.1416;

}

void main (void)

{

  {

    using namespace first;

    cout << var << endl;

  }

  {

    using namespace second;

    cout << var << endl;

  }

}

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

3. СТАНДАРТНАЯ БИБЛИОТЕКА ШАБЛОНОВ STL

Стандартная библиотека шаблонов STL (standard template library) – это набор шаблонов функций и классов в языке С++, включающий в себя различные контейнеры данных (список, очередь, множество, отображение, хэш таблица, очередь с приоритетами) и базовые алгоритмы (сортировка, поиск).

Стандартная библиотека шаблонов является именованной областью с именем std. При ее использовании включаемые файлы пишутся без расширения .h, а к некоторым еще добавляется приставка c. Например, аналогом библиотек <stdio.h>, <limits.h> в STL будут <cstdio>, <climits>.

Для подключения стандартной библиотеки шаблонов следует воспользоваться директивой:

using namespace std;

#include <iostream> void main (void) {   std::cout << "Hello, world!\n"; }

#include <iostream> using namespace std; void main (void) {   cout << "Hello, world!\n"; }

Библиотека STL содержит пять основных видов компонентов:

1.    алгоритм (algorithm): определяет вычислительную процедуру.

2.    контейнер (container): управляет набором объектов в памяти.

3.    итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.

4.    функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.

5.    адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

Контейнерами называются часто встречающиеся способы организации данных: динамические массивы, списки, очереди, стеки.

 Алгоритмы не являются частью контейнеров, а образуют отдельную подсистему. Но при этом почти любой алгоритм может применяться к почти любому контейнеру. Вызывая метод для некоторого алгоритма, мы вызываем этот метод сам по себе, а не для экземпляра некоторого класса. Контейнер же, к которому применяется алгоритм, передается в качестве параметра.

 Итератор - это указатель, который может двигаться по элементам контейнера. Итераторы играют такую же роль, как индекс у элемента массива. Через индекс массива мы можем получить некоторый элемент массива, и через итератор мы можем получить некоторый элемент контейнера.

4. ВЕКТОРЫ

 Вектором называется последовательность объектов с прямым доступом. Поддерживает константное время вставки-удаления  элемента из конца последовательности и линейное время вставки-удаления из середины или начала. Количество элементов вектора изменяется динамически, управление памятью совершается автоматически. Для использования векторов следует включить библиотеку:

#include <vector>

Для создания экземпляра вектора можно воспользоваться одним из следующих конструкторов:

Конструктор	описание конструктора
vector()	Создание пустого вектора
vector(size_type n)	создание вектора из n элементов
vector(size_type n, const T& t)	создание вектора из n копий t
vector(const vector&)	Копирующий конструктор

Пример 4.1. Рассмотрим работу конструкторов векторов на примерах.

Создание пустого вектора v (массива нулевой длины, не содержащего ни одного элемента):

vector<int> v;

Создание вектора v длины 10:

vector<int> v(10);

Создание вектора v длины 10, все элементы которого равны 5:

vector<int> v(10,5);

Пусть имеется массив чисел m. Для того чтобы создать вектор v, содержащий эти же числа, следует воспользоваться копирующим конструктором:

int m[] = {1,2,3,4,5};

vector<int> v(m,m+5);

Для создания еще одного вектора u с элементами 3, 4, 5 можно воспользоваться конструктором копированием интервала:

vector<int> u(&v[2],&v[5]);

Через reference будем обозначать тип “ссылка”. Следующие методы созданы для работы с вектором:

метод	описание метода
void clear()	удаление всех элементов. Вектор становится пустым
size_type size() const	вычисляет размер вектора
bool empty() const	возвращает истину, если вектор пустой
reference operator[](size_type n)	оператор индексирования, возвращает n–ый элемент вектора
reference front()	возвращает первый элемент вектора
reference back()	возвращает последний элемент вектора

Пример 4.2. Пусть имеется массив чисел m. Создадим вектор v, скопировав в него данные массива m.

int m[] = {1,2,3,4,5};

vector<int> v(m,m+5);

Выведем размер вектора:

printf("Size: %d\n",v.size());

Выведем первый и последний элементы вектора:

printf("First: %d, Last: %d\n",v.front(),v.back());

Выведем все элементы вектора, используя оператор индексирования:

for(int i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");

Следующая таблица описывает методы вставки и удаления элементов вектора:

метод	описание метода
void push_back(const T& x)	вставка элемента x в конец вектора
void pop_back()	удаление последнего элемента

Итератором называется указатель на объект. Создается итератор следующим образом:

имя_шаблона<тип>::iterator имя_итератора

Класс vector имеет следующие встроенные итераторы:

итератор	описание итератора
const_iterator begin() const	указатель на начало вектора
const_iterator end() const	указатель на конец вектора

Пример 4.3. Занесем в вектор v числа 4, 10, 1. Выведем элементы вектора v при помощи итератора iter.

vector<int> v;

vector<int>::iterator iter;

v.push_back(4); v.push_back(10); v.push_back(1);

for(iter=v.begin();iter!=v.end();iter++) printf("%d ",*iter); printf("\n");

Для вставки и удаления элементов внутри вектора используются методы, аргументами которых выступают итераторы:

метод	описание метода
iterator insert(iterator pos,         const T& x)	вставка элемента x в позицию pos
iterator erase(iterator pos)	удаление элемента, на который указывает итератор pos
iterator erase(iterator first,              iterator last)	удаление всех элементов, расположенных в промежутке [first..last]

Пример 4.4. Занесем в вектор v квадраты натуральных чисел от 1 до 10. Удалим из вектора значения 16, 25, 36, 49.

vector<int> v;

for(i=1;i<=10;i++) v.push_back(i*i);

for(i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");

v.erase(v.begin()+3,v.end()-3);

for(i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");

Упражнение 4.1. Имеется лужа некоторой формы, имеющей определенную глубину. Известно, что поперечный разрез лужи одинаков на всех глубинах. Массив rates содержит скорость наполнения лужи в определенные интервалы времени,  durations[i] содержит время, в течении которого лужа наполнялась со скоростью rates[i]. За все интервалы времени, указанные в durations, лужа наполнилась до высоты height. Необходимо определить площадь поперечного разреза лужи.

Класс: SwimmingPool

Метод: int area(vector<int> rates, vector<int> durations,

                int height)

Ограничения: массивы rates и durations содержат одинаковое количество чисел, 1 £ rates[i],durations[i],height £ 100.

Вход. Массивы  rates и durations, содержащие скорость и время наполнения лужи. Целое число height содержит глубину лужи.

Выход. Площадь поперечного разреза лужи.

Пример входа

rates	durations	height
{1,2,3,4,5}	{5,4,3,2,1}	10
{5,4,3,2,1}	{1,2,3,4,5}	100
{100}	{1}	100

Пример выхода

3

0

1

Вычисляем объем воды, которой наполнилась лужа. Разделив полученный объем на высоту, получим площадь поперечного разреза лужи.

#include <cstdio>

#include <vector>

using namespace std;

class SwimmingPool

{

public:

  int area(vector<int> rates, vector<int> durations, int height)

  {

    int i,vol=0;

    for(i=0;i<rates.size();i++)

      vol += rates[i]*durations[i];

    return vol / height;

  }

};

Упражнение 4.2. В футболе за победу команда получает 3 очка, за ничью 1 очко, за проигрыш – 0. Массивы wins и ties содержат информацию об играх, проведенных футбольными командами в лиге: wins[i] равно числу выигранных матчей i - ой командой, ties[i] равно числу матчей, сведенных i - ой командой вничью. Необходимо найти команду с наибольшим количеством очков.

Класс: Soccer

Метод: int maxPoints(vector<int> wins, vector<int> ties)

Ограничения: массивы wins  и ties содержат одинаковое количество чисел, 0 £ wins[i],ties[i] £ 100.

Вход. Массивы  wins и ties, содержащие информацию о командах.

Выход. Наибольшее количество очков, заработанное одной командой в лиге.

Пример входа

wins	ties
{1,4,3,0,0}	{3,1,5,3,1}
{12,45,20,17,48,0}	{48,10,53,94,0,100}
{35,0}	{0,76}

Пример выхода

14

145

105

Для каждой команды вычисляем полученное количество очков в лиге. Среди набранного количества очков каждой командой находим наибольшее значение.

#include <cstdio>

#include <vector>

using namespace std;

class Soccer

{

public:

  int maxPoints(vector<int> wins, vector<int> ties)

  {

    int max = 0;

    for(int i=0;i<wins.size();i++)

      if (wins[i]*3+ties[i] > max) max = wins[i]*3+ties[i];

    return max;

  }

};