Курс лекций CS (первый семестр)
.pdfКафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Лекция №3.
Алгоритм и его свойства.
Понятие алгоритм является основным для всей области компьютерного программирования, поэтому мы должны начать с тщательного анализа этого термина.
Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в IX в. (825 г.) дал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван
алгоризмом.
С 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого состоял в комбинировании четырех операций арифметического исчисления — сложения, вычитания, умножения, деления.
К 1950 г. алгорисмус стал алгорифмом. Смысл алгорифма чаще всего связывался с алгорифмами Евклида, например, нахождения наибольшего общего делителя двух чисел. Вплоть до 30-х годов понятие алгоритма имело скорее методологическое, чем математическое значение. Под алгоритмом понимали конечную совокупность точно сформулированных правил, которые позволяют решать те или иные классы задач. Такое определение алгоритма не является строго математическим, так как в нем не содержится точной характеристики того, что следует понимать под классом задач и под правилами их решения. В течение длительного времени математики довольствовались этим определением, поскольку общей теории алгоритмов фактически не существовало.
В двадцатых годах нашего века задача такого определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине 30-х годов в работах известных математиков Гильберта, Гѐделя, Черча, Клини, Поста и Тьюринга в двух формах. Первое решение было основано на понятии особого класса арифметических функций, получивших название рекурсивных функций, второе — на описании точно очерченного класса процессов.
Первоначально теория алгоритмов возникла в связи с внутренними потребностями теоретической математики. Математическая логика, основания математики, алгебра, геометрия и анализ остаются и сегодня одной из основных областей приложения теории алгоритмов.
Другая ее область возникла в 40-х годах в связи с созданием быстродействующих электронных вычислительных и управляющих машин. Появление ЭВМ способствовало развитию теории алгоритмов, вызвало к жизни разделы этой теории, имеющие ярко выраженную прикладную направленность. Это прежде всего алгоритмические системы и алгоритмические языки, являющиеся основой современной теории программирования для универсальных ЭВМ, и способы точного описания отображений, реализуемых цифровыми автоматами.
Алгоритм – это понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.
11
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Пример. Вычислить значения y по формуле
Y=(Ax+B)*(Cx-D)
для любого значения х, при заданных значениях констант A, B, C, D.
Чтобы решить эту задачу достаточно выполнить последовательность следующих действий:
1.Умножить А на х, результат обозначить R1.
2.R1 сложить с В, результат обозначить R2.
3.Умножить С на х, результат обозначить R3.
4.Из R3 вычесть D, результат обозначить R4.
5.Умножить R2 на R4, считать результат значением y.
Это предписание является алгоритмом решения поставленной задачи. Для человека, выполняющего действия, уже необязательно знать исходную формулу для вычисления значения y. Ему нужно всего лишь строго следовать указанному предписанию, исполняя его пункт за пунктом.
Каждый алгоритм строится в расчете на некоторого исполнителя. Для того чтобы исполнитель мог решить задачу по заданному алгоритму, необходимо, чтобы он был в состоянии выполнить каждое действие, предписываемое командами алгоритма. Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя.
Однако, алгоритм – это не просто набор конечного числа правил. Алгоритм обладает следующими свойствами: понятность, точность, конечность. Понятность: алгоритм составляется только из команд, входящих в систему команд исполнителя. Алгоритм должен быть понятным исполнителю, т.е. каждая команда должна входить в систему команд исполнителя. Таким образом, для правильного построения алгоритма необходимо знать систему команд исполнителя. Точность: каждая команда алгоритма управления определяет однозначное действие исполнителя. Конечность (или результативность): выполнение алгоритма должно приводить к результату за конечное число шагов.
Кроме того, последовательность действий исполнителя всегда применяется к некоторым исходным данным. Например, для вышеуказанного алгоритма необходимо знать значения всех переменных, входящих в формулу. Полный набор данных: необходимый и достаточный набор данных для решения поставленной задачи (получения исходного результата).
Алгоритмы работы с величинами.
12
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Величина – это отдельный информационный объект, который имеет имя, значение и тип. Величины бывают постоянными и переменными. Постоянная величина (константа) не изменяет своего значения в ходе выполнения алгоритма. Константа может обозначаться собственным значением (числа 10, 3.5) или символьным именем (число ). Переменная величина (переменная) может изменять значение в ходе выполнения алгоритма. Переменная всегда обозначается символическим именем (X, A, R5 и т.п.). Тип величины определяет множество значений, которые может принимать величина, и множество действий, которые можно выполнять с этой величиной. Основные типы величин: целый, вещественный, символьный, логический.
Выражение – запись, определяющая последовательность действий над величинами. Выражение может содержать константы, переменные, знаки операций, функции.
Например:
A+B, 2*X-Y, K+L-sin(X).
Команда присваивания – команда исполнителю, в результате которой переменная получает новое значение. Формат команды:
Имя_переменной=выражение;
Исполнение команды присваивания происходит в таком порядке: сначала вычисляется выражение, затем полученное значение присваивается переменной.
Пример 1. Пусть переменная А имела значение 6. Какое значение получит переменная А после выполнения команды: А=2*А-1.
Решение. Вычисление выражения 2*А-1 при А=6 даст число 11. Значит новое значение переменной А будет равно 11.
Пример 2. (Циклическая перестановка.) Написать последовательность команд присваивания, в результате выполнения которых переменные А и В поменяются местами.
Решение. Для решения этой задачи потребуется еще одна дополнительная переменная С.
С=А;
13
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
A=B;
B=C;
Составим трассировочную таблицу для начальных значений A=3, B=7.
A |
B |
C |
|
|
|
3 |
7 |
- |
|
|
|
3 |
7 |
3 |
|
|
|
7 |
7 |
3 |
|
|
|
3 |
7 |
3 |
|
|
|
Любой алгоритм может быть построен из команд присваивания, ввода, вывода, ветвления и цикла.
Команда ввода – команда, по которой значения переменных задаются через устройства ввода (например, клавиатуру).
Пример. Ввод А; – ввод значения переменной А с клавиатуры компьютера.
14
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Команда вывода – команда, по которой значение величины отражается на устройстве вывода компьютера (например, на экран дисплея).
Пример. Вывод Х ;– значение переменной Х выводится на экран.
Команда ветвления – разделяет алгоритм на два пути в зависимости от некоторого условия; затем исполнение алгоритма выходит на общее продолжение. Ветвление бывает полное и неполное.
Полное ветвление.
если (условие)
то |
действие 1 |
иначе |
действие 2 |
кв |
|
Неполное ветвление.
если |
(условие) |
то |
действие |
кв |
|
15
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Пример. Записать алгоритм нахождения большего из двух чисел А и В.
Решение. алг максимальное число
вещ А,В
нач
ввод А,В;
если (А>B)
то вывод А;
иначе вывод В;
кв
кон
16
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Лекция №4.
Команда цикла.
Команда цикла обеспечивает повторное выполнение последовательности команд (тела цикла) по некоторому условию. Циклы бывают трех типов: цикл с параметром, цикл с предусловием и цикл с постусловием.
Цикл с предусловием – цикл, выполнение которого повторяется, пока истинно условие цикла:
пока (условие)
нц
тело цикла
кц
Пример. Вывести на экран заданное количество приветствий.
17
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Решение.
алг Привет
цел i
нач
ввод i
пока (i>0)
нц
вывод ―Привет‖;
i=i-1;
кц
кон
Цикл с постусловием – цикл, выполнение которого выполняет, пока истинно условие цикла, которое располагается после тела цикла.
нц
тело цикла
кц
пока (условие)
18
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Тело цикла с предусловием может ни разу не выполняться, если условие продолжения цикла сразу не выполняется. Цикл с постусловием выполняется всегда, по крайней мере, один раз.
Пример. Вывести на экран заданное количество приветствий.
Решение.
алг Привет
цел i
нач
ввод i
нц
вывод ―Привет‖;
i=i-1;
кц
пока (i>0);
кон
Недостатком данного алгоритма в отличие от предыдущего является то, что строка ―Привет‖ выведется на экран даже в том случае, если пользователь введет неположительное число i (целое – не означает только положительные).
19
Кафедра теоретической механики ИМЭМ ОНУ им. И.И.Мечникова
Цикл с параметром –повторное выполнение тела цикла, пока целочисленный параметр пробегает множество всех значений от начального (In) до конечного (Ik) c шагом k.
для i от In до Ik шаг k
нц
тело цикла
кц
Пример. Вывести на экран заданное количество приветствий.
Решение.
алг Привет
20