Файл: Алгоритмизация как обязательный этап разработки программы ( Свойства алгоритма ).pdf

Линейные алгоритмы. Базовая структура «следование» означает, что несколько операторов выполняются последовательно друг за другом, и только один раз за время выполнения программы. Структура «следование» используется для реализации задач, имеющих линейный алгоритм решения. Это означает, что такой алгоритм не содержит проверок условий и повторений, действия в нем выполняются последовательно, одно за другим.

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

Существует структура с полным и неполным ветвлением.

Структура с полным ветвлением (если - то - иначе) записывается так:

Если <условие>

то <действия 1>

иначе <действия 2>

Все если

Команда выполняется так: если <условие> является истинным, то выполняются <действия 1>, записанные после ключевого слова то, если <условие> является ложным, то выполняются <действия 2>, записанные после слова иначе.

Структура с неполным ветвлением (если - то) не содержит части, начинающейся со слова иначе:

Если <условие>

то <действия 1>

Все если

Команда выполняется так: если <условие> является истинным, то выполняются <действия 1>, записанные после ключевого слова то.

Циклические алгоритмы. При составлении алгоритмов решения большинства задач возникает необходимость в неоднократном повторении одних и тех же команд. Алгоритм, составленный с использованием многократных повторений одних и тех же действий (циклов), называется циклическим. Однако слово «неоднократно» не означает «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма («зацикливание» алгоритма), нарушает требование его результативности - получения результата за конечное число шагов.

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

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

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

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

Еще один вид циклов - цикл с параметром, или арифметический цикл. Тело цикла выполняется, пока параметр цикла i пробегает множество значений от начального (In) до конечного (Ik).

1.5. Время выполнения программ

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

1. быть простым для понимания, перевода в программный код и отладки;

2. эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.

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

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

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

Работа по решению любой задачи с использованием компьютера включает в себя следующие шесть этапов:

1.Постановка задачи.

2.Формализация задачи.

3.Построение алгоритма.

4.Составление программы на языке программирования.

5.Отладка и тестирование программы.

6.Проведение расчетов и анализ полученных результатов.

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

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

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

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

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

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

Основой профессиональной грамотности программиста является развитое алгоритмическое мышление.

ЭВМ - исполнитель алгоритмов. Как известно, каждый алгоритм (программа) составляется для конкретного исполнителя, т.е. в рамках его системы команд. О каком же исполнителе идет речь при изучении темы «Программирование для ЭВМ»? Ответ очевиден: исполнителем здесь является компьютер, а точнее говоря, комплекс ЭВМ + система программирования. Программист составляет программу на том языке, на который ориентирована система программирования.

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

3. Главные принципы, лежащие в основе создания эффективных алгоритмов

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

Ну, а если такого запаса нет, то как все-таки разработать хороший алгоритм? С чего начать? У всех есть печальный опыт, когда смотришь на задачу и не знаешь, что делать. Рассмотрим три общих метода решения задач, полезных для разработки алгоритмов.

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

Этот метод выглядит очень разумно. Но, как и большинство общих методов решения задач или разработки алгоритмов, его не всегда легко перенести на конкретную задачу. Осмысленный выбор более простых задач - скорее, искусство или интуиция, чем наука. Более того, не существует общего набора правил для определения класса задач, которые можно решать с помощью такого подхода. Размышление над любой конкретной задачей начинается с постановки вопросов. Частные цели могут быть установлены, когда получены ответы на следующие вопросы:

1.Можем ли мы решить часть задачи? Можно ли, игнорируя некоторые условия, решить оставшуюся часть задачи?

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

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

4.Встречались ли мы с похожей задачей, решение которой известно? Можно ли видоизменить ее решение для решения нашей задачи? Возможно ли, что эта задача эквивалентна известной нерешенной задаче?

Второй метод разработки алгоритмов известен как метод подъема. Алгоритм подъема начинается с принятия начального предположения или вычисления начального решения задачи. Затем начинается насколько возможно быстрое движение «вверх» от начального решения по направлению к лучшим решениям. Когда алгоритм достигнет такой точки, из которой больше невозможно двигаться наверх, алгоритм останавливается. К сожалению, мы не можем всегда гарантировать, что окончательное решение, полученное с помощью алгоритма подъема, будет оптимальным. Эта ситуация часто ограничивает применение метода подъема.

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

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

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

Заключение

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