Алгоритмизация и программирование. Язык Паскаль

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

§ 35. Целочисленные алгоритмы
2-е изд. § 36. Структуры (записи)
§ 00. Множества
§ 37. Динамические массивы
§ 00. Списки
§ 38. Стек, очередь, дек
§ 39. Деревья
§ 40. Графы
§ 41. Динамическое программирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
1

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 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. Решето Эратосфена

Алгоритмизация и программирование. Язык Паскаль, 11 класс
4
Решето Эратосфена
Задача. Вывести все простые числа от 2 до N.
Объявление переменных:
const N = 100;
var i, k: integer;
A: array[2..N] of boolean;
Сначала все невычеркнуты:
for i:= 2 to N do
A[i]:= True;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
5
Решето Эратосфена
Вычёркивание непростых:
k:= 2;
while k*k <= N do begin
if A[k] then begin
i:= k*k;
while i <= N do begin
A[i]:= False;
i:= i + k
end
end;
k:= k + 1
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 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. «Длинные» числа

Алгоритмизация и программирование. Язык Паскаль, 11 класс
9
«Длинные» числа
A = 12345678
Упаковка элементов:
A
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!
longint:
от –231 = – 2 147 483 648 до 231 – 1 = 2 147 483 647.
?
Какие основания можно использовать?
должны помещаться все
промежуточные результаты!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
12
Вычисление факториала
Умножение «длинного» числа на k:
r:= 0;
for i:= 0 to N do begin
s:= A[i]*k + r;
A[i]:= s mod d;
r:= s div d
end;
Вычисление 100!:
for k:=2 to 100 do begin
...
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
15
Вывод длинного числа
Вывод числа с лидирующими нулями:
procedure Write6(x: longint);
var M: longint;
begin
M:= 100000;
while M > 0 do begin
write(x div M);
x:= x mod M;
M:= M div 10
end
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

16
Алгоритмизация и
программирование.
Язык Паскаль
§ 36. Структуры (записи)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

18. Структуры (записи)

Алгоритмизация и программирование. Язык Паскаль, 11 класс
18
Структуры (записи)
Структура – это тип данных, который может включать в
себя несколько полей – элементов разных типов (в
том числе и другие структуры).
новый тип данных
type
структура (запись)
TBook = record
author: string[40];{ автор, строка }
title: string[80]; { название, строка}
count: integer
{ количество, целое }
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
19
Объявление структур
const N = 100;
var B: TBook; { одна структура }
Books: array[1..N] of TBook; { массив }
?
Сколько места занимает в памяти?
writeln(sizeof(TBook)); { 124 }
writeln(sizeof(B));
{ 124 }
writeln(sizeof(Books)); { 12400 }
type
40 + 1 (размер) байт
TBook = record
author: string[40];
80 + 1 (размер) байт
title: string[80];
count: integer
2 байта (FreePascal)
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
20
Обращение к полям структур
Точечная нотация:
B.author { поле author структуры B }
Books[5].count { поле count структуры
Books[5] }
writeln(sizeof(B.author)); { 41 }
writeln(sizeof(B.title)); { 81 }
writeln(sizeof(B.count)); { 2 }
read(B.author); { ввод полей }
read(B.title);
read(B.count);
writeln(B.author, ' ', { вывод }
B.title, '. ', B.count, ' шт.' );
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
21
Обращение к полям структур
Присваивание:
B.author:= 'Пушкин А.С.';
B.title:= 'Полтава';
B.count:= 1;
Использование:
p:= Pos(' ', B.author);
fam:= Copy(B.author, 1, p-1); { фамилия }
B.count:= B.count – 1; { одну книгу взяли }
if B.count = 0 then
writeln('Этих книг больше нет!');
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
22
Запись структур в файлы
Текстовые файлы:
символ-разделитель
'Пушкин А.С.';'Полтава';12
'Лермонтов М.Ю.';'Мцыри';8
Типизированные файлы:
var F: file of TBook;
!
Сложно читать,
ошибки!
Assign(F, 'books.dat');
Rewrite(F);
B.author:= 'Тургенев И.С.';
B.title:= 'Муму';
B.count:= 2;
for i:=1 to N do
write(F, B);
write(F, Books[i]);
Close(F);
только для TBook!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
23
Чтение структур из файла
Assign(F, 'books.dat');
Reset(F);
только для TBook!
Read(F, B);
writeln(B.author,', ',B.title,
', ',B.count);
Close(F);
for i:= 1 to N do { известное количество }
read(F, Books[i]);
счётчик прочитанных структур
i:= 0;
while not Eof(F) do begin { до конца файла }
i:= i + 1;
Read(F, Books[i])
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
24
Сортировка структур
Ключ — это поле, по которому выполняется сортировка.
Ключ – фамилия автора:
Какой метод?
for i:=1 to N-1 do
for j:=N-1 downto i do
if Books[j].author > Books[j+1].author
then begin
var B: TBook;
B:= Books[j];
Books[j]:= Books[j+1];
Books[j+1]:= B
end;
?
структуры перемещаются в памяти
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

25. Указатели

