Алгоритмизация и программирование. Язык C++. (§ 38 - § 45)

1. Алгоритмизация и программирование. Язык C++

1
Алгоритмизация и
программирование.
Язык C++
§ 38. Целочисленные алгоритмы
§ 39. Структуры
§ 40. Динамические массивы
§ 41. Списки
§ 42. Стек, очередь, дек
§ 43. Деревья
§ 44. Графы
§ 45. Динамическое программирование
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

2. Алгоритмизация и программирование. Язык C++

2
Алгоритмизация и
программирование.
Язык C++
§ 38. Целочисленные
алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

3. Решето Эратосфена

3
Алгоритмизация и программирование. Язык C++, 11 класс
Решето Эратосфена
3 4 5 6 7 8 9 10 11 12 13 14 15 16
22 3
Алгоритм:
1) начать с k = 2
Эратосфен Киренский
2) «выколоть» все числа через k, начиная с 2k···kk
(Eratosthenes, Ερατοσθδνη)
3) перейти к следующему «невыколотому» k
(ок. 275-194 до н.э.)
<=N N , то перейти к шагу 2
4) если kk··k<=
5) напечатать все числа, оставшиеся «невыколотыми»
Новая версия – решето Аткина.
?
Как улучшить?
высокая скорость, количество операций
O((N·log N)·log log N )
нужно хранить в памяти все числа от 1 до N
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

4. Решето Эратосфена

4
Алгоритмизация и программирование. Язык C++, 11 класс
Решето Эратосфена
Задача. Вывести все простые числа от 2 до N.
Объявление переменных:
const int N = 100;
bool A[N+1];
выделяем на 1
int i, k;
элемент больше,
чтобы начать с
A[1]
Сначала все невычеркнуты:
for ( i = 2; i <= N; i++ )
A[i] = true;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

5. Решето Эратосфена

