Решение задачи на ЭВМ – сложный и трудоемкий процесс. Любая задача начинается с постановки задачи. На основе словесной формулировки задачи выбираются переменные, подлежащие определению, записываются ограничения, связи между переменными, в совокупности образующие математическую модель решаемой проблемы. Анализируется метод решения. На этом этапе необходимо принять очень важное решение – использовать ли имеющееся готовое программное обеспечение или разрабатывать собственную программу. Дешевле и быстрее использовать имеющиеся в наличии готовые разработки. Обновление программного обеспечения – задача программистов. В этом случае традиционно выделяются следующие основные этапы решения задачи на ЭВМ:
1) постановка задачи, разработка математической модели;
2) выбор метода численного решения;
3) разработка алгоритма и структуры данных;
4) проектирование программы;
5) производство окончательного программного продукта;
6) решение задачи на ЭВМ.
Постановка задачи – точное описание исходных данных, условий задачи и целей ее решения. На этом этапе многие из условий задачи, заданные в форме различных словесных описаний, необходимо выразить на точном (формальном) языке математики. Часто задача программирования задается в математической формулировке, поэтому необходимость в выполнении этапов 1 и 2 отпадает. Для решения достаточно сложных задач этап формализации может потребовать значительных усилий и времени. Среди опытных программистов распространено мнение, что выполнить этап формализации – это значит сделать половину всей работы по созданию программы.
Выбор метода решения тесно связан с постановкой задачи. На первом этапе задача сводится к математической модели, для которой известен метод решения. Метод численного решения сводит решение задачи к последовательности арифметических и логических операций. Однако возможно, что для полученной модели известны несколько методов решения и тогда предстоит выбрать лучший. Можно усовершенствовать существующий или разработать новый метод решения формализованной задачи. Эта работа по своему характеру является научно–исследовательской и может потребовать значительных усилий. Разработкой и изучением таких методов занимается раздел математики, называемый численным анализом.
При выборе метода надо учитывать требования, предъявляемые постановкой задачи, и возможности его реализации на конкретной ЭВМ: точность решения, быстроту получения результата, требуемые затраты оперативной памяти для хранения исходных и промежуточных данных и результатов.
Алгоритм устанавливает последовательность точно определенных действий, приводящих к решению задачи. При этом последовательность действий может задаваться посредством словесного или графического описаний. Если выбранный для решения задачи численный метод реализован в виде стандартной библиотечной подпрограммы, то алгоритм обычно сводится к описанию и вводу исходных данных, вызову стандартной подпрограммы и выводу результатов на экран или на печать. Более характерен случай, когда стандартные подпрограммы решают лишь какую–то часть задачи. Здесь эффективным подходом является разделение сложной исходной задачи на некоторые подзадачи, реализующиеся отдельными модулями. Определяется общая структура алгоритма, взаимодействие между отдельными модулями, детализируется логика. Этот этап тесно связан со следующим этапом проектирования программы.
Проектирование программы включает в себя несколько подзадач. Во–первых, необходимо выбрать язык программирования. Во–вторых, определить, кто будет использовать разработанное программное обеспечение и каким должен быть интефейс (средство общения с пользователем). В–третьих, решить все вопросы по организации данных. В–четвертых, кодирование, т. е. описание алгоритмов с помощью инструкций выбранного языка программирования. Если задача, для которой разрабатывается алгоритм, сложная, то не следует сразу пытаться разрешить все проблемы. Сложившийся в настоящее время подход к разработке сложных программ состоит в последовательном использовании принципов проектирования сверху вниз, модульного и структурного программирования.
Окончательный программный продукт получается после отладки и испытания программы. При программировании и вводе данных с клавиатуры могут быть допущены ошибки. Их обнаружение, локализацию и устранение выполняют на этапе отладки и испытания (тестирования) программы. Причем могут быть допущены логические ошибки и на этапе постановки задачи, и на этапе алгоритмизации. В этом случае необходимо вернуться к предыдущим этапам. Дорабатывать и улучшать программу можно в течение всего жизненного цикла программного продукта.
Решение задачи на ЭВМ – выполнение всех предусмотренных программой вычислений и вывод результатов расчета на экран дисплея или на печать.
Пример. Построить траекторию движения тела, брошенного под углом к горизонту, и определить дальность бросания.
Постановка задачи, разработка математической модели. Для упрощения модели примем следующие допущения:
а) пренебрегаем кривизной Земли, считая ее поверхность плоскостью;
б) ускорение свободного падения считаем константой;
в) пренебрегаем сопротивлением воздуха;
г) пренебрегаем движением Земли.
Математическое описание объекта. Уравнения движения тела, брошенного под углом к горизонту, в Декартовых координатах записываются следующим образом:
Пусть движение тела, брошенного под углом к горизонту с начальной скоростью Vo (рис. 1), описывается системой уравнений (1). и Vo заданы. Требуется определить дальность полета и положение тела в каждый момент времени от t = 0 до tKс шагом h.
Алгоритм решения лучше всего представить в виде схемы (рис. 2).
Вторым этапом решения задачи можно пренебречь, так как никакого особенного численного метода решения в данном случае применять не нужно. Точка падения определяется из системы уравнений при условии Y = 0.
Изменяя значение t с шагом h, рассчитываем координаты X, Y.
На следующем этапе алгоритм записывается на языке программирования и текст программы переносится на носитель, с которого она вводится в ЭВМ. Часто программа вводится с клавиатуры дисплея в оперативную память компьютера, а затем записывается на диск.
По готовой программе производятся расчеты и результаты сравниваются с контрольным примером. Контрольным примером могут служить экспери-ментальные данные. Если в процессе отладки программы возникают ошибки, то их необходимо исправить.
Способы записи алгоритма
Алгоритм и его свойства
В основе решения любой задачи лежит понятие алгоритма. Под алгоритмом принято понимать “точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату” (ГОСТ 19.781–74).
При составлении алгоритмов следует учитывать ряд требований, выполнение которых приводит к формированию необходимых свойств.
Алгоритм должен быть однозначным, исключающим произвольность толкования любого из предписаний и заданного порядка исполнения. Это свойство алгоритма называется определенностью.
Реализация вычислительного процесса должна через определенное число шагов привести к выдаче результатов или сообщения о невозможности решения задачи. Это свойство алгоритма называется результативностью.
Решение однотипных задач с различными исходными данными можно осуществлять по одному и тому же алгоритму, что дает возможность создавать типовые программы для решения задач при различных вариантах задания значений исходных данных. Это свойство алгоритма называется массовостью.
Предопределенный алгоритмом вычислительный процесс можно расчленить на отдельные этапы, элементарные операции. Это свойство алгоритма называется дискретностью.
Алгоритмизация – техника составления алгоритмов и программ для решения задач на ЭВМ.
2.2. Изобразительные средств а для описания алгоритмов
К изобразительным средствам описания алгоритмов относятся следующие основные способы их представления:
а) словесный (записи на естественном языке);
б) структурно–стилизованный (записи на языке псевдокода);
в) программный (тексты на языках программирования);
г) графический (схемы графических символов).
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных и задается в произвольном изложении на естественном языке. Способ основан на использовании общепринятых средств общения между людьми и, с точки зрения написания, трудностей для авторов алгоритмов не представляет. Однако для “исполнителей” такие описания алгоритмов часто неприемлемы. Они строго не формализуемы, страдают многословностью записей, допускают неоднозначность толкования отдельных предписаний. Поэтому такой способ описания алгоритмов не имеет широкого распространения.
Пример. Записать алгоритм нахождения наибольшего общего делителя двух натуральных чисел (m и n) на естественном языке.
При таком словесном способе содержание алгоритма может быть следующим:
1) если числа равны, то необходимо взять любое из них в качестве ответа, в противном случае – продолжить выполнение алгоритма;
2) определить большее из чисел;
3) заменить большее число разностью большего и меньшего чисел;
4) повторить алгоритм с начала.
Структурно–стилизованный способ записи алгоритмов основан на формализованном представлении предписаний, задаваемых путем использования ограниченного набора типовых синтаксических конструкций. Такие средства описания алгоритмов часто называются псевдокодами. Разновидностью структурно–стилизованного способа описания алгоритмов является известный школьникам алгоритмический язык в русской нотации (АЯРН).
Пример. Приведем описанный на АЯРН алгоритм решения задачи об определении принадлежности точки D треугольнику АВС.
алг Определение принадлежности точки треугольнику (действ xA, yA, хB, уB, хC, уC, хD, уDцелое z лит а);
арг хА, уА, хВ, уВ, хС, уС, хD, уD;
рез z,а;
нач
действ S1, S2, S3, S4
вычислить значение S1, равное площади тр–ка АВС;
вычислить значение S2, равное площади тр–ка АВD;
вычислить значение S3, равное площади тр–ка АСD;
вычислить значение S4, равное площади тр–ка СDВ;
если S1 = S2+S3+S4
то z:= 1,
а:= “точка внутри треугольника”,
иначе z:= 0,
а:= “точка вне треугольника”,
все
напечатать значение а:
кон
Программный способ записи алгоритмов – это алгоритм, записанный на языке программирования, позволяющем на основе строго определенных правил формировать последовательность предписаний, однозначно отражающих смысл и содержание частей алгоритма с целью их последующего исполнения на ЭВМ.
Пример. Программа на языке Бейсик перевода температуры из градусов Цельсия в градусы Фаренгейта.
PRINT “Перевод температуры из град. Цельсия в град. Фаренгейта”
PRINT “Укажите температуру в град. Цельсия”
INPUT C
6 IF C = 9999 THEN 7
F = C*1.8 +32
PRINT C, F
GOTO 6
7 END
На рис. 3 приведена схема алгоритма перевода температуры из шкалы Цельсия в шкалу Фаренгейта. Перевод осуществляется по формуле:
Температура по Фаренгейту = (температура по Цельсию) 180/100 +32.
Для графического изображения алгоритмов используются графические символы. Наиболее распространенными являются блочные символы (блоки), соединяемые линиями передач управления. Существует государственный стандарт на выполнение графической записи алгоритма. Графическая запись алгоритма является наиболее наглядной. Перечень условных графических символов, их наименования, форма, размеры и отображаемые функции устанавливаются ГОСТ 19.003–80.
Схемы могут быть представлены также в виде структограмм или по имени их авторов, диаграммами Нэсси – Шнейдермана.
Схемы алгоритмов
Использование схем позволяет представить алгоритм в наглядной форме, поэтому они наиболее часто используются.
Вычислительный блок представляет собой прямоугольник, в котором записываются расчетные формулы. Причем формула должна быть записана таким образом, что вычисляемая переменная записывается слева, далее идет знак равенства (в данном случае этот знак называется присваиванием), далее – расчетная формула.
Проверка условия изображается ромбом, внутри которого записывается это условие. В результате проверки выбирается один из двух возможных путей вычислительного процесса.
Если условие выполняется, то есть имеет значение ДА, то следующим выполняется этап по стрелке ДА. Если условие не выполняется, то осуществляется переход по стрелке НЕТ.
Начало и конец вычислительного процесса изображаются овалом, в котором записываются слова “Начало” или “Останов”.
При решении задач на ЭВМ исходные данные задаются при вводе в машину. Ввод данных может осуществляться разными способами, например, с клавиатуры, с перфоленты, с диска и т. д. Задание численных значений исходных данных мы будем называть вводом, а фиксацию результатов расчета – выводом. Ввод исходных данных и вывод результатов изображаются параллелограммом. Внутри него пишется слово “Ввод” или “Вывод” и перечисляются переменные, подлежащие вводу или выводу.
Параллелограммом обозначается ввод – вывод, не привязанный к какому–либо конкретному устройству. Если ввод или вывод осуществляется с использованием конкретных устройств, то блоки ввода – вывода изображаются с помощью специальных фигур.
Комментарий используется в тех случаях, когда пояснение не помещается внутри блока.
По стандарту высота блока равна а, ширина 2а, где размер а выбирается из ряда 10, 15, 20 мм. Блоки “начало” и “конец” имеют высоту 0.5а.
Линии потока проводят параллельно внешним краям рамки листа. Направление линий потока сверху вниз и слева направо принимают за основное; если линии потока основного направления не имеют изломов, то их направление стрелками можно не обозначать. В остальных случаях направление линий потока обозначать стрелкой обязательно. Записи внутри символа или рядом с ним должны выполняться машинописью или чертежным шрифтом и должны быть краткими. В левом верхнем углу в разрыве линий ставится номер блока.
В настоящее время основная тенденция в использовании схем алгоритмов состоит не столько в указании последовательности операций, сколько в группировании блочных символов в виде базовых управляющих конструкций. К ним относятся следование, ветвление и повторение. Основные структуры алгоритмов – это ограниченный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий. Такие структуры рекомендуются при использовании так называемого структурного подхода к разработке алгоритмов и программ. Структурный подход предполагает использование только нескольких основных структур, комбинация которых дает все многообразие алгоритмов и программ.
