Алгоритмизация и программирование
Алгоритмизация и программирование
Решето Эратосфена
Решето Эратосфена
Решето Эратосфена
Решето Эратосфена
«Длинные» числа
«Длинные» числа
«Длинные» числа
Вычисление факториала
Вычисление факториала
Вычисление факториала
Вывод длинного числа
Вывод длинного числа
Вывод длинного числа
Вывод длинного числа
Алгоритмизация и программирование
Зачем нужны структуры?
Структуры (записи)
Объявление структур
Обращение к полям структур
Обращение к полям структур
Запись структур в файлы
Чтение структур из файла
Сортировка структур
Указатели
Сортировка по указателям
Сортировка по указателям
Алгоритмизация и программирование
Зачем нужны множества?
Использование множеств
Использование множеств
Использование множеств
Вывод множества на экран
Сравнение множеств
Множества в памяти
Множества в памяти
Алгоритмизация и программирование
Чем плох обычный массив?
Динамические структуры данных
Динамические массивы (FreePascal)
Динамические массивы (FreePascal)
Динамические массивы (FreePascal)
Расширение массива
Расширение массива
Как это работает?
Как это работает?
Алгоритмизация и программирование
Зачем нужны списки?
Алгоритм (псевдокод)
Хранение данных
Хранение данных
Основной цикл
Поиск слова
Поиск места вставки
Вставка слова
Вставка слова
Расширение списка
Вся программа
Модули
Структура модуля
Модуль WordList
Подключение модуля
Связные списки
Связные списки
Связные списки: структуры данных
Алгоритмизация и программирование
Что такое стек?
Реверс массива
Использование динамического массива
Использование динамического массива
Использование динамического массива
Вычисление арифметических выражений
Вычисление арифметических выражений
Использование стека
Скобочные выражения
Скобочные выражения (стек)
Скобочные выражения (стек)
Скобочные выражения (стек)
Скобочные выражения (стек)
Что такое очередь?
Заливка области
Заливка: использование очереди
Очередь (динамический массив)
Очередь (динамический массив)
Очередь (динамический массив)
Заливка
Заливка (основной цикл)
Очередь: статический массив
Очередь: статический массив
Что такое дек?
Алгоритмизация и программирование
Что такое дерево?
Рекурсивные определения
Деревья поиска
Обход дерева
Обход дерева
Обход КЛП – обход «в глубину»
Обход КЛП – обход «в глубину»
Обход «в ширину»
Обход «в ширину»
Вычисление арифметических выражений
Вычисление арифметических выражений
Вычисление арифметических выражений
Использование связанных структур
Работа с памятью
Основная программа
Построение дерева
Вычисление по дереву
Приоритет операции
Последняя выполняемая операция
Двоичное дерево в массиве
Алгоритмизация и программирование
Что такое граф?
Связность графа
Дерево – это граф?
Взвешенные графы
Ориентированные графы (орграфы)
Жадные алгоритмы
Жадные алгоритмы
Задача Прима-Крускала
Раскраска вершин
Раскраска вершин
Раскраска вершин
Кратчайший маршрут
Кратчайший маршрут
Кратчайший маршрут
Кратчайший маршрут
Кратчайший маршрут
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Флойда
Алгоритм Флойда + маршруты
Задача коммивояжера
Некоторые задачи
Алгоритмизация и программирование
Что такое динамическое программирование?
Динамическое программирование
Динамическое программирование
Количество вариантов
Количество вариантов
Оптимальное решение
Оптимальное решение
Оптимальное решение (бидоны)
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Задача о куче
Количество программ
Количество программ
Количество программ
Количество программ
Размен монет
Размен монет
Размен монет
Конец фильма
Источники иллюстраций
8.70M
Categories: programmingprogramming informaticsinformatics

Алгоритмизация и программирование. Целочисленные алгоритмы. 11 класс

1. Алгоритмизация и программирование

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

2. Алгоритмизация и программирование

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

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

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

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

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

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

5
Алгоритмизация и программирование, 11 класс
Решето Эратосфена
Вычёркивание непростых:
k:= 2
нц пока k*k <= N
если A[k] то
i:= k*k
нц пока i <= N
A[i]:= нет
i:= i + k
кц
все
k:= k + 1
кц
К.Ю. Поляков, Е.А. Ерёмин, 2013
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;
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

10
Алгоритмизация и программирование, 11 класс
Вычисление факториала
Задача 1. Вычислить точно значение факториала
100! = 1·2·3·…·99·100
?
Как оценить количество цифр?
201 цифра
1·2·3·…·99·100 < 100100
основание
6 цифр в ячейке 34 ячейки
1000000
цел N = 33
const N = 33;
целтаб A[0:N]
var A: array[0..N]
of longint;
Основной алгоритм:
длинное
число
[A]:= 1
нц для k от 2 до 100
[A]:= [A] * k
кц
К.Ю. Поляков, Е.А. Ерёмин, 2013
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
r := перенос в
A[1]
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]?
К.Ю. Поляков, Е.А. Ерёмин, 2013
*3
остаётся в
A[0]
s:= A[1]*k +
r
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

Алгоритмизация и программирование, 11 класс
15
Вывод длинного числа
Вывод числа с лидирующими нулями:
алг Write6 (цел x)
нач
цел M, xx
xx:= x
M:= 100000
нц пока M > 0
вывод div(xx, M)
xx:= mod(xx, M)
M:= div(M, 10)
кц
кон
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, 11 класс
16
Вывод длинного числа
Вывод числа с лидирующими нулями:
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

17. Алгоритмизация и программирование

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

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

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

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

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

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

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

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

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

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

22
Алгоритмизация и программирование, 11 класс
Обращение к полям структур
Присваивание:
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('Этих книг больше нет!');
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

23
Алгоритмизация и программирование, 11 класс
Запись структур в файлы
Текстовые файлы:
символ-разделитель
'Пушкин А.С.';'Полтава';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!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

24
Алгоритмизация и программирование, 11 класс
Чтение структур из файла
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

25
Алгоритмизация и программирование, 11 класс
Сортировка структур
Ключ – фамилия автора:
?
Какой метод?
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:=
B:= Books[j];
Books[j];
Books[j]:=
Books[j]:= Books[j+1];
Books[j+1];
Books[j+1]:=
Books[j+1]:= BB
end;
структуры перемещаются в памяти
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

26. Указатели

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

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

27
Алгоритмизация и программирование, 11 класс
Сортировка по указателям
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

Нагибин Ю. … … Астафьев В. … … Васильев Б. … … …
!
Сами структуры не перемещаются!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

28
Алгоритмизация и программирование, 11 класс
Сортировка по указателям
обращение к
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);
К.Ю. Поляков, Е.А. Ерёмин, 2013
';
';
',
',
http://kpolyakov.spb.ru

29. Алгоритмизация и программирование

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

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

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

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

31
Алгоритмизация и программирование, 11 класс
Использование множеств
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';
множество
цифр
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

32
Алгоритмизация и программирование, 11 класс
Использование множеств
Задача. Вывести все различные цифры, присутствующие
в символьной строке 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.
вывод через перебор
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

34
Алгоритмизация и программирование, 11 класс
Вывод множества на экран
первый
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
fsUnderlin
e
fsItalic
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

35
Алгоритмизация и программирование, 11 класс
Сравнение множеств
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
if
A <> B
C <> B
then
then
write('A <> B');
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'); { нет }
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

38. Алгоритмизация и программирование

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

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

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

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

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

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

41
Алгоритмизация и программирование, 11 класс
Динамические массивы (FreePascal)
Объявление:
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]);
наибольши
й индекс
К.Ю. Поляков, Е.А. Ерёмин, 2013
!
Массив знает свой размер!
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

45
Алгоритмизация и программирование, 11 класс
Расширение массива
Расширение по 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;
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

46
Алгоритмизация и программирование, 11 класс
Как это работает?
Эксперимент:
SetLength(A, 100);
write(sizeof(A)); 4
write(100*sizeof(integer));
!
200
A – это указатель!
0
1
2
3

100
A
размер массива
type TArray
data:
size:
end;
= record
array of integer;
integer
Как записать в файл?
К.Ю. Поляков, Е.А. Ерёмин, 2013
?
http://kpolyakov.spb.ru

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

47
Алгоритмизация и программирование, 11 класс
Как это работает?
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 }
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

48. Алгоритмизация и программирование

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

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

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

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

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

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

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

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

52
Алгоритмизация и программирование, 11 класс
Хранение данных
Переменная-список:
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?
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

53
Алгоритмизация и программирование, 11 класс
Основной цикл
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?
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

54
Алгоритмизация и программирование, 11 класс
Поиск слова
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

55
Алгоритмизация и программирование, 11 класс
Поиск места вставки
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

57
Алгоритмизация и программирование, 11 класс
Вставка слова
список
меняется
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

58
Алгоритмизация и программирование, 11 класс
Расширение списка
список
меняется
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
элементов
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

59
Алгоритмизация и программирование, 11 класс
Вся программа
program AlphaList;
{ объявления типов
типов TPair и TWordList
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.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

60. Модули

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

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

61
Алгоритмизация и программирование, 11 класс
Структура модуля
unit WordList;
«интерфейс» –
общедоступная
interface
информация:
•объявление типов данных

•объявления процедур и
implementation
функций

end.
«реализация» – внутренняя
информация модуля:
•код процедур и функций
•внутренние данные
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

62. Модуль WordList

62
Алгоритмизация и программирование, 11 класс
Модуль 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.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

67. Алгоритмизация и программирование

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

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

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

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

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

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

70
Алгоритмизация и программирование, 11 класс
Использование динамического массива
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

71
Алгоритмизация и программирование, 11 класс
Использование динамического массива
«Вытолкнуть» из стека в 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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

72
Алгоритмизация и программирование, 11 класс
Использование динамического массива
Заполнение стека:
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

80
Алгоритмизация и программирование, 11 класс
Скобочные выражения (стек)
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

84
Алгоритмизация и программирование, 11 класс
Очередь (динамический массив)
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;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

85
Алгоритмизация и программирование, 11 класс
Очередь (динамический массив)
Добавить точку в очередь:
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
К.Ю. Поляков, Е.А. Ерёмин, 2013
5
4
http://kpolyakov.spb.ru

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

86
Алгоритмизация и программирование, 11 класс
Очередь (динамический массив)
Получить первую точку в очереди:
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
К.Ю. Поляков, Е.А. Ерёмин, 2013
?
Что плохо?
http://kpolyakov.spb.ru

87. Заливка

87
Алгоритмизация и программирование, 11 класс
Заливка
Константы и переменные:
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));
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

88
Алгоритмизация и программирование, 11 класс
Заливка (основной цикл)
пока очередь не пуста
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;
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

92. Алгоритмизация и программирование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9
5
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

111
Алгоритмизация и программирование, 11 класс
Последняя выполняемая операция
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;
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

113. Алгоритмизация и программирование

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

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

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

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

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

116
Алгоритмизация и программирование, 11 клас
English     Русский Rules