5
Алгоритмизация и программирование. Язык C++, 11 класс
Решето Эратосфена
Вычёркивание непростых:
k = 2;
while ( k*k <= N ) {
if ( A[k] ) {
i = k*k;
while ( i <= N )
{
A[i] = false;
i += k;
}
}
k ++;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

6. Решето Эратосфена

6
Алгоритмизация и программирование. Язык C++, 11 класс
Решето Эратосфена
Вывод результата:
for ( i = 2; i <= N; i++ )
if ( A[i] )
cout << i << " ";
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

7. «Длинные» числа

7
Алгоритмизация и программирование. Язык C++, 11 класс
«Длинные» числа
Ключи для шифрования: 256 битов.
Целочисленные типы данных: 64 битов.
?
Как хранить?
Длинное число – это число, которое не помещается в
переменную одного из стандартных типов данных
языка программирования.
«Длинная арифметика» – алгоритмы для работы с
длинными числами.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

8. «Длинные» числа

8
Алгоритмизация и программирование. Язык C++, 11 класс
«Длинные» числа
A = 12345678
A
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
0
0
?
Что плохо?
нужно хранить длину числа
неудобно вычислять (с младшего разряда!)
неэкономное расходование памяти
Обратный порядок элементов:
A
9
8
7
6
5
4
3
2
1
0
0
0
1
2
3
4
5
6
7
8
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

9. «Длинные» числа

9
Алгоритмизация и программирование. Язык C++, 11 класс
«Длинные» числа
Упаковка элементов:
A
A = 12345678
9
8
7
6
5
4
3
0
0
0
0
0
0
0
2
1
0
12 345 678
12345678 = 12·10002 + 345·10001 + 678·10000
?
На что похоже?
система счисления
с основанием 1000!
long int:
от –231 = – 2 147 483 648 до 231 – 1 = 2 147 483 647.
?
Какие основания можно использовать?
должны помещаться все
промежуточные результаты!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

10. Вычисление факториала

10
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление факториала
Задача 1. Вычислить точно значение факториала
100! = 1·2·3·…·99·100
?
Как оценить количество цифр?
201 цифра
1·2·3·…·99·100 < 100100
основание
6 цифр в ячейке 34 ячейки
1000000
const int N = 33;
long int A[N+1];
Основной алгоритм:
длинное
число
[A] = 1;
for ( k = 2; k <= 100; k ++ )
[A] = [A] * k;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

11. Вычисление факториала

11
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление факториала
основание d = 1 000 000
[A] = 12345678901734567
A
3
2
1
0
0
12345
678901
734567
734 567·3 = 2 203 701
r = перенос в A[1]
?
*3
остаётся в
A[0]
Как найти перенос?
s = A[0]*k;
A[0] = s % d;
r = s / d;
?
Что изменится для A[1]?
К.Ю. Поляков, Е.А. Ерёмин, 2014
s = A[1]*k +
r;
http://kpolyakov.spb.ru

12. Вычисление факториала

12
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление факториала
Умножение «длинного» числа на k:
r = 0;
for ( i = 0; i <= N; i++ ) {
s = A[i] * k + r;
A[i] = s % d;
r = s / d;
}
все разряды
Вычисление 100!:
for ( k = 2; k <= 100; k++ )
{
...
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

13. Вывод длинного числа

13
Алгоритмизация и программирование. Язык C++, 11 класс
Вывод длинного числа
A
3
2
1
0
0
1
2
3
?
Какое число?
[A] = 1000002000003
• найти старший ненулевой разряд
i = N;
while ( ! A[i] )
i --;
• вывести этот разряд
cout << A[i];
• вывести все следующие разряды, добавляя
лидирующие нули до 6 цифр
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

14. Вывод длинного числа

14
Алгоритмизация и программирование. Язык C++, 11 класс
Вывод длинного числа
Вывод остальных разрядов:
for ( k = i-1; k >= 0; k-- )
Write6 ( A[k] );
Write6:
x = 12345
x /
100000
012345
x %
100000
К.Ю. Поляков, Е.А. Ерёмин, 2014
со старшего
x
M
x / M
12345
100000
0
12345
10000
1
2345
1000
2
345
100
3
45
10
4
5
1
5
http://kpolyakov.spb.ru

15. Вывод длинного числа

Алгоритмизация и программирование. Язык C++, 11 класс
15
Вывод длинного числа
Вывод числа с лидирующими нулями:
void Write6 ( long int x )
{
long int M = 100000;
while ( M > 0 )
{
cout << x / M;
x %= M;
M /= 10;
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

16. Алгоритмизация и программирование. Язык C++

16
Алгоритмизация и
программирование.
Язык C++
§ 39. Структуры
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

17. Зачем нужны структуры?

17
Алгоритмизация и программирование. Язык C++, 11 класс
Зачем нужны структуры?
Книги в библиотеках:
символьные
• автор
строки
• название
• количество экземпляров
целое число
•…
?
Как хранить данные?
Несколько массивов:
string authors[N];
string titles[N];
int count[N];
...
неудобно работать
(сортировать и
т.д.), ошибки
Задачa: объединить разнотипные данные в один блок.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

18. Структуры

18
Алгоритмизация и программирование. Язык C++, 11 класс
Структуры
Структура – это тип данных, который может включать в
себя несколько полей – элементов разных типов (в
том числе и другие структуры).
новый тип данных
typedef struct
структура
{
string author; // автор, строка
string title;
// название, строка
int count;
// количество, целое
} TBook;
название типа
данных
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

19. Объявление структур

19
Алгоритмизация и программирование. Язык C++, 11 класс
Объявление структур
const
TBook
TBook
?
int N = 100;
B;
Books[N];
Сколько места занимает в памяти?
cout
cout
cout
<<
<<
<<
sizeof(TBook) << endl;
sizeof(B) << endl;
sizeof(Books) << endl;
typedef
typedef struct
struct
4 байта
{{
string
string author;
author;
4 байта
string
string title;
title;
int
int count;
count;
}} TBook;
4 байта
TBook;
К.Ю. Поляков, Е.А. Ерёмин, 2014
//
//
//
!
12
12
1200
Это указатели!
http://kpolyakov.spb.ru

20. Обращение к полям структур

20
Алгоритмизация и программирование. Язык C++, 11 класс
Обращение к полям структур
Точечная нотация:
B.author // поле author структуры B
Books[5].count // поле count структуры
// Books[5]
cout
cout
cout
cin
cin
cin
<<
<<
<<
>>
>>
>>
sizeof(B.author) << endl;
sizeof(B.title) << endl;
sizeof(B.count) << endl;
//
//
//
4
4
4
B.author;
B.title;
B.count;
cout << B.author << " " << B.title << ". “
<< B.count << " шт.";
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

21. Обращение к полям структур

21
Алгоритмизация и программирование. Язык C++, 11 класс
Обращение к полям структур
Присваивание:
B.author = "Пушкин А.С.";
B.title = "Полтава";
B.count = 1;
Использование:
B.count --;
// одну книгу взяли
if( B.count == 0 )
cout << "Этих книг больше нет!";
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

22. Запись структур в файлы

22
Алгоритмизация и программирование. Язык C++, 11 класс
Запись структур в файлы
Текстовые файлы:
символ-разделитель
'Пушкин А.С.';'Полтава';12
'Лермонтов М.Ю.';'Мцыри';8
!
Сложно читать,
ошибки!
Двоичные файлы:
поток
двоичный
вывода
ofstream Fout;
Fout.open ( "books.dat", ios::binary );
Fout.write ( (char*) &B, sizeof(TBook) );
Fout.write ( (char*) Books,
адрес
в
сколько
12*sizeof(TBook)
);
памяти
байтов
Fout.close ();
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

23. Чтение структур из файла

23
Алгоритмизация и программирование. Язык C++, 11 класс
Чтение структур из файла
Одна структура:
ifstream *Fin;
Fin.open ( "books.dat", ios::binary );
Fin.read ( (char*) &B, sizeof(B) );
cout << B.author << " " << B.title
адрес в
сколько
<< ". "памяти
<< B.count байтов
<< " шт.";
Fin.сlose ();
Сразу несколько структур:
Fout.read ( (char*) Books,
5*sizeof(TBook) );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

24. Чтение структур из файла

24
Алгоритмизация и программирование. Язык C++, 11 класс
Чтение структур из файла
Число структур неизвестно:
const int N = 100;
int M;
...
Fin.read ( (char*) Books,
N*sizeof(TBook) );
M = Fin.gcount() / sizeof(TBook);
cout << "Прочитано " << M << " структур.";
!
gcount возвращает число успешно
прочитанных байтов!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

25. Сортировка структур

25
Алгоритмизация и программирование. Язык C++, 11 класс
Сортировка структур
Ключ – фамилия автора:
?
for ( i = 0; i < N - 1; i++ )
for ( j = N - 2; j >= i; j-- )
if ( Books[j].author >
Books[j+1].author) )
{
TBook В;
B
=
Books[j];
B = Books[j];
Books[j]
Books[j+1];
Books[j] =
= Books[j+1];
Books[j+1]
B;
Books[j+1] =
= B;
}
Какой метод?
структуры перемещаются в памяти
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

26. Указатели

26
Алгоритмизация и программирование. Язык C++, 11 класс
Указатели
Указатель – это переменная, в которой можно сохранить
адрес любой переменной заданного типа.
TBook *p;
указатель на
переменную типа
TBook
p = &B;
p->author
p=
B &Books[2];
B.author
p
0
1
2
3
4
Books
p->author Books[2].author
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

27. Сортировка по указателям

27
Алгоритмизация и программирование. Язык C++, 11 класс
Сортировка по указателям
TBook *p[N], *p1;
for ( i = 0; i < N; i++ )
p[i] = &Books[i];
p[0]
Books
p[1]
p[2]
0
1
2
…
Нагибин Ю. … … Астафьев В. … … Васильев Б. … … …
Задача – переставить указатели:
p[2]
Books
p[0]
p[1]
0
1
2
…
Нагибин Ю. … … Астафьев В. … … Васильев Б. … … …
!
Сами структуры не перемещаются!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

28. Сортировка по указателям

28
Алгоритмизация и программирование. Язык C++, 11 класс
Сортировка по указателям
обращение к
for ( i = 0; i < M-1; i++ )
полям через
for ( j = M-2; j >= i; j-- )
указатели
if ( p[j]->author > p[j+1]->author )
{
переставляем
p1 = p[j]; p[j]= p[j+1];
указатели!
p[j+1]= p1;
}
TBook
Вывод результата: *p1;
for ( i = 0; i < M; i++ )
cout << p[i]->author << " " << p[i]->title
<< ". " << p[i]->count
<< " шт." << endl;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

29. Алгоритмизация и программирование. Язык C++

29
Алгоритмизация и
программирование.
Язык C++
§ 40. Динамические массивы
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

30. Чем плох обычный массив?

30
Алгоритмизация и программирование. Язык C++, 11 класс
Чем плох обычный массив?
const int N = 100;
статический
массив
int A[N];
• память выделяется при трансляции
• нужно заранее знать размер
• изменить размер нельзя
Задача. В файле записаны фамилии (сколько –
неизвестно!). Вывести их в другой файл в алфавитном
порядке.
• выделить заранее большой блок (с запасом)
• выделять память во время работы программы
(динамически!)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

31. Динамические структуры данных

31
Алгоритмизация и программирование. Язык C++, 11 класс
Динамические структуры данных
… позволяют
• создавать новые объекты в памяти
• изменять их размер
• удалять из памяти, когда не нужны
Задача. Ввести с клавиатуры целое значение N, затем –
N целых чисел, и вывести на экран эти числа в
порядке возрастания.
//
//
//
прочитать данные из файла в массив
отсортировать их по возрастанию
вывести массив на экран
?
В чём проблема?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

32. Динамические массивы

Алгоритмизация и программирование. Язык C++, 11 класс
32
Динамические массивы
Объявление:
int *A;
!
Память не выделяется!
Выделение памяти:
A = new int[N];
количеств
о
элементов
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

33. Динамические массивы

Алгоритмизация и программирование. Язык C++, 11 класс
33
Динамические массивы
Использование массива:
for ( i = 0; i < N; i++ )
cin >> A[i];
...
for ( i = 0; i < N; i++ )
{
A[i] = i;
cout << A[i] << " ";
}
Освобождение памяти:
delete [] A;
удаление
массива
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

34. Тип vector (библиотека STL)

34
Алгоритмизация и программирование. Язык C++, 11 класс
Тип vector (библиотека STL)
STL = Standard Template Library
!
Вектор – это массив переменного размера!
Заголовочный файл:
#include <vector>
Объявление:
vector <int> A;
Размер:
пустой
массив типа
int
cout << A.size();
Заполнение (добавление в конец):
for ( i = 0; i < N; i++ )
A.push_back ( i + 1 );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

35. Тип vector (библиотека STL)

Алгоритмизация и программирование. Язык C++, 11 класс
35
Тип vector (библиотека STL)
Обработка :
for ( i = 0; i < A.size(); i++ )
cout << A[i] << " ";
!
Так же, как с обычным массивом!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

36. Динамические матрицы

36
Алгоритмизация и программирование. Язык C++, 11 класс
Динамические матрицы
!
Матрица – это массив из массивов!
Указатель на матрицу:
новый тип
данных: указатель
typedef int *pInt;
pInt *A;
указатель на указатель
Выделение памяти под массив указателей:
A = new pInt[N];
Выделение памяти под элементы матрицы:
A[0] = new int[M*N];
число элементов
матрицы
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

37. Динамические матрицы

37
Алгоритмизация и программирование. Язык C++, 11 класс
Динамические матрицы
0
1
2
N-2
N-1
массив
указателей
A
M
M
Расстановка указателей:
for ( i = 1; i < N; i++ )
A[i] = A[i-1] + M;
Работа с матрицей:
for ( i = 0; i < N; i++ )
for ( j = 0; j < M; j++ )
A[i][j] = i + j;
К.Ю. Поляков, Е.А. Ерёмин, 2014
M
M
Удаление:
delete []
delete []
A[0];
A;
http://kpolyakov.spb.ru

38. Динамические матрицы

38
Алгоритмизация и программирование. Язык C++, 11 класс
Динамические матрицы
0
1
2
N-2
N-1
массив
указателей
A
M
!
M
M
Строки могут быть разной длины!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

39. Динамические матрицы

39
Алгоритмизация и программирование. Язык C++, 11 класс
Динамические матрицы
Выделение памяти:
for ( i = 0; i < N; i++ )
A[i] = new int[M];
Освобождение памяти:
for ( i = 0; i < N; i++ )
delete [] A[i];
освободить
память для
отдельных строк
delete [] A;
освободить
массив указателей
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

40. Динамические матрицы (vector)

40
Алгоритмизация и программирование. Язык C++, 11 класс
Динамические матрицы (vector)
Объявление:
typedef vector<int> vint;
vector <vint> A;
вектор из векторов
Изменение размера (число строк):
A.resize ( N );
Установка размера строк:
for ( i = 0; i < N; i++ )
A[i].resize ( M );
!
Строки могут быть
разной длины!
Использование:
for ( i = 0; i < N; i++ )
for ( j = 0; j < M; j++ )
A[i][j] = i + j;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

41. Расширение массива

41
Алгоритмизация и программирование. Язык C++, 11 класс
Расширение массива
Задача. С клавиатуры вводятся натуральные числа, ввод
заканчивается числом 0. Нужно вывести на экран эти
числа в порядке возрастания.
?
Какой размер массива нужен?
Ввод данных:
cin >> x;
while ( x != 0 )
{
A.push_back(x);
автоматическое
расширение
cin >> x;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

42. Алгоритмизация и программирование. Язык C++

42
Алгоритмизация и
программирование.
Язык C++
§ 41. Списки
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

43. Зачем нужны списки?

43
Алгоритмизация и программирование. Язык C++, 11 класс
Зачем нужны списки?
Задача. В файле находится список слов, среди которых
есть повторяющиеся. Каждое слово записано в
отдельной строке. Построить алфавитно-частотный
словарь: список слов в алфавитном порядке, справа
от каждого слова должно быть указано, сколько раз
оно встречается в исходном файле.
!
Нужно вставлять новые слова в список!
Список – это упорядоченный набор элементов одного
типа, для которого введены операции вставки
(включения) и удаления (исключения).
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

44. Алгоритм (псевдокод)

44
Алгоритмизация и программирование. Язык C++, 11 класс
Алгоритм (псевдокод)
пока есть слова в файле
{
прочитать очередное слово
если оно есть в списке то
увеличить на 1 счётчик для этого слова
иначе
{
добавить слово в список
записать 1 в счетчик слова
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

45. Использование контейнера map (STL)

45
Алгоритмизация и программирование. Язык C++, 11 класс
Использование контейнера map (STL)
Map («отображение») – это словарь (ассоциативный
массив). Индексы элементов – любые данные.
Объявление:
#include <map>
...
map <string,int> L;
индекс –
данные –
строка
целые
Размер словаря:
int p = L.count ( s );
Увеличение счётчика слова s:
L[s] ++;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

46. Использование контейнера map (STL)

46
Алгоритмизация и программирование. Язык C++, 11 класс
Использование контейнера map (STL)
Вставка слова:
L.insert ( pair <string,int> (s,1) );
Заполнение словаря:
пара «строка – счётчик»
пока есть
данные в
файле
сколько раз
встречается слово?
while ( Fin >> s ) {
int p;
p = L.count ( s );
if ( p == 1 )
L[s] ++;
else
L.insert ( pair <string,int> (s, 1) );
}
while ( Fin >> s ) L[s] ++;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

47. Вывод результата

47
Алгоритмизация и программирование. Язык C++, 11 класс
Вывод результата
Итератор (или курсор) – специальный объект, который
позволяет перебрать все элементы контейнера.
Объявление:
тип контейнера
map <string,int>::iterator it;
На первый элемент:
it = L.begin();
Вывод данных по текущему элементу:
автомат: 1
ананас: 12
...
Fout << it->first << ": "
<< it->second;
Все элементы:
for ( it = L.begin(); it != L.end(); it++ )
Fout << it->first << ": "
<< it->second << endl;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

48. Связные списки (list)

48
Алгоритмизация и программирование. Язык C++, 11 класс
Связные списки (list)
Head
«голова»
данные
данные
конец
списка
данные NULL
узлы могут размещаться в разных местах в памяти
только последовательный доступ
Рекурсивное определение:
• пустой список – это список
• список – это узел и связанный с ним список
!
Применение: много вставок в середину
и удалений элементов!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

49. Связные списки

49
Алгоритмизация и программирование. Язык C++, 11 класс
Связные списки
Циклический список:
Head
данные
данные
Двусвязный список:
Head
NULL данные
данные
«хвост»
данные
данные
Tail
NULL
обход в двух направлениях
сложнее вставка и удаление
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

50. Алгоритмизация и программирование. Язык C++

50
Алгоритмизация и
программирование.
Язык C++
§ 42. Стек, дек, очередь
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

51. Что такое стек?

51
Алгоритмизация и программирование. Язык C++, 11 класс
Что такое стек?
Стек (англ. stack – стопка) – это линейный список, в
котором элементы добавляются и удаляются только с
одного конца («последним пришел – первым ушел»).
LIFO = Last In – First Out.
Системный стек:
• адреса возврата из подпрограмм
• передача аргументов подпрограмм
• хранение локальных переменных
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

52. Реверс массива

52
Алгоритмизация и программирование. Язык C++, 11 класс
Реверс массива
Задача. В файле записаны целые числа. Нужно вывести
их в другой файл в обратном порядке.
пока файл не пуст
{
прочитать x
добавить x в стек
}
пока стек не
{
вытолкнуть
записать x
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
5
4
3
2
5
4
3
2
1
1
пуст
число из стека в x
в файл
http://kpolyakov.spb.ru

53. Использование контейнера stack (STL)

53
Алгоритмизация и программирование. Язык C++, 11 класс
Использование контейнера stack (STL)
#include <stack>
...
stack <int> S;
стек целых
чисел
Основные операции со стеком:
• push – добавить элемент на вершину стека
• pop – удалить элемент с вершины стека
• top – вернуть элемент с вершины стека
(без удаления)
• empty – вернуть true, если стек пуст,
и false в противном случае.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

54. Использование контейнера stack (STL)

54
Алгоритмизация и программирование. Язык C++, 11 класс
Использование контейнера stack (STL)
Переменные:
ifstream Fin;
ofstream Fout;
stack <int> S;
int x;
Чтение данных и загрузка в стек:
Fin.open ( "input.dat" );
while ( Fin >> x )
S.push ( x );
Fin.close();
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

55. Использование контейнера stack (STL)

55
Алгоритмизация и программирование. Язык C++, 11 класс
Использование контейнера stack (STL)
Вывод в обратном порядке:
Fout.open ( "output.dat" );
while ( ! S.empty() )
{
Fout << S.top() << endl;
S.pop();
}
Fout.close();
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

56. Вычисление арифметических выражений

56
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление арифметических выражений
?
Как компьютер вычисляет арифметические
выражения?
(5+15)/(4+7-1) инфиксная форма (знак операции
между данными)
1920 (Я. Лукашевич): префиксная форма
(знак операции перед данными)
/ + 5 15 - + 4 7 1
/ 20 - + 4 7 1
/ 20 - 11 1
/ 20 10
2
К.Ю. Поляков, Е.А. Ерёмин, 2014
не нужны скобки
первой стоит последняя
операция (вычисляем с конца)
http://kpolyakov.spb.ru

57. Вычисление арифметических выражений

57
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление арифметических выражений
(5+15)/(4+7-1)
1950-е: постфиксная форма
(знак операции после данных)
5 15 + 4 7 + 1 - /
20 4 7 + 1 - /
20 11 1 - /
20 10 /
2
!
К.Ю. Поляков, Е.А. Ерёмин, 2014
не нужны скобки
вычисляем с начала
Вычисляем с помощью стека!
http://kpolyakov.spb.ru

58. Использование стека

58
Алгоритмизация и программирование. Язык C++, 11 класс
Использование стека
5 15 + 4 7 + 1 - /
5
5
1
5
5
15
2
0
+
4
2
0
4
7
4
2
0
7
1
1
2
+
0
1
1
1
2
1
0
1
0
2
0
2
/
• если число – «втолкнуть» в стек
• если операция – выполнить с верхними элементами
стека
!
В стеке остается результат!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

59. Скобочные выражения

59
Алгоритмизация и программирование. Язык C++, 11 класс
Скобочные выражения
Задача. Вводится символьная строка, в которой записано
некоторое (арифметическое) выражение,
использующее скобки трёх типов: ( ), [ ] и { }.
Проверить, правильное ли расставлены скобки.
()[{()[]}]
[()
[()}
)(
([)]
Для одного типа скобок:
счётчик
?
0
(
)
(
(
)
(
(
)
)
)
1
0
1
2
1
2
3
2
1
0
Когда выражение правильное?
• счётчик всегда 0
• в конце счётчик = 0
К.Ю. Поляков, Е.А. Ерёмин, 2014
!
({[)}]
Для разных скобок
не работает!
http://kpolyakov.spb.ru

60. Скобочные выражения (стек)

60
Алгоритмизация и программирование. Язык C++, 11 класс
Скобочные выражения (стек)
(
[
(
(
[
(
[
(
{
[
(
(
{
[
(
{
[
(
[
(
(
(
[
(
)
{
(
)
}
]
• если открывающая скобка – «втолкнуть» в стек
• если закрывающая скобка – снять парную со стека
?
)
Когда выражение правильное?
• когда встретили закрывающую скобку, на вершине
стека лежит соответствующая открывающая
• в конце работы стек пуст
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

61. Скобочные выражения (стек)

61
Алгоритмизация и программирование. Язык C++, 11 класс
Скобочные выражения (стек)
Константы и переменные:
const string L = "([{", //
R = ")]}"; //
string str;
// рабочая
stack <char> S; // стек
bool err;
// была ли
int i, p;
char c;
Вывод результата:
открывающие
закрывающие
строка
ошибка?
if ( ! err )
cout << "Скобки расставлены верно.";
else
cout << "Скобки расставлены неверно.";
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

62. Скобочные выражения (стек)

62
Алгоритмизация и программирование. Язык C++, 11 класс
Скобочные выражения (стек)
for ( ii = 0;
0; ii < str.size(); i++ ) {
p = L.find (( str[i] );
открывающую
if (( p >= 0 )
скобку в стек
S.push
S.push ( str[i] );
p = R.find (( str[i] );
если
if (( p >= 0 ) {
закрывающая
if
if ( S.empty
S.empty () )
скобка…
err = true;
else
else {
c = S.top(); S.pop();
if ( p!=
p!= L.find(c) )
если не та
err = true;
скобка…
}
if
if ( err
err ) break;
}}
Что ещё?
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

63. Что такое очередь?

63
Алгоритмизация и программирование. Язык C++, 11 класс
Что такое очередь?
Очередь – это линейный список,
для которого введены две
операции:
• добавление элемента в конец
• удаление первого элемента
FIFO = Fist In – First Out.
Применение:
• очереди сообщений в операционных системах
• очереди запросов ввода и вывода
• очереди пакетов данных в маршрутизаторах
•…
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

64. Заливка области

64
Алгоритмизация и программирование. Язык C++, 11 класс
Заливка области
Задача. Рисунок задан в виде матрицы A, в которой
элемент A[y][x] определяет цвет пикселя на
пересечении строки y и столбца x. Перекрасить в цвет
2 одноцветную область, начиная с пикселя (x0,y0).
0 1 2 3 4
0
1
2
3
4
0
1
0
3
0
1
1
1
3
1
0
1
0
1
1
1
2
2
2
0
К.Ю. Поляков, Е.А. Ерёмин, 2014
1
2
2
2
0
0 1 2 3 4
0
(1,2)
1
2
3
4
0
2
0
3
0
2
2
2
3
1
0
2
0
1
1
1
2
2
2
0
1
2
2
2
0
http://kpolyakov.spb.ru

65. Заливка: использование очереди

65
Алгоритмизация и программирование. Язык C++, 11 класс
Заливка: использование очереди
добавить в очередь точку (x00,y00)
запомнить цвет начальной точки
пока очередь не пуста
{
взять из очереди точку (x,y)
если A[y][x] = цвету начальной точки то
{
A[y][x] = 2;
добавить в очередь точку (x-1,y)
добавить в очередь точку (x+1,y)
добавить в очередь точку (x,y-1)
добавить в очередь точку (x,y+1)
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

66. Очередь queue (STL)

66
Алгоритмизация и программирование. Язык C++, 11 класс
Очередь queue (STL)
#include <queue>
typedef struct {
int x, y;
} TPoint;
queue <TPoint> Q;
структура
«точка»
контейнер «очередь»
из точек
Построение структуры «точка»:
TPoint Point ( int x, int y )
{
TPoint P;
P.x = x; P.y = y;
return P;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

67. Очередь queue (STL)

67
Алгоритмизация и программирование. Язык C++, 11 класс
Очередь queue (STL)
Основные операции:
• push – добавить элемент в конец очереди
• pop – удалить первый элемент в очереди
• front – вернуть первый элемент в очереди
(без удаления)
• empty – вернуть true, если очередь пуста,
и false в противном случае.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

68. Заливка

68
Алгоритмизация и программирование. Язык C++, 11 класс
Заливка
Константы и переменные:
const int XMAX = 5, YMAX = 5,
NEW_COLOR = 2;
int A[YMAX][XMAX];
// матрица
queue <TPoint> Q;
// очередь
int i, j, x0, y0, color;
TPoint pt;
Начало программы:
// заполнить матрицу A
y0 = 0; x0 = 1;
// начать заливку отсюда
color = A[y0][x0]; // цвет начальной точки
Q.push ( Point(x0,y0) );
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

69. Заливка (основной цикл)

69
Алгоритмизация и программирование. Язык C++, 11 класс
Заливка (основной цикл)
пока очередь не пуста
while ( ! Q.empty() ) {
pt = Q.front(); Q.pop();
if ( A[pt.y][pt.x] == color ) {
A[pt.y][pt.x] = NEW_COLOR;
if ( pt.x > 0 )
Q.push ( Point(pt.x-1,pt.y) );
if ( pt.y > 0 )
Q.push ( Point(pt.x,pt.y-1) );
if ( pt.x < XMAX-1 )
Q.push( Point(pt.x+1,pt.y) );
if ( pt.y < YMAX-1 )
Q.push( Point(pt.x,pt.y+1) );
}
Что можно улучшить?
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

70. Очередь: статический массив

70
Алгоритмизация и программирование. Язык C++, 11 класс
Очередь: статический массив
голова
Head
Tail
хвост
0
1
2
3
4
Удаление элемента:
Head
N-1
5
Tail
0
N-1
1
2
3
4
Добавление элемента:
Head
5
Tail
0
N-1
2
3
4
не двигаем элементы
К.Ю. Поляков, Е.А. Ерёмин, 2014
5
6
нужно знать размер
http://kpolyakov.spb.ru

71. Очередь: статический массив

71
Алгоритмизация и программирование. Язык C++, 11 класс
Очередь: статический массив
Замыкание в кольцо:
Tail
Head
1
7
N
8
9
1
Очередь заполнена:
Tail
2
3
4
5
Head
1
7
6
N
8
9
10 11 12
Очередь пуста:
1
2
3
4
5
6
Tail Head
1
N
!
Вариант: хранить размер очереди в переменной!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

72. Что такое дек?

72
Алгоритмизация и программирование. Язык C++, 11 класс
Что такое дек?
Дек – это линейный список, в котором можно добавлять и
удалять элементы как с одного, так и с другого конца.
Моделирование:
• статический массив (кольцо)
• динамический массив
• связный список
!
К.Ю. Поляков, Е.А. Ерёмин, 2014
STL: deque!
http://kpolyakov.spb.ru

73. Алгоритмизация и программирование. Язык C++

73
Алгоритмизация и
программирование.
Язык C++
§ 43. Деревья
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

74. Что такое дерево?

74
Алгоритмизация и программирование. Язык C++, 11 класс
Что такое дерево?
«Сыновья» А: B, C.
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G. «Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

75. Рекурсивные определения

75
Алгоритмизация и программирование. Язык C++, 11 класс
Рекурсивные определения
1)
2)
пустая структура – это дерево
дерево – это корень и несколько связанных с ним
отдельных (не связанных между собой) деревьев
Двоичное (бинарное) дерево:
1) пустая структура – это двоичное дерево
2) двоичное дерево – это корень и два связанных с ним
отдельных двоичных дерева («левое» и «правое»
поддеревья)
Применение:
• поиск в большом массиве неменяющихся данных
• сортировка данных
• вычисление арифметических выражений
• оптимальное сжатие данных (метод Хаффмана)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

76. Деревья поиска

76
Алгоритмизация и программирование. Язык C++, 11 класс
Деревья поиска
Ключ – это значение, связанное с узлом дерева, по
которому выполняется поиск.
6
3
1
8
4
7
9
• слева от узла – узлы с
меньшими или равными
ключами
• справа от узла – узлы с
большими или равными
ключами
O(log N)
?
Сложность поиска?
К.Ю. Поляков, Е.А. Ерёмин, 2014
Двоичный поиск O(log N)
Линейный поиск O(N)
http://kpolyakov.spb.ru

77. Обход дерева

77
Алгоритмизация и программирование. Язык C++, 11 класс
Обход дерева
Обойти дерево «посетить» все узлы по одному разу.
список узлов
КЛП – «корень-левый-правый» (в прямом порядке):
посетить корень
обойти левое поддерево
обойти правое поддерево
ЛКП – «левый-корень-правый» (симметричный):
посетить корень
обойти левое поддерево
обойти правое поддерево
ЛПК – «левый-правый-корень» (в обратном порядке):
посетить корень
обойти левое поддерево
обойти правое поддерево
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

78. Обход дерева

78
Алгоритмизация и программирование. Язык C++, 11 класс
Обход дерева
(1+4)*(9-5)
*
+
«в
глубину»
1
4
9
5
КЛП: * + 1 4 – 9 5
префиксная форма
ЛКП: 1 + 4 * 9 - 5
инфиксная форма
ЛПК: 1 4 + 9 5 - *
постфиксная форма
Обход «в ширину»: «сыновья», потом «внуки», …
* + - 1 4 9 5
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

79. Обход КЛП – обход «в глубину»

79
Алгоритмизация и программирование. Язык C++, 11 класс
Обход КЛП – обход «в глубину»
записать в стек корень дерева
пока стек не пуст
{
выбрать узел V с вершины стека
посетить узел V
если у узла V есть правый сын то
добавить в стек правого сына V
если у узла V есть левый сын то
добавить в стек левого сына V
}
?
Почему сначала добавить правого сына?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

80. Обход КЛП – обход «в глубину»

80
Алгоритмизация и программирование. Язык C++, 11 класс
Обход КЛП – обход «в глубину»
(1+4)*(9-5)
*
+
4
1
*
9
+
-
1
4
-
4
-
*
+
1
К.Ю. Поляков, Е.А. Ерёмин, 2014
5
-
9
5
5
4
–
9
5
http://kpolyakov.spb.ru

81. Обход «в ширину»

81
Алгоритмизация и программирование. Язык C++, 11 класс
Обход «в ширину»
записать в очередь корень дерева
пока очередь не пуста
{
выбрать узел V из очереди
посетить узел V
если у узла V есть левый сын то
добавить в очередь левого сына V
если у узла V есть правый сын то
добавить в очередь правого сына V
}
?
Почему сначала добавить левого сына?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

82. Обход «в ширину»

82
Алгоритмизация и программирование. Язык C++, 11 класс
Обход «в ширину»
(1+4)*(9-5)
*
+
4
1
голова
очереди
*
К.Ю. Поляков, Е.А. Ерёмин, 2014
9
5
+
4
1
-
5
9
4
1
5
9
4
5
9
5
*
+
-
1
4
9
5
http://kpolyakov.spb.ru

83. Вычисление арифметических выражений

83
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление арифметических выражений
?
40–2*3–4*5
Что будет в корне дерева?
В корень дерева нужно поместить последнюю из
операций с наименьшим приоритетом.
-
-
40–2*3
4*5
-
-
40
*
2*3
*
40
4
К.Ю. Поляков, Е.А. Ерёмин, 2014
*
2
4
5
3
5
http://kpolyakov.spb.ru

84. Вычисление арифметических выражений

84
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление арифметических выражений
Построение дерева:
найти последнюю выполняемую
если операций нет то
{
создать узел-лист
выход
}
поместить операцию в корень
построить левое поддерево
построить правое поддерево
!
операцию
дерева
Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

85. Вычисление арифметических выражений

85
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление арифметических выражений
Вычисление по дереву:
n1 = значение
значение левого
левого поддерева
поддерева
n2 = значение
значение правого
правого поддерева
поддерева
результат = операция(n1, n2)
!
Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

86. Использование связанных структур

86
Алгоритмизация и программирование. Язык C++, 11 класс
Использование связанных структур
Дерево – нелинейная структура динамический
массив неудобен!
данные
данные NULL NULL
typedef struct
typedef struct
{
string data;
PNode left;
PNode right;
} TNode;
К.Ю. Поляков, Е.А. Ерёмин, 2014
данные NULL NULL
ссылка
вперёд
TNode *PNode;
TNode
новый тип:
адрес узла
ссылки на
сыновей
http://kpolyakov.spb.ru

87. Работа с памятью

Алгоритмизация и программирование. Язык C++, 11 класс
87
Работа с памятью
PNode p;
// указатель на узел
Выделить память для узла:
p = new TNode;
Обращение к новому узлу (по указателю):
p->data = s;
p->left = NULL;
p->right = NULL;
Освобождение памяти:
delete p;
не массив,
поэтому нет []
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

88. Основная программа

Алгоритмизация и программирование. Язык C++, 11 класс
88
Основная программа
main()
{
PNode T;
string s;
// ввести строку s
T = MakeTree ( s );
cout << "Результат: ", Calc(T);
}
!
Нужно построить MakeTree и Calc!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

89. Построение дерева

89
Алгоритмизация и программирование. Язык C++, 11 класс
Построение дерева
PNode
PNode MakeTree ( string s )
вернёт адрес
{{
нового
int
int k;
дерева
PNode
PNode Tree;
Tree
Tree = new struct TNode;
TNode;
kk = LastOp ( ss );
);
if ( k == -1 )) {{
// новый узел –– лист
лист (число)
(число)
}
else
else {
// новый узел –– операция
операция
// построить
построить поддеревья
поддеревья
}
return
return Tree;
}}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

90. Построение дерева

90
Алгоритмизация и программирование. Язык C++, 11 класс
Построение дерева
Новый узел – лист:
Tree->data = s;
Tree->left = NULL;
Tree->right = NULL;
нет сыновей!
Новый узел – операция:
один символ!
Tree->data = s.substr(k,1);
Tree->left = MakeTree
MakeTree
( (s.substr(0,k)
s.substr(0,k)
););
Tree->right = MakeTree
MakeTree
( (s.substr(k+1)
s.substr(k+1)
););
!
К.Ю. Поляков, Е.А. Ерёмин, 2014
Рекурсия!
до конца строки
http://kpolyakov.spb.ru

91. Вычисление по дереву

91
Алгоритмизация и программирование. Язык C++, 11 класс
Вычисление по дереву
int
int Calc
Calc (( PNode
PNode Tree
Tree ))
{{
это число
(лист)
int
int n1,
n1, n2,
n2, res;
res;
if
if (( Tree->left
Tree->left ==
== NULL
NULL ))
res
res == atoi
atoi (( Tree->data.c_str()
Tree->data.c_str() );
);
else
else {{
n1
n1 == Calc
Calc (( Tree->left
Tree->left );
);
Рекурсия!
n2
n2 == Calc
Calc (( Tree->right
Tree->right );
);
switch
switch (( Tree->data[0]
Tree->data[0] )) {{
case
case '+':
'+': res
res == n1
n1 ++ n2;
n2; break;
break;
case
case '-':
'-': res
res == n1
n1 -- n2;
n2; break;
break;
case
case '*':
'*': res
res == n1
n1 ** n2;
n2; break;
break;
case
case '/':
'/': res
res == n1
n1 // n2;
n2; break;
break;
default:
default: res
res == 99999;
99999;
}}
}}
return
return res;
res;
}}
!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

92. Приоритет операции

Алгоритмизация и программирование. Язык C++, 11 класс
92
Приоритет операции
int Priority ( char op )
{
switch ( op )
{
case '+':
case '-': return 1;
case '*':
case '/': return 2;
}
return 100;
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

93. Последняя выполняемая операция

93
Алгоритмизация и программирование. Язык C++, 11 класс
Последняя выполняемая операция
int LastOp ( string s )
вернёт номер
{
символа
int i, minPrt, res;
minPrt = 50; // любое между 2 и 100
res = -1;
for ( i = 0; i < s.size(); i++ )
if ( Priority(s[i]) <=
<= minPrt )
{
minPrt = Priority(s[i]);
res = i;
Почему <=?
}
return res;
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

94. Двоичное дерево в массиве

94
Алгоритмизация и программирование. Язык C++, 11 класс
Двоичное дерево в массиве
0
--
**
A[0]
A[1]
A[2]
3
4
5
6
7
8
9
10
3
4
5
6
7
8
9
10
5
6
7
8
9
10
7
8
9
10
**
0
22
2
- - *
-40
40
1
44
55
33
2
- - * 40 *
0
1
2
3
4
- - * 40 * 4 5
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
1
0
1
2
3
4
5
6
- - * 40 * 4 5
A[4]
К.Ю. Поляков, Е.А. Ерёмин, 2014
A[9]
A[10]
A[i]
2 3
A[2*i+1]
?
A[2*i+2]
?
http://kpolyakov.spb.ru

95. Алгоритмизация и программирование. Язык C++

95
Алгоритмизация и
программирование.
Язык C++
§ 44. Графы
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

96. Что такое граф?

96
Алгоритмизация и программирование. Язык C++, 11 класс
Что такое граф?
Граф – это набор вершин и связей между ними (рёбер).
Матрица смежности:
A
B
C
D
Список смежности:
( A(B, C),
B(A, C, D),
C(A, B, С, D),
D(B, C) )
К.Ю. Поляков, Е.А. Ерёмин, 2014
A
0
1
1
0
B
1
0
1
1
C
1
1
1
1
D
0
1
1
0
петля
http://kpolyakov.spb.ru

97. Связность графа

97
Алгоритмизация и программирование. Язык C++, 11 класс
Связность графа
Связный граф – это граф, между любыми вершинами
которого существует путь.
A
B
C
D
A
C
B
D
компоненты связности
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

98. Дерево – это граф?

98
Алгоритмизация и программирование. Язык C++, 11 класс
Дерево – это граф?
Дерево – это связный граф без циклов (замкнутых путей).
A
C
B
D
ABC
BCD
ABDC
CCC…
К.Ю. Поляков, Е.А. Ерёмин, 2014
дерево
http://kpolyakov.spb.ru

99. Взвешенные графы

99
Алгоритмизация и программирование. Язык C++, 11 класс
Взвешенные графы
A
12
B
8
C
5
6
4
D
2
Весовая матрица:
A
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4
вес ребра
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

100. Ориентированные графы (орграфы)

100
Алгоритмизация и программирование. Язык C++, 11 класс
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра
называю дугами.
A
8
5
12
B
!
6
A
C
4
D
A
B
C
D
12
B
12
C
8
5
D
6
4
4
Весовая матрица может быть несимметрична!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

101. Жадные алгоритмы

101
Алгоритмизация и программирование. Язык C++, 11 класс
Жадные алгоритмы
Жадный алгоритм – это многошаговый алгоритм, в
котором на каждом шаге принимается решение,
лучшее в данный момент.
Задача. Найти кратчайший маршрут из А в F.
2
B
9
A
1
К.Ю. Поляков, Е.А. Ерёмин, 2014
C
7
8
4
D
1
3
E
F
5
http://kpolyakov.spb.ru

102. Жадные алгоритмы

102
Алгоритмизация и программирование. Язык C++, 11 класс
Жадные алгоритмы
Задача. Найти кратчайший маршрут из А в F.
2
9
A
4
?
!
B
C
7
8
1
D
1
3
E
F
2
Это лучший маршрут?
Жадный алгоритм не всегда даёт наилучшее
решение!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

103. Задача Прима-Крускала

103
Алгоритмизация и программирование. Язык C++, 11 класс
Задача Прима-Крускала
Задача. Между какими городами нужно проложить линии
связи, чтобы все города были связаны в одну систему
и общая длина линий связи была наименьшей?
(минимальное остовное дерево)
2
A
B
9
7
8
D
1
3
F
2
4
C
E
1
Алгоритм Крускала:
Лучшее решение!
• начальное дерево – пустое
• на каждом шаге добавляется ребро минимального
веса, которое ещё не входит в дерево и не
приводит к появлению цикла
!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

104. Раскраска вершин

104
Алгоритмизация и программирование. Язык C++, 11 класс
Раскраска вершин
2
B
9
A
4
C
7
8
1
D
1
3
E
F
2
for (i = 0; i < N; i ++) col[i] = i;
каждой
вершине
свой цвет
Сделать N-1 раз:
• ищем ребро минимальной длины среди всех рёбер,
концы которых окрашены в разные цвета;
• найденное ребро (iMin,jMin) добавляется в список
выбранных, и все вершины, имеющие цвет
col[jMin], перекрашиваются в цвет col[iMin].
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

105. Раскраска вершин

105
Алгоритмизация и программирование. Язык C++, 11 класс
Раскраска вершин
Данные:
const int N = 6;
int W[N][N]; // весовая матрица
int col[N]; // цвета вершин
// номера вершин для выбранных ребер
int ostov[N-1][2];
int i, j, k, iMin, jMin, min, c;
Вывод результата:
for ( i = 0; i < N-1; i ++ )
cout << "(" << ostov[i][0] << ","
<< ostov[i][1] << ")" << endl;
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

106. Раскраска вершин

106
Алгоритмизация и программирование. Язык C++, 11 класс
Раскраска вершин
for ( k = 0;
0; kk < N-1; k++ ) {{
//
// поиск
поиск ребра
ребра сс минимальным
минимальным весом
весом
minDist
minDist = 99999;
for
for ( ii = 0;
0; ii < N; i ++ )
нет цикла
for
for ( j = 0; jj < N; j ++ )
if
if ( col[i]
col[i] != col[j] &&
W[i][j]
W[i][j] < minDist ) {
iMin = i; jMin = j; minDist == W[i][j];
}
//
// добавление
добавление ребра
ребра вв список
список выбранных
выбранных
ostov[k][0]
ostov[k][0] = iMin; ostov[k][1] = jMin;
//
// перекрашивание вершин
вершин
cc = col[jMin];
for
for ( ii = 0;
0; ii < N; i ++ )
if
if ( col[i] == c ) col[i] = col[iMin];
}}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

107. Кратчайший маршрут

107
Алгоритмизация и программирование. Язык C++, 11 класс
Кратчайший маршрут
Алгоритм Дейкстры (1960):
B
2
4
R
P
8
9
A
A
0
×
7
C
B
2
A
C
4
A
D
A
1
E
A
D
1
3
E
F
2
Э.В. Дейкстра
F
кратчайшее расстояние
A откуда ехать
ближайшая от A
невыбранная вершина
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

108. Кратчайший маршрут

108
Алгоритмизация и программирование. Язык C++, 11 класс
Кратчайший маршрут
Алгоритм Дейкстры (1960):
B
2
8
9
A
4
R
P
7
A
0
×
B
2
A
W[x,z]
X
C
C
4
A
Z
W[x,y]
К.Ю. Поляков, Е.А. Ерёмин, 2014
D
9
A
B
1
E
A
W[z,y]
Y
D
1
3
E
F
2
Э.В. Дейкстра
F
кратчайшее расстояние
A откуда ехать
может быть так, что
W[x,z] + W[z,y] < W[x,y]
http://kpolyakov.spb.ru

109. Кратчайший маршрут

109
Алгоритмизация и программирование. Язык C++, 11 класс
Кратчайший маршрут
Алгоритм Дейкстры (1960):
B
2
8
9
A
4
R
P
7
A
0
×
B
2
A
W[x,z]
X
C
C
4
A
Z
W[x,y]
К.Ю. Поляков, Е.А. Ерёмин, 2014
D
9
B
1
E
5
A
C
W[z,y]
Y
D
1
3
E
F
2
Э.В. Дейкстра
F
кратчайшее расстояние
A откуда ехать
может быть так, что
W[x,z] + W[z,y] < W[x,y]
http://kpolyakov.spb.ru

110. Кратчайший маршрут

110
Алгоритмизация и программирование. Язык C++, 11 класс
Кратчайший маршрут
Алгоритм Дейкстры (1960):
B
2
4
R
P
8
9
A
A
0
×
7
B
2
A
!
C
C
4
A
D
9
8
B
E
1
E
5
C
D
1
3
E
F
Э.В. Дейкстра
2
F
7 кратчайшее расстояние
E откуда ехать
При рассмотрении вершин F и D
таблица не меняется!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

111. Кратчайший маршрут

111
Алгоритмизация и программирование. Язык C++, 11 класс
Кратчайший маршрут
R
P
?
A
0
×
B
2
A
C
4
A
D
8
E
E
5
C
F
7
E
длины
кратчайших
маршрутов из A в
другие вершины
Как найти сам маршрут?
R
P
A
0
×
B
2
A
C
4
A
D
8
E
E
5
C
F
7
E
A C E F
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

112. Алгоритм Дейкстры

112
Алгоритмизация и программирование. Язык C++, 11 класс
Алгоритм Дейкстры
Данные:
const int N = 6;
int W[N][N];
// весовая
bool active[N]; // вершина
int R[N], P[N];
int i, j, min, kMin;
матрица
не выбрана?
Начальные значения (выбор начальной вершины):
for ( i = 0; i < N; i ++ ) {
active[i] = true; // все вершины не выбраны
R[i] = W[0][i];
// рёбра из вершины 0
P[i] = 0;
}
active[0] = false; // вершина уже выбрана
P[0] = -1;
// это начальная вершина
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

113. Алгоритм Дейкстры

113
Алгоритмизация и программирование. Язык C++, 11 класс
Алгоритм Дейкстры
Основной цикл:
выбор
for ( i = 0; i < N-1; i++ ) {
следующей
вершины,
minDist = 99999;
ближайшей к A
for ( j = 0; j < N; j ++ )
if ( active[j] && R[j] < minDist) {
minDist = R[j];
kMin = j;
проверка
}
маршрутов через
вершину kMin
active[kMin] = false;
for ( j = 0; j < N; j ++ )
if ( R[kMin]+W[kMin][j] < R[j] ) {
R[j] = R[kMin] + W[kMin][j];
P[j] = kMin;
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

114. Алгоритм Дейкстры

114
Алгоритмизация и программирование. Язык C++, 11 класс
Алгоритм Дейкстры
Вывод результата (маршрут 0 N-1):
i = N-1;
для начальной
while ( i != -1 )
вершины P[i]=-1
{
cout << i << " ";
i = P[i]; // к следующей вершине
}
R
P
A
0
×
B
2
A
C
4
A
D
8
E
E
5
C
F
7
E
A C E F
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

115. Алгоритм Флойда

115
Алгоритмизация и программирование. Язык C++, 11 класс
Алгоритм Ф