Тема 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