Введение в специальность Алгоритмы и структуры данных НИЖЕГОРОДСКИЙ ИНСТИТУТ

кафедрой информатики и ИТ
к. ф.-м.н., доцент
i.tsvetkova@niu.ranepa.ru
http://niu.ranepa.ru/

структуры данных http://www.iprbookshop.ru/63821.html Никлаус Вирт - знаменитый швейцарский специалист по программированию,

автор языка Паскаль.

математики.
Мухаммед ибн Муса аль-Хорезми (Alhorithmi), 783-850 гг., «Книга о сложении

и вычитании»
Алгоритм - это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу.
Программа - конкретная формулировка абстрактных алгоритмов, основанная на конкретных представлениях и структурах данных.

решения конкретного множества задач и обладает пятью важными чертами: конечность,

определённость, ввод, вывод, эффективность». (Кнут, Д.Э. Искусство программирования. Том 1 : Основные алгоритмы / Д.Э. Кнут; под общей редакцией Ю.В. Козаченко; перевод с английского С.Г. Тригуб, Ю.Г. Гордиенко, И.В. Красикова. - Москва : Вильямс, 2004. - 720 с. - ISBN 5-8459-0080-8)

Определенность. Действия, которые необходимо произвести на каждом шаге, должны быть

определены строго и недвусмысленно в каждом возможном случае.
Вход (input). Алгоритм всегда имеет некоторое (иногда равное нулю) количество входных данных, то есть величин, передаваемых ему до начала работы.
Выход (output). Алгоритм всегда обязан иметь одну или несколько выходных величин. Алгоритмы, не имеющие выходных данных, бесполезны на практике.
Эффективность. От алгоритма требуется, чтобы он был эффективным. Это означает, что все операции, которые необходимо произвести в алгоритме, должны быть достаточно простыми, чтобы их в принципе можно было выполнить точно и за конечное время.

- полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в

себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.;
графическая – блок-схемы (текст и графика);
программная - тексты на языках программирования.

равный 1;
задать число для хранения произведения, равное 1;
заменить произведение, умножив

произведение на счетчик;
если значения счетчика и целого числа равны, то взять произведение в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
увеличить счетчик на 1;
повторить алгоритм с шага 4.

применимости алгоритма
надо цель выполнения алгоритма
нач описание промежуточных величин
|

последовательность команд (тело алгоритма)
кон

алг Факториал (арг цел N, рез цел F)
дано | N
надо | F = 1*2*3* ...*N
нач цел i
ввод N; F:=1
нц для i от 1 до N
F:=F*i
кц
вывод "F = ", F
кон

Factorial
{
  class Program
   {
      static void Main(string[] args)
 

     {
          int N, F = 1, i;
          Console.WriteLine("Расчет факториала.  Введите число N = ");
           N = Convert.ToInt32(Console.ReadLine());
          for (i = 2; i <= N; i++)
               F = F * i;
          Console.WriteLine("F = " F);
          Console.ReadKey();
       }
   }
}

систем. Условные обозначения и правила выполнения
Блок-схема – совокупность символов, соответствующих

этапам работы алгоритма и соединяющих их линий.

1 цифры в нумерации групп
Да
Нет

образование’
иначе string2:= ‘среднее профессиональное образование’
все
i>0
string1:= ‘очная форма обучения’
Да
Нет
string1:= ‘среднее профессиональное

образование’

j=2 string3:=‘второй курс’
при j=3 string3:=‘третий курс’
при j=4 string3:=‘четвертый курс’
все
Нет

j=2 string3:=‘второй курс’
при j=3 string3:=‘третий курс’
при j=4 string3:=‘четвертый курс’
иначе string3:=‘пятый

курс’
все

Нет

String:3:=‘пятый курс’

которая называется телом цикла
1) Цикл типа пока. Предписывает выполнять тело

цикла до тех пор, пока выполняется условие, записанное после слова «пока».

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

диапазоне.

с постусловием;
цикл с заданным числом повторений.

2
оператор 3
если условие 2 то оператор 4
иначе оператор 5
если условие

1 то
если условие 2 то оператор 4
иначе
начало
оператор 1
оператор 2
оператор 3
конец
иначе оператор 5

если условие 1 то
начало
оператор 1
оператор 2
оператор 3
конец
иначе
если условие 2 то оператор 4
иначе оператор 5

14, y = -5 значение переменной z будет равно ...

6 значение переменной s будет равно ...

ними.

Структура данных — программная единица, позволяющая хранить и обрабатывать множество

однотипных и/или логически связанных данных.

Понятие структуры данных

Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

данных.
Уничтожение – противоположна по своему действию операции создания.
Выбор

– обеспечивает доступ к данным внутри самой структуры.
Обновление – позволяет изменять значения данных в структуре и добавлять (удалять) выбранные данные.

всегда может быть представлена с использованием ограниченного числа элементарных управляющих

структур (последовательность, ветвление, цикл).

Идея доказательства этого утверждения:
преобразование каждой части алгоритма в одну из трех основных структур или их комбинацию;
после достаточного числа таких преобразований оставшаяся неструктурированной часть либо исчезнет, либо станет ненужной;
в результате получится алгоритм, эквивалентный исходному и использующий лишь 3 управляющие структуры.