Алгоритмизация и программирование. Язык C. Целочисленные алгоритмы (§ 38 - § 45)

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

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

for ( i = 2; i <= N; i++ )
A[i] = true;

выделяем на 1 элемент больше, чтобы начать с A[1]

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

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

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

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

long int:

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

A = 12345678

201 цифра

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

const int N = 33;
long int A[N+1];

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

[A] = 1;
for ( k = 2; k <= 100; k ++ )
[A] = [A] * k;

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

основание 1000000

r = перенос в A[1]

s = A[0]*k;
A[0] = s % d;
r = s / d;

s:= A[1]*k + r;

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

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

for ( k = 2; k <= 100; k++ )
{
...
}

все разряды

i = N;
while ( ! A[i] )
i --;

printf ( "%ld", A[i] );

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

со старшего

Write6:

x = 12345

012345

x / 100000

x % 100000

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

char authors[N][40];
char titles[N][80];
int count[N];
...

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

typedef struct
{
char author[40]; // автор, строка
char title[80]; // название, строка
int count; // количество, целое
} TBook;

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

структура

название типа данных

typedef struct
{
char author[40];
char title[80];
int count;
} TBook;

4 байта

40 байт

80 байт

printf ( "%d\n", sizeof(B.author) ); // 40
printf ( "%d\n", sizeof(B.title) ); // 80
printf ( "%d\n", sizeof(B.count) ); // 4

gets ( B.author );
gets ( B.title );
scanf ( "%d", &B.count );

printf ( "%s %s. %d шт.",
B.author, B.title, B.count );

B.count --; // одну книгу взяли
if( B.count == 0)
puts ( "Этих книг больше нет!" );

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

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

"wb" – запись в двоичный файл
"rb" – чтение двоичного файла
"ab" – добавление к двоичному файлу

binary, двоичный

адрес в памяти

размер блока

сколько блоков

fread ( &Books[0], sizeof(TBook), 5, Fin );

Одна структура:

Сразу несколько структур:

адрес в памяти

размер блока

сколько блоков

адрес в памяти

размер структуры

сколько структур

Число структур неизвестно:

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

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

TBook В;

TBook *p;

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

p = &B;

p = &Books[2];

p->author ⇔ Books[2].author

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

TBook *p1;

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

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

for ( i = 0; i < M; i++ )
printf ( "%s, %s, %d\n",
p[i]->author, p[i]->title,
p[i]->count );

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

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

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

… позволяют

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

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

преобразовать к указателю на int

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

размер блока

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

free ( A );

указатель на указатель

Выделение памяти под элементы матрицы:

A[0] =(int*)calloc( N*M, sizeof(int));

число элементов матрицы

новый тип данных: указатель

Расстановка указателей:

Работа с матрицей:

for ( i = 0; i < N; i++ )
for ( j = 0; j < M; j++ )
A[i][j] = i + j;

Удаление:

free ( A[0] );
free ( A );

Выделение памяти:

for ( i = 0; i < N; i++ )
free ( A[i] );

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

free ( A );

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

освободить массив указателей

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

N = 0;
scanf ( "%d", &x );
while ( x!= 0 ) {
N ++;
A = (int*) realloc ( A, N*sizeof(int) );
A[N-1] = x;
scanf ( "%d", &x );
}

перераспределить память

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

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

typedef struct
{
TPair *data;
int capacity; // размер массива
int size;
} TWordList;

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

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

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

Начальные значения:

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

F = fopen ( "output.txt", "w" );
for ( p = 0; p < L.size; p++ )
fprintf ( F, "%s: %d\n",
L.data[p].word, L.data[p].count );
fclose ( F );

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

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

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

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

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

Сдвиг вниз:

с последнего

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

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

сдвиг вниз

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

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

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

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

wordlist.c

alphalist.c

wordlist.c

alphalist.c

#include "wordlist.h"

#include "wordlist.h"

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

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

конец списка

LIFO = Last In – First Out.

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

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

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

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

1

2

3

4

5

5

4

3

2

1

void Push ( TStack *pS, int x )
{
pS->size ++;
if ( pS->size > pS->capacity ) {
pS->capacity += 10;
pS->data = (int*) realloc ( pS->data,
sizeof(int)*pS->capacity );
}
pS->data[pS->size-1] = x;
}

указатель

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

указатель

void InitStack ( TStack *pS, int capacity )
{
pS->data = (int*) calloc ( capacity,
sizeof(int) );
pS->capacity = capacity;
pS->size = 0;
}

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

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

Заполнение стека:

while ( S.size > 0 )
{
x = Pop( &S );
fprintf ( Fout, "%d\n", x );
}

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

FILE *Fin;

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

bool isEmpty ( TStack S )
{
return S.size == 0;
}

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

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

if ( ! err )
printf ( "Скобки расставлены верно." );
else
printf ( "Скобки расставлены неверно." );

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

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

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

FIFO = Fist In – First Out.

Применение:

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

(1,2)

TPoint Point ( int x, int y )
{
TPoint P;
P.x = x; P.y = y;
return P;
}

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

структура «точка»

структура «очередь» (динамический массив)

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

4

5

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

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

2

4

3

4

5

1

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

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

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

int A[YMAX][XMAX]; // матрица
TQueue Q; // очередь
int i, j, x0, y0, color;
TPoint pt;

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

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

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

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

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

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

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

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

Применение:

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

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

O(log N)

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

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

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

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

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

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

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

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

1 4 + 9 5 - *

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

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

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

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

* + - 1 4 9 5

«в глубину»

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

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

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

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

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

новый тип: адрес узла

p = (PNode) calloc ( 1, sizeof(TNode) );

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

strcpy ( p->data, s );
p->left = NULL;
p->right = NULL;

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

free(p);

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

пустая строка!

MakeTree ( sLeft );
MakeTree ( &s[k+1] );

strcpy ( Tree->data, s );
Tree->left = NULL;
Tree->right = NULL;

Новый узел – лист:

Новый узел – операция:

нет сыновей!

один символ!

k

s

sLeft

дальше – нули!

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 = 0; i < N; i ++) col[i] = i;

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

Данные:

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

for ( i = 0; i < N-1; i ++ )
printf ( "(%d,%d)\n", ostov[i][0],
ostov[i][1] );

нет цикла

9

B

5

C

Данные:

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

for ( i = 0; i < N; i ++ ) {
active[i] = true; // все вершины не выбраны
R[i] = W[0][i]; // рёбра из вершины 0
P[i] = 0;
}
active[0] = false; // вершина уже выбрана
P[0] = -1; // это начальная вершина

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

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

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

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

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

A → C → E → F

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

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

for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
if ( W[i][k] + W[k][j] < W[i][j] ) {
W[i][j] = W[i][k] + W[k][j];
P[i][j] = P[k][j];
}

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

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

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

O(N!)

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

int Fib ( int N )
{
if ( N < 3 )
return 1;
else return Fib(N-1) + Fib(N-2);
}

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

Заполнение массива:

F[1] = 1; F[2] = 1;
for ( i = 3; i <= N; i++ )
F[i] = F[i-1] + F[i-2];

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]