programmingSimilar presentations:
Алгоритмизация и программирование. Язык C++
1. Алгоритмизация и программирование. Язык C++
§ 35. Целочисленные алгоритмы§ 36. Структуры
§ 37. Динамические массивы
§ 00. Списки
§ 38. Стек, очередь, дек
§ 39. Деревья
§ 40. Графы
§ 41. Динамическое программирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
1
2. Алгоритмизация и программирование. Язык C++
2Алгоритмизация и
программирование.
Язык C++
§ 35. Целочисленные
алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
3. Решето Эратосфена
Алгоритмизация и программирование. Язык C++, 11 класс3
Решето Эратосфена
22 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Алгоритм:
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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
4. Решето Эратосфена
Алгоритмизация и программирование. Язык C++, 11 класс4
Решето Эратосфена
Задача. Вывести все простые числа от 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;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
5. Решето Эратосфена
Алгоритмизация и программирование. Язык C++, 11 класс5
Решето Эратосфена
Вычёркивание непростых:
k = 2;
while ( k*k <= N ) {
if ( A[k] ) {
i = k*k;
while ( i <= N )
{
A[i] = false;
i += k;
}
}
k ++;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
6. Решето Эратосфена
Алгоритмизация и программирование. Язык C++, 11 класс6
Решето Эратосфена
Вывод результата:
for ( i = 2; i <= N; i++ )
if ( A[i] )
cout << i << " ";
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
7. «Длинные» числа
Алгоритмизация и программирование. Язык C++, 11 класс7
«Длинные» числа
Ключи для шифрования: 256 битов.
Целочисленные типы данных: 64 битов.
? Как хранить?
Длинное число – это число, которое не помещается в
переменную одного из стандартных типов данных
языка программирования.
«Длинная арифметика» – алгоритмы для работы с
длинными числами.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
8. «Длинные» числа
Алгоритмизация и программирование. Язык C++, 11 класс8
«Длинные» числа
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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
9. «Длинные» числа
Алгоритмизация и программирование. Язык C++, 11 класс9
«Длинные» числа
A = 12345678
Упаковка элементов:
A
9
8
7
6
5
4
3
2
1
0
0
0
0
0
0
0
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.
? Какие основания можно использовать?
должны помещаться все
промежуточные результаты!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
10. Вычисление факториала
Алгоритмизация и программирование. Язык C++, 11 класс10
Вычисление факториала
Задача 1. Вычислить точно значение факториала
100! = 1·2·3·…·99·100
? Как оценить количество цифр?
201 цифра
1·2·3·…·99·100 < 100100
основание 1000000
6 цифр в ячейке 34 ячейки
const int N = 33;
long int A[N+1];
Основной алгоритм:
длинное
[A] = 1;
число
for ( k = 2; k <= 100; k ++ )
[A] = [A] * k;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
11. Вычисление факториала
Алгоритмизация и программирование. Язык C++, 11 класс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]?
К.Ю. Поляков, Е.А. Ерёмин, 2018
s = A[1]*k + r;
http://kpolyakov.spb.ru
12. Вычисление факториала
Алгоритмизация и программирование. Язык C++, 11 класс12
Вычисление факториала
Умножение «длинного» числа на 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++ )
{
...
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
13. Вывод длинного числа
Алгоритмизация и программирование. Язык C++, 11 класс13
Вывод длинного числа
A
3
2
1
0
0
1
2
3
? Какое число?
[A] = 1000002000003
• найти старший ненулевой разряд
i = N;
while ( ! A[i] )
i --;
• вывести этот разряд
cout << A[i];
• вывести все следующие разряды, добавляя
лидирующие нули до 6 цифр
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
14. Вывод длинного числа
Алгоритмизация и программирование. Язык C++, 11 класс14
Вывод длинного числа
Вывод остальных разрядов:
for ( k = i-1; k >= 0; k-- )
Write6 ( A[k] );
Write6:
x = 12345
x / 100000
012345
x % 100000
К.Ю. Поляков, Е.А. Ерёмин, 2018
со старшего
x
12345
12345
M
100000
10000
x / M
0
1
2345
345
45
1000
100
10
2
3
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;
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
16. Алгоритмизация и программирование. Язык C++
16Алгоритмизация и
программирование.
Язык C++
§ 36. Структуры
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
17. Зачем нужны структуры?
Алгоритмизация и программирование. Язык C++, 11 класс17
Зачем нужны структуры?
Книги в библиотеках:
• автор
символьные строки
• название
целое число
• количество экземпляров
•…
? Как хранить данные?
Несколько массивов:
string authors[N];
string titles[N];
int count[N];
...
неудобно работать
(сортировать и т.д.),
ошибки
Задачa: объединить разнотипные данные в один блок.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
18. Структуры
Алгоритмизация и программирование. Язык C++, 11 класс18
Структуры
Структура – это тип данных, который может включать в
себя несколько полей – элементов разных типов (в
том числе и другие структуры).
новый тип данных
typedef struct
структура
{
string author; // автор, строка
string title;
// название, строка
int count;
// количество, целое
} TBook;
название типа
данных
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
19. Объявление структур
Алгоритмизация и программирование. Язык C++, 11 класс19
Объявление структур
const int N = 100;
TBook B;
TBook Books[N];
? Сколько места занимает в памяти?
cout << sizeof(TBook) << endl; // 12
cout << sizeof(B) << endl;
// 12
cout << sizeof(Books) << endl; // 1200
typedef struct
4 байта
{
string author;
4 байта
string title;
int count;
4 байта
} TBook;
К.Ю. Поляков, Е.А. Ерёмин, 2018
! Это указатели!
http://kpolyakov.spb.ru
20. Обращение к полям структур
Алгоритмизация и программирование. Язык C++, 11 класс20
Обращение к полям структур
Точечная нотация:
B.author // поле author структуры B
Books[5].count // поле count структуры
// Books[5]
cout << sizeof(B.author) << endl; // 4
cout << sizeof(B.title) << endl; // 4
cout << sizeof(B.count) << endl; // 4
cin >> B.author;
cin >> B.title;
cin >> B.count;
cout << B.author << " " << B.title << ". “
<< B.count << " шт.";
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
21. Обращение к полям структур
Алгоритмизация и программирование. Язык C++, 11 класс21
Обращение к полям структур
Присваивание:
B.author = "Пушкин А.С.";
B.title = "Полтава";
B.count = 1;
Использование:
B.count --;
// одну книгу взяли
if( B.count == 0 )
cout << "Этих книг больше нет!";
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
22. Запись структур в файлы
Алгоритмизация и программирование. Язык C++, 11 класс22
Запись структур в файлы
Текстовые файлы:
символ-разделитель
'Пушкин А.С.';'Полтава';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 ();
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
23. Чтение структур из файла
Алгоритмизация и программирование. Язык C++, 11 класс23
Чтение структур из файла
Одна структура:
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) );
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
24. Чтение структур из файла
Алгоритмизация и программирование. Язык C++, 11 класс24
Чтение структур из файла
Число структур неизвестно:
const int N = 100;
int M;
...
Fin.read( (char*) Books,
N*sizeof(TBook) );
M = Fin.gcount() / sizeof(TBook);
cout << "Прочитано " << M << " структур.";
возвращает число успешно
! gcount
прочитанных байтов!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
25. Сортировка структур
Алгоритмизация и программирование. Язык C++, 11 класс25
Сортировка структур
Ключ — это поле, по которому выполняется сортировка.
Ключ – фамилия автора:
? Какой метод?
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];
Books[j] = Books[j+1];
Books[j+1] = B;
}
структуры перемещаются в памяти
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
26. Указатели
Алгоритмизация и программирование. Язык C++, 11 класс26
Указатели
Указатель – это переменная, в которой можно сохранить
адрес любой переменной заданного типа.
TBook *p;
указатель на
переменную типа TBook
p = &B;
p->author
p = &Books[2];
B.author
B
p
0
1
2
3
4
Books
p->author Books[2].author
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
27. Сортировка по указателям
Алгоритмизация и программирование. Язык C++, 11 класс27
Сортировка по указателям
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
…
Нагибин Ю. … … Астафьев В. … … Васильев Б. … … …
! Сами структуры не перемещаются!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
28. Сортировка по указателям
Алгоритмизация и программирование. Язык C++, 11 класс28
Сортировка по указателям
обращение к полям
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;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
29. Алгоритмизация и программирование. Язык C++
29Алгоритмизация и
программирование.
Язык C++
§ 37. Динамические массивы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
30. Чем плох обычный массив?
Алгоритмизация и программирование. Язык C++, 11 класс30
Чем плох обычный массив?
const int N = 100;
int A[N];
статический
массив
• память выделяется при трансляции
• нужно заранее знать размер
• изменить размер нельзя
Задача. В файле записаны фамилии (сколько –
неизвестно!). Вывести их в другой файл в алфавитном
порядке.
• выделить заранее большой блок (с запасом)
• выделять память во время работы программы
(динамически!)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
31. Динамические структуры данных
Алгоритмизация и программирование. Язык C++, 11 класс31
Динамические структуры данных
… позволяют
• создавать новые объекты в памяти
• изменять их размер
• удалять из памяти, когда не нужны
Задача. Ввести с клавиатуры целое значение N, затем –
N целых чисел, и вывести на экран эти числа в
порядке возрастания.
// прочитать данные из файла в массив
// отсортировать их по возрастанию
// вывести массив на экран
? В чём проблема?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
32. Динамические массивы
Алгоритмизация и программирование. Язык C++, 11 класс32
Динамические массивы
Объявление:
int *A;
! Память не выделяется!
Выделение памяти:
A = new int[N];
количество
элементов
К.Ю. Поляков, Е.А. Ерёмин, 2018
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;
удаление
массива
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
34. Тип vector (библиотека STL)
Алгоритмизация и программирование. Язык C++, 11 класс34
Тип 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 );
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
35. Тип vector (библиотека STL)
Алгоритмизация и программирование. Язык C++, 11 класс35
Тип vector (библиотека STL)
Обработка :
for ( i = 0; i < A.size(); i++ )
cout << A[i] << " ";
! Так же, как с обычным массивом!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
36. Динамические матрицы
Алгоритмизация и программирование. Язык C++, 11 класс36
Динамические матрицы
! Матрица – это массив из массивов!
новый тип данных:
Указатель на матрицу:
указатель
typedef int *pInt;
pInt *A;
указатель на указатель
Выделение памяти под массив указателей:
A = new pInt[N];
Выделение памяти под элементы матрицы:
A[0] = new int[M*N];
число элементов
матрицы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
37. Динамические матрицы
Алгоритмизация и программирование. Язык C++, 11 класс37
Динамические матрицы
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;
К.Ю. Поляков, Е.А. Ерёмин, 2018
M
M
удаление
данных
Удаление:
delete [] A[0];
delete [] A;
удаление
указателей
http://kpolyakov.spb.ru
38. Динамические матрицы
Алгоритмизация и программирование. Язык C++, 11 класс38
Динамические матрицы
0
1
N-2
2
N-1
массив
указателей
A
M
M
M
! Строки могут быть разной длины!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
39. Динамические матрицы
Алгоритмизация и программирование. Язык C++, 11 класс39
Динамические матрицы
Выделение памяти:
for ( i = 0; i < N; i++ )
A[i] = new int[M];
Освобождение памяти:
for ( i = 0; i < N; i++ )
delete [] A[i];
освободить
память для
отдельных строк
delete [] A;
освободить массив
указателей
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
40. Динамические матрицы (vector)
Алгоритмизация и программирование. Язык C++, 11 класс40
Динамические матрицы (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;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
41. Расширение массива
Алгоритмизация и программирование. Язык C++, 11 класс41
Расширение массива
Задача. С клавиатуры вводятся натуральные числа, ввод
заканчивается числом 0. Нужно вывести на экран эти
числа в порядке возрастания.
? Какой размер массива нужен?
Ввод данных:
cin >> x;
while ( x != 0 )
{
A.push_back(x);
cin >> x;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
автоматическое
расширение
http://kpolyakov.spb.ru
42. Алгоритмизация и программирование. Язык C++
42Алгоритмизация и
программирование.
Язык C++
§ 00. Списки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
43. Зачем нужны списки?
Алгоритмизация и программирование. Язык C++, 11 класс43
Зачем нужны списки?
Задача. В файле находится список слов, среди которых
есть повторяющиеся. Каждое слово записано в
отдельной строке. Построить алфавитно-частотный
словарь: список слов в алфавитном порядке, справа
от каждого слова должно быть указано, сколько раз
оно встречается в исходном файле.
! Нужно вставлять новые слова в список!
Список – это упорядоченный набор элементов одного
типа, для которого введены операции вставки
(включения) и удаления (исключения).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
44. Алгоритм (псевдокод)
Алгоритмизация и программирование. Язык C++, 11 класс44
Алгоритм (псевдокод)
пока есть слова в файле
{
прочитать очередное слово
если оно есть в списке то
увеличить на 1 счётчик для этого слова
иначе
{
добавить слово в список
записать 1 в счетчик слова
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
45. Использование контейнера map (STL)
Алгоритмизация и программирование. Язык C++, 11 класс45
Использование контейнера map (STL)
Map («отображение») – это словарь (ассоциативный
массив). Индексы элементов – любые данные.
Объявление:
#include <map>
...
map <string,int> L;
индекс –
строка
данные –
целые
Размер словаря:
int p = L.count ( s );
Увеличение счётчика слова s:
L[s] ++;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
46. Использование контейнера map (STL)
Алгоритмизация и программирование. Язык C++, 11 класс46
Использование контейнера 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] ++;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
47. Вывод результата
Алгоритмизация и программирование. Язык C++, 11 класс47
Вывод результата
Итератор (или курсор) – специальный объект, который
позволяет перебрать все элементы контейнера.
тип контейнера
Объявление:
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;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
48. Связные списки (list)
Алгоритмизация и программирование. Язык C++, 11 класс48
Связные списки (list)
Head
конец
списка
«голова»
данные
данные
данные NULL
узлы могут размещаться в разных местах в памяти
только последовательный доступ
Рекурсивное определение:
• пустой список – это список
• список – это узел и связанный с ним список
! Применение: много вставок в середину
и удалений элементов!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
49. Связные списки
Алгоритмизация и программирование. Язык C++, 11 класс49
Связные списки
Циклический список:
Head
данные
данные
Двусвязный список:
Head
NULL данные
данные
«хвост»
данные
Tail
данные NULL
обход в двух направлениях
сложнее вставка и удаление
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
50. Алгоритмизация и программирование. Язык C++
50Алгоритмизация и
программирование.
Язык C++
§ 38. Стек, дек, очередь
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
51. Что такое стек?
Алгоритмизация и программирование. Язык C++, 11 класс51
Что такое стек?
Стек (англ. stack – стопка) – это линейный список, в
котором элементы добавляются и удаляются только с
одного конца («последним пришел – первым ушел»).
LIFO = Last In – First Out.
Системный стек:
• адреса возврата из подпрограмм
• передача аргументов подпрограмм
• хранение локальных переменных
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
52. Реверс массива
Алгоритмизация и программирование. Язык C++, 11 класс52
Реверс массива
Задача. В файле записаны целые числа. Нужно вывести
их в другой файл в обратном порядке.
пока файл не пуст
{
прочитать x
добавить x в стек
}
5
4
3
2
5
4
3
2
1
1
пока стек не пуст
{
вытолкнуть число из стека в x
записать x в файл
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
53. Использование контейнера stack (STL)
Алгоритмизация и программирование. Язык C++, 11 класс53
Использование контейнера stack (STL)
#include <stack>
...
stack <int> S;
стек целых
чисел
Основные операции со стеком:
• push – добавить элемент на вершину стека
• pop – удалить элемент с вершины стека
• top – вернуть элемент с вершины стека
(без удаления)
• empty – вернуть true, если стек пуст,
и false в противном случае.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
54. Использование контейнера stack (STL)
Алгоритмизация и программирование. Язык C++, 11 класс54
Использование контейнера stack (STL)
Переменные:
ifstream Fin;
ofstream Fout;
stack <int> S;
int x;
Чтение данных и загрузка в стек:
Fin.open ( "input.dat" );
while ( Fin >> x )
S.push ( x );
Fin.close();
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
55. Использование контейнера stack (STL)
Алгоритмизация и программирование. Язык C++, 11 класс55
Использование контейнера stack (STL)
Вывод в обратном порядке:
Fout.open ( "output.dat" );
while ( ! S.empty() )
{
Fout << S.top() << endl;
S.pop();
}
Fout.close();
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
56. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык C++, 11 класс56
Вычисление арифметических выражений
? Как компьютер вычисляет арифметические
выражения?
(5+15)/(4+7-1) инфиксная форма (знак операции
между данными)
1920 (Я. Лукашевич): префиксная форма
(знак операции перед данными)
/ + 5 15 - + 4 7 1
/ 20 - + 4 7 1
/ 20 - 11 1
/ 20 10
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
не нужны скобки
первой стоит последняя
операция (вычисляем с конца)
http://kpolyakov.spb.ru
57. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык C++, 11 класс57
Вычисление арифметических выражений
(5+15)/(4+7-1)
1950-е: постфиксная форма
(знак операции после данных)
5 15 + 4 7 + 1 - /
20 4 7 + 1 - /
не нужны скобки
вычисляем с начала
20 11 1 - /
20 10 /
2
! Вычисляем с помощью стека!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
58. Использование стека
Алгоритмизация и программирование. Язык C++, 11 класс58
Использование стека
5 15 + 4 7 + 1 - /
1
5
5
15
4
2
0
4
7
4
2
0
7
1
5
1
2
5
+
+
0
2
• если число – «втолкнуть» в стек 0
1
1
1
21
0
1
0
2
0
2
/
• если операция – выполнить с верхними элементами
стека
! В стеке остается результат!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
59. Скобочные выражения
Алгоритмизация и программирование. Язык C++, 11 класс59
Скобочные выражения
Задача. Вводится символьная строка, в которой записано
некоторое (арифметическое) выражение,
использующее скобки трёх типов: ( ), [ ] и { }.
Проверить, правильное ли расставлены скобки.
()[{()[]}]
[()
[()}
)(
([)]
Для одного типа скобок:
счётчик
0
(
)
(
(
)
(
(
)
)
)
1
0
1
2
1
2
3
2
1
0
({[)}]
? Когда выражение правильное?
• счётчик всегда 0
! Для разных скобок
• в конце счётчик = 0
не работает!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
60. Скобочные выражения (стек)
Алгоритмизация и программирование. Язык C++, 11 класс60
Скобочные выражения (стек)
(
(
[
(
[
(
[
(
(
[
(
)
{
[
(
{
(
{
[
(
(
{
[
(
)
[
(
}
(
]
)
• если открывающая скобка – «втолкнуть» в стек
• если закрывающая скобка – снять парную со стека
? Когда выражение правильное?
• когда встретили закрывающую скобку, на вершине
стека лежит соответствующая открывающая
• в конце работы стек пуст
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
61. Скобочные выражения (стек)
Алгоритмизация и программирование. Язык C++, 11 класс61
Скобочные выражения (стек)
Константы и переменные:
const string L = "([{", // открывающие
R = ")]}"; // закрывающие
string str;
// рабочая строка
stack <char> S; // стек
bool err;
// была ли ошибка?
int i, p;
char c;
Вывод результата:
if ( ! err )
cout << "Скобки расставлены верно.";
else
cout << "Скобки расставлены неверно.";
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
62. Скобочные выражения (стек)
Алгоритмизация и программирование. Язык C++, 11 класс62
Скобочные выражения (стек)
for ( i = 0; i < str.size(); i++ ) {
p = L.find ( str[i] );
открывающую
if ( p >= 0 )
скобку в стек
S.push ( str[i] );
p = R.find ( str[i] );
если закрывающая
if ( p >= 0 ) {
скобка…
if ( S.empty () )
err = true;
else {
c = S.top(); S.pop();
if ( p!= L.find(c) ) если не та скобка…
err = true;
}
if ( err ) break;
}
Что ещё?
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
63. Что такое очередь?
Алгоритмизация и программирование. Язык C++, 11 класс63
Что такое очередь?
Очередь – это линейный список,
для которого введены две
операции:
• добавление элемента в конец
• удаление первого элемента
FIFO = Fist In – First Out.
Применение:
• очереди сообщений в операционных системах
• очереди запросов ввода и вывода
• очереди пакетов данных в маршрутизаторах
•…
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
64. Заливка области
Алгоритмизация и программирование. Язык C++, 11 класс64
Заливка области
Задача. Рисунок задан в виде матрицы A, в которой
элемент A[y][x] определяет цвет пикселя на
пересечении строки y и столбца x. Перекрасить в цвет
2 одноцветную область, начиная с пикселя (x0,y0).
0 1 2 3 4
0 1 2 3 4
0 0 1 0 1 1
0 0 2 0 1 1
1 1 1 1 2 2
(1,2)
1 2 2 2 2 2
2 0 1 0 2 2
2 0 2 0 2 2
3 3 3 1 2 2
3 3 3 1 2 2
4 0 1 1 0 0
4 0 1 1 0 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
65. Заливка: использование очереди
Алгоритмизация и программирование. Язык C++, 11 класс65
Заливка: использование очереди
добавить в очередь точку (x0,y0)
запомнить цвет начальной точки
пока очередь не пуста
{
взять из очереди точку (x,y)
если A[y][x] = цвету начальной точки то
{
A[y][x] = цвет заливки;
добавить в очередь точку (x-1,y)
добавить в очередь точку (x+1,y)
добавить в очередь точку (x,y-1)
добавить в очередь точку (x,y+1)
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
66. Очередь queue (STL)
Алгоритмизация и программирование. Язык C++, 11 класс66
Очередь 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;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
67. Очередь queue (STL)
Алгоритмизация и программирование. Язык C++, 11 класс67
Очередь queue (STL)
Основные операции:
• push – добавить элемент в конец очереди
• pop – удалить первый элемент в очереди
• front – вернуть первый элемент в очереди
(без удаления)
• empty – вернуть true, если очередь пуста,
и false в противном случае.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
68. Заливка
Алгоритмизация и программирование. Язык C++, 11 класс68
Заливка
Константы и переменные:
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) );
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
69. Заливка (основной цикл)
Алгоритмизация и программирование. Язык C++, 11 класс69
Заливка (основной цикл)
пока очередь не пуста
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) );
}
Что можно улучшить?
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
70. Очередь: статический массив
Алгоритмизация и программирование. Язык C++, 11 класс70
Очередь: статический массив
голова
Head
Tail
хвост
0
N-1
1
2
3
4
Удаление элемента:
Head
5
Tail
0
N-1
1
2
3
4
Добавление элемента:
Head
5
Tail
0
N-1
2
3
4
не двигаем элементы
К.Ю. Поляков, Е.А. Ерёмин, 2018
5
6
нужно знать размер
http://kpolyakov.spb.ru
71. Очередь: статический массив
Алгоритмизация и программирование. Язык C++, 11 класс71
Очередь: статический массив
Замыкание в кольцо:
Tail
Head
1
7
N
8
9
1
Очередь заполнена:
Tail
2
3
4
5
Head
1
7
6
N
8
9
10 11 12
Очередь пуста:
1
1
2
3
4
5
6
Tail Head
N
! Вариант: хранить размер очереди в переменной!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
72. Что такое дек?
Алгоритмизация и программирование. Язык C++, 11 класс72
Что такое дек?
Дек – это линейный список, в котором можно добавлять и
удалять элементы как с одного, так и с другого конца.
Моделирование:
• статический массив (кольцо)
• динамический массив
• связный список
! STL: deque!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
73. Алгоритмизация и программирование. Язык C++
73Алгоритмизация и
программирование.
Язык C++
§ 39. Деревья
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
74. Что такое дерево?
Алгоритмизация и программирование. Язык C++, 11 класс74
Что такое дерево?
A
1
B
D
C
E
F
«Сыновья» А: B, C.
2
Высота дерева —
наибольшее
расстояние от
корня до листа
G
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G. «Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
75. Рекурсивные определения
Алгоритмизация и программирование. Язык C++, 11 класс75
Рекурсивные определения
1) пустая структура – это дерево
2) дерево – это корень и несколько связанных с ним
отдельных (не связанных между собой) деревьев
Двоичное (бинарное) дерево:
1) пустая структура – это двоичное дерево
2) двоичное дерево – это корень и два связанных с ним
отдельных двоичных дерева («левое» и «правое»
поддеревья)
Применение:
• поиск в большом массиве неменяющихся данных
• сортировка данных
• вычисление арифметических выражений
• оптимальное сжатие данных (метод Хаффмана)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
76. Деревья поиска
Алгоритмизация и программирование. Язык C++, 11 класс76
Деревья поиска
Ключ – это значение, связанное с узлом дерева, по
которому выполняется поиск.
6
3
1
8
4
7
9
• слева от узла – узлы с
меньшими или равными
ключами
• справа от узла – узлы с
большими или равными
ключами
O(log N)
? Сложность поиска?
К.Ю. Поляков, Е.А. Ерёмин, 2018
Двоичный поиск O(log N)
Линейный поиск O(N)
http://kpolyakov.spb.ru
77. Обход дерева
Алгоритмизация и программирование. Язык C++, 11 класс77
Обход дерева
Обойти дерево «посетить» все узлы по одному разу.
список узлов
КЛП – «корень-левый-правый» (в прямом порядке):
посетить корень
обойти левое поддерево
обойти правое поддерево
ЛКП – «левый-корень-правый» (симметричный):
обойти левое поддерево
посетить корень
обойти правое поддерево
ЛПК – «левый-правый-корень» (в обратном порядке):
обойти левое поддерево
обойти правое поддерево
посетить корень
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
78. Обход дерева
Алгоритмизация и программирование. Язык C++, 11 класс78
Обход дерева
(1+4)*(9-5)
*
+
«в глубину»
1
-
4
9
5
КЛП: * + 1 4 – 9 5
префиксная форма
ЛКП: 1 + 4 * 9 - 5
инфиксная форма
ЛПК: 1 4 + 9 5 - *
постфиксная форма
Обход «в ширину»: «сыновья», потом «внуки», …
* + - 1 4 9 5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
79. Обход КЛП – обход «в глубину»
Алгоритмизация и программирование. Язык C++, 11 класс79
Обход КЛП – обход «в глубину»
записать в стек корень дерева
пока стек не пуст
{
выбрать узел V с вершины стека
посетить узел V
если у узла V есть правый сын то
добавить в стек правого сына V
если у узла V есть левый сын то
добавить в стек левого сына V
}
? Почему сначала добавить правого сына?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
80. Обход КЛП – обход «в глубину»
Алгоритмизация и программирование. Язык C++, 11 класс80
Обход КЛП – обход «в глубину»
(1+4)*(9-5)
*
+
4
1
*
-
9
5
5
9
+
-
1
4
-
4
-
-
9
5
*
+
1
4
–
К.Ю. Поляков, Е.А. Ерёмин, 2018
5
http://kpolyakov.spb.ru
81. Обход «в ширину»
Алгоритмизация и программирование. Язык C++, 11 класс81
Обход «в ширину»
записать в очередь корень дерева
пока очередь не пуста
{
выбрать узел V из очереди
посетить узел V
если у узла V есть левый сын то
добавить в очередь левого сына V
если у узла V есть правый сын то
добавить в очередь правого сына V
}
? Почему сначала добавить левого сына?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
82. Обход «в ширину»
Алгоритмизация и программирование. Язык C++, 11 класс82
Обход «в ширину»
(1+4)*(9-5)
*
+
4
1
голова
очереди
*
К.Ю. Поляков, Е.А. Ерёмин, 2018
-
9
5
+
4
1
-
5
9
4
1
5
9
4
5
9
5
*
+
-
1
4
9
5
http://kpolyakov.spb.ru
83. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык C++, 11 класс83
Вычисление арифметических выражений
? Что будет в корне дерева?
40–2*3–4*5
В корень дерева нужно поместить последнюю из
операций с наименьшим приоритетом.
-
-
40–2*3
4*5
-
-
40
*
2*3
*
40
4
К.Ю. Поляков, Е.А. Ерёмин, 2018
*
2
4
5
3
5
http://kpolyakov.spb.ru
84. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык C++, 11 класс84
Вычисление арифметических выражений
Построение дерева:
найти последнюю выполняемую операцию
если операций нет то
{
создать узел-лист
выход
}
поместить операцию в корень дерева
построить левое поддерево
построить правое поддерево
! Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
85. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык C++, 11 класс85
Вычисление арифметических выражений
Вычисление по дереву:
n1 = значение левого поддерева
n2 = значение правого поддерева
результат = операция(n1, n2)
! Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
86. Использование связанных структур
Алгоритмизация и программирование. Язык C++, 11 класс86
Использование связанных структур
Дерево – нелинейная структура динамический
массив неудобен!
данные
данные NULL NULL
данные NULL NULL
ссылка вперёд
typedef struct TNode *PNode;
typedef struct TNode
новый тип:
{
адрес узла
string data;
PNode left;
ссылки на
PNode right;
сыновей
} TNode;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
87. Работа с памятью
Алгоритмизация и программирование. Язык C++, 11 класс87
Работа с памятью
PNode p;
// указатель на узел
Выделить память для узла:
p = new TNode;
Обращение к новому узлу (по указателю):
p->data = s;
p->left = NULL;
p->right = NULL;
Освобождение памяти:
delete p;
не массив,
поэтому нет []
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
88. Основная программа
Алгоритмизация и программирование. Язык C++, 11 класс88
Основная программа
int main()
{
PNode T;
string s;
// ввести строку s
T = MakeTree ( s );
cout << "Результат: ", Calc(T);
}
! Нужно построить MakeTree и Calc!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
89. Построение дерева
Алгоритмизация и программирование. Язык C++, 11 класс89
Построение дерева
PNode MakeTree ( string s )
вернёт адрес
{
нового дерева
int k;
PNode Tree;
Tree = new struct TNode;
k = LastOp ( s );
if ( k == -1 ) {
// новый узел – лист (число)
}
else {
// новый узел – операция
// построить поддеревья
}
return Tree;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
90. Построение дерева
Алгоритмизация и программирование. Язык C++, 11 класс90
Построение дерева
Новый узел – лист:
Tree->data = s;
Tree->left = NULL;
Tree->right = NULL;
нет сыновей!
Новый узел – операция:
один символ!
Tree->data = s.substr(k,1);
Tree->left = MakeTree ( s.substr(0,k) );
Tree->right = MakeTree ( s.substr(k+1) );
! Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2018
до конца строки
http://kpolyakov.spb.ru
91. Вычисление по дереву
Алгоритмизация и программирование. Язык C++, 11 класс91
Вычисление по дереву
int Calc ( PNode Tree )
это число
{
(лист)
int n1, n2, res;
if ( Tree->left == NULL )
res = atoi ( Tree->data.c_str() );
else {
n1 = Calc ( Tree->left );
Рекурсия!
n2 = Calc ( Tree->right );
switch ( Tree->data[0] ) {
case '+': res = n1 + n2; break;
case '-': res = n1 - n2; break;
case '*': res = n1 * n2; break;
case '/': res = n1 / n2; break;
default: res = 99999;
}
}
return res;
}
!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
92. Приоритет операции
Алгоритмизация и программирование. Язык C++, 11 класс92
Приоритет операции
int Priority ( char op )
{
switch ( op )
{
case '+':
case '-': return 1;
case '*':
case '/': return 2;
}
return 100;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
93. Последняя выполняемая операция
Алгоритмизация и программирование. Язык C++, 11 класс93
Последняя выполняемая операция
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;
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
94. Двоичное дерево в массиве
Алгоритмизация и программирование. Язык C++, 11 класс94
Двоичное дерево в массиве
-
0
-
*
*
2
A[0]
A[1]
A[2]
4
5
3
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
5
6
7
8
9
10
7
8
9
10
- - * 40 *
0
1
2
3
4
- - * 40 * 4 5
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
2
- - *
0
40
1
0
1
2
3
4
5
6
- - * 40 * 4 5
A[4]
К.Ю. Поляков, Е.А. Ерёмин, 2018
A[9]
A[10]
A[i]
2 3
?
A[2*i+1]
A[2*i+2]
?
http://kpolyakov.spb.ru
95. Алгоритмизация и программирование. Язык C++
95Алгоритмизация и
программирование.
Язык C++
§ 40. Графы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
96. Что такое граф?
Алгоритмизация и программирование. Язык C++, 11 класс96
Что такое граф?
Граф – это набор вершин и связей между ними (рёбер).
Матрица смежности:
A
B
C
D
Список смежности:
( A(B, C),
B(A, C, D),
C(A, B, С, D),
D(B, C) )
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
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. Связность графа
Алгоритмизация и программирование. Язык C++, 11 класс97
Связность графа
Связный граф – это граф, между любыми вершинами
которого существует путь.
A
B
C
A
C
B
D
D
компоненты связности
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
98. Дерево – это граф?
Алгоритмизация и программирование. Язык C++, 11 класс98
Дерево – это граф?
Дерево – это связный граф без циклов (замкнутых путей).
A
A
C
B
D
B
ABC
BCD
D
ABDC
CCC…
К.Ю. Поляков, Е.А. Ерёмин, 2018
H
C
E
F
G
J
дерево
http://kpolyakov.spb.ru
99. Взвешенные графы
Алгоритмизация и программирование. Язык C++, 11 класс99
Взвешенные графы
A
12
B
8
2
C
5
6
Весовая матрица:
A
4
D
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4
вес ребра
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
100. Ориентированные графы (орграфы)
Алгоритмизация и программирование. Язык C++, 11 класс100
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра
называю дугами.
A
8
5
12
B
6
A
C
4
D
A
B
C
D
12
B
12
C
8
5
D
6
4
4
! Весовая матрица может быть несимметрична!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
101. Жадные алгоритмы
Алгоритмизация и программирование. Язык C++, 11 класс101
Жадные алгоритмы
Жадный алгоритм – это многошаговый алгоритм, в
котором на каждом шаге принимается решение,
лучшее в данный момент.
Задача. Найти кратчайший маршрут из А в F.
2
B
9
A
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
7
D
8
4
1
3
E
F
5
http://kpolyakov.spb.ru
102. Жадные алгоритмы
Алгоритмизация и программирование. Язык C++, 11 класс102
Жадные алгоритмы
Задача. Найти кратчайший маршрут из А в F.
2
B
9
A
4
C
7
D
8
1
1
3
E
F
2
? Это лучший маршрут?
! Жадный алгоритм не всегда даёт наилучшее
решение!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
103. Задача Прима-Крускала
Алгоритмизация и программирование. Язык C++, 11 класс103
Задача Прима-Крускала
Задача. Между какими городами нужно проложить линии
связи, чтобы все города были связаны в одну систему
и общая длина линий связи была наименьшей?
(минимальное остовное дерево)
7
D
B
2
1
8
3
9
A
F
4
C
1
2
E
!
Алгоритм Крускала:
Лучшее решение!
• начальное дерево – пустое
• на каждом шаге добавляется ребро минимального
веса, которое ещё не входит в дерево и не
приводит к появлению цикла
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
104. Раскраска вершин
Алгоритмизация и программирование. Язык C++, 11 класс104
Раскраска вершин
2
B
9
A
4
C
7
D
8
1
1
3
E
for (i = 0; i < N; i ++) col[i] = i;
F
2
каждой
вершине
свой цвет
Сделать N-1 раз:
• ищем ребро минимальной длины среди всех рёбер,
концы которых окрашены в разные цвета;
• найденное ребро (iMin,jMin) добавляется в список
выбранных, и все вершины, имеющие цвет
col[jMin], перекрашиваются в цвет col[iMin].
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
105. Раскраска вершин
Алгоритмизация и программирование. Язык C++, 11 класс105
Раскраска вершин
Данные:
const int N = 6;
const int INF = 30000; // большое число
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;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
106. Раскраска вершин
Алгоритмизация и программирование. Язык C++, 11 класс106
Раскраска вершин
for ( k = 0; k < N-1; k++ ) {
// поиск ребра с минимальным весом
minDist = INF;
for ( i = 0; i < N; i ++ )
нет цикла
for ( j = 0; j < N; j ++ )
if ( col[i] != col[j] &&
W[i][j] < minDist ) {
iMin = i; jMin = j; minDist = W[i][j];
}
// добавление ребра в список выбранных
ostov[k][0] = iMin; ostov[k][1] = jMin;
// перекрашивание вершин
c = col[jMin];
for ( i = 0; i < N; i ++ )
if ( col[i] == c ) col[i] = col[iMin];
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
107. Кратчайший маршрут
Алгоритмизация и программирование. Язык C++, 11 класс107
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
4
dist
selected
C
A
0
+
выбрана?
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
1
B
2
C
4
1
3
F
2
E
D
Э.В. Дейкстра
E
F
кратчайшее
расстояние от A
ближайшая от A
невыбранная вершина
http://kpolyakov.spb.ru
108. Кратчайший маршрут
Алгоритмизация и программирование. Язык C++, 11 класс108
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
4
C
dist
selected
W[x,z]
X
A
0
+
Z
W[x,y]
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
1
B
2
+
C
4
W[z,y]
Y
1
3
F
2
E
D
9
E
Э.В. Дейкстра
F
может быть так, что
W[x,z] + W[z,y] < W[x,y]
http://kpolyakov.spb.ru
109. Кратчайший маршрут
Алгоритмизация и программирование. Язык C++, 11 класс109
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
4
C
dist
selected
W[x,z]
X
A
0
+
Z
W[x,y]
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
1
B
2
+
C
4
+
W[z,y]
Y
1
3
F
2
E
D
9
E
5
Э.В. Дейкстра
F
может быть так, что
W[x,z] + W[z,y] < W[x,y]
http://kpolyakov.spb.ru
110. Кратчайший маршрут
Алгоритмизация и программирование. Язык C++, 11 класс110
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
4
dist
selected
C
A
0
+
B
2
+
D
3
F
D
9
8
E
5
+
Э.В. Дейкстра
2
E
1
C
4
+
1
F
7
длины кратчайших
маршрутов из A в
другие вершины
! При рассмотрении вершин F и D
таблица не меняется!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
111. Как найти сам кратчайший маршрут?
Алгоритмизация и программирование. Язык C++, 11 класс111
Как найти сам кратчайший маршрут?
B
2
C
4
A
0
D
8
9
A
dist
7
B
2
3
F
2
E
1
C
4
1
D
8
E
5
F
7
dist[D] + DF = 8 + 1 = 9
dist[E] + EF = 5 + 2 = 7
откуда
приехали в
F?
A C E F
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
112. Алгоритм Дейкстры
Алгоритмизация и программирование. Язык C++, 11 класс112
Алгоритм Дейкстры
Данные:
const int N = 6;
const int INF = 30000;
int W[N][N];
// весовая матрица
bool selected[N]; // вершина выбрана?
int dist[N];
// расстояние от A
int start, V, minDist;
Начальные значения (выбор начальной вершины):
start = 0; // начальная вершина
for ( int i = 0; i < N; i ++ ) {
selected[i] = false; // все не выбраны
dist[i] = W[start][i];
}
selected[start] = true; // уже выбрана
dist[start] = 0;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
113. Алгоритм Дейкстры
Алгоритмизация и программирование. Язык C++, 11 класс113
Алгоритм Дейкстры
Основной цикл:
пока ещё есть
minDist = 0;
вершины
V = start;
проверка
while ( minDist < INF ) {
маршрутов через
selected[V] = true;
вершину V
for( int i = 0; i < N; i++ )
if ( dist[V]+W[V][i] < dist[i] )
dist[i] = dist[V] + W[V][i];
minDist = INF;
выбор следующей
for( int i = 0; i < N; i++ )
вершины,
if ( !selected[i] &&
ближайшей к A
dist[i] < minDist ) {
minDist = dist[i];
V = i;
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
114. Алгоритм Дейкстры
Алгоритмизация и программирование. Язык C++, 11 класс114
Алгоритм Дейкстры
Вывод результата (маршрут 0 N-1):
пока не пришли в
V = N - 1;
начальную вершину
cout << V << " ";
обратным ходом
while( V != start ) {
for( int i=0; i<N; i++ )
if( i != V &&
dist[i] + W[i][V] == dist[V] ) {
V = i;
break;
нашли вершину i, из
}
которой могли прийти в
вершину V
cout << " <- " << V;
}
Она единственная?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
115. Алгоритм Флойда
Алгоритмизация и программирование. Язык C++, 11 класс115
Алгоритм Флойда
Все кратчайшие пути (из любой вершины в любую)
Идея:
K
W[i][k]
I
W[k][j]
W[i][j]
J
? Какова сложность?
O(N3)
проверить все
для всех
вершины
пар вершин
for( int k = 0; k < N; k++ )
без
for( int i = 0; i < N; i++ )
вершины k
for( int j = 0; j < N; j++ )
if( W[i][k] + W[k][j] < W[i][j] )
W[i][j] = W[i][k] + W[k][j];
путь через
вершину k
К.Ю. Поляков, Е.А. Ерёмин, 2018
? Как найти сам маршрут?
http://kpolyakov.spb.ru
116. Задача коммивояжера
Алгоритмизация и программирование. Язык C++, 11 класс116
Задача коммивояжера
Коммивояжер (бродячий торговец) должен выйти из города 1
и, посетив по разу в неизвестном порядке города 2,3,...N,
вернуться обратно в город 1. В каком порядке надо обходить
города, чтобы путь коммивояжера был кратчайшим?
! Это NP-полная задача, которая строго решается
только перебором вариантов (пока)!
Точные методы:
большое время счета для
1) простой перебор;
больших N
2) метод ветвей и границ;
O(N!)
3) метод Литтла;
4) …
Приближенные методы:
1) метод случайных перестановок (Matlab)
не гарантируется
2) генетические алгоритмы
оптимальное
3) метод муравьиных колоний
решение
4) …
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
117. Некоторые задачи
Алгоритмизация и программирование. Язык C++, 11 класс117
Некоторые задачи
Задача на минимум суммы. Имеется N домов, в каждом из
которых живет pi жителей (i=1,...,N). Надо разместить
магазин в одном из них так, чтобы общее расстояние,
проходимое всеми жителями по дороге в магазин, было
минимальным.
Задача о наибольшем потоке. Есть система труб, которые
имеют соединения в N узлах. Один узел S является
источником, еще один – стоком T. Известны пропускные
способности каждой трубы. Надо найти наибольший поток
от источника к стоку.
Задача о наибольшем паросочетании. Есть M мужчин и N
женщин. Каждый мужчина указывает несколько (от 0 до N)
женщин, на которых он согласен жениться. Каждая
женщина указывает несколько мужчин (от 0 до M), за
которых она согласна выйти замуж. Требуется заключить
наибольшее количество моногамных браков.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
118. Алгоритмизация и программирование. Язык C++
118Алгоритмизация и
программирование.
Язык C++
§ 41. Динамическое
программирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
119. Что такое динамическое программирование?
Алгоритмизация и программирование. Язык C++, 11 класс119
Что такое динамическое программирование?
;
Числа Фибоначчи:
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
.
F5
F4
F3
F2
int Fib ( int N )
{
F2
F1
if ( N < 3 )
return 1;
else return Fib(N-1) + Fib(N-2);
}
F3
F2
F1
повторное вычисление тех же значений
! Запоминать то, что вычислено!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
120. Динамическое программирование
Алгоритмизация и программирование. Язык C++, 11 класс120
Динамическое программирование
F1
1
F2
1
F3
2
F4
3
F5
5
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
Объявление массива:
const int N = 10;
int F[N+1]; // чтобы начать с 1
Заполнение массива:
F[1] = 1; F[2] = 1;
for ( i = 3; i <= N; i++ )
F[i] = F[i-1] + F[i-2];
F45: рекурсия: 8 с
дин. программирование: < 0,01 с
? Можно ли обойтись без массива?
К.Ю. Поляков, Е.А. Ерёмин, 2018
нужны только
два последних!
http://kpolyakov.spb.ru
121. Динамическое программирование
Алгоритмизация и программирование. Язык C++, 11 класс121
Динамическое программирование
Динамическое программирование – это способ
решения сложных задач путем сведения их к более
простым задачам того же типа.
B
5
2
A
1
С
D
20
30
40
ABE: 5 + 20 = 25
E
AСE: 2 + 30 = 32
ADE: 1 + 40 = 41
увеличение скорости
дополнительный расход памяти
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
122. Количество вариантов
Алгоритмизация и программирование. Язык C++, 11 класс122
Количество вариантов
Задача. Найти количество KN цепочек, состоящих из N
нулей и единиц, в которых нет двух стоящих подряд
единиц.
Решение «в лоб»:
битовые цепочки
1
2
3
N-1
N
0/1
• построить все возможные цепочки
• проверить каждую на «правильность»
? Сколько возможных цепочек?
2N
Сложность
алгоритма O(2N)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
123. Количество вариантов
Алгоритмизация и программирование. Язык C++, 11 класс123
Количество вариантов
Задача. Найти количество KN цепочек, состоящих из N
нулей и единиц, в которых нет двух стоящих подряд
единиц.
Простые случаи:
KN = KN-1 + KN-2 = FN+2
N = 1: 0 1
K1=2
N = 2: 00 01 10 K2=3
Общий случай:
1
2
3
1
2
3
1
0
N-1
N
N-1
N
0
KN-1
KN-1 «правильных»
цепочек начинаются
с нуля!
KN-2 «правильных»
цепочек начинаются
с единицы!
KN-2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
124. Оптимальное решение
Алгоритмизация и программирование. Язык C++, 11 класс124
Оптимальное решение
Задача. В цистерне N литров молока. Есть бидоны
объемом 1, 5 и 6 литров. Нужно разлить молоко в
бидоны так, чтобы все бидоны были заполнены и
количество используемых бидонов было
минимальным.
Перебор?
при больших N – очень долго!
«Жадный алгоритм»?
N = 10: 10 = 6 + 1 + 1 + 1 + 1
10 = 5 + 5 K = 2
K=5
! Не даёт оптимального решения!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
125. Оптимальное решение
Алгоритмизация и программирование. Язык C++, 11 класс125
Оптимальное решение
KN – минимальное число бидонов для N литров
Сначала выбрали бидон…
1 л: KN = 1 + KN-1
5 л:
KN = 1 + KN-5
6 л: KN = 1 + KN-6
min
Рекуррентная формула:
KN = 1 + min (KN-1 , KN-5 , KN-6)
при N 6
KN = 1 + min (KN-1 , KN-5)
при N = 5
KN = 1 + KN-1
при N < 5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
126. Оптимальное решение (бидоны)
Алгоритмизация и программирование. Язык C++, 11 класс126
Оптимальное решение (бидоны)
KN = 1 + min (KN-1 , KN-5 , KN-6)
N
KN
P
0
0
0
1
1
1
2
2
1
3
3
1
4
4
1
5
1
5
6
1
6
7
2
1
8
3
1
9
4
1
10
2
5
8
3
1
9
4
1
10
2
5
объём бидона, взятого последним
N
KN
P
0
0
0
1
1
1
2 бидона
2
2
1
3
3
1
5 + 5
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
4
1
5
1
5
6
1
6
7
2
1
! Похоже на алгоритм Дейкстры!
http://kpolyakov.spb.ru
127. Задача о куче
Алгоритмизация и программирование. Язык C++, 11 класс127
Задача о куче
Задача. Из камней весом pi (i=1, …, N) набрать кучу
весом ровно W или, если это невозможно,
максимально близкую к W (но меньшую, чем W).
Решение «в лоб»:
1
2
3
N-1
N
1
0
0
1
0
камень
взят
камень
не взят
! Выбрать лучшую цепочку!
? Сколько возможных цепочек?
2N
Сложность
алгоритма O(2N)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
128. Задача о куче
Алгоритмизация и программирование. Язык C++, 11 класс128
Задача о куче
Задача. Из камней весом pi (i=1, …, N) набрать кучу
весом ровно W или, если это невозможно,
максимально близкую к W (но меньшую, чем W).
Идея: сохранять в массиве решения всех более простых
задач этого типа (при меньшем количестве камней N и
меньшем весе W).
Пример: W = 8, камни 2, 4, 5 и 7
1
2
3
4
i
2
4
5
7
pi
0
0
0
0
0
1
0
2
2
3
2
4
2
5
2
6
2
7
2
8
2
w
базовые случаи
T[i][w] – оптимальный вес, полученный для
кучи весом w из i первых по счёту камней.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
129. Задача о куче
Алгоритмизация и программирование. Язык C++, 11 класс129
Задача о куче
1
2
3
4
2
4
5
7
0
0
0
0
0
1
0
0
2
2
2
3
2
2
4
2
4
5
2
4
6
2
6
7
2
6
8
2
6
Добавляем камень с весом 4:
для w < 4 ничего не меняется!
для w 4:
если его не брать: T[2][w] = T[1][w]
если его взять:
T[2][w] = 4 + T[1][w-4]
? Какой вариант выбрать?
К.Ю. Поляков, Е.А. Ерёмин, 2018
max
http://kpolyakov.spb.ru
130. Задача о куче
Алгоритмизация и программирование. Язык C++, 11 класс130
Задача о куче
1
2
3
4
2
4
5
7
0
0
0
0
0
1
0
0
0
2
2
2
2
3
2
2
2
4
2
4
4
5
2
4
5
6
2
6
6
7
2
6
7
8
2
6
7
Добавляем камень с весом 5:
для w < 5 ничего не меняется!
для w 5:
если его не брать: T[3][w] = T[2][w]
если его взять:
T[3][w] = 5 + T[2][w-5]
max
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
131. Задача о куче
Алгоритмизация и программирование. Язык C++, 11 класс131
Задача о куче
1
2
3
4
2
4
5
7
0
0
0
0
0
1
0
0
0
0
2
2
2
2
2
3
2
2
2
2
4
2
4
4
4
5
2
4
5
5
6
2
6
6
6
7
2
6
7
7
8
2
6
7
7
Добавляем камень с весом 7:
для w < 7 ничего не меняется!
для w 7:
если его не брать: T[4][w] = T[3][w]
если его взять:
T[4][w] = 7 + T[3][w-7]
max
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
132. Задача о куче
Алгоритмизация и программирование. Язык C++, 11 класс132
Задача о куче
Добавляем камень с весом pi:
для w < pi ничего не меняется!
max
для w pi:
если его не брать: T[i][w] = T[i-1][w]
если его взять:
T[i][w] = pi + T[i-1][w-pi]
Рекуррентная формула:
при w < pi: T[i][w] = T[i-1][w]
при w pi: T[i][w] = max ( T[i-1][w],
pi+T[i-1][w-pi])
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
133. Задача о куче
Алгоритмизация и программирование. Язык C++, 11 класс133
Задача о куче
? Какие камни нужно взять?
2
4
5
7
0
0
0
0
0
1
0
0
0
0
2
2
2
2
2
3
2
2
2
2
Оптимальный вес 7
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
2
4
4
4
5
2
4
5
5
6
2
6
6
6
7
2
6
7
7
8
2
6
7
7
5 + 2
http://kpolyakov.spb.ru
134. Задача о куче
Алгоритмизация и программирование. Язык C++, 11 класс134
Задача о куче
? Какова сложность алгоритма?
Заполнение таблицы:
N
2
4
5
7
0
0
0
0
0
1
0
0
0
0
2
2
2
2
2
W+1
3
2
2
2
2
4
2
4
4
4
5
2
4
5
5
6
2
6
6
6
7
2
6
7
7
8
2
6
7
7
! Сложность O(N W) !
псевдополиномиальный
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
135. Количество программ
Алгоритмизация и программирование. Язык C++, 11 класс135
Количество программ
Задача. У исполнителя Утроитель есть команды:
1. прибавь 1
2. умножь на 3
Сколько есть разных программ, с помощью которых
можно из числа 1 получить число 20?
? Как решать, не выписывая все программы?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
136. Количество программ
Алгоритмизация и программирование. Язык C++, 11 класс136
Количество программ
Как получить число N:
N-1
если делится на 3!
N
3
+1
N
последняя
команда
*3
Рекуррентная формула:
KN = KN-1
KN = KN-1 + KN/3
К.Ю. Поляков, Е.А. Ерёмин, 2018
если N не делится на 3
если N делится на 3
http://kpolyakov.spb.ru
137. Количество программ
Алгоритмизация и программирование. Язык C++, 11 класс137
Количество программ
Рекуррентная формула:
если N не делится на 3
если N делится на 3
KN = KN-1
KN = KN-1 + KN/3
Заполнение таблицы:
N
KN
1
1
2
3
4
5
6
7
8
9
10
1
2
2
2
3
3
3
5
5
одна пустая!
N
KN
K2+K1
K5+K2
K8+K3
11
12
13
14
15
16
17
18
19
20
5
7
7
7
9
9
9
12
12
12
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
138. Количество программ
Алгоритмизация и программирование. Язык C++, 11 класс138
Количество программ
20
Только точки изменения:
N
KN
1
1
3
2
6
3
9
5
12
7
15
9
18
12
21
15
Программа:
K[1] = 1;
for ( int i = 2; i <= N; i ++ )
{
K[i] = K[i-1];
if ( i % 3 == 0 )
K[i] = K[i] + K[i/3];
}
? Где ответ?
К.Ю. Поляков, Е.А. Ерёмин, 2018
? Как объявить массив K?
http://kpolyakov.spb.ru
139. Размен монет
Алгоритмизация и программирование. Язык C++, 11 класс139
Размен монет
Задача. Сколькими различными способами можно
выдать сдачу размером W рублей, если есть монеты
достоинством pi (i=1, …, N)? В наборе есть монета
достоинством 1 рубль (p1 = 1).
Перебор?
при больших N и W – очень долго!
Динамическое программирование:
запоминаем решения всех задач меньшей
размерности: для меньших значений W и меньшего
числа монет N.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
140. Размен монет
Алгоритмизация и программирование. Язык C++, 11 класс140
Размен монет
Пример: W = 10, монеты 1, 2, 5 и 10
1
2
3
4
i
1
2
5
10
pi
0
1
1
1
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
1
10
1
w
базовые случаи
T[i][w] – количество вариантов для суммы
w с использованием i первых по счёту монет.
Рекуррентная формула (добавили монету pi):
при w < pi: T[i][w] = T[i-1][w] без этой монеты
при w pi: T[i][w] = T[i-1][w] + T[i][w-pi]
все варианты размена остатка
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
141. Размен монет
Алгоритмизация и программирование. Язык C++, 11 класс141
Размен монет
Пример: W = 10, монеты 1, 2, 5 и 10
1
2
3
4
1
2
5
10
0
1
1
1
1
1
1
1
1
1
2
1
2
2
2
3
1
2
2
2
4
1
3
3
3
5
1
3
4
4
6
1
4
5
5
7
1
4
6
6
8
1
5
7
7
9
1
5
8
8
10
1
6
10
11
Рекуррентная формула (добавили монету pi):
при w < pi: T[i,w] = T[i-1][w]
при w pi: T[i,w] = T[i-1][w] + T[i][w-pi]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
142. Конец фильма
Алгоритмизация и программирование. Язык C++, 11 класс142
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
143. Источники иллюстраций
Алгоритмизация и программирование. Язык C++, 11 класс143
Источники иллюстраций
1. wallpaperscraft.com
2. www.mujerhoy.com
3. www.pinterest.com
4. www.wayfair.com
5. www.zchocolat.com
6. www.russiantable.com
7. www.kursachworks.ru
8. ebay.com
9. centrgk.ru
10. www.riverstonellc.com
11. 53news.ru
12. 10hobby.ru
13. ru.wikipedia.org
14. иллюстрации художников издательства «Бином»
15. авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru