Понятие алгоритма. Принципы построения алгоритма. Компьютер как исполнитель алгоритма. Этапы решения задач на ЭВМ. Порядок разработки программы для решения

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

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

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

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

Третий этап – алгоритмизация задачи. На основе математического описания необходимо разработать алгоритм решения.

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

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

Исполнителем может быть не только человек, но и автомат. Компьютер – лишь частный, но наиболее впечатляющий пример исполнителя, чьё поведение основано на реализации алгоритма. Более того, создание персонального компьютера оказало воздействие на развитие теории алгоритмов, одной из областей дискретной математики.

Эффективный метод построения алгоритма – метод пошаговой детализации (последовательного построения). При этом сложная задача разбивается на ряд более простых. Для каждой подзадачи – свой алгоритм. Универсальный эффективный метод построения алгоритма является основой структурного программирования (языки QBasic, Turbo Pascal и др.).

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

Используются различные способы записи алгоритмов:

– словесный (запись рецептов в кулинарной книге, инструкции по использованию технических устройств и т. п.);

– графический – пример на рисунке;

– структурно-стилизованный (для записи используется язык псевдокода).

Свойства алгоритма. При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств.

Однозначность алгоритма – единственность толкования исполнителем правил выполнения действий и порядка их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя (сложить А и В).

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

Результативность алгоритма – предполагает, что выполнение алгоритма должно завершиться получением определённых результатов. У нас для целых А и В всегда будет вычислена сумма.

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

Правильность алгоритма – способность алгоритма давать правильные результаты решения поставленных задач.

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

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

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

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

Контрольные примеры стремятся выбрать так, чтобы при работе с ними программа прошла все основные пути блок-схем алгоритма, поскольку на каждом из путей могут быть свои ошибки, а детализация плана зависит от того, как поведёт себя программа на этих примерах. На одном она может «зациклиться», на другом дать бессмысленный результат. Сложные программы отлаживают отдельными фрагментами.

Для повышения качества выполнения этого этапа используются специальные программы – отладчики, которые позволяют исполнить программу «по шагам» с наблюдением за изменением значений переменных, выражений и других объектов программы, с отслеживанием выполнения операторов.

Седьмой этап – исполнение отлаженной программы и анализ результатов. На этом этапе программист запускает программу и задаёт исходные данные, требуемые по условию задачи.

Полученные результаты анализируются постановщиком задачи, и на основании этого анализа вырабатываются соответствующие решения, рекомендации, выводы. Например, если при решении задачи на ПК результат 2+3=4, то следует изменить алгоритм и программу.

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

Современные компьютеры не настолько совершенны, чтобы понимать программы, написанные на каком-либо употребляемом человеком языке.

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

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

 

Язык программирования Турбо- Паскаль. Структура языка Turbo-Pascal, основные понятия. Запись и порядок выполнения операций в арифметическом выражении. Стандартные математические функции и процедуры Turbo-Pascal

Система программирования Turbo Pascal предназначена для выполнения этапов решения задачи на алгоритмическом языке Паскаль и включает в себя три главные компоненты: редактор текстов, компилятор, исполнительную систему.

С помощью встроенного в систему текстового редактора можно формировать в памяти любые тексты, не только программы на Паскале. В частности, это могут быть исходные данные решаемой задачи в текстовой форме. Текст программы, созданный редактором, можно сохранить на диске в виде файла с именем следующего формата <имя файла>.раs, где pas — это стандартное расширение имени файла, созданного системным редактором. Имя файла задается пользователем.

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

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

Turbo Pascal позволяет редактировать, компилировать, компоновать и выполнять Паскаль-программы. При этом пользователю предоставляется высокая скорость компиляции, удобство работы с компьютером и мощная библиотека процедур и функций.

Программа на Паскале в общем случае состоит из нескольких файлов. Один из них содержит главную программу, а остальные – модули. Главная программа состоит из заголовка, блока и заканчивается точкой — признаком конца программы. В свою очередь, блок содержит разделы описаний и раздел операторов. В общем случае «скелет» программы можно представить следующим образом:

{ Спецификация программы }

Program <имя программы> (заголовок программы);

Uses (раздел объявления модулей);

Label (раздел объявления меток);

Const (раздел объявления констант);

Type (раздел объявления типов);

Var (раздел объявления переменных);

Procedure(function) (раздел объявления подпрограмм: процедурили функций);

Begin

<операторы > (раздел операторов, обязательная часть);

end.

Все указанные разделы отделяются друг от друга точкой с запятой.

Раздел операторов должен обязательно присутствовать в любой программе и является основным. Предшествующие разделы носят характер описаний и не обязательно содержаться в программе.

Заголовок программы состоит из зарезервированного слова program и имени программы (со списком параметров, заключенных в круглые скобки). Завершается заголовок точкой с запятой.

В Turbo Pascal имеются особенности в структуре программы. Так, заголовок программы необязателен и игнорируется компилятором. Порядок размещения разделов произвольный, можно создавать несколько одинаковых разделов. Единственное правило, которое необходимо выдерживать, - в любом месте программы можно использовать лишь элементы (метки, типы, константы, переменные, подпрограммы и т. д.), которые были определены ранее по тексту программы или являются предопределенными элементами языка. Исключением из этого правила может быть лишь определение типа-указателя через неопределенный до этого тип. Однако этот тип в дальнейшем должен быть обязательно определен.

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

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

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

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

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

Знаки операций предназначены для обозначения тех или иных арифметических, логических или других действий. Они бывают двух типов: состоящие из небуквенных символов (например, +, -, * и т.д.) и буквенные операции (например, not, mod, div и т. д.), представляющие собой зарезервированные слова. Операции над данными делятся на унарные (применимые к одному операнду) и бинарные (применимые к двум операндам). Приведем примеры бинарных арифметических операций (в таблице буква I обозначает целые типы, R — вещественные типы):

Знак	Выражение	Типы операндов	Тип результата	Операция
+	А+В	R,R I,I I,R; R,I	R I R	Сложение
-	А-В	R,R I,I I,R; R,I	R I R	Вычитание
*	А*В	R,R I,I I,R; R,I	R I R	Умножение
/	А/В	R,R I,I I,R; R,I	R R R	Вещественное деление
Div	A div B	I, I	I	Целое деление
Mod	A mod B	I, I	I	Остаток от деления

Арифметическое выражение задает порядок выполнения действий над числовыми величинами. Арифметические выражения содержат арифметические операции, функции, операнды, круглые скобки. Одна константа или одна переменная — простейшая форма арифметического выражения.

Порядок выполнения операций в арифметическом выражении подчиняется трем правилам:

1. Правилу скобок. Оно гласит, что первыми выполняются операции в скобках. Если имеется несколько пар вложенных скобок, вычисления начинаются с самых внутренних скобок.

2. Правилу учета приоритета операций: вначале вычисляются значения функций, затем выполняются операции умножения и деления и в последнюю очередь - операции сложения и вычитания.

3. Правилу следования: операции одинакового старшинства (приоритета) выполняются слева направо в порядке их следования.

В качестве операндов в выражении, кроме констант и переменных, можно использовать стандартные функции. Аргументы функций обязательно заключаются в круглые скобки. Приоритет выполнения функции выше, чем приоритет выполнения арифметических операций. Рассмотрим стандартные функции Турбо Паскаля (в таблице буква I обозначает целые типы, R — вещественные типы):

Обращение	Тип аргумента	Тип результата	Тип действия
pi	-	R	Число π
abs(x)	I,R	I,R	Модуль (абсолютная величина) числа х
sqr(x)	I,R	I,R	Квадрат х
sqrt(x)	I,R	R	Корень квадратный из х (х≥0)
sin(x)	I,R	R	Синус х (х в радианах)
cos(x)	I,R	R	Косинус х (х в радианах)
arctan(x)	I,R	R	Арктангенс х (результат в радианах)
exp(x)	I,R	R	Экспонента е в степени х (е≈2,71828)
ln(x)	I,R	R	Натуральный логарифм х (x>0)
trunc(x)	R	I	Целая часть х
int(x)	I,R	R	Целая часть х
round(x)	R	I	Округление х до ближайшего целого
frac(x)	I,R	R	Дробная часть х
random	-	I	Случайное число [0,1)
random(x)	I	R	Случайное число [0,х)
dec(x,[n])	I	I	Уменьшение х на n, при отсутствии n – на 1
inc(x,[n])	I	I	Увеличение х на n, при отсутствии n – на 1
odd(x)	Longint	Boolean	true, если значение x нечетное; false, если x четное
ord(x)	любой порядковый	Longint	Порядковый номер значения х в его типе. Если х – символ, то функция возвращает код символа
pred(x)	любой порядковый	тот же, что для x	Предыдущее относительно х значение в его типе
succ(x)	любой порядковый	тот же, что для x	Следующее относительно х значение в его типе
chr(x)	Byte	Char	Определяет символ с указанным кодом (х – число, определяющее код символа)

Турбо Паскале не содержит некоторые часто используемые математические функции, поэтому при их вычислении используют эквивалентные математические формулы:

Функция	Эквивалентная математическая формула	Запись в программе
ax		exp(x*ln(a))
tg(x)		sin(x)/cos(x)
arcsin(x)		arctan(x/sqrt(1-x*x))
arccos(x)		arctan(sqrt(1-x*x)/x)
logax		ln(x)/ln(a)

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

Структура процедуры имеет следующий вид:

Procedure <имя процедуры>(формальные параметры: их тип);

Var

(локальные переменные)

begin

...

end;

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

Процедура вызывается по имени:

<имя процедуры> (фактические параметры);

Значение каждого фактического параметра при вызове процедуры передаётся формальному параметру. Временно управление передаётся процедуре. После завершения работы процедуры управление возвращается в основную программу.

Каждый формальный параметр указывается вместе со своим типом. Соответствующий ему фактический параметр указывается без типа. Между формальными и фактическими параметрами должно быть соответствие по количеству параметров, по их типу и порядку следования.

Заголовок процедуры может выглядеть так:

PROCEDURE GG(a,b,c:integer); вызыватьсятак: GG(3,n,m)

Здесь a,b,c-формальные параметры, а 3, n, m-фактические параметры

Таким образом в процедуру передаются значения: a=3, b=n, c=m

Переменные описанные в процедуре после слова Var, являются внутренними переменными процедуры или промежуточными, они не являются данными для операций внутри процедуры и не являются результатом её выполнения, а нужны лишь для промежуточных действий. Данные и результаты описываются в круглых скобках после имени процедуры. Перед описанием переменных-результатов пишут служебное слово var.