Алгоритмизация и программирование. Язык Паскаль, 11 класс
25
Указатели
Указатель – это переменная, в которой можно сохранить
адрес любой переменной заданного типа.
type PBook = ^TBook;
pointer
указатель на
переменную типа TBook
var P: PBook;
P:=@B;
P^.author
P:=@Books[3];
P
B.author
B
1
2
3
4
5
Books
P^.author Books[3].author
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
26
Сортировка по указателям
var p: array[1..N] of PBook;
for i:=1 to N do
p[i]:= @Books[i];
p[1]
Books
p[2]
p[3]
1
2
3
…
Нагибин Ю. … … Астафьев В. … … Васильев Б. … … …
Задача – переставить указатели:
p[3]
Books
p[1]
p[2]
1
2
3
…
Нагибин Ю. … … Астафьев В. … … Васильев Б. … … …
!
Сами структуры не перемещаются!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
27
Сортировка по указателям
обращение к полям
for i:= 1 to N-1 do
через указатели
for j:= N-1 downto i do
if p[j]^.author > p[j+1]^.author
then begin
переставляем
p1:= p[j]; p[j]:= p[j+1];
указатели!
p[j+1]:= p1
end;
var p1: PBook;
Вывод результата:
for i:=1 to N do
writeln( p[i]^.author, '; ',
p[i]^.title, '; ',
p[i]^.count );
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

28. Алгоритмизация и программирование. Язык Паскаль

28
Алгоритмизация и
программирование.
Язык Паскаль
2-е издание
§ 00. Множества
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

29. Зачем нужны множества?

Алгоритмизация и программирование. Язык Паскаль, 11 класс
29
Зачем нужны множества?
Задача. Определить количество знаков препинания в
символьной строке.
Некрасиво!
count:= 0;
for i:=1 to Length(s) do
if (s[i]='.') or (s[i]=',')
or (s[i]=';') or (s[i]=':')
or (s[i]='!') or (s[i]='?') then
count:= count + 1;
!
Использование множества:
входит во
множество
if s[i] in ['.', ',', ';', ':', '!', '?'] then
count:= count + 1;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

30. Использование множеств

Алгоритмизация и программирование. Язык Паскаль, 11 класс
30
Использование множеств
if s[i] in ['0'.. '9'] then
count:= count + 1;
диапазон
if s[i] in ['a'..'z', '0'..'9',
'.', '-', '_'] then
{ символ правильный }
Переменная типа «множество»:
var digits: set of '0'..'9';
множество цифр
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

31. Использование множеств

Алгоритмизация и программирование. Язык Паскаль, 11 класс
31
Использование множеств
Задача. Вывести все различные цифры, присутствующие
в символьной строке s.
var s: string;
i: integer;
c: char;
digits: set of '0'..'9';
begin
readln(s);
digits:=[]; { пустое множество }
for i:=1 to Length(s) do
сложить два
if s[i] in ['0'..'9']
множества
then digits:= digits + [s[i]];
for c:='0' to '9' do
if c in digits then writeln(c)
end.
вывод через перебор
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

32. Использование множеств

Алгоритмизация и программирование. Язык Паскаль, 11 класс
32
Использование множеств
var cs: set of char;
bs: set of byte;
до 255
элементов
Имена для элементов множества:
стили шрифта
жирный
курсив
type TFontStyles = (fsBold, fsItalic,
fsUnderline);
подчёркивание
var fs: set of TFontStyles;
Операции с множеством:
fs:= [fsBold, fsItalic]; { присвоить значение}
fs:= fs + [fsUnderline]; { добавить элементы }
fs:= fs - [fsItalic];
{ исключить элементы }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

33. Вывод множества на экран

Алгоритмизация и программирование. Язык Паскаль, 11 класс
33
Вывод множества на экран
первый
type TFontStyles = (fsBold, fsItalic,
fsUnderline);
var style: TFontStyles;
последний
fs:= [fsBold, fsItalic];
for style:=fsBold to fsUnderline do
if style in fs then
write(1)
Что будет выведено?
else write(0);
?
fsBold
110
fsUnderline
fsItalic
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

34. Сравнение множеств

Алгоритмизация и программирование. Язык Паскаль, 11 класс
34
Сравнение множеств
var A, B, C: set of 0..9;
...
A:= [1,2,3,4]; B:= [2,3]; C:= [2,3]
Равенство/неравенство:
if A = B then write('A = B'); { нет }
if B = C then write('B = C'); { да }
if A <> B then write('A <> B'); { да }
if C <> B then write('C <> B'); { нет }
Включение одного в другое:
if A >= B then write('A >= B'); { да }
if C <= B then write('C <= B'); { да }
if A > B then write('A > B'); { да }
if C < B then write('C < B'); { нет }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
35
Множества в памяти
var digits: set of 0..9;
Пустое множество:
digits:= [];
Непустое множество:
digits:= [1, 3, 5, 7];
Пересечение множеств:
digits:= [1, 3, 5, 7] *
[2, 3, 4];
логическое
умножение
К.Ю. Поляков, Е.А. Ерёмин, 2018
?
Как хранить в
памяти?
0123456789
0000000000
0123456789
0101010100
0123456789
0101010100
0011100000
0001000000
[3]
!
AND
Аппаратно!
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
36
Множества в памяти
Объединение множеств:
digits:= [1, 3, 5, 7] +
[2, 3, 4];
0123456789
0101010100
0011100000
0111110100
OR
логическое
сложение [1, 2, 3, 4, 5, 7]
Вычитание множеств:
digits:= [1, 3, 5, 7] [2, 3, 4];
0123456789
0101010100
0011100000
0100010100
[1, 5, 7]
?
Как сделать с помощью битовых операций?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

37. Алгоритмизация и программирование. Язык Паскаль

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

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
40
Динамические массивы
Объявление:
var A: array of integer;
Выделение памяти:
read(N);
SetLength(A, N);
?
размер
не указан
Какие индексы?
[0.. N-1]
установить
длину
Чтение данных:
for i:=0 to N-1 do read(A[i]);
for i:=0 to High(A) do read(A[i]);
наибольший
индекс
К.Ю. Поляков, Е.А. Ерёмин, 2018
!
Массив знает свой размер!
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
41
Динамические массивы
Определение длины:
writeln( Length(A) );
Освобождение памяти:
SetLength(A, 0);
Динамические матрицы (FreePascal):
var A: array of array of integer;
A
SetLength(A, 4, 3);
writeln( High(A) );
writeln( High(A[0]) );
К.Ю. Поляков, Е.А. Ерёмин, 2018
3
2
http://kpolyakov.spb.ru

42. Динамические матрицы (PascalABC.NET)

Алгоритмизация и программирование. Язык Паскаль, 11 класс
42
Динамические матрицы (PascalABC.NET)
var A: array of array of integer;
const N = 4;
выделение
const M = 3;
памяти
...
Setlength(A, N);
for var i:=0 to High(A) do
SetLength(A[i], M);
writeln( High(A) );
writeln( High(A[0]) );
3
2
for var i:=0 to High(A) do
SetLength(A[i], 0);
Setlength(A, 0);
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
освобождение
памяти
http://kpolyakov.spb.ru

43. Динамические массивы (FreePascal)

Алгоритмизация и программирование. Язык Паскаль, 11 класс
43
Динамические массивы (FreePascal)
В подпрограммах:
procedure printArray(X: array of integer);
begin
for i:= 0 to High(X) do
write(X[i], ' ')
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
44
Расширение массива
Задача. С клавиатуры вводятся натуральные числа, ввод
заканчивается числом 0. Нужно вывести на экран эти
числа в порядке возрастания.
?
Какой размер массива нужен?
Расширение по 1 элементу:
read(x);
while x <> 0 do begin
SetLength(A, Length(A)+1);
A[High(A)]:= x;
read(x)
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
?
Что плохо?
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
45
Расширение массива
Расширение по 10 элементов:
N:= 0; { счётчик элементов }
read(x);
while x <> 0 do begin
if N > High(A) then
SetLength(A, Length(A)+10);
A[N]:= x;
N:= N + 1;
read(x)
Зачем нужен счётчик?
end;
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

46. Как это работает?

Алгоритмизация и программирование. Язык Паскаль, 11 класс
46
Как это работает?
Эксперимент:
SetLength(A, 100);
write(sizeof(A)); 4
write(100*sizeof(integer));
!
200
A – это указатель!
0
A
1
2
3
…
100
размер массива
type TArray = record
data: array of integer;
size: integer
Как записать в файл?
end;
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

47. Как это работает?

Алгоритмизация и программирование. Язык Паскаль, 11 класс
47
Как это работает?
var A: array of array of integer;
!
Динамическая матрица – это массив указателей!
SetLength(A, 10);
выделить массив
указателей
Строки разной длины:
A
for i:=0 to High(A) do
SetLength(A[i], i+1);
writeln(Length(A[0])); { 1 }
writeln(Length(A[9])); { 10 }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

48. Алгоритмизация и программирование. Язык Паскаль

48
Алгоритмизация и
программирование.
Язык Паскаль
§ 00. Списки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

51. Хранение данных

Алгоритмизация и программирование. Язык Паскаль, 11 класс
51
Хранение данных
Пара «слово-счётчик»:
type
TPair = record
word: string;
count: integer
end;
{ слово }
{ счётчик }
Список таких пар:
динамический
type
массив
TWordList = record
data: array of TPair;
size: integer
количество слов
end;
в списке
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

52. Хранение данных

Алгоритмизация и программирование. Язык Паскаль, 11 класс
52
Хранение данных
Переменная-список:
var L: TWordList;
Начальные значения:
SetLength(L.data, 0);
L.size:= 0;
Вывод результата:
автомат: 1
Assign(F, 'output.dat');
ананас: 12
Rewrite(F);
...
for p:=0 to L.size-1 do
writeln(F, L.data[p].word, ': ',
L.data[p].count);
Close(F);
Как объявить p?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

53. Основной цикл

Алгоритмизация и программирование. Язык Паскаль, 11 класс
53
Основной цикл
while not Eof(F)
{ пока не конец файла }
do begin
readln(F, s);
{ читаем слово }
p:= Find(L, s);
{ ищем его в словаре}
if p >= 0 then
{ если нашли... }
Inc(L.data[p].count)
{ ...увеличить счётчик }
else begin
{ иначе... }
p:= FindPlace(L, s); { найти место }
InsertWord(L, p, s); { вставить в список }
end
end;
Как объявить s?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

