Лекция 3 Алгоритмизация и программирование

1. Основы алгоритмизации

   1. Представление об алгоритме

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

Алгоритм – это конечная последовательность однозначно сформулированных действий преобразования исходных данных в искомый результат, заданная в виде формального описания. Рассматривается два класса алгоритмов: числовые алгоритмы, в которых решение сводится к арифметическим действиям; логические алгоритмы ‑ решение сводится к логическим действиям. Собственно решение задачи или выполнение действий по данному алгоритму является его исполнением.

Алгоритм характеризуется следующими свойствами:

• дискретность – последовательность заранее определенных действий, каждое следующее действие выполняется после завершения предыдущего;

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

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

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

• конечность – возможность исполнения алгоритма, получение результата за конечное число шагов и за приемлемое время (исключается зацикливание выполнения алгоритма).

2. Способы записи алгоритмов

Алгоритмизация – процесс разработки алгоритма для решения задачи и записи его в какой либо удобной форме. Затем алгоритм реализуется в виде компьютерной программы. Следовательно, необходимо иметь такие способы записи алгоритмов, которые легко воспринимаются человеком, но являются достаточно строгими, чтобы их можно было впоследствии перевести на язык компьютера.

Существуют различные способы записи алгоритмов. К основным относятся описательный, графический и программный способы. Описательным называется алгоритм, составленный на естественном языке, в частности, математическом языке (формул).

Графический способ записи алгоритмов

Графический способ отличает компактная и наглядная форма записи логической структуры (блок-схемы) алгоритма (фрагмента) в виде специальных графических знаков с указанием связи между ними. По мере роста сложности фрагмента алгоритма логическая структура перегружается деталями и связями и блок-схема становится сложной для восприятия. По этой причине блок-схемы используются в основном для записи типовых базовых структур , на которые декомпозируется алгоритм решения задачи в целом. При графическом представлении алгоритма с помощью блок-схемы каждый шаг в алгоритме отображается на схеме некоторой геометрической фигурой (блоком) и дополняется элементом описания (словесного, на псевдо алгоритмическом языке или алгоритмическом языке Basic, Pascal, Fortran, C и др.). Основные блоки, которые используются при составлении графического алгоритма по ГОСТ 19.701-90, изображены в табл. 3.1. Использование блок-схем, состоящих из типового набора блоков, позволяет трактовать алгоритм однозначно.

Таблица 3.1. Условные обозначения на блок-схемах алгоритмов

Основные блоки по ГОСТ 19.701-90	Описательное (словесное) описание
	Начало (конец) алгоритма.
	Данные ‑ ввод данных (с клавиатуры), вывод данных (на печать).
	Процесс. Выполнение операции или группы операций, приводящее к изменению значения.
	Решение. Внутри блока записывается условие. Блок имеет один вход и два альтернативных выхода: «да» ‑ условие выполнено, «нет» ‑ условие не выполнено.

Программный способ записи алгоритмов

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

Алгоритмические или процедурные языки (Pascal, Basic, C и др.) предназначены для однозначного описания алгоритмов в виде некоторой последовательности операторов языка. Основные операторы языка Pascal, которые используются при составлении программного описания алгоритма, приведены в табл. 3.2.

Таблица 3.2. Основные операторы языка Pascal

Оператор языка Pascal	Назначение
begin <Оператор1>; <Оператор2> end.	Алгоритм начинается словом begin (операторная скобка) – это начало последовательности операторов. Завершает алгоритм слово end с точкой.
<Переменная>:=<Выражение>	Оператор присваивания ‑ в левой части указывается имя переменной, правая часть представляет собой выражение того же типа, что и переменная. Пара символов «:=», связывающая левую и правую части оператора присваивания, означает «вычислить выражение и присвоить значение переменной».
ReadLn(<Переменная>);	По оператору ReadLn вызывается встроенная процедура ввода данных и программа останавливается в ожидании ввода значения переменной. В этот момент необходимо набрать на клавиатуре нужное число и нажать клавишу Enter.
WriteLn('Строка символов',<Переменная>);	Оператор обращения к процедуре вывода данных на экран «Строки символов» (текста) (WRITE Line – записать строку) и значения переменной.
IF <условие> THEN <оператор1> ELSE <оператор2>;	Условный оператор. Вычисляется условное выражение <условие>. Если результат есть TRUE (истина), то выполняется <оператор1>, а <оператор2> пропускается; если результат есть FALSE (ложь), наоборот, <оператор1> пропускается, а выполняется <оператор2>
IF <условие> THEN <оператор1>;	Часть ELSE <оператор2> условного оператора может быть опущена. Тогда при значении TRUE условного выражения выполняется <оператор1>, в противном случае этот оператор пропускается (соответствует блоку «Решение») блок-схемы.
FOR<пар_цик>:=<нач_знач>ТО <кон_знач> DO <оператор>	Счетный оператор цикла FOR. Вначале вычисляется выражение <нач_знач> и осуществляется присваивание счетчику цикла начального значения <пар_цик> : = <нач_знач>. После этого циклически повторяется: проверка условия повторения цикла <пар_цик> <= <кон_знач>; если условие не выполнено, оператор FOR завершает свою работу; выполнение произвольного оператора (тела цикла) <оператор> ; наращивание переменной счетчика цикла<пар_цик> на единицу
WHILE <условие> DO <оператор>	Оператор цикла WHILE с предпроверкой условия. Если выражение <условие> имеет значение TRUE, то выполняется <оператор>, после чего вычисление выражения <условие> и его проверка повторяются. Если <условие> имеет значение FALSE, оператор WHILE прекращает свою работу.
REPEAT <оператор> UNTIL <условие>	Оператор цикла REPEAT с постпроверкой условия. Выполняется <оператор> и проверяется условие повторения цикла. Если выражение <условие> имеет значение TRUE, то, выполнение <оператора> продолжается. Если <условие> имеет значение FALSE, оператор REPEAT прекращает свою работу (выход из цикла).
begin ...... begin ...... end; ...... end;	Составной или пустой оператор – это последовательность операторов алгоритма (программы), входящих в составной оператор, среди которых могут быть другие вложенные составные операторы.

