Электроэнергетика и электротехника
К. С. Галиев, Е. К. Печурина
ОСНОВЫ
АЛГОРИТИМИЗАЦИИ
И ПРОГРАММИРОВАНИЯ
Учебно-методическое пособие
для студентов-бакалавров,
изучающих «Информатику»
Под редакцией профессора В.И. Лойко
Краснодар
2013
УДК 004(078)
ББК 32.81
Г15
Рецензенты:
Г. А. Аршинов – доктор технических наук, профессор
(Кубанский государственный аграрный университет);
Е. В. Луценко – доктор экономических наук, профессор
(Кубанский государственный аграрный университет).
Галиев К. С.
| Г15 | Основы алгоритмизации и программирования: учеб.-метод. пособие / К. С. Галиев, Е .К. Печурина. – Краснодар: КубГАУ, 2013. – 94 с. |
Учебно-методическое пособие посвящено одному из главных разделов дисциплины «Информатика» - основам разработки алгоритма решения задач и технологии написания текста исходного кода программы. Данное пособие предназначено прежде всего тем студентам-бакалаврам, у которых в названии направления подготовки отсутствуют слова «компьютерных технологий и систем». К ним относятся студенты факультетов: энергетики и электрификации; архитектурно-инженерного и др.
УДК 004(078)
ББК 32.81
Ó К. С. Галиев, Е. К. Печурина, 2013
Ó ФГБОУ ВПО «Кубанский государственный аграрный университет», 2013
Оглавление
ВВЕДЕНИЕ. 5
1 ОПИСАНИЕ АЛГОРИТМОВ.. 8
1.1 Понятие алгоритма. 8
1.2 Формы описания алгоритмов. 8
1.3 Свойства алгоритмов. 10
1.4 Элементы блок-схемы.. 10
1.5 Структуры алгоритмов. 13
1.6 Примеры циклических структур. 20
1.7 Вложенные циклы.. 23
1.8 Об эффективности алгоритма. 25
1.9 Алгоритм укрупненный и подробный. 33
1.10 Контрольные вопросы: 34
2 ПРИМЕРЫ СОСТАВЛЕНИЯ БЛОК-СХЕМ.. 36
2.1 Решение квадратного уравнения. 36
2.2 Вычисления в одномерной последовательности. 37
2.5 Вычисление значений функции. 39
2.6 Поиск max и min. 42
2.7 Сортировка чисел. 43
2.8 Задания для упражнения. 51
3 ОСНОВЫ АЛГОРИТМИЧЕСКОГО ЯЗЫКА ПАСКАЛЬ. 53
3.1 Основные понятия. 53
3.2 Операторы языка Паскаль. 56
3.3 Функции и процедуры.. 64
3.4 Замечание о структуре текста на языке Паскаль. 66
4 ПРИМЕРЫ ПРОГРАММ НА ЯЗЫКЕ ПАСКАЛЬ. 67
4.1 Задача о временах года. 67
4.2 Квадратное уравнение. 68
4.3 Суммирование чисел. 69
4.4 Задача о пробежке. 72
4.5 Вычисление значений функции. 72
4.6 Поиск максимального числа. 74
4.7 Поиск max и min. 75
4.8 Сортировка чисел. 76
4.9 Двумерный массив (матрица) 78
4.10 Задания для программирования. 80
5 ИНТЕГРИРОВАННАЯ СРЕДА ПРОГРАММИРОВАНИЯ.. 82
5.1 Понятие среды программирования. 82
5.2 Описание IDE Borland Pascal 82
5.3 Порядок работы в Borland Pascal 85
ЗАКЛЮЧЕНИЕ. 89
Литература: 90
Приложение 1. 91
Приложение 2. 93
ВВЕДЕНИЕ
В настоящее время компьютеры используются практически во всех сферах деятельности человека. Компьютер является аппаратно-программным комплексом. При этом программное обеспечение является неотъемлемой и важнейшей частью компьютера. При всём многообразии программ и программных комплексов у них есть одна общая черта – технологии разработки.
В данном учебном пособии рассматриваются основные (элементарные) вопросы разработки алгоритмов и программ с использованием алгоритмического языка. Одной из наиболее важных целей данного пособия является привитие студентам навыков алгоритмического мышления. Зачем?
Во-первых, в соответствии с Федеральном государственным образовательным стандартом высшего профессионального образования (ФГОС ВПО) подготовки бакалавра, практически по всем направлениям, выпускник должен обладать рядом общекультурных компетенций, в том числе, владением культурой мышления, способностью к постановке цели и выбору путей ее достижения (ОК-1). Для обладания профессиональными компетенциями (ПК) в части информационных технологий изучается дисциплина «Информатика» [11]. К основным разделам содержания дисциплины относятся, также в числе прочих: алгоритмизация и программирование; языки программирования высокого уровня; программное обеспечение и технологии программирования (см. Приложения 1,2).
Во-вторых, алгоритмы ведут нас по жизни постоянно и как бы незаметно. По сути дела, любая инструкция (к сотовому телефону, стиральной машине, автомобильному навигатору и т.п.) - это алгоритм. И умение читать такие алгоритмы - необходимое условие для приспособления человека, тем более с высшим образованием, к условиям жизни в современном мире.
В-третьих, по определению, алгоритм - это последовательность команд, предназначенная исполнителю, для решения поставленной задачи. Исполнителем алгоритма может быть не только человек, но и компьютер, автоматическое устройство и т.п. Для такого исполнителя алгоритм должен быть составлен весьма подробно и очень четко, чтобы можно было выполнить все команды "не раздумывая". Студент, изучающий информатику, обязан иметь представление о формах описания алгоритма и технологии разработки программы для компьютера.
В первой части учебного пособия приводятся понятие алгоритма, способы описания алгоритма, примеры составления блок-схем.
Во второй части описываются основные операторы алгоритмического языка Паскаль, приводятся примеры составления исходного кода программ, описывается работа в среде программирования Borland Pascal для разработки компьютерной программы.
Учебное пособие предназначено для студентов-бакалавров, изучающих дисциплины «Информатика», «Информационные технологии».
ЧАСТЬ 1.
АЛГОРИТМИЗАЦИЯ
1 ОПИСАНИЕ АЛГОРИТМОВ
1.1 Понятие алгоритма
Понятие алгоритма – одно из основных в информатике и программировании. Напомним, что информатика занимается вопросами автоматизированной обработки информации, а автоматизация осуществляется вычислительной машиной, работающей по заранее составленному алгоритму. Алгоритм – это инструкция для достижения цели. Программирование – это написание инструкции в виде команд для вычислительной машины.
Алгоритмом называется точная и понятная исполнителю инструкция для решения задачи при известных исходных данных.
Это определение алгоритма следует запомнить и обратить внимание на каждое слово, а именно, 1) алгоритм – это инструкция, 2) инструкция для решения задачи, 3) инструкция для исполнителя, 4) инструкция точная и понятная, 5) исходные данные известны.
Исполнителем алгоритма может быть человек или вычислительная машина. Для вычислительной машины алгоритм составляется человеком. Поэтому, человек должен сначала сам разобраться с ходом решения задачи, чтобы затем поручить решение задачи машине, написав для нее инструкцию в виде машинных команд. Вычислительная машина или компьютер (computer – вычислитель) - это одно и то же, т.е. синонимы.
1.2 Формы описания алгоритмов
Каждому типу исполнителя (человеку или компьютеру) соответствует своя форма описания алгоритма. Различают 4 формы описания алгоритма:
1) в виде обычного текста, желательно написанного по пунктам;
2) в виде чертежной схемы, называемой блок-схемой;
3) на специальном языке, называемым алгоритмическим языком;
4) в виде последовательности машинных команд, называемых компьютерной программой.
Первые две формы описания алгоритма предназначены для исполнителя-человека. Четвёртая – компьютерная программа – предназначена для исполнителя-компьютера. Третья форма описания - на алгоритмическом языке - является промежуточной, она разрабатывается человеком и она способна быть воспринятой, «прочитанной» компьютером. Компьютер может перевести текст с алгоритмического языка в свои машинные команды и стать исполнителем алгоритма.
Вначале ход решения задачи на уровне идеи описывается обычным текстом. Затем в более продуманной форме описывается блок-схемой. Блок-схема является лаконичным и строгим описанием алгоритма, не допускающим разночтения; блок-схема понимается только однозначно. Содержание блок-схемы переписывается алгоритмическим языком в специальный текст, называемый листингом программы или исходным кодом программы. Листинг программы переводится (транслируется или компилируется) в машинные команды и получается компьютерная программа.
Первые две формы описания алгоритма называются алгоритмизацией, последние две формы описания алгоритма называются программированием. Поэтапная разработка алгоритма и его реализация в виде компьютерной программы, называется алгоритмизацией и программированием.
Напомним, всё это нужно для того, чтобы заставить машину (компьютер) решать наши задачи вместо нас. Замена человека машиной для выполнения определенного вида работ называется автоматизацией. В нашем случае это вычислительные работы, это стремление автоматизировать обработку информации.
1.3 Свойства алгоритмов
При разработке алгоритма следует исходить из того, чтобы он обладал следующими свойствами:
· Понятность — алгоритм должен включать только те понятия (слова, конструкции, схемы, операторы, команды), которые исполнителю понятны и доступны, которые входят в его систему команд. Например, алгоритм решения квадратного уравнения для исполнителя ученика 8 класса должен быть написан более подробно, чем для ученика 11 класса или студента вуза.
· Дискретность – алгоритм, т.е. ход решения задачи, должен быть разбит на отдельные действия, шаги. Каждое следующее действие должно выполняться только после завершения предыдущего действия.
· Однозначность – алгоритм должен всегда выдавать одинаковый результат при одних и тех же исходных данных. Иногда это свойство называют детерминированностью, т.е. отсутствием вероятностного развития событий.
· Конечность (завершенность, результативность) – алгоритм должен выдать результат за конечное число шагов.
· Массовость – алгоритм мог быть применен для решения не только одной конкретной задачи, но и класса однотипных задач. Другими словами, алгоритм должен без переделки позволять многократное решение задачи с разными вариантами исходных данных. Например, решение квадратного уравнения с различными значениями коэффициентов.
1.4 Элементы блок-схемы
Блок-схемой называется графическое изображение алгоритма, т.е. описание хода решения задачи с помощью геометрических фигур и прямых линий.
Блок-схема строится с использованием следующих фигур:
1) эллипс - показывает начало или конец алгоритма (имеет один выход или один вход). Разрешается использовать английские слова begin - начало, end - конец.
2) параллелограмм - показывает ввод или вывод данных
(имеет один вход и один выход). Можно использовать английские слова read - ввод, write - вывод.
3) прямоугольник - показывает вычисления, действия, присваивания (имеет один вход и один выход). Введем обозначания:
· один символ = (равно) означает сравнение, равенство;
· два символа := (двоеточие и равно) означает присваивание.
4) ромб - показывает проверку условия; ответом является «да» или «нет» (имеет один вход и два выхода). Один из выходов снабжается надписью «да», второй выход может иметь или не иметь надпись «нет». Иногда слова «да-нет» заменяют значками «+» и «−».
5) шестиугольник - показывает изменение счетчика
при циклических вычислениях (имеет два входа и два выхода). Многократно повторяющаяся часть называется «телом цикла». Запись k :=1,n означает, что k изменяется от 1 до n , т.е. k =1,2,3,…,n. Тело цикла выполняется n раз. При k > n происходит выход из цикла. Изменение счетчика можно также записать в виде k := k1, k2, h; где k1 - начальное значение; k2 - последнее значение; h – шаг изменения. Если h=1, то его можно не указывать.
Примечания: 1) внутри тела цикла не разрешается изменение счетчика k; 2) шестиугольник называют блоком модификации.
Приведенные 5 фигур вполне достаточны для составления блок-схем в учебных целях. Полный перечень геометрических фигур, используемых в блок-схемах, приводится в стандартах ГОСТ 19.701-90, ГОСТ 19.002-80, ГОСТ 19.003-80.
1.5 Структуры алгоритмов
При разработке алгоритма могут встретиться следующие три структуры хода вычислений. Эти структуры алгоритмов носят названия: 1) линейный, 2) ветвление, 3) цикл. Структуры алгоритмов можно наглядно показать с помощью блок‑схемы.
1.5.1 Линейная структура
Структура алгоритма называется линейной, когда все действия выполняются последовательно одно за другим, как бы в одну линию (рисунок 1.1). Например, вычисление суммы и произведения двух чисел. Опишем алгоритм: 1) ввести числа a и b, т.е. узнать их значения; 2) вычислить сумму sum = a+b и произведение pr = a*b; 3) вывести результат вычислений.
Рисунок 1.1 – Пример линейной структуры.
1.5.2 Структуры ветвления
Структура алгоритма называется разветвляющейся, если в ходе выполнения алгоритма производится проверка некоторого условия и от результата проверки условия («да» или «нет») дальнейшее действие идет по одной или другой ветви. Различают 4 вида структуры ветвления, которым присваивают следующие короткие названия: 1) «если-то», 2) «если-то-иначе», 3) «выбор», 4) «выбор-иначе».
Рассмотрим подробно эти структуры ветвления.
1.5.2.1 Структура ветвления «если-то». Если проверка условия показывает «да», то выполняется указанное действие (рисунок 1.2). Например, если x > 0, то принять y = 1/x.
Рисунок 1.2 – Структура ветвления «если-то».
1.5.2.2 Структура ветвления «если-то-иначе». Если проверка условия показывает «да», то выполняется действие1, иначе выполнится действие2 (рисунок 1.3). Например, если первое число больше второго, то максимальным будет первое число, иначе максимальным будет второе число. Опишем алгоритм: если a > b , то max := a, иначе max := b.
Рисунок 1.3 – Структура ветвления «если-то-иначе».
1.5.2.3 Структура ветвления «выбор». Конструкция «выбор» формулируется так: При выполнении условия1, осуществляется действие1; при выполнении условия2, осуществляется действие2; и так далее; при выполнении условияN, осуществляется действиеN (рисунок 1.4).
Рисунок 1.4 – Структура ветвления «выбор».
1.5.2.3 Структура ветвления «выбор-иначе». Конструкция «выбор-иначе» формулируется так: При выполнении условия1, осуществляется действие1; при выполнении условия2, осуществляется действие2; и так далее; при выполнении условияN, осуществляется действиеN; иначе осуществляется действиеN2 (рисунок 1.5).
Рисунок 1.5 – Структура ветвления «выбор-иначе».
Пример 1.1.При заданном номере месяца h, указать время года. Времена года это весна, лето, осень, зима. При неправильно заданном месяце, указать на ошибку (рисунок 1.6).
Рисунок 1.6 − Фрагмент блок-схемы к примеру 1.1.
1.5.3 Циклическая структура
Структура алгоритма называется циклической, когда многократно выполняется некоторая группа однотипных вычислений. Многократно повторяющаяся часть называется телом цикла. Циклический алгоритм всегда состоит из двух частей: первая часть – тело цикла, вторая часть – условие повторения цикла. От взаимного расположения этих частей различают три циклические структуры: 1) цикл с предусловием, 2) цикл с постусловием, 3) цикл с параметром.
1.5.3.1 Циклс предУсловием. Условие повторения цикла располагается перед телом цикла (рисунок 1.7).
Рисунок 1.7 – Циклс предУсловием.
1.5.3.2 Цикл с постУсловием. Условие повторения цикла располагается после тела цикла (рисунок 1.8).
Рисунок 1.8 – Циклс постУсловием.
1.5.3.3 Цикл с параметром. Параметром цикла является переменная, которая отсчитывает количество повторений тела цикла. Чаще всего записывается k :=1,n ; что означает изменение k от 1 до n с шагом 1 (рисунок 1.9).
Рисунок 1.9 – Циклс параметром.
Тело цикла выполняется n раз; при k > n происходит выход из цикла. Параметр цикла можно также записать в виде
k := k1, k2, h; где k1 - начальное значение; k2 - последнее значение; h – шаг изменения. Если h=1, то его можно не указывать. Внутри тела цикла не разрешается изменение параметра k.
Относительно этих трех разновидностей циклических структур отметим следующее. Циклы с предусловием и постусловием применяются при итерационных вычислениях, когда заранее не известно количество повторений тела цикла. При известном количестве повторений тела цикла применяют цикл с параметром.
1.6 Примеры циклических структур
1.6.1 Суммирование чисел
Пример 1.2. Вычислить сумму из n заданных чисел.
Перед составлением алгоритма рассмотрим следующую аналогию. В некоторую корзину S надо сложить n штук заданных чисел (типа бочонок лото). Вначале следует очистить корзину, т.е. S=0. Затем в корзину положить первое число; получим S := S+a1 (читается так: к прежнему значению S прибавить a1 и получить новое значение S=0+a1 =a1). Затем опять S := S+a2 (к прежнему S прибавить a2 и получить новое значение S = a1+ a2 ) и т.д. заполнять нашу корзину.
В этой задаче количество вычислений типа S := S+ak заранее известно, их n штук. Запись S := S+ak означает, что сначала надо выполнить вычисления справа, т.е. S+ak , затем полученный результат присвоить левой переменной S.
Теперь нетрудно описать алгоритм вычисления: 1) ввод n, т.е. узнать количество заданных чисел, 2) S :=0, 3) организовать цикл с параметром k :=1,n и телом цикла из двух действий: ввод ak и вычисление S := S+ak, 4) вывод суммы S (рисунок 1.10).
Рисунок 1.10 − Блок-схема к примеру 1.2.
1.6.2 Задача о пробежке
Пример 1.3. Спортсмен на тренировке пробегает в первый день расстояние S= S1. В каждый следующий день увеличивает длину пробежки на pr процентов по отношению к вчерашнему, т.е. приращение расстояния составляет величину p*S, где коэффициент p=pr/100. Таким образом, расстояние пробежки следующего дня равно S + p*S. Возникает вопрос, сколько потребуется дней, чтобы пробежать расстояние Sn ?
Например, S1=500 м, p=0,1 (pr=10%); Sn=2000 м. Через сколько дней длина пробежки будет 2000 м ?
Эта задача итерационного характера, здесь заранее неизвестно количество циклических вычислений S := S + p*S. Известно лишь условие завершения цикла, это S ≥ Sn.
Опишем алгоритм вычислений: 1) ввод S1, p, Sn ;
2) в первый день k:=1; S := S1 ; 3) в следующие дни k := k+1; S := S + p*S ; 4) если S ≥ Sn , то выход из цикла, иначе переход к 3-му пункту; 5) вывод искомого количества дней n := k.
Рассмотрим выполнение алгоритма по шагам.
1) Ввод S1=500, p=0,1; Sn=2000.
2) k :=1, S := S1=500;
3) k := k+1 =1+1 =2, S := S + p*S =500+0,1*500 =550;
4) k := k+1 =2+1 =3, S := S + p*S =550+0,1*550 =605;
5) k := k+1 =3+1 =4, S := S + p*S =605+0,1*605 =665,5;
- - - - - - - - -
17) k := k+1=15+1=16, S := S + p*S =1898,7+0,1*1898,7 = 2088,6;
Таким образом, результат будет достигнут в 16-й день (расстояние более 2000 м).
Блок-схема решения данной задачи представлена на рисунке 1.11.
Рисунок 1.11 − Блок-схема к примеру 1.3.
1.7 Вложенные циклы
Может оказаться так, что тело цикла содержит внутри себя некоторый циклический процесс. В таком случае говорят о вложенных циклах. Уровень вложения может быть различным.
Например, вычисление суммы чисел в матрице описывается вложенным циклом в 2 уровня: внешний цикл описывает перемещение по строкам, а внутри строки перемещение по столбцам представляет собой внутренний цикл.
Пример 1.4. Обозначим матрицу A = { aij}, где i :=1,n; j :=1,m; n,m – размеры матрицы; i – номер строки; j – номер столбца; S – сумма элементов матрицы.
Сумму чисел матрицы вычисляем по аналогии с примером 1.2. Сначала выделяем строку и суммируем числа в этой строке. Строка i меняется от 1 до n. Внутри строки элементы меняются по индексу j от 1 до m. Перемещения по строкам образуют внешний цикл, перемещения внутри строки образуют внутренний цикл (рисунок 1.12).
Рисунок 1.12 − Фрагмент блок-схемы к примеру 1.4.
1.8 Об эффективности алгоритма
Выше были указаны основные свойства алгоритма. Обобщением этих свойств является эффективность алгоритма. Рассмотрим это понятие на примере нахождения максимального числа max среди заданных чисел.
Пример 1.5. Нахождения максимального числа max из двух чисел a, b. Алгоритм: 1) ввод чисел, 2) сравнение двух чисел, 3) вывод результата (рисунок 1.13).
Рисунок 1.13 – Поиск max (алгоритм «если-то-иначе»).
.
Пример 1.6. Нахождения максимального числа max из трех чисел a, b, c. Алгоритм: 1) ввод чисел; 2) сравнение двух чисел a и b; 3) если направление «да», то сравнение a и c, иначе сравнение b и c; 4) нахождение max из двух чисел; 5) вывод результата.
Для трех чисел (например, 3,4,5) возможны шесть разных вариантов (var) перестановок чисел.
| a | ||||||
| b | ||||||
| c | ||||||
| Var |
На блок-схеме (рисунок 1.14) выносками показаны номера вариантов сочетаний чисел в данном направлении после выполнения сравнения.
Рисунок 1.14 – Поиск max (алгоритм «если-то-иначе»).
Составленная блок-схема не содержит ошибок и приводит к правильному результату. Однако такая блок-схема нам не нравится: она кажется сложной для восприятия и содержит дублирующий блок с присвоением. Тем не менее, в связи с отсутствием ошибок, продолжим рассуждения.
Пример 1.7. Нахождения максимального числа max из 4-х чисел a, b, c, d. Здесь возможны 24 варианта перестановок чисел.
| a | ||||||||||||
| b | ||||||||||||
| c | ||||||||||||
| d | ||||||||||||
| Var | ||||||||||||
| a | ||||||||||||
| b | ||||||||||||
| c | ||||||||||||
| d | ||||||||||||
| Var |
Рассуждая аналогично предыдущему примеру, будем строить следующий алгоритм: 1) ввод 4-х чисел; 2) на первом уровне сравнение двух чисел a > b; 3) в каждом из направлений «да-нет» по 12 вариантов сочетаний чисел; если направление «да», то в этой ветви на втором уровне сравнение a > c; 4) на третьем уровне два сравнения a > d (8 вариантов чисел)
и c > d (4 варианта чисел); и т.д. (рисунок 1.15).
Рисунок 1.15 – Поиск max (алгоритм «если-то-иначе»).
Эта блок-схема не содержит ошибок, однако она сложна для восприятия. Можно окончательно запутаться при построении блок-схемы поиска max , например, из 15 чисел. Делаем вывод: поиск max по алгоритмам, приведенным в примерах 1.5-1.7, неэффективен.
При поиске max из двух чисел, неэффективность алгоритма не замечается и не проявляется. Принятая за основу идея поиска max из двух заданных чисел, с использованием структуры ветвления «если-то-иначе», оказывается неудачной для большего количества чисел. Приведенная идея поиска max путем сравнения заданных чисел между собой по схеме «если‑то-иначе», оказалась неэффективной.
Пример 1.8. Рассмотрим другую идею поиска max из двух чисел. Опишем алгоритм: 1) ввести оба числа; 2) первое число принять за max; 3) второе число сравнить с max, используя ветвление «если‑то»; 4) вывод max (рисунок 1.16).
Рисунок 1.16 – Поиск max (алгоритм «если-то»).
Пример 1.9. Поиск max из трех чисел. Опишем алгоритм: 1) ввести числа; 2) первое число принять за max; 3) второе число сравнить с max по схеме «если‑то»; 4) аналогично, третье число сравнить с max; 5) вывод max (рисунок 1.17).
Рисунок 1.17 – Поиск max (алгоритм «если-то»).
Теперь сравните алгоритмы поиска max в примерах 1.5, 1.6 и в примерах 1.8, 1.9. Эффективность последних алгоритмов очевидна – они чрезвычайно просты для восприятия и понимания. Основная идея следующая: первое число принимается за max, затем остальные числа поочередно сравниваются с max по схеме «если‑то»; сравниваются числа не между собой, а сравнивается очередное число с тем значением max, которое определилось на предыдущем шаге.
Пример 1.10. Поиск max из n чисел: a1, a2,…, ak,…, an ; Опишем алгоритм: 1) ввод n; 2) ввод a1 ; max := a1 ; 3) организовать цикл с переменной k, которая изменяется
от 2 до n, т.е. k := 2, n и с телом цикла: ввод ak и сравнение ak > max по схеме «если‑то»; 4) вывод max. Всё очень просто и понятно (рисунок 1.18).
Таким образом, будем считать алгоритм эффективным, если он компактный и простой для восприятия и вычисления.
В книге Дональда Кнута «Искусство программирования», приводится следующее определение: «Алгоритм считается эффективным, если все его операции достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги» [1].
Разработка эффективного алгоритма является творческой работой, направленной на поиск ответа кратчайшим путем.
Пример 1.11. Известен случай из биографии великого математика Карла Фридриха Гаусса. Учитель младших классов дал задачу: сложить числа от 1 до 100. Ученики, кроме одного Карла, стали суммировать поочередно все числа (по схеме нашего примера 1.2). Юный Гаусс обратил внимание на то, что сумма двух крайних чисел дают одинаковый результат: 1+100=101; 2+99=101; 3+98=101, и т.д.; таких слагаемых 50 штук, половина всех чисел. Гаусс первым дал ответ = 101*50 =5050. Алгоритм Гаусса для вычисления суммы целых чисел от 1 до n по формуле S=(1+n)*n/2 оказался более эффективным, чем схема примера 1.2 (рис.1.2). Количество вычислений по схеме примера 1.2 зависит от n, а по алгоритму Гаусса только одно вычисление по формуле.
Примечание: формула Гаусса верна только для непрерывного ряда целых чисел от 1 до n. Алгоритм же суммирования по схеме примера 1.2 может применяться для произвольного набора чисел, в этом смысле, он наиболее эффективен.
Рисунок 1.18 − Блок-схема к примеру 1.10.
(поиск max из n чисел).
Примеры 1.8-1.11 завершают рассмотрение вопроса об эффективности алгоритма.
1.9 Алгоритм укрупненный и подробный
В блок-схемах фигура прямоугольника указывает на выполнение вычислений, связанных с присваиванием или на выполнение группы действий. В частности, прямоугольником показывается тело цикла – многократно повторяющаяся часть. Иногда, для удобства восприятия алгоритма, некоторую его часть обозначают прямоугольником и затем эту часть показывают отдельно в подробном исполнении.
Например, блок-схема вычисления суммы чисел в примере 1.2 показана подробно. Разложим эту схему на две части: укрупненная схема и подробная ссылка на укрупненный блок (рисунок 1.19).
а) б) Блок суммирования
Рисунок 1.19 − Блок-схема суммирования n чисел;
а) укрупненная схема,
б) подробная схема блока суммирования.
Известно, что чем более подготовлен исполнитель для решения задачи, тем менее подробно можно описывать алгоритм. Например, решение квадратного уравнения (определение корней) для школьника-восьмиклассника следует описать более подробно, чем для 11-классника. Как было сказано, это следует из уровня подготовки исполнителя. Исполнитель-человек обладает определенным багажом знаний, способен логически мыслить и ему порой достаточно подсказать идею, чтобы прийти к верному решению. Исполнитель-компьютер – это техническое устройство (набор элементов из железа, пластмассы, проводов и т.п.), по существу «нечто безмозглое», ничего самостоятельно «думать и решать» не способен; компьютер может только неукоснительно выполнять последовательность простейших команд, заранее составленных человеком. Поэтому для исполнителя-компьютера необходимо составлять подробнейший алгоритм действий на машинном языке.
Таким образом, для исполнителя-человека алгоритм составляется либо в укрупненном, либо в подробном виде, в зависимости от его уровня знаний, а для исполнителя-компьютера алгоритм всегда составляется в подробном виде, в форме компьютерной программы.
1.10 Контрольные вопросы:
1. Что называется алгоритмом ?
2. На что обратить внимание в определении понятия алгоритм?
3. Какими основными свойствами должны обладать алгоритмы?
4. Исполнитель алгоритма.
5. Формы описания алгоритма.
6. Какая форма описания алгоритма является наиболее продуманной и подробной? и почему?
7. Что называется алгоритмизацией?
8. Что называется программированием?
9. Что такое блок-схема?
10. Какие вычислительные структуры могут содержать алгоритмы?
11. Какова структура линейного алгоритма?
12. Из каких блоков составляется линейная структура алгоритма?
13. Какая характерная особенность разветвляющейся структуры алгоритма?
14. Из каких блоков составляется разветвляющаяся структура алгоритма?
15. На какие виды подразделяется структура ветвления?
16. Какой вычислительный процесс называется циклическим?
17. Из каких двух частей состоит циклическая структура алгоритма?
18. На какие три вида подразделяется циклическая структура?
19. Для каких задач следует использовать цикл с параметром?
20. В каких задачах используется цикл с предусловием или постусловием?
21. Что означают записи k := 1,n или k := k1, k2, h ?
22. Что означают записи S := S+a и S = a+b ?
23. Что значит вложенный цикл?
24. Что понимается под эффективностью алгоритма?
2 ПРИМЕРЫ СОСТАВЛЕНИЯ БЛОК-СХЕМ
2.1 Решение квадратного уравнения
Пример 2.1. Определить корни квадратного уравнения
Опишем алгоритм: 1) ввести коэффициенты a,b,c; 2) вычислить дискриминант d=b2-4ac; 3) если d ≥ 0, то вычислить корни
и вывести их значения, иначе вывести сообщение «корней нет» (рисунок 2.1).
| начало |
| конец |
| d:= b2 - 4ac |
| d ≥ 0 |
| вычислить x1, x2 |
| нет |
| вывод «корней нет» |
| ввод a,b,c |
| да |
| вывод x1, x2 |
Рисунок 2.1 − Решение квадратного уравнения
2.2 Вычисления в одномерной последовательности
Пример 2.2. Для заданной последовательности чисел найти сумму всех чисел, сумму отрицательных чисел и их количество, сумму положительных чисел и их количество.
Обозначения: n – количество чисел; a1, a2,…, ak,…, an - последовательность заданных чисел; k := 1,n - индекс k меняется от 1 до n; S - сумма всех чисел; S1 , t – сумма и количество отрицательных чисел; S2 , p – сумма и количество положительных чисел; S2 = S – S1 ; p = n – t;
За основу берем схему суммирования n чисел (см. рисунок 1.10) и добавляем блок суммирования отрицательных чисел, при этом суммируем также их количество. Блок-схема данной задачи приведена на рисунке 2.2.
а) б)
Рисунок 2.2 − Блок-схема к примеру 2.2;
а) укрупненная схема,
б) подробная схема блока суммирования.
Пример 2.3.Вычислить сумму следующего ряда
Данный ряд убывающий и ограниченный. Найти сумму ряда и количество членов n.
Опишем алгоритм: 1) вначале примем k=0, сумма S=0; 2) берем k := k+1; 3) вычисляем ak ; 4) если ak > 10-1, то вычислить S:= S+ak и перейти к пункту 2, иначе переход к пункту 5; 5) вывод S и k ; последнее значение k есть n.
| начало |
| k := 0; S := 0; |
| конец |
| вычислить ak |
| k := k+1 |
| ak > 10 -1 |
| S:= S+ak |
| нет |
| вывод S, k |
Рисунок 2.3 − Блок-схема к примеру 2.3.
Пример 2.4. Заданы две последовательности чисел ak , bk , k := 1,n . Вычислить элементы третьей последовательности по формуле ck = ak - 2bk .
Рисунок 2.4 − Блок-схема к примеру 2.4.
2.5 Вычисление значений функции
Пример 2.5. Вычислить значения следующей функции. На отрезке x = [12; 14] с шагом h = 0,2 задана функция
| x |
| 1 2 3 4 |
| n k |
Здесь k := 1,n - номера точек на оси x;
n = (14 – 12)/0,2 +1 = 11 - количество точек на оси.
Вычислить значения функции в заданных точках.
Решение: Значения x в точках разбиения оси известны: x = 12; x := x + 0,2; и т.д. до x = 14. Для каждого значения x надо вычислить y. Это циклический алгоритм. Телом цикла является вычисление y по верхней или нижней формуле.
Покажем все три циклические структуры: 1) цикл с предусловием, 2) цикл с постусловием, 3) цикл с параметром (рис. 2.5 – 2.6).
а) цикл с постУсловием б) тело цикла
Рисунок 2.5 − Блок-схема к примеру 2.5
а) цикл с предУсловием б) цикл с параметром k
Рисунок 2.6 − Блок-схема к примеру 2.5
2.6 Поиск max и min
Пример 2.6. Найти max, min и их местоположение в последовательности из n чисел ak , индекс k := 1, n;
Обозначим:
r - местоположение max, т.е. max = ar ;
t - местоположение min, т.е. min = at ;
Алгоритм поиска max был рассмотрен в примере 1.10. Добавим в тот алгоритм поиск min и индексов t, r. В начале принимаем max = a1 , min = a1 , значит r =1, t =1 (рис. 2.7).
а) укрупненная схема б) блок поиска max, min, t, r
| начало |
| ввод n |
| ввод a1 |
| max := a1, r :=1 min := a1, t :=1 |
| Блок поиска max, min, t, r |
| конец |
| Вывод max, min, t, r |
Рисунок 2.7 − Поиск max, min, t, r ;
2.7 Сортировка чисел
Сортировка чисел – это упорядочение заданного массива чисел по их значению (по возрастанию или по убыванию). Сортировка достигается перестановкой чисел местами. Рассмотрим два способа сортировки (например, по возрастанию):
· линейная сортировкарРР
· ,
· пузырьковая сортировка.
1. Метод линейной сортировки заключается в том, чтобы в массиве найти min и его обменять с первым числом. Затем выполняются аналогичные действия с укороченным массивом, кроме первого элемента. Всего таких действий, с поиском min и перестановкой чисел, на единицу меньше размера массива. В учебнике [2] метод линейной сортировки назван методом прямой выборки.
2. Идея пузырьковой сортировки основана на том, что более «легкий» элемент «всплывает выше» по сравнению с соседним элементом. Сравниваются два соседних числа с конца массива и при необходимости переставляются местами. Самый «легкий» элемент (min) оказывается на первом месте. Затем выполняются аналогичные действия с укороченным массивом (кроме первого элемента). Всего таких действий на единицу меньше размера массива.
Пример 2.7. Рассмотрим одномерный массив из n чисел: а1,а2,а3,…,аn; или а= {аk; k :=1,n; }. Здесь запись k :=1,n означает, что k изменяется от 1 до n,
т.е. k =1,2,3,…,n.
2.7.1 Линейная сортировка (по возрастанию).
Пусть n=7 (смотри исходный массив, рисунок 2.8).
1. В строке ищем min и его номер ячейки t. В исходной строке min= a5 = -7; ячейка t=5.
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | ||
| -5 | -7 | исходный массив | ||||||
| -7 | -5 | (1) | этапы | |||||
| -5 | (2) | преобразований | ||||||
| (3) | i | |||||||
| (4) | i =1,2,…, n-1 | |||||||
| (5) | ||||||||
| (6) | ||||||||
| -7 | -5 | отсортирован |
Рисунок 2.8 − Перестановка при линейной сортировке.
2. Делаем перестановку чисел между ячейками 1 и t . Сначала в ячейку t=5 запишем первое число, затем в первую ячейку запишем min.
Для четкого понимания выполняемых действий, примем два следующих обозначения:
· первое – равенство,обозначим символом = (равно);
· второе - замена, т.е. присваивание нового значения, обозначим двумя символами := (двоеточие и равно).
Тогда, перестановка запишется так:
at = a5 := a1 =4; a1 := min = -7. Или at := a1 ; a1 := min .
Данная строка читается так: ячейку с минимальным числом at равным a5 , заменили числом a1 , равным 4; число a1 заменили min , равным -7. Или at заменили на a1 ; a1 заменили на min.
В результате получим a5 =4, a1 = -7 (смотри первый этап преобразования, рисунок 2.8).
3. Аналогично рассмотрим оставшуюся часть массива, т.е. кроме первой ячейки (смотри этапы преобразований):
(2-этап): первый элемент остатка - это a2 =8;
min=a3= -5; ячейка t=3;
перестановка at := a2 ; a2 := min; результат a3 =8, a2 = -5;
(3-этап): первый элемент остатка - это a3 =8,
min= a5 = 4; ячейка t=5;
перестановка at := a3 ; a3 := min; результат a5 =8, a3 = 4;
(4-этап): первый элемент остатка - это a4 =7,
min= a7 = 6; ячейка t=7;
перестановка at := a4, a4 := min; результат a7 =7, a4 = 6;
(5-этап): первый элемент остатка - это a5 =8,
min= a7 = 7; ячейка t=7;
перестановка at := a5, a5 := min; результат a7 =8, a5 = 7;
(6-этап): первый элемент остатка - это a6 =9,
min= a7 = 8; ячейка t=7;
перестановка at := a6, a6 := min; результат a7 =9, a6 = 8;
4. Таким образом, всего n-1 =6 этапов преобразований. На каждом этапе i =1,2,…, n-1 выполняются два действия:
· первое – поиск min и номера ячейки t,
· второе – перестановка at := ai, ai := min; (рисунок 2.9).
Рисунок 2.9 – Преобразования массива
при линейной сортировке.
Подробный алгоритм поиска min и t рассмотрен в предыдущем примере 2.6 (см. рисунок 2.7). В нашем случае сортировки чисел будет отличие в алгоритме поиска; связано это с тем, что у нас выполняется перестановка чисел, в процессе которой мы должны обозревать сразу все числа, и поэтому необходимо сначала ввести все числа в виде массива данных. Индекс элемента массива будем указывать в квадратных скобок.
5. Алгоритм линейной сортировки по возрастанию представлен укрупненной блок-схемой на рисунке 2.10 и подробными схемами на рисунке 2.11.
| Блок сортировки данных |
| конец |
| начало |
| ввод исходного массива данных |
| Вывод результата сортировки |
Рисунок 2.10 − Укрупненная блок-схема сортировки.
| ввод n |
| k > n |
| k := 1, n |
| ввод a[k] |
сортировки:
| k > n |
| k := 1, n |
| вывод a[k] |
в) блок-схема линейной сортировки данных:
| i := 1, n-1 |
| перестановка a[t] := a[i],; a[i] := min |
| min := a[k]; t := k |
| i =n |
| k := i+1, n |
| a[k] <min |
| да |
| min = a[i]; t = i |
| k >n |
| Внешний цикл, (этапы преобразования) |
| Внутренний цикл, (поиск min и его номера t) |
Рисунок 2.11 − Фрагменты схемы сортировки
(приложение к рисунку 2.10).
2.7.2 Пузырьковая сортировка (по возрастанию).
Исходные данные те же.
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | |
| -5 | -7 | исходный массив |
| a6 | a7= | à | ||||
| a5 | a6= | -7 | à | -7 | ||
| a4 | a5= | -7 | à | -7 | ||
| a3 | a4= | -5 | -7 | à | -7 | -5 |
| a2 | a3= | -7 | à | -7 | ||
| a1 | a2= | -7 | à | -7 |
1. С конца массива сравниваются два соседних числа и при необходимости переставляются местами – меньшее значение ставится впереди. Самый «легкий» элемент min=-7 оказывается на первом месте.
| a[k-1]>a[k] |
| перестановка |
| min := a[k]; a[k]:=a[k-1]; a[k-1]:=min; |
| k := n, i+1, -1 |
| да |
| k = i |
Рисунок 2.12 − Блок-схема циклического
«проталкивания легкого элемента наверх».
Здесь k := n, i+1, -1 означает, что k изменяется от n до i+1 с шагом -1, т.е. k убывает до значения i+1. На первом этапе i =1 параметр цикла k принимает значения 7, 6, 5,…,2.
2. Аналогично рассмотрим оставшуюся часть массива, т.е. кроме первой ячейки (смотри этапы преобразований, рисунок 2.13):
| -7 | -5 | (1) | этапы | |||||
| -5 | (2) | преобразований | ||||||
| (3) | i | |||||||
| (4) | i =1,2,…, n-1 | |||||||
| (5) | ||||||||
| (6) | ||||||||
| -7 | -5 | отсортирован |
Рисунок 2.13 – Преобразование массива
при пузырьковой сортировке.
Алгоритм этапов преобразований можно показать следующей схемой (рисунок 2.14):
| i := 1, n-1 |
| Тело цикла «проталкивание легкого элемента наверх» |
| i = n |
Рисунок 2.14 – Блок-схема этапов преобразований.
3. Окончательный алгоритм сортировки может быть представлен укрупненной схемой (см. рисунок 2.10) и подробной блок-схемой самой пузырьковой сортировки по возрастанию (рисунок 2.15).
| Внешний цикл, этапы преобразования |
| i := 1, n-1 |
| min := a[k]; a[k]:=a[k-1]; a[k-1]:=min; |
| i =n |