54. Поиск слова

Алгоритмизация и программирование. Язык Паскаль, 11 класс
54
Поиск слова
function Find(L: TWordList;
word: string): integer;
var i: integer;
вернуть -1, если
begin
нет в списке
Find:= -1;
for i:=0 to L.size-1 do
if L.data[i].word = word then begin
Find:= i;
вернуть номер
элемента в списке
break
end
выйти из цикла
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

55. Поиск места вставки

Алгоритмизация и программирование. Язык Паскаль, 11 класс
55
Поиск места вставки
function FindPlace(L: TWordList;
word: string): integer;
var i, p: integer;
begin
-1: не найдено
первое слово
p:= -1;
«больше» заданного
for i:=0 to L.size-1 do
if L.data[i].word > word then begin
p:= i;
запомнить номер
break
если не найдено,
end;
вставить в конец
if p < 0 then p:= L.size;
FindPlace:= p
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

56. Вставка слова

Алгоритмизация и программирование. Язык Паскаль, 11 класс
56
Вставка слова
0 автомат
1 ананас
...
k-1 дар
дерево k дом
k+1 дорога
...
ящерица
Сдвиг вниз:
1
автомат
1
12
ананас
...
дар
12 1
3
15
5
1
с последнего
0
дерево
дом
дорога
3
k-1
1
k
15 k+1
5
...
ящерица
1
L.size-1
for i:=L.size-1 downto k+1 do
L.data[i]:= L.data[i-1];
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

57. Вставка слова

Алгоритмизация и программирование. Язык Паскаль, 11 класс
57
Вставка слова
список меняется
procedure InsertWord(var L: TWordList;
k: integer;
word: string);
var i: integer;
увеличить размер,
begin
если нужно
IncSize(L);
сдвиг вниз
for i:=L.size-1 downto k+1 do
L.data[i]:= L.data[i-1];
L.data[k].word:= word; { записать слово }
L.data[k].count:= 1
{ встретилось 1 раз }
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

58. Расширение списка

Алгоритмизация и программирование. Язык Паскаль, 11 класс
58
Расширение списка
список меняется
procedure IncSize (var L: TWordList);
begin
если новый размер больше
размера массива
Inc(L.size);
if L.size > Length(L.data) then
SetLength(L.data, Length(L.data) + 10)
end;
добавить 10
элементов
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

59. Вся программа

Алгоритмизация и программирование. Язык Паскаль, 11 класс
59
Вся программа
program AlphaList;
{ объявления типов TPair и TWordList }
var F: text;
w: string;
L: TWordList;
p: integer;
{ процедуры и функции }
begin
SetLength(L.data, 0);
L.size:= 0;
Assign(F, 'input.dat');
Reset(F);
{ основной цикл: составление списка слов }
Close(F);
{ вывод результата в файл output.dat }
end.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

60. Модули

Алгоритмизация и программирование. Язык Паскаль, 11 класс
60
Модули
program AlphaList;
{ процедура 1 }
{ процедура 2 }
{ процедура 3 }
{ процедура 4 }
{ ...}
{ процедура N-1 }
{ процедура N }
begin
{ программа }
end.
program AlphaList;
uses WordList;
begin
{ программа }
end.
проще разбираться
(«разделяй и властвуй»)
модуль пишет другой
программист
К.Ю. Поляков, Е.А. Ерёмин, 2018
unit WordList;
{ процедура 1 }
{ процедура 2 }
{ процедура 3 }
{ процедура 4 }
{ ...}
{ процедура N-1 }
{ процедура N }
end.
http://kpolyakov.spb.ru

61. Структура модуля

Алгоритмизация и программирование. Язык Паскаль, 11 класс
61
Структура модуля
unit WordList;
interface
…
implementation
«интерфейс» –
общедоступная информация:
• объявление типов данных
• объявления процедур и
функций
…
end.
«реализация» – внутренняя
информация модуля:
• код процедур и функций
• внутренние данные
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

62. Модуль WordList

Алгоритмизация и программирование. Язык Паскаль, 11 класс
62
Модуль WordList
unit WordList;
interface
{ объявления типов TPair и TWordList }
function Find(L: TWordList;
word: string): integer;
function FindPlace(L: TWordList;
word: string): integer;
procedure InsertWord(var L: TWordList;
k: integer; word: string);
implementation
{ код процедур и функций }
end.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

63. Подключение модуля

Алгоритмизация и программирование. Язык Паскаль, 11 класс
63
Подключение модуля
program AlphaList;
uses WordList;
{ подключение модуля }
var F: text;
s: string;
тип известен из
L: TWordList;
интерфейса модуля
p: integer;
begin
{ тело основной программы }
end.
можно использовать
все процедуры,
объявленные в
интерфейсе модуля
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

66. Связные списки: структуры данных

Алгоритмизация и программирование. Язык Паскаль, 11 класс
66
Связные списки: структуры данных
Односвязный список:
указатель
type
PNode = ^TNode;
TNode = record
data: integer;
next: PNode
ссылка на
end;
следующий узел
Двусвязный список:
type
PNode =
TNode =
data:
prev,
end;
^TNode;
record
integer;
next: PNode
К.Ю. Поляков, Е.А. Ерёмин, 2018
ссылки на
предыдущий
(previous) и
следующий узлы
http://kpolyakov.spb.ru

