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

Этапы решения задач на ПК. Понятие алгоритма и его свойства. Способы записи алгоритмов. Алгоритмизация линейных, ветвящихся и циклических вычислительных процессов. Типовые алгоритмы (сортировки, поиска и т.д.).

Этапы подготовки задачи к решению на компьютере.

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

· постановка задачи;

· алгоритмизация;

· программирование;

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

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

Алгоритмизация - это процесс построения алгоритма задачи.

Под программированием понимается процесс кодирования составленного алгоритма на одном из языков программирования.

Отладка программы предполагает исправление синтаксических и семантиче­ских (смысловых) ошибок в тексте программы и проверку работоспособности программы на контрольном примере.

Понятие алгоритма, его свойства и изображение.

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

Слово алгоритм происходит от имени математика IX века Аль - Хорезми, который сформулировал правила выполнения арифметических действий.

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

Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применяется алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные. (См. рис. 30).

Входные данные Выходные данные

		Алгоритм

FFffff

Рис. 30. Представление алгоритма вычислительного процесса.

Основными свойствами алгоритма являются:

1. Детерминированность (определенность). Предполагает получение одно­значного результата процесса при заданной исходной информации. Благо­даря этому свойству процесс выполнения алгоритма носит механический ха­рактер.

2. Результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат.

3. Массовость. Это свойство предполагает, что алгоритм должен быть приго­ден для решения всех задач данного типа.

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

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

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

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

Перечень символов, их наименование, отображаемые ими функции, форма и размеры определяются ГОСТ 19.003-80, ГОСТ 19.002-80 и ГОСТ 19701-90.

Не вдаваясь во все тонкости проектирования блок- схем алгоритмов, исполь­зуем обозначения некоторых символов для описания логики рассматриваемых нами вычислительных процессов. См. таблицу 6.

Некоторые символы блок-схем Таблица 6.

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

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

При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:

· линейный;

· ветвящийся;

· циклический.

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

Примером линейной алгоритмической структуры может служить алгоритм решения задачи 1 со следующим условием: вычислить и вывести результаты вычисления выражения

На рис.31 представлена блок-схема решения этой задачи. Так как данная схема - первая, рассматриваемая в данном пособии, то объясним подробно назначение каждого из используемых в ней блоков. Блоки 1 и 5 служат соответственно для обозначения начала и окончания вычислительного процесса.

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

1 начало   ввод a, b   a2 +b2 y = 100   вывод y   конец	Для того, чтобы можно было получить результат, который по условию задачи 1 должен располагаться в области памяти Y,необходимо до выполнения расчетов поместить числовые данные в области памяти a иb. Для указания процесса ввода данных в схеме используется блок 2. Процесс получения результата вычислений описывается в блоке 3.
Рис. 31 Блок-схема алгоритма решения задачи 1.

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

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

В качестве примера ветвящейся алгоритмической структуры рассмотрим процесс вычисления выражения задачи 2:

Появление условия при решении этой задачи связано с возможным делением на ноль. Такая ситуация возникает, если будут введены в области памяти a и b два одинаковых числа.

Блок-схема решения задачи 2 показана на рис.32.

Рассмотрим особенности построения этой схемы алгоритма. Блоки 3,4,5,6 представляют единую конструкцию “альтернатива”. Начинается эта конструкция с блока 3 (блока “решения”), из которого выходят две ветви алгоритма (два плеча альтернативы), определяющие отдельные направления обработки информации.

1 начало ввод a, b     да 3 нет a - b ¹ 0   4 6 a2 +b2 вывод y = a - b “ Решения нет”   вывод y     конец	Блоки 4 и 5 расположены на ветви “ДА”, а блок 6 - на ветви “НЕТ”. Для данной алгоритмической структуры характерно, что в любой момент ее реализации осуществляется обработка только по какой - либо одной из ветвей. Для описания ветвящегося вычислительного процесса ранее рассмотренную группу операторов пополним еще одним.
Рис.32. Блок-схема алгоритма решения задачи 2.

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

Классификация циклов представлена на рис.33

Циклы