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

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

Этапы решения задач на ЭВМ. Алгоритм и его свойства. Способы записи алгоритма: словесный способ; структурно-стилизованный способ; блочно-схематический способ; структурограммы Насси-Шнейдермана; программный способ. Основные структуры алгоритмов: алгоритмы линейной структуры, алгоритмы разветвляющейся структуры, множественный выбор, алгоритмы циклической структуры, алгоритмы со структурой вложенных циклов, подчиненные алгоритмы. Принцип программного управления.

Этапы решения задач на ЭВМ

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

1)     постановка задачи, разработка математической модели;

2)     выбор метода численного решения;

3)     разработка алгоритма и структуры данных;

4)     проектирование программы;

5)     производство окончательного программного продукта;

6)     решение задачи на ЭВМ.

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

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

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

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

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

Решение задачи на ЭВМ – выполнение всех предусмотренных программой вычислений и вывод результатов расчета на экран дисплея или на печать.

Алгоритм и его свойства

ЭВМ – глупые машины: они не будут ничего делать до тех пор, пока им не прикажут, а при получении приказа строго следуют всем указаниям, даже если последние бессмысленны. Для того чтобы вычислительная машина смогла решить какую-либо задачу, следует сформировать определенную последовательность команд называемую алгоритмом.

Алгоритм – это простое и четкое описание действий, приводящее к получению результата.

Алгоритмом является процесс нахождения корней квадратного уравнения. Сборником алгоритмов является книга рецептов.

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

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

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

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

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

Предопределенный алгоритмом вычислительный процесс можно расчленить на отдельные этапы, элементарные операции. Это свойство алгоритма называется дискретностью.

Алгоритмизация – это техника составления алгоритмов и программ для решения задач на ЭВМ.

Способы записи алгоритма: словесный способ; структурно-стилизованный способ; блочно-схематический способ; структурограммы Насси-Шнайдермана; программный способ

Существует четыре способа записи алгоритма:

1.      словесный (записи на естественном языке)

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

3.      графический (схемы графических символов)

4.      программный (тексты на языках программирования)

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

Пример. Найти максимальное число из двух данных натуральных чисел.

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

2.      Определить большее из чисел, оно является максимальным.

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

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

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

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

алг Нахождение max (x, y)

арг  x, y

рез z

запр  x, y

если  x>y  то

присв z знач x

иначе  присв z знач y

кон если

сооб  z

кон

Графический способ. Для графического изображения алгоритмов используются графические символы (блоки).

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

Команды алгоритма помешаются внутрь блоков, соединенных стрелками, показывающими очередность выполнения команд алгоритма. Приняты определенные стандарты графических изображений блоков. По стандарту высота блока равна a, ширина 2a, где размер выбирается из ряда 10, 15, 20мм. Блоки «начало» и «конец» имеют высоту 0,5a. Для записи команды внутри блоков используется естественный язык с элементами математической символики.

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

             +                              –                                              

Схемы могут быть представлены также в виде структурограмм (схемы Насси-Шнейдермана).

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

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