67. Алгоритмизация и программирование. Язык Паскаль

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

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

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

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

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

70. Использование динамического массива

Алгоритмизация и программирование. Язык Паскаль, 11 класс
70
Использование динамического массива
type TStack = record
data: array of integer;
size: integer
end;
«Втолкнуть» x в стек:
изменяется
procedure Push(var S: TStack; x: integer);
begin
if S.size > High(S.data) then
SetLength(S.data, Length(S.data) + 10);
S.data[S.size]:= x;
S.size:= S.size + 1
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

71. Использование динамического массива

Алгоритмизация и программирование. Язык Паскаль, 11 класс
71
Использование динамического массива
«Вытолкнуть» из стека в x :
изменяется
function Pop(var S:TStack): integer;
begin
S.size:= S.size-1;
Pop:= S.data[S.size]
end;
Инициализация стека :
procedure InitStack(var S: TStack);
begin
SetLength(S.data, 0);
S.size:= 0
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

72. Использование динамического массива

Алгоритмизация и программирование. Язык Паскаль, 11 класс
72
Использование динамического массива
Заполнение стека:
var F: text;
InitStack(S);
while not Eof(F) do begin
read(F, x);
Push(S, x)
end;
Вывод результата в файл:
for i:=0 to S.size-1 do begin
x:= Pop(S);
writeln(F, x)
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
73
Вычисление арифметических выражений
?
Как компьютер вычисляет арифметические
выражения?
(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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
74
Вычисление арифметических выражений
(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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
75
Использование стека
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

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
78
Скобочные выражения (стек)
Модель стека:
type TStack = record
data: array of char;
size: integer
end;
Cтек пуст:
function isEmpty(S: TStack): boolean;
begin
isEmpty:= (S.size = 0)
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
79
Скобочные выражения (стек)
Константы и переменные:
const L = '([{'; {
R = ')]}'; {
var S: TStack;
p, i: integer;
str: string;
err: boolean;
c: char;
открывающие скобки }
закрывающие скобки }
{ рабочая строка }
{ признак ошибки }
Вывод результата:
if not err then
writeln('Выражение правильное.')
else writeln('Выражение неправильное.');
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
80
Скобочные выражения (стек)
for i:=1 to Length(str) do begin
открывающую
p:= Pos(str[i], L);
if p > 0 then Push(S, str[i]); скобку в стек
p:= Pos(str[i], R);
если закрывающая
скобка…
if p > 0 then begin
if isEmpty(S) then err:= True
else begin
если не та скобка…
c:= Pop(S);
if p <> Pos(c,L) then err:= True
end;
if err then break
end
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
83
Заливка: использование очереди
добавить в очередь точку (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

84. Очередь (динамический массив)

Алгоритмизация и программирование. Язык Паскаль, 11 класс
84
Очередь (динамический массив)
type TPoint = record
x, y: integer
end;
TQueue = record
data: array of TPoint;
size: integer
end;
Построение структуры «точка»:
function Point(x, y: integer): TPoint;
begin
Point.x:= x;
Point.y:= y
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

85. Очередь (динамический массив)

Алгоритмизация и программирование. Язык Паскаль, 11 класс
85
Очередь (динамический массив)
Добавить точку в очередь:
procedure Put(var Q: TQueue; pt: TPoint);
begin
расширить,
if Q.size > High(Q.data) then
если нужно
SetLength(Q.data,
Length(Q.data) + 10);
Q.data[Q.size]:= pt;
Q.size:= Q.size + 1;
end;
1
2
3
4
0
1
2
3
К.Ю. Поляков, Е.А. Ерёмин, 2018
5
4
http://kpolyakov.spb.ru

86. Очередь (динамический массив)

Алгоритмизация и программирование. Язык Паскаль, 11 класс
86
Очередь (динамический массив)
Получить первую точку в очереди:
function Get(var Q:TQueue): TPoint;
var i: integer;
уменьшить
begin
размер
Get:= Q.data[0];
Q.size:= Q.size - 1;
продвинуть
for i:=0 to Q.Size - 1 do
оставшиеся
Q.data[i]:= Q.data[i+1];
элементы
end;
1
2
3
4
5
0
1
2
3
4
К.Ю. Поляков, Е.А. Ерёмин, 2018
?
Что плохо?
http://kpolyakov.spb.ru

87. Заливка

Алгоритмизация и программирование. Язык Паскаль, 11 класс
87
Заливка
Константы и переменные:
const XMAX = 5; YMAX = 5;
NEW_COLOR = 2;
var Q: TQueue;
x0, y0, color: integer;
A: array[1..YMAX,1..XMAX] of integer;
pt: TPoint;
Начало программы:
{ заполнить матрицу A }
x0:= 2; y0:= 1;
{ начать заливку отсюда }
color:= A[y0,x0]; { цвет начальной точки }
Put(Q, Point(x0,y0));
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
88
Заливка (основной цикл)
пока очередь не пуста
while not isEmpty(Q) do begin
pt:= Get(Q); { взять точку из очереди }
if A[pt.y, pt.x] = color then begin
A[pt.y, pt.x]:= NEW_COLOR;
if pt.x > 1 then
Put(Q, Point(pt.x-1, pt.y));
if pt.x < XMAX then
Put(Q, Point(pt.x+1, pt.y));
if pt.y > 1 then
Put(Q, Point(pt.x, pt.y-1));
if pt.y < YMAX then
Put(Q, Point(pt.x, pt.y+1))
end
Что можно улучшить?
end;
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
90
Очередь: статический массив
Замыкание в кольцо:
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
!
Вариант: хранить размер очереди в переменной!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

92. Алгоритмизация и программирование. Язык Паскаль

92
Алгоритмизация и
программирование.
Язык Паскаль
§ 39. Деревья
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
93
Что такое дерево?
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

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

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

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
97
Обход дерева
(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

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

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

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
101
Обход «в ширину»
(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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
102
Вычисление арифметических выражений
?
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

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
105
Использование связанных структур
Дерево – нелинейная структура динамический
массив неудобен!
данные
данные nil nil
данные nil nil
ссылка вперёд
type
PNode =
TNode =
data:
left,
end;
^TNode; { указатель на узел }
record { узел дерева }
string[20];
right: PNode { ссылки на сыновей }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
106
Работа с памятью
var p: PNode;
{ указатель на узел }
Выделить память для узла:
New(p);
Обращение к новому узлу (по указателю):
p^.data:= s;
p^.left:= nil;
p^.right:= nil;
Освобождение памяти:
Dispose(p);
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
107
Основная программа
var T: PNode; { ссылка на дерево }
s: string; { строка с выражением }
{ процедуры и функции }
begin
readln(s);
T:= Tree(s); { построить дерево }
writeln('Результат: ',
Calc(T)); { вычисление }
end.
!
Нужно построить Tree и Calc!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
108
Построение дерева
function Tree(s: string): PNode;
вернёт адрес
var k: integer;
нового дерева
begin
New(Tree);
{ выделить память }
k:= LastOp(s); { вернет 0, если нет операции }
if k = 0 then begin { создать лист }
Tree^.data:= s;
Tree^.left:= nil;
Tree^.right:= nil
end
else begin
{ создать узел-операцию }
Tree^.data:= s[k];
Tree^.left:= Tree(Copy(s,1,k-1));
Tree^.right:= Tree(Copy(s,k+1,Length(s)-k))
end
Рекурсия!
end;
!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
109
Вычисление по дереву
function Calc(Tree: PNode): integer;
var n1, n2, res: integer;
begin
одно число
if Tree^.left = nil then
Val(Tree^.data, Calc, res)
else begin
n1:= Calc(Tree^.left);
Рекурсия!
n2:= Calc(Tree^.right);
case Tree^.data[1] of
'+': Calc:= n1 + n2;
'-': Calc:= n1 - n2;
'*': Calc:= n1 * n2;
'/': Calc:= n1 div n2;
else Calc:= MaxInt
end
end
end;
!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
110
Приоритет операции
function Priority(op: char): integer;
begin
case op of
'+','-': Priority:= 1;
'*','/': Priority:= 2
else
Priority:= 100
end
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
111
Последняя выполняемая операция
function LastOp(s: string): integer;
var i, minPrt: integer;
вернёт номер
символа
begin
minPrt:= 50; { любое между 2 и 100 }
LastOp:= 0; { если нет операции }
for i:=1 to Length(s) do
if Priority(s[i]) <= minPrt then begin
minPrt:= Priority(s[i]);
LastOp:= i
end
Почему <=?
end;
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

113. Алгоритмизация и программирование. Язык Паскаль

113
Алгоритмизация и
программирование.
Язык Паскаль
§ 40. Графы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
114
Что такое граф?
Граф – это набор вершин и связей между ними (рёбер).
Матрица смежности:
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

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
117
Взвешенные графы
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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
118
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра
называю дугами.
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

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

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

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

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

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

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

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

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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
123
Раскраска вершин
Данные:
const N = 6;
INF = MaxInt; { большое число }
var
{ весовая матрица }
W: array[1..N,1..N] of integer;
{ цвета вершин }
col: array[1..N] of integer;
{ номера вершин для выбранных ребер }
ostov: array[1..N-1,1..2] of integer;
i, j, k, iMin, jMin, min, c: integer;
Вывод результата:
for i:=1 to N-1 do
writeln('(', ostov[i,1], ',',
ostov[i,2], ')');
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
124
Раскраска вершин
for k:= 1 to N-1 do begin
{ поиск ребра с минимальным весом }
min:= INF;
for i:= 1 to N do
for j:= 1 to N do
if (col[i] <> col[j]) and
(W[i,j] < min) then begin
iMin:= i; jMin:= j; min:= W[i,j]
end;
ostov[k,1]:= iMin; { добавление ребра }
ostov[k,2]:= jMin;
c:= col[jMin];
for i:= 1 to N do { перекрашивание вершин }
if col[i] = c then
col[i]:= col[iMin]
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
125
Кратчайший маршрут
Алгоритм Дейкстры (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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
126
Кратчайший маршрут
Алгоритм Дейкстры (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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
127
Кратчайший маршрут
Алгоритм Дейкстры (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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
128
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
4
C
A
0
+
dist
selected
!
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

129. Как найти сам кратчайший маршрут?

Алгоритмизация и программирование. Язык Паскаль, 11 класс
129
Как найти сам кратчайший маршрут?
B
2
4
C
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

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
130
Алгоритм Дейкстры
Данные:
const N = 6;
INF = 30000;
var W: array[1..N,1..N] of integer;
selected: array[1..N] of boolean;
dist: array[1..N] of integer;
i, start, minDist, V: integer;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
131
Алгоритм Дейкстры
Начальные значения (выбор начальной вершины):
start:= 1;
{ это начало маршрута }
for i:=1 to N do begin
selected[i]:= False; { все не выбраны }
dist[i]:= W[start,i]; { прямые маршруты}
end;
selected[start]:= True; { A выбрана }
dist[start]:= 0;
{ от A до A - 0 }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
132
Алгоритм Дейкстры
Основной цикл:
?
Какова сложность?
minDist := 0;
V := start;
O(N2)
while minDist < INF do begin
selected[V] := True;
for i:=1 to N do { обновляем длины путей }
if dist[V]+W[V][i] < dist[i] then
dist[i] := dist[V]+W[V][i];
minDist := INF;
for i:=1 to N do { ищём следующую вершину }
if (not selected[i]) and
(dist[i] < minDist) then begin
minDist := dist[i];
V := i;
end;
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
133
Алгоритм Дейкстры
Вывод результата (маршрут 0 N-1):
V := N;
пока не пришли в
начальную вершину
write( V:2 );
обратным ходом
while V <> start do begin
for i:=1 to N do
if (i <> V) and
(dist[i] + W[i][V] = dist[V])
then begin
V := i;
нашли вершину i, из
break
которой могли прийти в
end;
вершину V
write(' <-', i:2)
end;
Она единственная?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование. Язык Паскаль, 11 класс
134
Алгоритм Флойда
Все кратчайшие пути (из любой вершины в любую)
Идея:
K
W[i][k]
I
W[k][j]
W[i][j]
?
Какова сложность?
O(N3)
J
проверить все
для всех
вершины
пар вершин
for k:=1 to N do
без
for i:=1 to N do
вершины k
for j:=1 to N do
if W[i][k] + W[k][j] < W[i][j] then
W[i][j]:= W[i][k] + W[k][j];
путь через
вершину k
К.Ю. Поляков, Е.А. Ерёмин, 2018
?
Как найти сам маршрут?
http://kpolyakov.spb.ru

135. Задача коммивояжера

Алгоритмизация и программирование. Язык Паскаль, 11 класс
135
Задача коммивояжера
Коммивояжер (бродячий торговец) должен выйти из города 1
и, посетив по разу в неизвестном порядке города 2,3,...N,
вернуться обратно в город 1. В каком порядке надо обходить
города, чтобы путь коммивояжера был кратчайшим?
!
Это NP-полная задача, которая строго решается
только перебором вариантов (пока)!
Точные методы:
большое время счета для
1) простой перебор;
больших N
2) метод ветвей и границ;
O(N!)
3) метод Литтла;
4) …
Приближенные методы:
1) метод случайных перестановок (Matlab)
не гарантируется
2) генетические алгоритмы
оптимальное
3) метод муравьиных колоний
решение
4) …
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

136. Некоторые задачи

Алгоритмизация и программирование. Язык Паскаль, 11 класс
136
Некоторые задачи
Задача на минимум суммы. Имеется N домой, в каждом из
которых живет pi жителей (i=1,...,N). Надо разместить
магазин в одном из них так, чтобы общее расстояние,
проходимое всеми жителями по дороге в магазин, было
минимальным.
Задача о наибольшем потоке. Есть система труб, которые
имеют соединения в N узлах. Один узел S является
источником, еще один – стоком T. Известны пропускные
способности каждой трубы. Надо найти наибольший поток
от источника к стоку.
Задача о наибольшем паросочетании. Есть M мужчин и N
женщин. Каждый мужчина указывает несколько (от 0 до N)
женщин, на которых он согласен жениться. Каждая
женщина указывает несколько мужчин (от 0 до M), за
которых она согласна выйти замуж. Требуется заключить
наибольшее количество моногамных браков.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

137. Алгоритмизация и программирование. Язык Паскаль

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

138. Что такое динамическое программирование?

Алгоритмизация и программирование. Язык Паскаль, 11 класс
138
Что такое динамическое программирование?
;
Числа Фибоначчи:
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
.
F5
F4
function Fib(N: integer):
F3
integer;
begin
F2
F1
if N < 3 then
Fib:= 1
else Fib:= Fib(N-1) + Fib(N-2)
end;
F3
F2
F2
F1
повторное вычисление тех же значений
!
Запоминать то, что вычислено!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

