Высокоцровневые методы информатики и првые методы информатики и программированияограммирования

Содержание

1 Алгоритмы 6

2 Алгоритмы сортировок 24

3 Элементарные и нелинейные структуры данных 49

4 Хеширование 91

5 Основные принципы разработки алгоритмов 114

Литература 174

Русскоязычные ресурсы InterNet 175

1 Алгоритмы

1.1 Основные определения: алгоритм, вход, результат; понятие правильного и неправильного алгоритма; псевдокод

Алгоритм – это формально описанная вычислительная процедура, получающая исходные данные (вход) и возвращающая результат (выход). Алгоритмы строятся для решения тех или иных вычислительных задач, при этом они должны удовлетворять следующим противоречащим друг другу требованиям:

Быть простым для понимания, перевода в программный код и отладки;
Эффективно использовать вычислительные ресурсы.

Алгоритм считают правильным (correct), если на любом допустимом входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. В этом случае говорят, что алгоритм решает (solve) данную вычислительную задачу. Неправильный алгоритм для некоторого входа может вообще не остановиться или дать неправильный результат. Алгоритм может быть описан различными способами, в том числе и при помощи псевдокода, принадлежащего более высокому уровню абстракции по сравнению с языками программирования высокого уровня (C#, Pascal, Basic и т.д.). В математическом пакете MathCAD при написании кода функций, определяемых пользователем, используется нотация, напоминающая описываемый ниже псевдокод.

Таблица 1.1 - Соглашения, лежащие в основе псевдокода

№	Описание
1	Отступ от левого поля указывает на уровень вложенности (это позволяет отказаться от применения begin и end)
2	Комментарий обозначается символом “►”.
3	Циклы while, for, repeat и условные конструкции имеют тот же смысл, что и в языке Pascal.
4	Символ “” имеет смысл оператора присваивания.
5	Запись i  j  e обозначает j  e; i  j или i  e.
6	Переменная, обозначающая массив или объект, считается указателем на составляющие его данные.
7	Все переменные (по-умолчанию) – локальные.
8	Оператор доступа к элементу массива пишется в квадратных скобках [].
9	Запись “A[1..j]” обозначает A[1], A[2], A[3]..A[j].
10	Доступ к полю (field) объекта (object): field[object].
11	Параметры в подпрограмму передаются по-значению (by value), но при передаче объекта его свойства копируются в виде указателей. Т.е. если в качестве параметра передается объект x, то присваивание x  y снаружи заметить нельзя, а f [x]  5 можно.

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

Листинг 1.1 – Псевдокод алгоритма сортировки вставками

procedure InsertSort(n: integer;

var A: array[1..n] of integer);

var

i, j, Tmp: integer;

begin

for i := 2 to n do begin

{Сохраняем текущий элемент}

Tmp := A[i];

{Сдвигаем элементы, большие, чем текущий}

j := i-1;

while (A[j] > Tmp) and (j > 1) do begin

A[j+1] := A[j];

j := j-1;

end;

{Вставляем текущий элемент}

A[j+1] := Tmp;

end;

Листинг 1.2 – Сортировка вставками

Содержание