Кузнецов Л.К.

Министерство финансов Российской Федерации

Всероссийская государственная налоговая академия

ИНФОРМАТИКА И ПРОГРАММИРОВАНИЕ

Бакалавры: 230700 "Прикладная информатика"

Язык программирования С++

Лабораторная работа № 03

АЛГОРИТМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА

Автор профессор кафедры "Прикладной информатики в экономике"

кандидат технических наук Л.К. Кузнецов

13 марта 2012 г.

Москва

ВГНА

2012

Лабораторная работа № 03

Алгоритмизация вычислительного процесса

Арифметические операции и математические функции языка С

Битовые операции

Цель работы:

• ознакомиться с понятием алгоритма и способами (средствами) за­писи алгоритмов;

• ознакомиться с описанием алгоритмов в виде блок-схем алгорит­мов и условными графическими обозначениями основных символов блок-схем;

• ознакомиться с алгоритмами типовых вычислительных процессов (линейных, разветвляющихся, циклических);

• научиться составлять простейшие алгоритмы линейных, разветвля­ющихся и циклических вычислительных процессов;

• ознакомиться с основными этапами подготовки и решения задачи на ЭВМ;

• ознакомиться с арифметическими операциями языка С++;

• ознакомиться с приоритетом арифметических операций языка С++;

• ознакомиться с использованием стандартных математических функций в программах на языке С++;

• с побитовыми логическими операциями и операциями сдвига языка C++.

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

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

1. Краткие теоретические сведения

1.1. Алгоритмизация вычислительного процесса

Ниже приводятся минимальные сведения, необходимые только для вы­полнения лабораторной работы.

Одним из важнейших понятий, на котором базируется применение ЭВМ для решения различного рода задач, является понятие алгоритма.

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

а) детерминированностью (определенностью) – набор указаний должен быть точен и понятен для возможных исполните­лей (то есть не оставляющим места для произвола). Эта характеристика обеспечивает однозначность искомого результата процесса при одних и тех же заданных исходных данных. Благодаря этому свойству процесс выполнений алгоритма носит механический характер;

б) массовостью, то есть его пригодностью для решения всех задач данного типа (класса), а не какой-нибудь одной конкрет­ной задачи. (Можно говорить, что алгоритм обладает массовостью, ес­ли он остается справедливым для любого возможного набора исходных данных);

в) результативностью, то есть свойством приводить к получению искомого результата за конечное число достаточно простых шагов (в частности, к выдаче сигнала о том, что алгоритм не применим к имеющимся исходным данным);

г) дискретностью, то есть возможностью расчленения алгоритма на отдельные элементарные акты (шаги, этапы), выполнение которых человеком или машиной не вызывает сомнений.

Рассмотрим в качестве примера алгоритм Евклида.

Пример 3.1. Алгоритм Евклида предназначен для нахождения наиболь­шего общего делителя (НОД) двух положительных целых чисел А и В (не равных нулю). Решение этой задачи может быть получено путем последо­вательного деления вначале большего числа на меньшее, затем меньшего числа на полученный остаток, первого остатка на другой и т.д. до тех пор, пока в остатке не получится нуль. Последний по счету делитель и будет искомым результатом.

Обозначим данные алгоритмизируемой задачи через X и У, приняв в качестве их начальных значений числа А и В, соответственно, и сведем деление к повторному вычитанию. Тогда алгоритм может быть сформули­рован следующим образом:

Этап 1. Положить X, равное А, и У, равное В. Перейти к этапу 2.

Этап 2. Проверить, X больше, чем У ? Если да, то перейти к эта­пу 4, иначе перейти к этапу 3.

Этап 3. Проверить, У больше, чем X ? Если да, то перейти к эта­пу 5, иначе перейти к этапу 6.

Этап 4. От X отнять У и дальше считать эту разность значением X. Перейти к этапу 2.

Этап 5. От У отнять X и далее считать эту разность значением У. Перейти к этапу 2.

Этап 6. Принять X за искомое значение НОД и прекратить процесс вычислений.

Проиллюстрируем использование алгоритма Евклида для нахождения НОД двух чисел: А = 95 и В = 60. Тогда последовательность выполнения этапов алгоритма, а также изменяющиеся значения X и У буду; та­кими, как показано в таблице. 3.1,

Таблица 3.1

Последовательность нахождения НОД для чисел по алгоритму Евклида

X	У	Номер этапа	X	У	Номер этапа	X	У	Номер этапа
95	60	1	35	25	2, 4	10	5	2, 4
95	60	2, 4	10	25	2, 3, 5	5	5	2, 3, 6
35	60	2, 3, 5	10	15	2, 3, 5	НОД = 5

В результате выполнения алгоритма для чисел А = 95 и В = 60 определим, что для них НОД = 5. Массовость алгоритма Евклида состоит в том, что его можно применить к любой паре целых положительных чисел.

Детерминированность алгоритма Евклида обеспечивается тем, что исполнитель умеет выполнять определенные этапами алгоритма действия и однозначно понимает, каких действий требует каждый этап, и, кроме того, знает, откуда начать выполнение алгоритма (с этапа 1). Детерминированность рассматриваемого алгоритма определяется и тем, что как окончательные, так и промежуточные результаты выполнения алго­ритма при одинаковых исходных данных, а также последовательность вы­полнении этапов будут идентичны у разных исполнителей. В частности, при определение НОД для чисел А = 95 и В = 60 процесс вычислений бу­дет всегда идти в последовательности, зафиксированной в таблице 3.1, и с теми же результатами.