139. Динамическое программирование

Алгоритмизация и программирование. Язык Паскаль, 11 класс
139
Динамическое программирование
F1
1
F2
1
F3
2
F4
3
F5
5
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
Объявление массива:
const N = 10;
var F: array[1..N] of integer;
Заполнение массива:
F[1]:= 1; F[2]:= 1;
for i:= 3 to N do
F[i]:= F[i-1] + F[i-2];
F45: рекурсия: 8 с
дин. программирование: < 0,01 с
?
Можно ли обойтись без массива?
К.Ю. Поляков, Е.А. Ерёмин, 2018
нужны только
два последних!
http://kpolyakov.spb.ru

140. Динамическое программирование

Алгоритмизация и программирование. Язык Паскаль, 11 класс
140
Динамическое программирование
Динамическое программирование – это способ
решения сложных задач путем сведения их к более
простым задачам того же типа.
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

141. Количество вариантов

Алгоритмизация и программирование. Язык Паскаль, 11 класс
141
Количество вариантов
Задача. Найти количество KN цепочек, состоящих из N
нулей и единиц, в которых нет двух стоящих подряд
единиц.
Решение «в лоб»:
битовые цепочки
1
2
3
N-1
N
0/1
• построить все возможные цепочки
• проверить каждую на «правильность»
?
Сколько возможных цепочек?
2N
Сложность
алгоритма O(2N)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

