Этапы решения задач на ПК. Понятие алгоритма и его свойства. Способы записи алгоритмов. Алгоритмизация линейных, ветвящихся и циклических вычислительных процессов. Типовые алгоритмы (сортировки, поиска и т.д.).
Этапы подготовки задачи к решению на компьютере.
Процесс подготовки любой задачи к ее решению на компьютере состоит из ряда последовательных этапов:
· постановка задачи;
· алгоритмизация;
· программирование;
· отладка программы.
Постановка задачи представляет собой процесс построения ее математической модели. На этом этапе формулируются цель и условия решения задачи, подробно описывается ее содержание.
Алгоритмизация - это процесс построения алгоритма задачи.
Под программированием понимается процесс кодирования составленного алгоритма на одном из языков программирования.
Отладка программы предполагает исправление синтаксических и семантических (смысловых) ошибок в тексте программы и проверку работоспособности программы на контрольном примере.
Понятие алгоритма, его свойства и изображение.
Алгоритмом называется точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи.
Слово алгоритм происходит от имени математика 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