Результативность алгоритма Евклида заключается в том, что он определяет процесс, приводящий дал любой пары целых положительных чи­сел к получению искомого НОД за конечное число шагов. Следует отме­тить, что свойство результативности не абсолютно. Например, алгоритм Евклида в приведенной выше формулировке результативен для целых положительных чисел. Попытка применять его к парам чисел, одно из ко­торых, равно нулю, будет безрезультатной: процесс никогда не завер­шится. Не завершится процесс и в том случае, когда одно из чисел от­рицательно. Использование, алгоритма для пары. 0 и 0 дает не верный, ре­зультат: НОД оказывается равным нулю, тогда как для такой пары чисел его вообще не существует. Рассмотренный пример позволяет говорить об области применимости алгоритма, представляющей собой множество ис­ходных данных, для которых алгоритм результативен.

Дискретность алгоритма Евклида состоит в том, что он расчленен на отдельные элементарные этапы, выполнение которых понятно возможному пользователю.

Разработка алгоритма более или менее сложной задачи требует высо­кой квалификации исполнителя и хорошего понимания содержания задачи. Разработка алгоритма является в значительной степени творческим эвристическим процессом, как правило, требует большой эрудиции, изобретательности, не традиционного подхода. Но после того как алгорит­мы разработаны, решение соответствующих задач осуществляется чисто механически и может быть автоматизировано. Этот факт свидетельствует о значении алгоритмов, разработка которых является необходимым этапом автоматизации решения любых задач.

С реализацией алгоритма непосредственно связано умение применять этот алгоритм к конкретным исходным данным решаемой задачи. Такое применение называется алгоритмическим процессом. Этот процесс заключается в переработке исходных данных по правилам, которые определя­ются данным алгоритмом.

Сущность алгоритмизации вычислительного процесса заключается в следующем [3]:

• в выделении автономных этапов вычислительного процесса;

• формальной записи содержания каждого из них;

• в назначении порядка выполнения выделенных автономных этапов вы­числительного процесса;

• проверке действительности (правильности) выбранного алгоритма по реализации заданного метода вычислений.

Чтобы довести до пользователя алгоритмы, в зависимости от их наз­начения, они должны быть формализованы по некоторым правилам (согла­шениям) посредством конкретных изобразительных средств, которые в конечном итоге формируют определенные вычислительные схемы этих ал­горитмов.

К основным изобразительным средствам алгоритмов относятся следу-юшке способы их записи [1-6]:

• словесный;

• формульно-словесный;

• логические схемы алгоритмов (ЛCA);

• граф-схемы алгоритмов (ГCA);

• блок-схемы алгоритмов (БСА);

• решающие таблицы;

• алгоритмические языки программирования.

Коротко приведем некоторые из приведенных способов записи ал­горитмов.

Словесная запись. При словесном способе записи ал­горитма содержание последовательных этапов вычислений задается в произвольной форме на естественном, например, русском языке. Нагляд­ным примером подобной записи может служить уже рассмотренная запись алгоритма Евклида (см. пример 3.1) .

Недостатком словесного способа записи алгоритма является отсутст­вие более или менее строгой формализации наглядности вычислитель­ного процесса. Вместе с тем с помощью данного способа можно описывать алгоритмы-с произвольной степенью детализация.

Формульно-словесная запись. Формульно-словесный способ записи алгоритма основан на задании инструкций о выполнении конкретных действий в определенной последовательности с использованием математических символов и выражений со словесными пояснениями.

В качестве примера рассмотрим формульно-словесную запись уже зна­комого алгоритма Евклида.

Начало.

0) Ввести (А,В).

1) X:= А, У:=В.

2) Если X > У, то перейти к п. 4, иначе перейти к п. 3.

3) Если У > X, то перейти к п. 3, иначе перейти к п.6.

4) X:= X - У; перейти к п. 2.

5) У:= У - X; перейти к п. 2.

6) НОД:=X.

7) Печать (НОД).

Конец.

Здесь вместо фраз типа "от х отнять у и далее считать, что эта разность является значением х" или "считать, что х равен у", ис­пользуются записи "х:=х-у" и "х:=у". Это позволяет белее компакт­но записать пункты 1,4,5 и 6. В пунктах 2 и 3 слово "больше" замене­но математическим знаком > . В некоторых пунктах (0, 1, 6) 0 отсутству­ют явные указания, куда перейти после вычисления. В этих случаях под­разумевается переход к пункту с порядковым номером на единицу боль­шим, чем у исполняемого.

Из приведенного примера видно, что при формульно-словесном спо­собе записи алгоритмов достигается также любая степень детализации вычислительного процесса. Он более компактен и нагляден по сравнению о предыдущим способом, но не является строго формальным. Формульно-словесный способ общепринят при описании различного рода математи­ческих выкладок, доказательстве теорем, легко читается и понятен многим пользователям без специальной подготовки.

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

Самостоятельные этапы алгоритма, выделенные в вычислительной схеме решения задачи, различны по своему назначению. Например, одни участки предусматривают вычисления с помощью арифметических операций. Такие участки называют арифметическими операторами. Другие уча­стки вычислений предназначены для проверки некоторых условий, выпол­нение которых определяет переход от одного этапа переработки данных к другому. Условия, на основании которых устанавливается порядок вы­полнения операторов, принято называть логическими операторами.

Полная последовательность арифметических и логических операторов, задающая весь процесс решения задачи называется логической схемой алгоритма (ЛСА). Эту ЛСА записывают в виде произведения операторов. Чтобы по ЛСА построить программу для решения задачи на ЭВМ, ее до­полняют такими специальными операторами управления, как ввод-вывод данных, печать результатов, останов машины и т.д.

Операторы на схеме обозначаются обычно условными (стандартными) символами. В практике программирования наиболее употребительней яв­ляются следующие символы-операторы:

И - оператор начала;

А - арифметический оператор;

П - оператор печати результатов;

Р - логический оператор;

Я - оператор останова (конца).

Операторы снабжаются номерами-индексами в соответствии с поряд­ком их следования на схеме. Логический оператор записывают как функ­цию, аргументом которой служит проверяемое условие, например Р (X = 0) или Р (X = У) и т.п.

Выполнение алгоритма, заданного ЛСА, начинается с самого левого сомножителя, после этого выполняется оператор, записанный правее от него. Если это логический оператор, то провернется условие, задавае­мое им. При выполнении этого условия очередным становится оператор, стоящий справа от него. В противном случае, когда логическое условие не соблюдается, оператор, подлежащий очередному выполнению, указы­вается стрелкой, ведущей от данного логического оператора к этому очередному оператору, Для компактности записей в начале и конце стрелок можно ставить номера, с помощью которых идентифицированы операторы-преемники управления. Отсутствие передачи управления от оператора слева к соседнему оператору справа обозначается точкой с запятой.

В качестве примера рассмотрена операторная схема записи алгоритма Евклида в рамках указанных выше обозначений символов-операторов.

В таблице 3.2 приведены символы-операторы, используемые в опера­торной схеме алгоритма данного примера.

Таблица 3.2

Значение символов-операторов алгоритма Евклида

№ п/п	Символ- оператор	Этап переработки данных, описываемый символом-оператором
0	И0	Начало алгоритма
1	В1	Ввод исходных данных А, В
2	А2	Вычисление значения X, равного А
3	А3	Вычисления значения У, равного В
4	Р4 (Х>У)	Проверка выполнения логического условия X > У
5	Р5 (У>Х)	Проверка выполнения логического условия У > Х
6	А6	Вычисление значения У, равного разности У - X
7	А7	Вычисление значения X, равного разности Х - У
8	А8	Вычисление значения НОД, равного X
9	П9	Печать результата вычисления значения НОД
10	Я10	Останов машины

Операторная схема алгоритма Евклида применительно к символам, при­веденным в таблице 3.2, имеет вид

И0

В1

А2

А3

Р4 (Х>У)

Р5 (У>Х)

А6

А7

А8

П9

Я10

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

Из существующих способов описания алгоритмов в практике програм­мирования наиболее часто используется описание алгоритмов в виде блок-схем, в первую очередь, из-за его наглядности.

При реализации практических задач составить сразу их алгоритм решения без определенной предварительной работы, как правило., невоз­можно. Здесь обычно необходимо выделить предполагаемые этапы вычис­лительного процесса, определяемого алгоритмом; установить возможные логические связи между ними и четко указать порядок их следования в вычислительной схеме. Кроме того, содержание каждого автономною этапа подлежит дальнейшему описанию и анализу для выявления его элемен­тарных, операций, которые необходимо выполнить в установленном ло­кальном (в пределах этапа) порядке. Все это в целом, в зависимости от различных условий порождает многообразные допустимые направления вы­числительного процесса, поэтому связи между этапами могут быть столь сложными, что не всегда представляется возможным сразу разобраться в структуре разрабатываемого алгоритма, отделить принципиальные связи от несущественных и т. д. Изобразительным средством, предназначенным для разрешения подобных затруднений, являются блок-схемы – рабочий инструмент программиста.

Блок-схемой называется графическое изображение логичес­кой структуры алгоритма, в которой каждый этап провеса переработки данных представляется в виде геометрических фигур (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций (отображаемых функций). Условные графические изображения, используемые для составления блок-схем принято называть символами. Перечень символов, их наименование, отображаемые ими функции, форма и размеры символов определяются ГОСТом I5003-80 [8], а правила выполнения блок-схем – ГОСТом 19002 [7].

Некоторые (наиболее часто употребляемые) символы и их обозначе­ния приведены в таблице 3.3.

Таблица 3.3

Состав, наименование, обозначение символов и отображаемые ими функции

Наименование	Обозначение	Функции
Процесс	в	Блок функции обработки данных любого вида: выполнение определенной операции или группы операций, приводящее к изменению значения, формы, размещения информации или к опреде­лению направления дальнейшего движения
Решение		Блок решения или функции переключательного типа. Внутри блока записывается условие. Блок имеет один вход и два альтернативных выхода: «да» — условие выполнено, «нет» — условие не выполнено
Данные		Блок отображает данные, носитель данных не определен. Преобразование данных в фор­му, пригодную для обработки (ввод) или регистрация результатов обработки (вывод)
Подготовка Модификация		Блок отражает модификацию команды или груп­пы команд с целью воздействия на некоторую последующую функцию (установка переклю­чателя, модификация индексного регистра или инициализация программы) Выполнение операций, меня­ющих команды или группу команд, изменяющих собственно програм­му
Терминатор		Блок отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы). Начало, конец, останов, пре­рывание процесса обработки данных или выполнения програм­мы, вход и выход в подпрограм­мах
Комментарий		Символическое обозначение используется для добавления комментариев. Пунктирные линии в символе комментария связаны с соответству­ющим блоком. Текст комментариев должен быть помещен около скобки Связь между элементом схемы и пояснением
Соединитель		Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители долж­ны быть одинаковыми Указание связи между прерванными линиями потока, связывающими символы
Граница цикла		Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т. д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие
Межстраничный соединитель		Указание связи между разъ­единенными частями алгорит­мов и программ, расположен­ных на разных листах
Предопределенный процесс		Блок для отображения подпрограммы или модуля Использование ранее созданных и отдельно описанных ал­горитмов или программ, вычисления по подпрограмме
Линия потока данных		Символ отображает поток данных или управле­ние Указание последовательности связей между символами

Ниже рассмотрены основные правила построения блок-схем, которые предусмотрены в названных ГОСТах [7, ].

При начертании символов размер а выбирается из ряда 10,15, 20 мм. Размер в = 1,5а. Допускается увеличивать размер а на число, кратное 5.

Блок-схема алгоритма состоит их отдельных блоков (символов), соединенных между собой линиями, указывающими последовательность вы­полнения этих блоков. Линии, которые связывают на схеме блочные сим­волы, принято называть линиями потока информации. Нормальным направ­лением линий потока (следования этапов процесса переработки данных) считается направление сверху вниз и слева направо и стрелками, как правило, не обозначается. Во всех других случаях обозначение направ­ления вычислительного процесса стрелками проставлять обязательно (то есть снизу вверх и справа налево). Линии, связывающие элементы схемы, должны проводиться только по вертикали или по гори зонте! ли, па­раллельно линии внешней рамки схемы и подводиться к середине сторон контура блочного символа. Чтобы показать изменение направления, ли­нии проводятся с изломом под углом 90⁰.

На схеме может быть пересечение двух не связанных линей потока или слияние их. Для отличия ситуаций пересечения и слияния потоков ин­формации используются специальные приемы начертания (см. рис 3.1).

		
	а)				б)
Рис. 3.1. Выполнение на схеме пересечения и слияния линий потоков информации: а) пересечение потоков; б) слияние потоков.

Все блоки блок-схемы имеют сквозную нумерацию.

В дальнейшем в этой и последующих лабораторных работах все блок-схемы алгоритмов должны быть выполнены в соответствию с требо­ваниями указанных ГОСТов [7,8] .

На рис 3.2а в качестве примера записи алгоритмов с использовани­ем блок-схем приведена запись алгоритма Евклида.

Как уже отмечалось, одной из форм записи алгоритмов является ис­пользование алгоритмических языков программирования.

Языки программирования являются изобразительным средством, служащим для непосредственной реализации алгорит­ма на ЭВМ. Язык программирования – это алгоритмически язык, предназначенный для записи программ и данных. В свою очередь, алгоритмический язык определяется как набор символов и система правил образования и однозначного истолкования конструкций из этих символов для задания алгоритмов.

Основной смысл алгоритмических языков состоит в том, что их символы и логика (правила записи) близки к принятым в математике и в естественном русском или английском языках. вместе с тем эта символика и правила строго однозначны и могут автоматически (формализовано) переводиться в команды машины. Представление алгоритмов на алгоритмическом языке - конечная цель программирования.

	1									1
	2									2
	3									3
	Х = А
	У = В										х = 0,5
					9
	4		Да							4
					X=X - Y
	5	Нет			10					5
			Да		Y=Y - X
	6	Нет
	НОД = Х 7									6
										7
	Вывод НОД, А, В
	8
											б)
	а)
Рис. 3.2. Блок-схемы алгоритмов: а) Евклида; б) линейного вычислительного процесса примера 3.2

Реализация алгоритмов на ЭВМ происходит по заранее составленной программе. В общем случае программой называют алгоритм, записанный в форме, воспринимаемой вычислительной машиной. Програм­ма получается путем описания алгоритма решения задачи на конкретном языке программирования.

Языки программирования можно рассматривать в двух группах: машин­ные языки и символические.

Машинный язык - это язык программирования, операторы которого состоят из машинных команд. Каждая машинная команда, пред­ставленная в виде цифрового кода, задает для ЭВМ информацию об од­ной операции: указывает вид операции (сложение, вычитание, сравне­ние и т.д.), адреса (номера) ячеек памяти, в которых хранятся исход­ные данные и результат операции. Программа в данном случае состоит из последовательности машинных команд. Процесс составления человеком программ на машинном языке конкретной ЭВМ принято называть ручным программированием.

Ручное программирование является трудоемким процессом, поэтому для его автоматизации разработаны специальные, более удобные и наг­лядные символические языки, которые делятся на два типа: языки типа Ассемблер и алгоритмические языки высокого уровня.

Язык Ассемблер является языком программирования, ориентированным на конкретную ЭВМ. Вместе с тем в этот язык введены элементы, упро­щающие и автоматизирующие процесс программирования: символьное обо­значение команд и ячеек памяти, широкое использование привычных для человека обозначений и др. Таким образом, программа, описанная на уровне языка Ассемблер, является более осмысленной для программиста по сравнению с программой в машинных кодах. Все это обусловило оп­ределение языка Ассемблер как машинно-ориентированного языка. Отме­тим также, что машинно-ориентированный язык - это язык программиро­вания, отражающий структуру вычислительной машины.

Алгоритмические языки высокого уровня являются языками программи­рования, которые позволяют записывать алгоритмы решения задач неза­висимо от структур, конкретных ЭВМ. Их преимуществом являются также компактность и наглядность записи алгоритма в формульно-словесном виде (в основном), возможность отражения особенностей определенного класса задач в составе средств языка. Использование алгоритмических языков существенно уменьшает трудоемкость программирования и значи­тельно упрощает процесс подготовки задачи для решения на ЭВМ в це­лом.

В настоящее время существует несколько сотен разнообразных алгоритмических языков, что объясняется разнообразием типов машин и главным образом, разнообразием классов решаемых задач. Все алгорит­мические языки могут быть объединены в две группы: проблемно-ориен­тированные языки (ориентированные на класс задач) и машинно-ориентированные (ориентированные на конкретный тип ЭВМ), Проблемно-ориенти­рованные языки программирования отражают особенности класса задач, к описанию которых они приспособлены. В качестве таких унифицированных языков программирования широко используются следующие языки: Форт­ран 1У и Алгол 60 для научно- и инженерно-технических задач, Кобол - для планово-экономических задач, GPSS, Симула, Симскрипт - для за­дач имитационного моделирования, ЛИСП - для задач обработки символьных данных (обработки списков), диалоговый язык Бейсик - для научных и ин­женерных задач на малых и мини-ЭВМ, РПГ - для решения различных задач обработки данных.

В то же время создаются универсальные языки программирования - ПЛ/I, Алгол-68, Паскаль, Ада, С, которые можно использовать для алго­ритмизации задач нескольких классов (проблем).

В системе программирования операционной системы ОС ЕС ЭВМ, наи­более распространенных в нашей стране универсальных ЭВМ, обязатель­но имеются такие трансляторы: Ассемблер, компиляторы фортрана, Ко­бола, ПЛ/1, Алгола-60 и транслятор для языка РПГ. Операционная сис­тема ОС ЕС ЭВМ остается открытой и для других языков программирова­ния, но трансляторы с этих языков включаются по дополнительному со­глашению.

Для нас в дальнейшем будет представлять алгоритмический язык ПЛ/1. Дадим его краткую характеристику. ПЛ/1 является универсальным языком программирования. Он в одинаковой степени удобен как для решения на­учных и инженерных задач, так и для решения различного роде экономи­ческих задач. Кроме того, он может быть использован для решения за­дач в реальном масштабе времени, а также для создания систем програм­мирования.

Другие способы записи алгоритмов, в частности, граф-схемный и ре­шающие таблицы, применяются в программировании весьма редко, поэто­му мы их не рассматриваем.

Чтобы реализовать программу на ЭВМ, записанную на символическом языке, необходимо ее предварительно перевести на машинный язык. Та­кой перевод осуществляет автоматически сама машина по специальной программе, называемой транслятором. По точному опреде­лению транслятор — это программа для перевода программ с одного языка на другой.

В связи с широким использованием ЭВМ в самых различных сферах человеческой деятельности возникла новая научная дисциплина - программирование, которая определяется как раздел прикладной математики, изучающей методы использования вычислительных машин для реализации алгоритмов.

Совокупность всех вычислительных процессов, которая используется для решения различного рода математических, научно-технических и других задач на ЭВМ в общем виде может быть разделена на три груп­пы; линейные, разветвляющиеся и циклические.

Заметим, что такое деление вычислительных процессов является не­сколько условным, так как на практике вычислительный процесс являет­ся, как правило, комбинацией отмеченных типов выделительных процес­сов.

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

Линейным [1-6] называют такой вычислительный процесс в котором самостоятельные этапы вычислений выполняется в линейной последовательности их записи (т.е. в естественном порядке): На блок-схеме линейный вычислительный процесс представляется последователь­ностью блоков. При этом на схеме блоки, выражающие автономные этапы вычислений, размещаются сверху вниз в порядке их выполнения. Для изучаемых процессов характерно, что направления вычислений не зависят от исходных данных или промежуточных результатов.

Пример 3.2. Составить блок-схему вычисления выражения

при значениях аргумента х = 0,5 и заданных значениях а, в, с.

Очевидно, функцию у можно вычислить в такой последовательности. Сначала найти значение выражения (ах² + в)/с, которое обозначим z. Затем определить выражение Sin ( + lnz).

Однако, чтобы, машина определила численное значение функции у, дополнительно необходимо, во-первых, ввести исходные данные (т.е. численные значения коэффициентов а, в, с); во-вторых, присвоить чис­ленное значение переменной х; в-третьих, вычислить численное значение искомой функции у; в-четвертых, вывести значение у из машины и, в-пятых, остановить машину. Таким образом, последовательность выполнения операций будет: 1) ввод исходных данных а, в и с; 2) присвоение аргументу численного значения х = 0,5; 3) вычисление z = (ах² + в)/с и у = Sin ( + lnz); 4) печать результата у; 5) ос­танов машины.

Используем начертание блоков из таблицы 3.3 и изобразим схему алгоритма (рис. 3.2б) . В алгоритме все блоки имеют последователь­ное соединение и выполняются один за другим в порядке следования их номеров.

Обычно алгоритм детализируется до элементарных операций. Так, блок 4 содержит 5 операций, а блок 5 будет включать в себя три под­программы для определения стандартных функций численными методами. Более того, блоки 2 и 6 также связаны с подпрограммами перевода чи­сел из десятичной системы счисления в двоичную при вводе и обратно при выводе. Степень детализации выбирается такой, чтобы установить лишь основную последовательность выполнения машиной задачи. Та по­следовательность, которая очевидна и не представляет трудности для составления программы, не расписывается. В целом детализация в опре­деленной степени произвольная и, как правило, определяется самим программистом, При этом преследуется цель - однозначно формализованно описать последовательность выполнения задачи при минимальной де­тализации вычислительного процесса.

В самих блоках названия операций обычно не записывают. Сама форма блока и его содержание дают полное представление об операци­ях, блок 2 - ввод а, в, с; блок 3 - присвоение аргументу х чис­ленного значения 0,5; блоки 4 и 5 - вычисления функций по приведен­ным формулам; блок 6 - вывод на печать (документ) результата у. Бло­ки I и 7 устанавливают начало и конец вычислительного процесса.

В практике вычислений мало встречается процессов, которые задают­ся только линейной последовательностью блоков (этапов). Как правило, направление вычислительного процесса при решении многих задач зави­сит от исходных данных или промежуточных результатов.

Вычислительный процесс называется разветвляющимся, если в зависимости от исходных условий или промежуточных результатов он реализуется по одному из нескольких, заранее предусмотренных (воз­можных) направлений. А каждое отдельное направление вычислений назы­вается ветвью вычислений.

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

Пример 3.3. Составить блок-схему вычисления выражения

Блок-схема определения одного из двух возможных значений b приве­дена на рис. 3.3а, из которого видно, что в данном примере вычисление происходит по двум взаимно исключающим ветвям. Если соблюдается ус­ловие r < -0,2, то процесс протекает с выполнением блоков 3, 5 и 6, в противном случае будут задействованы блоки 3, 4 и 6. Таким об­разом, выполняется только один из двух блоков 4 или 5, что и требует алгоритм задачи.

Количество возможных направлений вычислений зависит от множества условий, влияющих на реализацию этих направлений. Кроме того, в за­висимости от характера исходных условий или промежуточных результа­тов разветвляющиеся процессы либо обязательно определяют искомый ре­зультат вычислений, либо не всегда определяют такой результат. Например, в блок-схеме рис. 3.3а в любом случае соблюдается одно из двух заданных условий.

Пример 3.4. Составить блок-схему вычислений выражения (рис 3.3б).

В данном примере разветвления организуются по трем возможным ветвям, при чем ни одна из этих ветвей не может выполниться, если значение  >2/3 или   0. В последнем случае значение  не определяется и управление передается на конец вычислительного про­цесса.

Заметим, что блок-схема алгоритма Евклида (рис. 3.1а) также описывает разветвляющийся вычислительный процесс

При решении многих практических задач требуется многократное повторение одних и тех же вычислений, но при различных исходных дан­ных. Многократно повторяемый участок вычислений называют циклом (или телом цикла), а программы, содержащие цикл, называют­ся циклическими. Переменная, значение которой изменяется при повторении вычислений, называется параметром цикла. Циклы составляют основу алгоритмизации и программирования за­дач для решения на ЭВМ. Без правильной алгоритмизации циклов различных типов невозможно постичь начальные азы программирования.

Примером задач, в которых используется цикл по переменной (аргументу), может служить вычисление таблиц. Будем строить таблицу (табулировать) функцию у = f (х) для монотонно изменяющегося набора аргументов x₁, x₂, х₃, .... x_n . Разность х = х_i+1 - х_i назовем шагом табуляции. Если х = const, то говорят о таблице с постоянным шагом. Такую таблицу можно задать, указав начальное значение аргумента, шаг его изменения и конечное значение аргумента х_Н, х и х_К, соответственно. Табуляция функции у = f (х) заключается в последовательном применении преобразования f (х) поочередно к разным значениям х. Вычисление f (х) будет представлять собой цикл. Этот цикл должен повторяться до тех пор. пока текущее значение х не превзойдет х_К.

	1		1
	2		2
								4
									Да
								Нет			8
	Н 3 ет		3					5	Да
	 < -0,2						
	4	Да						Нет
							6		Да		9
	b = 1/						
								Нет
	5							7	Да		10
							
	b 6 = r2/4 +1							Нет
											11
	7
											12
Рис. 3.3. Блок-схемы алгоритмов разветвляющихся вычислительных процессов: a) примера 3.3; б) примера 3.4

Кратко остановимся на вопросах организации циклических процессов. При организации любого цикла необходимо проделать следующие дейст­вия:

1. Установить начальное значение параметра цикла.

2. Провести выделения в цикле.

3. После выполнения цикла изменить значение параметра цикла.

4. Проверить условие выхода из цикла.

Исходя из этого, типовая блок-схема циклического вычислительного процесса обычно состоит из четырёх блоков, реализующих вышеуказанные действия (рис. 3.4).

Построение блок-схемы циклического процесса рассмотрим на примере.

	х = -8			Б1:	хi: = xН, i = 0, установление начального значения параметра цикла х (подготовка цикла).
	у = -11,5/х + ехр(-х)			Б2:	уi: = f (хi), тело цикла (вычисления в цикле).
				Б2:	вывод в цикле текущих значений у и х (то есть хi и уi).
	х:= x + 2			Б3:	хi+1:= xi + х, изменение параметра цикла (подготовка следующего цикла вычислений).
Да				Б4:	хi+1  хК, проверка условия выхода из цикла.
		Нет
Рис. 3.4. Блок-схема алгоритма циклического вычислительного процесса примера 3.4

Пример 3.3. Составить блок-схему вычисления значений функции

у = - 11,5/х + е^-х

для х_Н = - 8, х = 2, х_К = 10.

Блок-схема будет иметь вид, показанный на рис. 3.4.

На рис. 3.4 блок Б1 служит для установки начальных значений параметра цикла х. Блок Б2 является телом цикла, это блок, в котором выполняются дей­ствия, представляющие собой цикл. Данный блок может быть очень боль­шим куском программы. К блоку Б2 следует отнести и вывод в цикле те­кущих значений у и х. Блок БЗ служит для изменения параметра цик­ла. Он подготавливает параметры цикла к очередному выполнению цикла Наконец, блок Б4 служит для проверки условия выхода из цикла. Этот блок определяет конечное число повторений цикла.

Порядок выполнения указанных блоков в общем случае может нару­гаться. Некоторые блоки могут задаваться неявно или видоизменяться. Тем не менее, данную блок-схему принято считать типовой. На рис. 3.4 приведен случай, когда в роли параметра цикла выступает аргумент вычисляемой функции, а число циклов заранее известно ( n = ((x_К-x_Н)/x).

В зависимости от ограничения числа повторений цикла различаются два их основных типа: циклы с известным количеством повторений и с неизвестным числом повторений. Исходя из структуры, циклы, в свою очередь, разбиваются на простые (не содержат внутри себя других циклов) и сложные (вложенные, содержащие один или несколько других циклов). Подробное изучение и блок-схемная формализация указанных разновид­ностей циклов будут проведены в последующих лабораторных работах при рассмотрении операторов цикла в алгоритмическом языке С++.

Процесс доведения задачи до решения на ЭВМ и ее непосредственная реализация на машине происходит за ряд этапов [1-6]:

1. Постановка задачи.

2. Математическое описание (формулировка) задачи.

3. Выбор и обоснование численного иди другого метода.

4. Алгоритмизация вычислительного процесса (разработка алгоритма).

5. Составление программы.

6. Отладка программы.

7. Подготовка исходных данных.

8. Решение задачи на ЭВМ (исполнение программы при заданных ис­ходных данных).

9. Анализ результатов решения задачи.

Рассмотрим содержание каждого этапа решения задачи на ЭВМ.

1. Постановка задачи. На данном этапе формирует­ся цель решения задачи и подробно описывается ее содержание, отмеча­ются факторы, оказывающие существенное влияние на ход вычислительного процесса или конечный результат. Подробно анализируется характер и сущность всех величин, используемых в задаче, и определяются условия, при которых она решается. Постановка задачи должна быть, в такой степени формальной, чтобы ее можно было легко истолковать единствен­ным образом. Корректность постановки задачи пользователем является важным моментом, так как от нее в значительной степени зависят все последующие этапы.

2. Математическое описание задачи. Настоящий этап характеризуется математической формализацией задачи, при которой существующие соотношения между величинами, определяющи­ми результат и ее целевую функцию (если такая имеется), выражаются посредством лаконичных математических формул. Таким образом, формиру­ется математическая модель явления с определенной точностью вычисле­ний. Здесь используются самые разнообразные разделы математики (осо­бенно прикладной) в зависимости от специфики решаемой задачи. На этом этапе в результате анализа существа задачи определяется объем и специфика исходных данных и начальных условий, вводится система ус­ловных обозначений, устанавливается принадлежность решаемой зада­чи к одному из известных классов задач и выбирается соответствующий математический аппарат. При этом все графические, табличные или иные функциональные зависимости следует выразить только с помощью строгих математических формул, уравнений, неравенств и других формальных средств математики.

3. Выбор и обоснование численного метода. На этом этапе устанавливается зависимость всех иско­мых результатов от исходных данных и разрабатываются также способы получения результатов, которые могут быть реализованы на |ВМ. Мате­матическая модель задачи (с учетом ее особенностей) путем конкретных численных методов (численные методы рассматриваются в специальном разделе математики - вычислительной математике) должны быть доведе­на до решения. Само по себе математическое описание в большинстве случаев трудно перевести на язык машины. А использование определен­ного численного метода приводит решение задачи к упорядоченному вы­полнению четырех арифметических действий и логических операций. Если одна и та же задача может быть решена с помощью различных численных методов, то выбирают тот, который удовлетворяет наилучшим образом ее основным требованиям. При обоснование выбора соответствующего численного метода определяющими факторами, наряду с прочими условиями, могут быть точность вычислений, время решения задачи на ЭВМ, требуемый объем основной памяти и другие.

Существо принимаемых на этом этапе решений во многом определяет качество выполнения следующего этапа - алгоритмизации. Его основное назначение - обеспечить точное и детальное описание процесса обра­ботки исходных данных для получения требуемого результата в соответ­ствия с выбранным методом.

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

Алгоритмизация заключается в разложении вычислительного процесса на возможные составные части, установлении порядка их следования, описании содержания каждой такой части в той или иной форме и после­дующей проверке, обеспечивается ли реализация выбранного метола. В большинстве случаев не удается сразу получить удовлетворительный ре­зультат. Поэтому алгоритмизация идет методом "проб и устранения ошибок", и для получения окончательного варианта требуется несколько шагов коррекции и анализа. Как правило, в процессе разработки алго­ритма проходит несколько этапов детализации, определяемой уровнем используемого в дальнейшем языка программирования. И для каждого такого этапа выполняется описанный выше итерационный процесс отработки схемы алгоритма. Подобный подход к алгоритмизации, когда первона­чально выделяются наиболее важные и существенные связи между ними, позволяет избежать излишней траты усилий на детализацию возможно ошибочных решений. Кроме того, ориентируясь на крупноблочную струк­туру, можно быстрее и проще разработать несколько различных алгорит­мов, провести их анализ, оценку и выбрать наилучший (оптимальный) вариант.

Эффект поэтапной детализации во многом зависит от того, как осу­ществляется структуризация алгоритма. Расчленение алгоритмизируемо­го процесса на составные части должно определяться не произволом программиста, а внутренней логикой самого процесса, Каждый элемент крупноблочной схемы алгоритма должен быть максимально самостоятель­ным и логически завершенным в такой степени, чтобы дальнейшую, дета­лизацию для элемента можно было выполнять независимо от детализации остальных элементов. Это позволяет осуществлять разработку алгорит­ма по частям одновременно нескольким программистам.

В процессе разработки алгоритма могут использоваться любые из ра­нее рассмотренных способов записи алгоритмов. В большинстве случаев в практике предпочтение отдается блок-схеме. Простота, минимум изо­бразительных средств, а главное, возможность наглядного, двумерного отображения структуры и логики алгоритма – выгодно отличают этот спо­соб от других способов со строчным (одномерным) характером записи алгоритмов. Однако на этом процесс не заканчивается: записанный в виде блок-схемы алгоритм нужно еще ввести в ЭВМ и исполнить его.

5. Составление программы. В процессе состав­ления программы алгоритм решения задачи, заданный в виде блок-схемы или другим изобразительным средством переводится на один из языков программирования ЭШ. Получения запись алгоритма на языке програм­мирования в закодированном виде переносится на перфокарты, перфолен­ту или магнитную ленту и затем с помощью устройств ввода передается в память машины. Если программа составлена на машинном языке (т.е. в машинных командах), то она непосредственно может быть реализована на ЭВМ. При записи программы на символическом (алгоритмическом) языке она сначала транслятором переводится на машинный язык и только после этого программа реализуется на ЭВМ. В процессе трансляции выявляются ошибки в записи конструкций алгоритмического языка (синтаксические ошибки).

6. Отладка программы. Процесс обнаружения и устра­нения ошибок в программе называется отладкой. Ошибки в программе бывают двоякого рода: синтаксические и логические. С помощью синтаксического контроля программы транслятором выявляются конструкции (сочетания символов), недопустимые с точки зрения правил их по­строения, принятых в данном алгоритмическом языке. Сообщения об этих ошибках ЭВМ автоматически выдает на печать в соответствии с диагностикой, предусмотренной в системе программирования. После ус­транения синтаксических ошибок проверяется логика работы исходной программы в процессе ее выполнения с конкретными исходными данными. Заранее в программе могут быть предусмотрены определенные контроль­ные соотношения или же вручную рассчитываются контрольные точки для их сопоставления с результатами, полученными на машине по данной программе. Необходимость контрольных вычислений даже в полном объеме и при типовых значениях исходных данных не противоречит целесообраз­ности разработки программы, так как она обычно предназначается для многократного использования - решения задачи при разных наборах ис­ходных данных. Общим и весьма эффективным методом отладки и поиска ошибок является прослеживание хода выполнения программы с помощью контрольных выводов на печать промежуточных результатов вычислений и сравнение их с результатами контрольного просчета, который, как правило, выполняется вручную для предварительно подобранных значе­ний и исходных данных, облегчающих такой просчет.

После отладки программы эти дополнительные операторы вывода на печать промежуточных результатов вычислений, обычно из программы исключаются. При совпадении результатов, полученных на машине, и контрольного (отладочного) варианта считается, что программа состав­лена правильно. Заметим, что в современных системах программирования для упрощения процесса обнаружения ошибок в исходной программе ис­пользуются специальные отладчики. Отладочные программы объединяются в систему, которая имеет свой специальный язык, задающий действия, производимые при отладке исходной программы на ЭВМ. К числу таких действий относятся, например, удаление, замена или вставка отдель­ных фрагментов программы, печатание значений заданных величин, чис­ла повторений определенных циклов и т.д. Только после того как поя­вится полная уверенность, что программа обеспечивает получение пра­вильных результатов, можно приступать к этапу рабочего счета по ней.

7. Подготовка исходных данных – важный этап в решении особенно экономических задач, включающий сбор данных, проверку их правильности, достоверности и точности. Исходные данные должны быть правильно записаны (расположены) согласно требованиям программы и подготовлены для ввода в машину.

8. Решение задачи на ЭВМ. После окончательной отладки программа с подробными инструкциями ее эксплуатации включает­ся в фонд программного обеспечения ЭВМ и по ней проводится решение задачи для всех вариантов исходных данных в интересах пользователя. Решение задачи на ЭВМ осуществляет оператор ЭВМ или пользователь, умеющий управлять машиной. Порядок работы на машине списывается в инструкции к машине, а при решении задачи по данной программе - в инструкции к программе.

9. Анализ результатов решения задачи. Результат решения в виде табуляграммы (текста и таблицы) или графи­ков выдается постановщику задачи, для которого она решалась. Полу­ченные результаты анализируется и оцениваются специалистом (пользователем) , поставившим задачу.

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

Приведенное деление процесса решения задачи на этапы в некоторой степени является условным, действительно, решения, принимаемые на некотором этапе, могут во многом определять действия на последующих этапах. С другой стороны, результаты, полученные на каком-то этапе, могут привести к основательному пересмотру предыдущих этапов.

К собственно программированию можно отнести лишь два этапа: алго­ритмизацию и составление программы. Запись алгоритма на некотором языке программирования особых трудностей не представляет, а перевод этой записи на машинный язык, как уже отмечалось, автоматизирован, фактически главные усилия при разработке программы направлены на конструирование и проверку лежащего в ее основе алгоритма. Трудность заключается в том, что этот процесс не поддается формализации из-за многообразия задач, способов их решения и неоднозначности самой алгоритмизации. Поэтому для практики программирования исключительно важным является классификация алгоритмов по способу организации уп­равления порядком выполнения действий: на линейные, разветвляющиеся и циклические.