142. Количество вариантов

Алгоритмизация и программирование. Язык Паскаль, 11 класс
142
Количество вариантов
Задача. Найти количество 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

143. Оптимальное решение

Алгоритмизация и программирование. Язык Паскаль, 11 класс
143
Оптимальное решение
Задача. В цистерне 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

144. Оптимальное решение

Алгоритмизация и программирование. Язык Паскаль, 11 класс
144
Оптимальное решение
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

145. Оптимальное решение (бидоны)

Алгоритмизация и программирование. Язык Паскаль, 11 класс
145
Оптимальное решение (бидоны)
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 бидона
3
3
1
4
4
1
5 + 5
!
2
2
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
5
1
5
6
1
6
7
2
1
Похоже на алгоритм Дейкстры!
http://kpolyakov.spb.ru

146. Задача о куче

Алгоритмизация и программирование. Язык Паскаль, 11 класс
146
Задача о куче
Задача. Из камней весом 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

147. Задача о куче

Алгоритмизация и программирование. Язык Паскаль, 11 класс
147
Задача о куче
Задача. Из камней весом 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

148. Задача о куче

Алгоритмизация и программирование. Язык Паскаль, 11 класс
148
Задача о куче
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

149. Задача о куче

Алгоритмизация и программирование. Язык Паскаль, 11 класс
149
Задача о куче
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

150. Задача о куче

Алгоритмизация и программирование. Язык Паскаль, 11 класс
150
Задача о куче
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

151. Задача о куче

Алгоритмизация и программирование. Язык Паскаль, 11 класс
151
Задача о куче
Добавляем камень с весом 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

152. Задача о куче

Алгоритмизация и программирование. Язык Паскаль, 11 класс
152
Задача о куче
?
Какие камни нужно взять?
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

153. Задача о куче

Алгоритмизация и программирование. Язык Паскаль, 11 класс
153
Задача о куче
?
Какова сложность алгоритма?
Заполнение таблицы:
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

154. Количество программ

Алгоритмизация и программирование. Язык Паскаль, 11 класс
154
Количество программ
Задача. У исполнителя Утроитель есть команды:
1. прибавь 1
2. умножь на 3
Сколько есть разных программ, с помощью которых
можно из числа 1 получить число 20?
?
Как решать, не выписывая все программы?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

155. Количество программ

Алгоритмизация и программирование. Язык Паскаль, 11 класс
155
Количество программ
Как получить число 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

156. Количество программ

Алгоритмизация и программирование. Язык Паскаль, 11 класс
156
Количество программ
Рекуррентная формула:
если 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

157. Количество программ

Алгоритмизация и программирование. Язык Паскаль, 11 класс
157
Количество программ
20
Только точки изменения:
N
KN
1
1
3
2
6
3
9
5
12
7
15
9
18
12
21
15
Программа:
K[1]:= 1;
for i:= 2 to N do begin
K[i]:= K[i-1];
if i mod 3 = 0 then
K[i]:= K[i] + K[i div 3]
end;
?
Где ответ?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

158. Размен монет

Алгоритмизация и программирование. Язык Паскаль, 11 класс
158
Размен монет
Задача. Сколькими различными способами можно
выдать сдачу размером W рублей, если есть монеты
достоинством pi (i=1, …, N)? В наборе есть монета
достоинством 1 рубль (p1 = 1).
Перебор?
при больших N и W – очень долго!
Динамическое программирование:
запоминаем решения всех задач меньшей
размерности: для меньших значений W и меньшего
числа монет N.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

159. Размен монет

Алгоритмизация и программирование. Язык Паскаль, 11 класс
159
Размен монет
Пример: 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-pii]
все варианты размена остатка
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

160. Размен монет

Алгоритмизация и программирование. Язык Паскаль, 11 класс
160
Размен монет
Пример: 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

161. Конец фильма

Алгоритмизация и программирование. Язык Паскаль, 11 класс
161
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

162. Источники иллюстраций

Алгоритмизация и программирование. Язык Паскаль, 11 класс
162
Источники иллюстраций
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
wallpaperscraft.com
www.mujerhoy.com
www.pinterest.com
www.wayfair.com
www.zchocolat.com
www.russiantable.com
www.kursachworks.ru
ebay.com
centrgk.ru
www.riverstonellc.com
53news.ru
10hobby.ru
ru.wikipedia.org
иллюстрации художников издательства «Бином»
авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru