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

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Алгоритм:
начать с 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

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

нц для 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;

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;

for i:= 2 to N do
if A[i] then
writeln ( i );

Длинное число – это число, которое не помещается в переменную одного из стандартных типов данных языка программирования.

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

Обратный порядок элементов:

от –231 = – 2 147 483 648 до 231 – 1 = 2 147 483 647.

longint:

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

A = 12345678

201 цифра

6 цифр в ячейке ⇒ 34 ячейки

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

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

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

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

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

основание 1000000

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;

s:= A[1]*k + r

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] );

for k:=i-1 downto 0 do
Write6(A[k]);

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

со старшего

Write6:

x = 12345

012345

x div 100000

x mod 100000

Несколько массивов:

var authors: array[1..N] of string;
titles: array[1..N] of string;
count: array[1..N] of integer;
...

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

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

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

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

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 (размер) байт

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

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

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

Assign(F, 'books.dat');
Rewrite(F);
B.author:= 'Тургенев И.С.';
B.title:= 'Муму';
B.count:= 2;
write(F, B);
Close(F);

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

только для TBook!

только для TBook!

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;

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

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

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

var B: TBook;

type PBook = ^TBook;

pointer

указатель на переменную типа TBook

var P: PBook;

P:=@B;

P:=@Books[3];

P^.author ⇔ Books[3].author

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

var p1: PBook;

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

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

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

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

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

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]='?')

диапазон

if s[i] in ['a'..'z', '0'..'9',
'.', '-', '_'] then
{ символ правильный }

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

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

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

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

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

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

Имена для элементов множества:

type TFontStyles = (fsBold, fsItalic,
fsUnderline);

стили шрифта

жирный

курсив

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

var fs: set of TFontStyles;

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

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

первый

последний

110

fsBold

fsItalic

fsUnderline

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] *
[2, 3, 4];

AND

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

[3]

OR

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

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

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

[1, 5, 7]

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

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

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

… позволяют

Задача. Ввести с клавиатуры целое значение N, затем – N целых чисел, и вывести на экран эти числа в порядке возрастания.

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

[0.. N-1]

Чтение данных:

for i:=0 to N-1 do read(A[i]);

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

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

SetLength(A, 4, 3);

writeln( High(A) );

3

writeln( High(A[0]) );

2

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

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

for i:=0 to High(A) do
SetLength(A[i], i+1);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

сдвиг вниз

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

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

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

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

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

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

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

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

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

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

пустой список – это список
список – это узел и связанный с ним список

конец списка

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

prev,

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

указатель

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

LIFO = Last In – First Out.

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

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

нц пока файл не пуст
прочитать x
добавить x в стек
кц

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

1

2

3

4

5

5

4

3

2

1

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 в стек:

«Вытолкнуть» из стека в x :

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

for i:=0 to S.size-1 do begin
x:= Pop(S);
writeln(F, x)
end;

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

var F: text;

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

/ + 5 15 - + 4 7 1

/ 20 - + 4 7 1

/ 20 - 11 1

/ 20 10

2

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

5 15 + 4 7 + 1 - /

20 4 7 + 1 - /

20 11 1 - /

20 10 /

2

()[{()[]}]

[()

)(

[()}

([)]

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

( ) ( ( ) ( ( ) ) )

счётчик 0

1

0

1

2

1

2

3

2

1

0

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

({[)}]

если открывающая скобка – «втолкнуть» в стек
если закрывающая скобка – снять парную со стека

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

Cтек пуст:

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

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

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

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

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

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

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

FIFO = Fist In – First Out.

Применение:

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

(2,1)

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

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

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

4

5

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

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

2

4

3

4

5

1

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

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

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

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

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

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

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

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

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

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

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

Применение:

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

слева от узла – узлы с меньшими или равными ключами
справа от узла – узлы с большими или равными ключами

O(log N)

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

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

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

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

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

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

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

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

1 4 + 9 5 - *

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

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

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

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

* + - 1 4 9 5

«в глубину»

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

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

значение левого поддерева
значение правого поддерева

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

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

New(p);

Обращение к новому узлу (по указателю):

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

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

Dispose(p);

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

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

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

<=

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

петля

Матрица смежности:

Список смежности:

( A(B, C), B(A, C, D), C(A, B, С, D), D(B, C) )

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

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

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

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

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

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

Данные:

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

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

9

B

5

C

Данные:

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

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; { это начало маршрута }

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

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

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

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

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

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

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

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;

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

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

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

O(N!)

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

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

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

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

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

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

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

0/1

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

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

2N

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

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

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

Перебор?

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

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

N = 10:

10 = 6 + 1 + 1 + 1 + 1

10 = 5 + 5

K = 5

K = 2

1 л:

KN = 1 + KN-5

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

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

2 бидона

5 + 5

камень
взят

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

2N

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

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

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

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

w

pi

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

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

i

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

0

2

2

4

5

6

7

7

0

2

2

4

5

6

7

7

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

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

одна пустая!

Перебор?

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

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

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

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

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]