Любой человек ежедневно встречается с множеством повседневных и профессиональных задач. Для решения многих из них существуют определенные правила (инструкции, предписания), объясняющие, как решать определенную задачу. В процессе решения можно применять готовые правила или формулировать собственные. Чем точнее и понятнее описаны правила решения задач, тем быстрее человек овладеет ими и будет эффективнее их применять. Решение многих задач человек передает техническим устройствам – ПК, автоматам, роботам и т. д. Их применение предъявляет очень строгие требования к точности описания правил и последовательности выполнения действий. Поэтому разрабатываются специальные алгоритмы для четкого и строгого описания различных правил.
Алгоритмизация — это раздел информатики, изучающий методы и приемы построений алгоритма, а также их свойства. Она является основным, базовым компонентом компьютерной грамотности в совре¬менном компьютерном мире.
Для достижения положительных результатов важную роль играет умение разрабатывать оптимальный алгоритм решения поставленной задачи, что требует от исполнителя наличия определенных навыков алгоритмизации и системного анализа, а также знания математики, физики, химии, экономики и других дисциплин.
Основу деятельности специалиста практически любой области составляет умение ставить задачи, разрабатывать алгоритмы, получать решения, производить анализ полученных данных и делать выводы. Поэтому в своей будущей профессиональной деятельности студенты должны уметь грамотно применять персональный компьютер (ПК) для решения научных и производственных задач.
Понятия и свойство алгоритмов
Понятие алгоритма. Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi — латинского написания имени Мухаммеда аль-Хорезми (787 — 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел — вот первые алгоритмы в математике. Правила алгебраических преобразований, способы вычислений корней уравнений также можно отнести к математическим алгоритмам.
Существует множество определений алгоритма приведем два из них:
Определение 1. Алгоритм — система формальных правил (команд), однозначно определяющих процесс решения задачи.
Определение 2. Алгоритм — конечная последовательность общепонятных предложений, формально, не требующая проявления человеческой изобретательности, исполнение которой позволяет за конечное время получить решение некоторой задачи из некоторого класса задач.
Алгоритм обладает рядом характерных свойств:
- Наличие ввода и вывода — свойство, заключающееся в наличии исходных данных для решения задачи и формировании алгоритмом одного или нескольких результатов; другими словами, алгоритм должен иметь входные и выходные данные. Перед разработкой алгоритма следует точно, однозначно определить входные и выходные данные: их состав, типы, диапазоны возможных значений.
- Детерминированность (определенность) — свойство, заключающееся в том, что каждое действие, правило алгоритма должно быть точно (однозначно) определено. Для однозначно понимаемой формы записи действий используют языки программирования.
- Конечность — свойство, заключающееся в том, что работа алгоритма должна заканчиваться после выполнения конечного числа действий (шагов, операций). Типичными действиями алгоритма являются ввод данных, обработка данных (вычисление значений, сортировка чисел и др.), вывод (запись) результатов в определенной форме (например, в форме таблицы или графика).
- Массовость — свойство, заключающееся в возможности решения задачи с различными вариантами наборов исходных данных. Наличие этого свойства имеет важное практическое значение, так как обес¬печивает возможность получения различных результатов, используя однажды разработанный алгоритм.
- Эффективность — свойство, заключающееся в использовании для алгоритма достаточно простых действий, которые могут быть выполнены точно и за конечный отрезок времени. Алгоритм должен быть «хорошим» с точки зрения некоторых критериев: продолжительность работы, требуемый объем памяти и др. Для этого в процессе разработки должен выполняться анализ алгоритмов.
Представление алгоритма
Для представления алгоритмов могут использоваться различные формы:
• словесное описание,
• словесно — формульное описание,
• блок-схема (схема программы, схема данных и другие),
• запись на языке программирования,
• запись в системе команд ЭВМ и другие.
Не все перечисленные формы представления строго соответствуют вышеприведенному определению, однако они находят практическое применение.
В процессе представления алгоритмов в общем случае выполняется переход от одной формы представления к другой в вышеуказанном порядке.
Словесное описание — представление алгоритма с помощью литературного или профессионального языка. Такое описание используется для изложения общей идеи, метода решения задачи. Это может быть инструкция по обработке документов, технология подготовки отчетов и тому подобные документы, в которых излагается последовательность действий, понятных исполнителю. Например, расчет бухгалтером почасовой заработной платы может быть описан следующим образом:
• получить табели учета рабочего времени сотрудников из подразделений,
• проверить правильность данных (количество часов, отработанных каждым сотрудником, не должно превышать количества рабочих часов в текущем месяце и др.),
• умножить тарифную ставку сотрудника (рублей/час) на количество отработанных часов,
• добавить начисления на зарплату (надбавки за руководство подразделением, премиальные и др.),
• вычесть удержания из заработной платы (подоходный налог, отчисления в пенсионный фонд, выплаты на погашение ссуды и др.),
• вычислить суммы по подразделениям, по предприятию,
• оформить ведомости на выдачу заработной платы по установленной форме.
Словесно-формульное описание алгоритма отличается от вышеприведенного словесного описания тем, что в нем используются математические формулы.
Блок-схема алгоритма — представление алгоритма в графической форме, в которой действия над данными изображаются в виде геометрических блоков с поясняющими надписями, а последовательность действий указывается соединительными линиями. Эта форма используется для наглядного представления процессов обработки данных, особенно в случаях с большим количеством проверок логических условий и разветвлений процессов (выбора последующих действий в зависимости от результатов предыдущих). Блок-схемы имеют несколько разновидностей. Государственный стандарт (ГОСТ) 19.701 устанавливает следующие виды графических программных документов:
• схема программ,
• схема данных,
• схема взаимодействия программ,
• схема работы системы,
• схема ресурсов системы
Программа на алгоритмическом языке — запись алгоритма с использованием операторов выбранного языка программирования. Текст программы, написанной на языке высокого уровня, понятен человеку (программисту). После преобразования этого текста в программу, состоящую из команд ЭВМ, можно выполнить решение задачи по разработанному алгоритму на ЭВМ. Для составления программ на каком-либо языке программирования следует изучить этот язык (алфавит, операторы), приемы использования для решения типовых задач.
Для изображения блок схемы используются следующие графические блоки
Линейные алгоритмы
В зависимости от состава операций и последовательности выполняемых действий алгоритмы принято разделять на:
- линейные,
- разветвляющиеся,
- циклические.
Основным элементарным действием в вычислительных алгоритмах является присваивание значения переменной величине. Если значение константы определено видом ее записи, то переменная величина получает конкретное значение только в результате присваивания. Присваивание может осуществляться двумя способами: с помощью команды присваивания и с помощью команды ввода.
Рассмотрим как пример правила деления обыкновенных дробей и опишем их так:
- Числитель первой дроби умножить на знаменатель второй дроби.
- Знаменатель первой дроби умножить на числитель второй дроби.
- Записать дробь, числитель которой есть результат выполнения пункта 1, а знаменатель — результат выполнения пункта 2.
В алгебраической форме это выглядит следующим образом:
Построим алгоритм деления дробей для ЭВМ. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочис¬ленные переменные a, b, c, d. Результатом — также целые величины m и n.
Формат команды присваивания следующий:
переменная:=выражение
Знак «:=» нужно читать как «присвоить».
Команда присваивания обозначает следующие действия, выполняемые компьютером:
- Вычисляется выражение.
- Полученное значение присваивается переменной.
В приведенном выше алгоритме присутствуют две команды присваивания. В блок-схемах команда присваивания записывается в прямоугольнике. Такой блок называется вычислительным блоком.
В описаниях алгоритмов необязательно соблюдать строгие правила в записи выражений. Их можно писать в обычной математической форме. Это еще не язык программирования со строгим синтаксисом.
В приведенном алгоритме присутствует команда ввода:
ввод a,b,c,d
В блок-схеме команда ввода записывается в параллелограмме — блоке ввода-вывода. При выполнении данной команды процессор прерывает работу и ожидает действий пользователя. Пользователь должен набрать на устройстве ввода (клавиатуре) значения вводимых переменных и нажать на клавишу ввода Enter. Значения следует вводить в том же порядке, в каком соответствующие переменные расположены в списке ввода. Обычно с помощью команды ввода присваиваются значения исходных данных, а команда присваивания используется для получения промежуточных и конечных величин.
Полученные компьютером результаты решения задачи должны быть сообщены пользователю. Для этих целей предназначена команда вывода:
вывод m,n
С помощью этой команды результаты выводятся на экран или на устройство печати на бумагу.
Поскольку присваивание является важнейшей операцией в вычислительных алгоритмах, обсудим ее более подробно.
Рассмотрим последовательное выполнение четырех команд присваивания, в которых участвуют две переменные величины а и b.
В приведенной ниже таблице напротив каждой команды присваивания указываются значения переменных, которые устанавливаются после ее выполнения.
| Команда | a | b |
| a:=1 | 1 | — |
| b := 2 * а | 1 | 2 |
| а:=b | 2 | 2 |
| b:=а + b | 2 | 4 |
Этот пример иллюстрирует три основных свойства команды присваивания:
- пока переменной не присвоено значение, она остается неопределенной;
- значение, присвоенное переменной, сохраняется в ней вплоть до выполнения следующей команды присваивания этой переменной;
- новое значение, присваиваемое переменной, заменяет ее предыдущее значение.
Рассмотрим один очень полезный алгоритм, который приходится часто использовать при программировании. Даны две величины: X и Y. Требуется произвести между ними обмен значениями. Например, если первоначально было Х= 1, Y= 2, то после обмена должно стать: Х= 2, Y= 1.
Хорошей моделью для решения этой задачи является следующая ситуация: имеются два стакана — один с молоком, другой с водой. Требуется произвести обмен их содержимым. Всякому ясно, что в этом случае нужен дополнительный третий пустой стакан. Последовательность действий будет следующей:
- перелить из первого стакана в третий;
- перелить из второго в первый;
- перелить из третьего во второй.
Цель достигнута!
По аналогии для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача обмена решается последовательным выполнением трех команд присваивания:
| Команда | X | Y | Z |
| Ввод X; Y | 1 | 2 | — |
| Z:=Х | 1 | 2 | 1 |
| Х:=Y | 2 | 2 | 1 |
| Y:=Z | 2 | 1 | 1 |
Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пустым. В результате же присваивания (Х:= Y) переменная, стоящая справа (Y), сохраняет свое значение.
Алгоритм для деления дробей имеет линейную структуру. В нем все команды выполняются в строго однозначной последовательности, каждая по одному разу. Линейный алгоритм составляется из команд присваивания, ввода, вывода и обращения к вспомогательным алгоритмам.
И так в линейных алгоритмах для получения результата решения задачи все запланированные действия должны быть последовательно выполнены по одному разу; при этом заданная последовательность действий не изменяется в зависимости от исходных и промежуточных данных.
Разветвляющиеся алгоритмы
На практике очень редко встречается, чтобы последовательность всех требуемых действий была известна заранее. Если на минуту покинуть мир алгоритмизации и программирования, можно спроецировать ветвление на многие жизненные ситуации. Если на улице дождь, человек берёт зонт, если очень жарко, будет выбрана одежда полегче и т. д. Всё зависит от условия выбора. Как тут не вспомнить рыцаря на распутье из русских народных сказок?
«Направо пойдёшь — жену найдёшь, налево пойдешь — богатым будешь, прямо пойдёшь — смерть найдёшь». Подобная ситуация заставляет принимать решения с учётом определённого условия. Если нужна жена, то витязь идёт направо, если богатство, то налево, если жизнь не мила, то прямо. Условия, которые влияют на решение, располагаются между словами «если» и «то».
От значения условий зависит дальнейшее поведение. Когда условие выполняется, оно принимает значение «истина», когда нет — «ложь».
Иногда анализ ситуации и выбор не вызывают особых затруднений, а иногда принять решение очень трудно. А всё потому, что принимающий решение пытается продумать каждый из вариантов и предугадать последствия выбора. Нельзя не вспомнить гроссмейстера, который анализирует позицию на ходы вперёд, прежде чем передвинуть фигуру на шахматной доске.
Компьютерные программы и игры тоже построены на выборе действий. А блок-схема при наличии ветвления приобретает иной вид:
Вычислительный процесс называется ветвящимся, если для его реализации предусмотрено несколько направлений (ветвей). Каждое отдельное направление процесса обработки данных является отдельной ветвью вычислений. Ветвление в программе — это выбор одной из нескольких последовательностей команд при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным или конечным результатам. Признак характеризует свойство данных и имеет два или более значений.
Ветвящийся процесс, включающий в себя две ветви, называется простым (рис 6), более двух ветвей — сложным. Сложный ветвящийся процесс можно представить с помощью простых ветвящихся процессов.
Направление ветвления выбирается логической провер¬кой, в результате которой возможны два ответа: «да» — усло¬вие выполнено и «нет» — условие не выполнено.
Структура ВЕТВЛЕНИЕ существует в двух основных вариантах: полное и неполное
Полное ветвление
Предполагает выполнение действий для обеих веток в алгоритме:
Если [условие], то [действие 1], иначе [действие 2]
Структура такого алгоритма представлена на рис.8.
Неполное ветвление
Предполагает выполнение действий только на одной ветви алгоритма (вторая отсутствует):
Если [условие], то [действие]
Структура такого алгоритма представлена на рис.9.
Итак, при разработке разветвляющегося алгоритма необходимо учитывать:
• что данный вид алгоритма применяется при наличии операций условного перехода;
• он чаще используется для вычислений функций, заданных несколькими арифметическими выражениями (формулами);
• инструкции в нем выполняются в зависимости от значения условия.
Составим алгоритм решения квадратного уравнения ax2+bx+c=0
Задача хорошо знакома из математики. Исходными данными здесь являются коэффициенты а, b, с. Решением в общем случае будут два корня х1 и х2, которые вычисляются по формуле:
Алгоритм должен обладать важнейшим свойством, предъявляемым к качественным алгоритмам, — универсальностью по отношению к исходным данным. Какими бы ни были значения исходных данных, алгоритм должен приводить к определенному результату и завершать работу. Результатом может быть число, но может быть и сообщение о том, что при определенных данных задача решения не имеет. Недопустимы остановки в середине алгоритма из-за невозможности выполнить какую-то операцию. Упомянутое свойство в литературе по программированию называют результативностью алгоритма (в любом случае должен быть получен какой-то результат).
Чтобы построить универсальный алгоритм, сначала требуется тщательно проанализировать математическое содержание задачи.
Решение уравнения зависит от значений коэффициентов а, b, с. Вот анализ рассмотренной выше задачи (ограничиваемся только поиском действительных корней):
если а = 0, b = 0, с = 0, то любое х — решение уравнения;
если а = 0, b = 0, с ≠ 0, то уравнение действительных решений не имеет;
если а = 0, b ≠ 0, то это линейное уравнение, которое имеет одно решение х = -с/b
если а ≠ 0 и d= b2 — 4ас ≥0, то уравнение имеет два действительных корня (формулы приведены выше);
если a≠0 и d< 0, то уравнение не имеет действительных корней.
Блок-схема алгоритма приведена на рисунке.
В этом алгоритме многократно использована структурная команда ветвления. Общий вид команды ветвления в блок-схемах следующий.
Вначале проверяется условие (вычисляется отношение, логическое выражение). Если условие истинно, то выполняется серия 1 — последовательность команд, на которую указывает стрелка с надписью «да» (положительная ветвь). В противном случае выполняется серия 2 (отрицательная ветвь).
Если на ветвях одного ветвления содержатся другие ветвления, то такой алгоритм имеет структуру вложенных ветвлений. Именно такую структуру имеет алгоритм «Корни квадратного уравнения».
И так разветвляющиеся алгоритмы содержат альтернативные действия процесса обработки данных; в таких алгоритмах состав последующих действий зависит от результатов предыдущих действий (от выполнения некоторых условий).
Циклические алгоритмы
Прежде чем приступить к основной теме параграфа, следует рассмотреть основные определения:
- цикл — повторение одних и тех же действий (шагов).
- тело цикла — последовательность действий, которые повторяются в цикле
- итерация — однократное исполнение тела цикла;
- условие выхода (условие окончания) — выражение, которое определяет, станет ли в очередной раз выполняться итерация либо произойдёт завершение цикла;
- счётчик цикла — переменная, которая сохраняет номер итерации.
Счётчик не обязательно должен содержаться в цикле и счётчик совсем не обязательно должен быть один, то есть условие выхода порой зависит от нескольких изменяемых переменных. Вдобавок к этому, условие выхода иногда зависит от внешних условий (как пример — наступление определённого времени).
Работа любого цикла вне зависимости от его вида включает в себя:
- первоначальную инициализацию циклических переменных;
- проверку условия выхода из цикла;
- выполнение тела;
- обновление циклической переменной на каждой итерации.
Виды циклических алгоритмов
Существует несколько типов алгоритмов циклической структуры.
- Циклы со счетчиком или по параметру, в которых какие-то действия выполняются определенное число раз;
- Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия.
Циклы со счетчиком используют, когда заранее известно какое число повторений тела цикла необходимо выполнить
Циклы в которых сначала проверяется условие, а затем, возможно, выполняется тело цикла называют циклы с предусловием (рис 10 ). Если условие проверяется после первого выполнения тела цикла, то циклы называются циклы с постусловием (рис 11 ).
Цикл с предусловием — это основная, но не единственная форма организации циклических алгоритмов. Другим вариантом является цикл с постусловием. Вернемся к алгоритму решения квадратного уравнения. К нему можно подойти с такой позиции: если a = 0, то это уже не квадратное уравнение и его можно не рассматривать. В таком случае будем считать, что пользователь ошибся при вводе данных, и следует предложить ему повторить ввод. Иначе говоря, в алгоритме будет предусмотрен контроль достоверности исходных данных с предоставлением пользователю возможности исправить ошибку. Наличие такого контроля — еще один признак хорошего качества программы.
В общем виде структурная команда цикл с постусловием или цикл—до. Здесь используется условие окончания цикла. Когда оно становится истинны, цикл заканчивает работу.
Рассмотрим следующую задачу: дано целое положительное число n. Требуется вычислить n! (n-факториал).
На рисунке приведена блок-схема алгоритма. В нем используются три переменные целого типа: n — аргумент; i — промежуточная переменная; F — результат. Для проверки правильности алгоритма построена трассировочная таблица. В такой таблице для конкретных значений исходных данных по шагам прослеживается изменение переменных, входящих в алгоритм. Данная таблица составлена для случая n = 3. Трассировка доказывает правильность алгоритма.
| Шаг | n | F | i | Условие |
| 1 | 3 | |||
| 2 | 1 | |||
| 3 | 1 | |||
| 4 | 1≤3 да | |||
| 5 | 1 | |||
| 6 | 2 | |||
| 7 | 2≤3 да | |||
| 8 | 2 | |||
| 9 | 3 | |||
| 10 | 3≤3 да | |||
| 11 | 6 | |||
| 12 | 4 | |||
| 13 | 4≤3 нет | |||
| 14 | выход |
Выполнение серии команд (тела цикла) повторяется, пока условие цикла истинно. Когда условие становится ложным, цикл заканчивает выполнение. И так циклические алгоритмы многократно используют часть действий для формирования результата решения задачи.
Оставить комментарий