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

версия – решето Аткина .
2 3 4 5

Алгоритм:
начать с k = 2
«выколоть» все числа через k, начиная с 2·k
перейти к следующему «невыколотому» k
если k <= N , то перейти к шагу 2
напечатать все числа, оставшиеся «невыколотыми»

высокая скорость, количество операций

нужно хранить в памяти все числа от 1 до N

O((N·log N)·log log N )

2

3

k·k

k·k <= N

до N.
Объявление переменных:
цел i, k, N = 100
логтаб A[2:N]

Сначала все невычеркнуты:

нц для i от 2 до N
A[i]:= да
кц

const N = 100;
var i, k: integer;
A: array[2..N]
of boolean;

for i:= 2 to N do
A[i]:= True;

если A[k] то
i:= k*k
нц пока

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;

N
если A[i] то
вывод i, нс
все
кц
for

данных: ≤ 64 битов.
Длинное число – это число, которое

«Длинная арифметика» – алгоритмы для работы с длинными числами.

(с младшего разряда!)
неэкономное расходование памяти
Обратный порядок элементов:

678·10000
система счисления с основанием 1000!
от –231 = – 2

longint:

должны помещаться все промежуточные результаты!

A = 12345678

= 1·2·3·…·99·100
1·2·3·…·99·100 < 100100
201 цифра
6 цифр в ячейке

цел N = 33
целтаб A[0:N]

const N = 33;
var A: array[0..N]
of longint;

Основной алгоритм:

[A]:= 1
нц для k от 2 до 100
[A]:= [A] * k
кц

длинное число

основание 1000000

2 203 701
*3
остаётся в A[0]
r := перенос в A[1]
s:=

s:= A[0]*k;
A[0]:= s mod d;
r:= s div d;

s:= A[1]*k + r

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;

Умножение «длинного» числа на k:

Вычисление 100!:

нц для k от 2 до 100
...
кц

for k:=2 to 100 do
begin
...
end;

этот разряд

вывести все следующие разряды, добавляя лидирующие нули до

i:= N
нц пока A[i] = 0
i:= i - 1
кц

i:= N;
while A[i] = 0 do
i:= i - 1;

вывод A[i]

write( A[i] );

0 шаг -1
Write6(A[k])
кц
for k:=i-1 downto 0 do

Вывод остальных разрядов:

со старшего

Write6:

x = 12345

012345

x div 100000

x mod 100000

(цел x)
нач
цел M, xx
xx:= x
M:= 100000

longint);
var M: longint;
begin
M:= 100000;

объединить разнотипные данные в один блок.
Несколько массивов:
var authors: array[1..N]

неудобно работать (сортировать и т.д.), ошибки

включать в себя несколько полей – элементов разных типов

type
TBook = record
author: string[40];{ автор, строка }
title: string[80]; { название, строка}
count: integer { количество, целое }
end;

новый тип данных

структура (запись)

одна структура }
Books: array[1..N] of TBook; {

writeln(sizeof(TBook)); { 124 }
writeln(sizeof(B)); { 124 }
writeln(sizeof(Books)); { 12400 }

type
TBook = record
author: string[40];
title: string[80];
count: integer
end;

2 байта (FreePascal)

40 + 1 (размер) байт

80 + 1 (размер) байт

B }
Точечная нотация:
Books[5].count { поле count структуры

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, ' шт.' );

Pos(' ', B.author);
fam:= Copy(B.author, 1, p-1); { фамилия }
B.count:=

Присваивание:

Использование:

F: file of TBook;
Assign(F, 'books.dat');
Rewrite(F);
B.author:= 'Тургенев И.С.';
B.title:=

for i:=1 to N do
write(F, Books[i]);

только для TBook!

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;

счётчик прочитанных структур

do
for j:=N-1 downto i do
if Books[j].author

структуры перемещаются в памяти

B:= Books[j];
Books[j]:= Books[j+1];
Books[j+1]:= B

var B: TBook;

адрес любой переменной заданного типа.
type PBook = ^TBook;
pointer
указатель на

var P: PBook;

P:=@B;

P:=@Books[3];

P^.author ⇔ Books[3].author

to N do
p[i]:= @Books[i];

Задача – переставить указатели:

for j:= N-1 downto i do
if p[j]^.author

var p1: PBook;

обращение к полям через указатели

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

for i:=1 to N do
writeln(p[i]^.author, '; ',
p[i]^.title, '; ',
p[i]^.count);

переставляем указатели!

символьной строке.
count:= 0;
for i:=1 to Length(s) do

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

if s[i] in ['.', ',', ';', ':', '!', '?'] then
count:= count + 1;

входит во

множество

['.', ',', ';', ':', '!', '?']

(s[i]='.') or (s[i]=',')
or (s[i]=';') or (s[i]=':')
or (s[i]='!') or (s[i]='?')

count:= count + 1;
диапазон
if s[i] in ['a'..'z', '0'..'9',

var digits: set of '0'..'9';

Переменная типа «множество»:

множество цифр

символьной строке s.
var s: string;
i: integer;

digits:= digits + [s[i]];

сложить два множества

вывод через перебор

set of byte;
до 255 элементов
Имена для элементов множества:
type TFontStyles

стили шрифта

жирный

курсив

подчёркивание

var fs: set of TFontStyles;

Операции с множеством:

fs:= [fsBold, fsItalic]; { присвоить значение}
fs:= fs + [fsUnderline]; { добавить элементы }
fs:= fs - [fsItalic]; { исключить элементы }

fs:= [fsBold, fsItalic];
for style:=fsBold to fsUnderline do
if style in fs then
write(1)
else write(0);

первый

последний

110

fsBold

fsItalic

fsUnderline

B'); { нет }
if B = C then write('B

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 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'); { нет }

[];
Непустое множество:
digits:= [1, 3, 5, 7];
Пересечение множеств:
digits:= [1, 3,

AND

логическое умножение

[3]

множеств:
digits:= [1, 3, 5, 7] +

OR

логическое сложение

Вычитание множеств:

digits:= [1, 3, 5, 7] -
[2, 3, 4];

[1, 5, 7]

array[1..N] of integer;
статический массив
память выделяется при трансляции
нужно заранее знать

Задача. В файле записаны фамилии (сколько – неизвестно!). Вывести их в другой файл в алфавитном порядке.

выделить заранее большой блок (с запасом)
выделять память во время работы программы (динамически!)

размер
удалять из памяти, когда не нужны
… позволяют
Задача. Ввести с

{ прочитать данные из файла в массив }
{ отсортировать их по возрастанию }
{ вывести массив на экран }

указан
Выделение памяти:
read(N);
SetLength(A, N);
установить длину
[0.. N-1]
Чтение данных:
for i:=0 to N-1

for i:=0 to High(A) do read(A[i]);

наибольший индекс

матрицы:
var A: array of array of integer;
SetLength(A, 4, 3);
writeln(

3

writeln( High(A[0]) );

2

for i:= 0 to High(X) do
write(X[i],

заканчивается числом 0. Нужно вывести на экран эти числа

Расширение по 1 элементу:

read(x);
while x <> 0 do begin
SetLength(A, Length(A)+1);
A[High(A)]:= x;
read(x)
end;

элементов }
read(x);
while x 0 do begin
if N

data: array of integer;
size:

integer;
SetLength(A, 10);
выделить массив указателей
for i:=0 to High(A) do
SetLength(A[i],

Строки разной длины:

writeln(Length(A[0])); { 1 }
writeln(Length(A[9])); { 10 }

среди которых есть повторяющиеся. Каждое слово записано в отдельной

Список – это упорядоченный набор элементов одного типа, для которого введены операции вставки (включения) и удаления (исключения).

очередное слово
если оно есть в списке то

string; { слово }
count: integer

Пара «слово-счётчик»:

type
TWordList = record
data: array of TPair;
size: integer
end;

Список таких пар:

динамический массив

количество слов в списке

'output.dat');
Rewrite(F);
for p:=0 to L.size-1 do
writeln(F, L.data[p].word, ': ',

автомат: 1
ананас: 12
...

конец файла }
do begin
readln(F, s);

word: string): integer;
var i: integer;
begin
Find:=

вернуть -1, если нет в списке

вернуть номер элемента в списке

выйти из цикла

word: string):

-1: не найдено

запомнить номер

если не найдено, вставить в конец

первое слово «больше» заданного

вниз:
с последнего

k: integer;

список меняется

увеличить размер, если нужно

сдвиг вниз

L.size > Length(L.data) then

список меняется

если новый размер больше размера массива

добавить 10 элементов

TWordList }
var F: text;
w: string;
L:

процедура 2 }
{ процедура 3 }
{ процедура

program AlphaList;
uses WordList;
begin
{ программа }
end.

unit WordList;
{ процедура 1 }
{ процедура 2 }
{ процедура 3 }
{ процедура 4 }
{ ...}
{ процедура N-1 }
{ процедура N }
end.

проще разбираться («разделяй и властвуй»)
модуль пишет другой программист

типов данных
объявления процедур и функций
«реализация» – внутренняя информация модуля:
код

TWordList }
function Find(L: TWordList;

implementation
{ код процедур и функций }
end.

F: text;
s: string;
L: TWordList;

тип известен из интерфейса модуля

можно использовать все процедуры, объявленные в интерфейсе модуля

памяти
только последовательный доступ
Рекурсивное определение:
пустой список – это список
список –

конец списка

и удаление

= ^TNode;
TNode = record
data: integer;

type
PNode = ^TNode;
TNode = record
data: integer;
next: PNode
end;

prev,

ссылка на следующий узел

указатель

ссылки на предыдущий (previous) и следующий узлы

это линейный список, в котором элементы добавляются и удаляются

LIFO = Last In – First Out.

Системный стек:

адреса возврата из подпрограмм
передача аргументов подпрограмм
хранение локальных переменных

вывести их в другой файл в обратном порядке.
нц пока

нц пока стек не пуст
вытолкнуть число из стека в x
записать x в файл
кц

1

2

3

4

5

5

4

3

2

1

data: array of integer;
size:

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;

изменяется

«Втолкнуть» x в стек:

Pop:= S.data[S.size]
end;
изменяется
procedure InitStack(var S: TStack);
begin
SetLength(S.data, 0);
S.size:= 0
end;
«Вытолкнуть»

Инициализация стека :

x);
Push(S, x)
end;
Заполнение стека:
for i:=0 to S.size-1 do begin

Вывод результата в файл:

var F: text;

данными)
первой стоит последняя операция (вычисляем с конца)
1920 (Я. Лукашевич):

/ + 5 15 - + 4 7 1

/ 20 - + 4 7 1

/ 20 - 11 1

/ 20 10

2

не нужны скобки

после данных)

не нужны скобки
вычисляем с начала
5 15 + 4

20 4 7 + 1 - /

20 11 1 - /

20 10 /

2

- /
если число – «втолкнуть» в стек
если операция –

некоторое (арифметическое) выражение, использующее скобки трёх типов: ( ),

()[{()[]}]

[()

)(

[()}

([)]

Для одного типа скобок:

( ) ( ( ) ( ( ) ) )

счётчик 0

1

0

1

2

1

2

3

2

1

0

счётчик всегда ≥ 0
в конце счётчик = 0

({[)}]

стека лежит соответствующая открывающая
в конце работы стек пуст
если открывающая

data: array of char;
size:

Модель стека:

Cтек пуст:

function isEmpty(S: TStack): boolean;
begin
isEmpty:= (S.size = 0)
end;

скобки }
R = ')]}'; { закрывающие

Константы и переменные:

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

if not err then
writeln('Выражение правильное.')
else writeln('Выражение неправильное.');

p:= Pos(str[i], L);
if p > 0 then Push(S,

открывающую скобку в стек

если закрывающая скобка…

если не та скобка…

которого введены две операции:
• добавление элемента в конец
• удаление первого элемента
FIFO

Применение:

очереди сообщений в операционных системах
очереди запросов ввода и вывода
очереди пакетов данных в маршрутизаторах
…

в которой элемент A[y,x] определяет цвет пикселя на пересечении

(2,1)

начальной точки
нц пока очередь не пуста
взять из очереди

x, y: integer
end;

function Point(x, y: integer): TPoint;
begin
Point.x:= x;
Point.y:= y
end;

Построение структуры «точка»:

TQueue; pt: TPoint);
begin
if Q.size > High(Q.data) then

расширить, если нужно

4

5

Q:TQueue): TPoint;
var i: integer;
begin
Get:= Q.data[0];
Q.size:= Q.size -

уменьшить размер

продвинуть оставшиеся элементы

2

4

3

4

5

1

NEW_COLOR = 2;
var Q: TQueue;
x0, y0,

{ заполнить матрицу A }
x0:= 2; y0:= 1; { начать заливку отсюда }
color:= A[y0,x0]; { цвет начальной точки }
Put(Q, Point(x0,y0));

Константы и переменные:

Начало программы:

Get(Q); { взять точку из очереди }
if A[pt.y,

пока очередь не пуста

элемента:

котором можно добавлять и удалять элементы как с одного,

Моделирование:

статический массив (кольцо)
динамический массив
связный список

A.
«Потомки» А: B, C, D, E, F,

«Предки» F: A, C.

Корень – узел, не имеющий предков (A).

Лист – узел, не имеющий потомков (D, E, F, G).

корень и несколько связанных с ним отдельных (не связанных

Двоичное (бинарное) дерево:

пустая структура – это двоичное дерево
двоичное дерево – это корень и два связанных с ним отдельных двоичных дерева («левое» и «правое» поддеревья)

Применение:

поиск в большом массиве неменяющихся данных
сортировка данных
вычисление арифметических выражений
оптимальное сжатие данных (метод Хаффмана)

дерева, по которому выполняется поиск.

слева от узла – узлы

O(log N)

Двоичный поиск O(log N)

Линейный поиск O(N)

одному разу.

⇒ список узлов
КЛП – «корень-левый-правый» (в прямом

посетить корень
обойти левое поддерево
обойти правое поддерево

ЛКП – «левый-корень-правый» (симметричный):

посетить корень
обойти левое поддерево
обойти правое поддерево

ЛПК – «левый-правый-корень» (в обратном порядке):

посетить корень
обойти левое поддерево
обойти правое поддерево

+ 4 * 9 - 5
1 4 + 9

префиксная форма

инфиксная форма

постфиксная форма

Обход «в ширину»: «сыновья», потом «внуки», …

* + - 1 4 9 5

«в глубину»

корень дерева
нц пока стек не пуст
V:= выбрать узел

очередь не пуста
V:= выбрать узел из очереди
посетить

из операций с наименьшим приоритетом.

то
создать узел-лист
выход
все
поместить операцию в корень дерева
построить левое

построить левое поддерево
построить правое поддерево

Построение дерева:

поддерева
результат:= операция(n1, n2)
значение левого поддерева
значение правого поддерева
Вычисление по

массив неудобен!
type
PNode = ^TNode; { указатель на узел

ссылка вперёд

{ указатель на узел }
New(p);
Обращение к новому узлу (по

p^.data:= s;
p^.left:= nil;
p^.right:= nil;

Освобождение памяти:

Dispose(p);

}
s: string; { строка с выражением }

{ выделить память }
k:=

вернёт адрес нового дерева

Tree(Copy(s,1,k-1));
Tree(Copy(s,k+1,Length(s)-k))

res: integer;
begin
if Tree^.left = nil then
Val(Tree^.data,

Calc(Tree^.left);
Calc(Tree^.right);

'+','-': Priority:= 1;
'*','/': Priority:= 2

integer;
begin
minPrt:= 50; { любое между 2 и 100

<=

вернёт номер символа

и связей между ними (рёбер).

петля
Матрица смежности:
Список смежности:
( A(B, C),

любыми вершинами которого существует путь.

граф без циклов (замкнутых путей).

рёбра называю дугами.

котором на каждом шаге принимается решение, лучшее в данный

Задача. Найти кратчайший маршрут из А в F.

связи, чтобы все города были связаны в одну систему

Алгоритм Крускала:

начальное дерево – пустое
на каждом шаге добавляется ребро минимального веса, которое ещё не входит в дерево и не приводит к появлению цикла

концы которых окрашены в разные цвета;
найденное ребро (iMin,jMin) добавляется

Сделать N-1 раз:

for i:=1 to N do col[i]:= i;

каждой вершине свой цвет

матрица }
W: array[1..N,1..N] of integer;

Данные:

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

for i:=1 to N-1 do
writeln('(', ostov[i,1], ',',
ostov[i,2], ')');

{ поиск ребра с минимальным весом }
min:=

A невыбранная вершина

< W[x,y]
может быть так, что
9
B

< W[x,y]
может быть так, что
5
C

вершины







A → C → E → F

integer;
active: array [1..N] of boolean;
R,

Данные:

Начальные значения (выбор начальной вершины):

for i:=1 to N do begin
active[i]:= True; { вершины не выбраны }
R[i]:= W[1,i]; { только маршруты из A }
P[i]:= 1 { вершина A }
end;
active[1]:= False; { вершина A выбрана }
P[1]:= 0; { это начало маршрута }

min:= MaxInt;
for j:= 1 to N do

Основной цикл:

выбор следующей вершины, ближайшей к A

проверка маршрутов через вершину kMin

< > 0 do begin
write(i:5);
i:= P[i]

Вывод результата (маршрут 1 → N):

для начальной вершины P[i]=0

i:= 1 to N do
for j:= 1

Все кратчайшие пути (из любой вершины в любую):

begin
for j:=1 to N do
P[i,j]:= i;

Дополнительная матрица:

for k:= 1 to N do
for i:= 1 to N do
for j:= 1 to N do
if W[i,k]+ W[k,j]< W[i,j] then begin
W[i,j]:= W[i,k]+ W[k,j];
P[i][j]:= P[k][j]
end;

Кратчайшие длины путей и маршруты:

1 и, посетив по разу в неизвестном порядке города

Точные методы:
простой перебор;
метод ветвей и границ;
метод Литтла;
…
Приближенные методы:
метод случайных перестановок (Matlab)
генетические алгоритмы
метод муравьиных колоний
…

большое время счета для больших N

O(N!)

не гарантируется оптимальное решение

пунктов, в каждом из которых живет pi школьников (i=1,...,N).

= 1
Fn = Fn-1 + Fn-2, при n >

function Fib(N: integer):
integer;
begin
if N < 3 then
Fib:= 1
else Fib:= Fib(N-1) + Fib(N-2)
end;

повторное вычисление тех же значений

of integer;
Заполнение массива:
F[1]:= 1; F[2]:= 1;
for i:= 3 to

F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2

нужны только два последних!

задач путем сведения их к более простым задачам того

1

2

5

ABE: 5 + 20 = 25

AСE: 2 + 30 = 32

ADE: 1 + 40 = 41

дополнительный расход памяти

увеличение скорости

N нулей и единиц, в которых нет двух стоящих

Решение «в лоб»:

0/1

битовые цепочки

построить все возможные цепочки
проверить каждую на «правильность»

2N

Сложность алгоритма O(2N)

N нулей и единиц, в которых нет двух стоящих

Простые случаи:

K1=2

N = 1:

0 1

K2=3

N = 2:

00 01 10

Общий случай:

KN-1 «правильных» цепочек начинаются с нуля!

KN-2 «правильных» цепочек начинаются с единицы!

KN-2

KN-1

KN = KN-1 + KN-2

= FN+2

бидоны объемом 1, 5 и 6 литров. Нужно разлить

Перебор?

при больших N – очень долго!

«Жадный алгоритм»?

N = 10:

10 = 6 + 1 + 1 + 1 + 1

10 = 5 + 5

K = 5

K = 2

для N литров
KN = 1 + KN-1
1 л:
KN =

5 л:

KN = 1 + KN-6

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

Рекуррентная формула:

, KN-5 , KN-6)

















2 бидона
5 + 5

…, N) набрать кучу весом ровно W или, если

камень
взят

камень
не взят

2N

Сложность алгоритма O(2N)

Решение «в лоб»:

…, N) набрать кучу весом ровно W или, если

Идея: сохранять в массиве решения всех более простых задач этого типа (при меньшем количестве камней N и меньшем весе W).

Пример: W = 8, камни 2, 4, 5 и 7

w

pi

базовые случаи

T[i,w] – оптимальный вес, полученный для кучи весом w из i первых по счёту камней.

i

< 4 ничего не меняется!
0
2
2
для w ≥ 4:
если его

T[2,w] = T[1,w]

если его взять:

T[2,w] = 4 + T[1,w-4]

max

4

4

6

6

6

< 5 ничего не меняется!
0
2
2
4
5
6
7
7

< 7 ничего не меняется!
0
2
2
4
5
6
7
7

< pi ничего не меняется!
Рекуррентная формула:

прибавь 1
2. умножь на 3
Сколько есть разных программ,

команда
Рекуррентная формула:
KN = KN-1 если N

если N не делится на 3
KN = KN-1

1

2

2

2

3

3

3

5

5

5

7

7

7

9

9

9

12

12

12

K2+K1

K5+K2

K8+K3

одна пустая!

2 to N do begin
K[i]:= K[i-1];

размером W рублей, если есть монеты достоинством pi (i=1,

Перебор?

при больших N и W – очень долго!

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

запоминаем решения всех задач меньшей размерности: для меньших значений W и меньшего числа монет N.

5 и 10
w
pi
базовые случаи
T[i,w] – количество вариантов для суммы

i

Рекуррентная формула (добавили монету pi):

при w < pi:

при w ≥ pi:

T[i,w] = T[i-1,w]

T[i,w] = T[i-1,w] + T[i,w-pi]

все варианты размена остатка

T[i-1,w]

без этой монеты

T[i,w-pi]

5 и 10
Рекуррентная формула (добавили монету pi):

163, г. Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной