Алгоритмизация и программирование. Язык C++
Алгоритмизация и программирование. Язык C++
Решето Эратосфена
Решето Эратосфена
Решето Эратосфена
Решето Эратосфена
«Длинные» числа
«Длинные» числа
«Длинные» числа
Вычисление факториала
Вычисление факториала
Вычисление факториала
Вывод длинного числа
Вывод длинного числа
Вывод длинного числа
Алгоритмизация и программирование. Язык C++
Зачем нужны структуры?
Структуры
Объявление структур
Обращение к полям структур
Обращение к полям структур
Запись структур в файлы
Чтение структур из файла
Чтение структур из файла
Сортировка структур
Указатели
Сортировка по указателям
Сортировка по указателям
Алгоритмизация и программирование. Язык C++
Чем плох обычный массив?
Динамические структуры данных
Динамические массивы
Динамические массивы
Тип vector (библиотека STL)
Тип vector (библиотека STL)
Динамические матрицы
Динамические матрицы
Динамические матрицы
Динамические матрицы
Динамические матрицы (vector)
Расширение массива
Алгоритмизация и программирование. Язык C++
Зачем нужны списки?
Алгоритм (псевдокод)
Использование контейнера map (STL)
Использование контейнера map (STL)
Вывод результата
Связные списки (list)
Связные списки
Алгоритмизация и программирование. Язык C++
Что такое стек?
Реверс массива
Использование контейнера stack (STL)
Использование контейнера stack (STL)
Использование контейнера stack (STL)
Вычисление арифметических выражений
Вычисление арифметических выражений
Использование стека
Скобочные выражения
Скобочные выражения (стек)
Скобочные выражения (стек)
Скобочные выражения (стек)
Что такое очередь?
Заливка области
Заливка: использование очереди
Очередь queue (STL)
Очередь queue (STL)
Заливка
Заливка (основной цикл)
Очередь: статический массив
Очередь: статический массив
Что такое дек?
Алгоритмизация и программирование. Язык C++
Что такое дерево?
Рекурсивные определения
Деревья поиска
Обход дерева
Обход дерева
Обход КЛП – обход «в глубину»
Обход КЛП – обход «в глубину»
Обход «в ширину»
Обход «в ширину»
Вычисление арифметических выражений
Вычисление арифметических выражений
Вычисление арифметических выражений
Использование связанных структур
Работа с памятью
Основная программа
Построение дерева
Построение дерева
Вычисление по дереву
Приоритет операции
Последняя выполняемая операция
Двоичное дерево в массиве
Алгоритмизация и программирование. Язык C++
Что такое граф?
Связность графа
Дерево – это граф?
Взвешенные графы
Ориентированные графы (орграфы)
Жадные алгоритмы
Жадные алгоритмы
Задача Прима-Крускала
Раскраска вершин
Раскраска вершин
Раскраска вершин
Кратчайший маршрут
Кратчайший маршрут
Кратчайший маршрут
Кратчайший маршрут
Кратчайший маршрут
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Флойда
Алгоритм Флойда + маршруты
Задача коммивояжера
Некоторые задачи
Алгоритмизация и программирование. Язык C++
Что такое динамическое программирование?
Динамическое программирование
Динамическое программирование
Количество вариантов
Количество вариантов
Оптимальное решение
Оптимальное решение
Оптимальное решение (бидоны)
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Количество программ
Количество программ
Количество программ
Количество программ
Размен монет
Размен монет
Размен монет
Конец фильма
Источники иллюстраций
8.07M
Categories: programmingprogramming informaticsinformatics

Алгоритмизация и программирование. Язык 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 класс
Алгоритм Ф
English     Русский Rules