Базовые алгоритмические конструкции

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

Линейный алгоритм

В линейном алгоритме действия выполняются последовательно одно за другим в виде линейной последовательности действия (базовая структура «следование»). Рассмотрим примеры линейных алгоритмов.

Пример 3.1. Вычислить высоты треугольника со сторонами a,b,c, используя формулы:

где .

Из множества алгоритмов для решения любой нетривиальной задачи выбирают тот, который требует меньше времени на исполнение или обеспечивает более высокую точность. При решении данной задачи для исключения повторений следует вычислить высоты, используя промежуточную переменную t.

, тогда

Вывести результаты с их наименованием.

Алгоритм решения имеет вид, представленный в табл. 3.1.

Табл. 3.1.

Блок-схема алгоритма	Алгоритм на языке Турбо Паскаль
Начало Вывод ' =', ' =', ' =', Конец ; p:=(a+b+c)/2 Ввод данных a,b,c	Begin ReadLn(a,b,c); p:=(a+b+c)/2; ; ; ; WriteLn('ha=', ' =', ' =', ) End.

Пример 3.2. Вычислить наиболее вероятную скорость V_в, среднюю скорость V_c и среднеквадратичную скорость V_k молекул газа с молекулярной массой М по формулам:

V_в = ; V_c = ; V_k = .

Преобразуем формулы для вычисления скоростей V_c и V_k, исключив повторяющиеся действия.

V_в = V_c = 2V_в/ V_k = V_в

Исходные данные для решения задачи приведены в табл. 3.2.

Табл. 3.2. Исходные данные для примера 3.2.

Исходные данные, результаты	Обозначения, размерность в системе Си
Vв, Vс, Vк	Наиболее вероятная скорость Vв молекул газа с молекулярной массой М при температуре Т; (м/с)
R = 8.3144*10^7 Эрг/(моль*К	R – универсальная газовая постоянная; (Дж/(моль*К)
Т = 25 град.С	T ‑ абсолютная температура газа; (град. Кельвина)
М(N2) = 28 г/моль	М ‑ молярная масса молекул газа, численно равная молекулярной массе; (кг/моль)
KR=10^7	R = 8,3144 Дж/(моль*К)
KM=10^-3	М(N2)=0,028 кг/моль
KT=273	TK=298 град. К

Алгоритм решения задачи на языке Турбо Паскаль имеет вид.

begin

ReadLn(R,T,MN, ,KR,KM,KT);

R:=R*KR;

T:= T+KT;

MN:= MN*KM;

VB:=sqrt(2*R*T/MN);

VC:=VB*2/ sqrt();

VK:= VB*sqrt(3/2);

WriteLn(' VB=',VB)

end.

Пример 3.3. Электрическая цепь представляет собой соединение трех сопротивлений R₁₁, R₁₂ и R₁₃ в виде звезды. Составить алгоритм вычисления сопротивлений электрической цепи R₂₁, R₂₂ и R₂₃ после преобразования звезды в треугольник по формулам:

R₂₁=(R₁₁R₁₃+R₁₁R₁₂+R₁₂R₁₃)/R₁₁,

R₂₂=(R₁₁R₁₃+R₁₁R₁₂+R₁₂R₁₃)/R_12,

R₂₃=(R₁₁R₁₃+R₁₁R₁₂+R₁₂R₁₃)/R_13.

Пример 3.4. Составить алгоритм для вычисления момента инерции J, момента сопротивления W и площади поперечного сечения S для кольца с внешним диаметром D и внутренним диаметром d₀ по следующим формулам.

J= ; W= S= .

Разветвляющийся алгоритм

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

Базовая структура «ветвление» существует в следующих основных вариантах: