5. ПРИНЦИПЫ ПРОГРАММИРОВАНИЯ

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

Термин алгоритм своим происхождением связан с именем выдающегося восточного математика Аль-Хорезми, который еще в IX веке сформулировал правила выполнения четырех арифметических действий. Этими правилами мы пользуемся до сих пор. В современной математике под алгоритмом понимается конечная последовательность точно определенных действий, приводящих к решению поставленной задачи. Алгоритмы существуют не только в математике и информатике. Они сопровождают жизнь человека в форме различных инструкций и правил.

Устанавливаемая алгоритмом последовательность действий задается в словесной или графической форме. Для реализации алгоритма на ЭВМ используются алгоритмические языки или языки программирования.

Обычно требуется, чтобы алгоритмы обладали следующими свойствами.

1) Дискретность. Это свойство алгоритма означает пошаговый характер получения результата.

2) Конечность. Работа алгоритма должна завершаться за конечное число шагов.

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

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

5) Результативность. Свойство означает получение результата после выполнения над исходными данными заданной алгоритмом последовательности действий.

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

5.2. Этапы подготовки задач к решению на ЭВМ

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

1) постановка (формализация) задачи;

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

3) разработка алгоритма решения задачи;

4) написание программы и ввод ее в память ЭВМ; 5)перевод программы в машинные команды (трансляция); 6)отладка и тестирование программы.

Рассмотрим далее содержание этих этапов.

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

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

– Что дано?

– Что нужно найти?

– Какова исходная информация?

– Какие накладываются ограничения на исходные данные?

– Какие сделаны допущения?

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

5.2.2. Выбор метода решения. Математическая модель

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

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

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

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

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

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

5.2.3. Разработка алгоритма

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

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

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

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

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

Пример. Записать словесным способом алгоритм решения линейного уравнения a xb.

1) Задать значения параметров a и b.

2) Если a не равно 0, то перейти к пункту 3. В противном случае перейти к пункту 5.

3) Вычислить xa/b и вывести значение переменной x.

4) Перейти к пункту 9.

5) Если b не равно 0, то перейти к пункту 6, в противном случае перейти к пункту 8.

6) Вывести текст "Решения нет".

7) Перейти к пункту 9.

8) Вывести текст: "Любое значение x является решением".

9) Конец алгоритма.

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

Пример. Записать словесным способом алгоритм вычисления суммы элементов последовательности

S  x₁ x₂ ... x_i, где i 1,n.

1) Задать значение n и значения x_i.

2) Присвоить i = 2.

3) Присвоить S = x_i.

4) Увеличить значение S на x_i.

5) Увеличить значение i на 1.

6) Если i не превышает n, то перейти к пункту 4.

7) Вывести значение S.

8) Стоп.

Здесь дан пример циклического алгоритма, в котором пп. 4, 5, 6 выполняются многократно и образуют цикл.

Граф-схемный, или блок-схемный, способ записи структура алгоритма изображается графически в виде набора некоторых геометрических фигур – блоков и связей между ними. Внутри блока записывается информация с содержанием действий на данном этапе алгоритма. Связи, изображаемые с помощью стрелок, указывают последовательность действий и соединяют блоки между собой. В Единой системе программной документации (ЕСПД) существует государственный стандарт ГОСТ 19.701-90 "Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения", регламентирующий запись алгоритма графическим способом. Условные обозначения основных элементов схем алгоритмов и программ, которые устанавливает данный стандарт, приведены в приложении.

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