Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
?> = {(*, t):t0^t^tl9 х0^х^хх},
где xi9 t{ — заданные числа. Входными данными алгоритмов В8 являются дополнительные условия, однозначно определяющие решение и(х, /) уравнения. Обычно это начальные и граничные условия, например
и(х, /0) = ф(х), х0^х^х19
и(х0> *) = Ы&’ /) = |Xi(/), t0^t^tl9
где ф(х), р0(/), цх(/)—заданные функции на входе алгоритма. Выходными данными является решение уравнения и(х9 /).
45
• 2.2. Структура алгоритмов
В гл. 1 определено понятие архитектуры ЭВМ как набора ресурсов ЭВМ, их структура, доступные программисту. Программист-пользователь может вообще не знать, как физически устроена и работает ЭВМ. Это знает инженер-электронщик. Для программирования важна логическая организация машины. По аналогии с архитектурой ЭВМ можно ввести понятие архитектуры алгоритма.
Архитектура алгоритма—это набор элементарных вычислительных блоков, их структура и логическая организация, необходимые для программирования задачи.
Программист-пользователь может не знать, как запрограммирован отдельный вычислительный блок и даже какой метод вычислений заложен в его основу, это должен знать инженер-математик. Хотя и не все инженеры-математики могут ответить на вопрос, по »какому алгоритму вычисляются значения элементарных функций.
Естественно задать вопрос: что же должен уметь пользователь при построении алгоритма решения задачи и программировании?
Пользователю необходимо уметь:
1) Спроектировать алгоритм методом «сверху вниз» — от сложного к простому, используя готовые (базовые) вычислительные алгоритмы из семейств, перечисленных в 1.1, и применяя «базовые логические схемы».
2) Выбрать те вычислительные алгоритмы, которые удовлетворяют требованиям задачи.
3) В случае отсутствия готового вычислительного алгоритма необходимо его * разработать, запрограммировать и включить в состав базовых вычислительных алгоритмов.
4) Наконец, необходимо запрограммировать весь алгоритм.
2.2.1. Проектирование алгоритма. Проектирование алгоритма
удобно сопровождать блок-схемами. В блок-схемах приняты стандартные графические средства, показанные на рис. 2.4. Внутрь графического знака записывается кратко действие алгоритма,
а в знак «связь» записывается метка, которая обозначает соединение с другой линией, имеющей кружок с такой же меткой. В ромб записываются анализируемые условия, а возможные результаты анализа обозначаются на выходящих из ромба линиях.
Имеются три базовые логические схемы, на основании которых можно спроектировать любой вычислительный алгоритм.
ср
-сг>
с
ТОЧКИ ВХОДА И ВЫХОДА ОБРАБОТКА ИНФОРМАЦИЯ ПРОВЕРКА УСЛОВИЯ
связь (или СЛИЯНИЕ) Рис. 2.4
Рис. 2.5
Последовательная схема (рис. 2.5). Состоит из трех компонентов: входа в вычислительный блок 7, вычислительного блока 2 и выхода из вычислительного блока 2.
Альтернативная схема (рис. 2.6). Состоит из проверки выполнения некоторого условия. Если условие выполняется, то вычисления производятся на блоке 7, если—нет, то на блоке 2. Заметим, что в схеме один из блоков может быть пустым (не содержит действий).
Схема повторения или схема цикла. Состоит из узла слияния, проверки условия и вычислительного блока (рис. 2.7). В этой схеме после узла слияния происходит проверка условия: если оно выполняется, то происходят вычисления на блоке,
Рис. 2.6
если—нет, то происходит выход из схемы. Таким образом, вычисления в блоке выполняются до тех пор, пока условия не будут выполняться. Поскольку условие проверяется до вычислительного блока, возможно, что действие блока не выполнится ни разу. С другой стороны, если условие всегда выполняется, то вычислительный процесс зацикливается, так как нет возможности попасть на выход схемы.
В качестве примера приведем блок-схему алгоритма суммирования кубов целых чисел (рис. 2.8)
ЛГ
5= I к\
кт= 1
Число N—входное данное, ?—выходное.
Рис. 2.7
47
Проектирование алгоритма методом «сверху вниз» на основе базовых логических схем и базовых алгоритмов состоит из следующих шагов. Исходный вычислительный алгоритм представляется в виде одного блока нулевого уровня, на вход которого подаются исходные данные задачи, на выходе получаются выходные данные. Базовыми алгоритмами будем называть те из алгоритмов описанных выше семейств, которые могут быть реализованы пользователем на его вычислительной машине. Например, совокупностью базовых алгоритмов можно считать алгоритмы, для которых представлены в гл. 12 описания фортран-программ.
Если задача может быть решена с помощью одного базового алгоритма, то проектирование на этом заканчивается, если—нет, то нулевой уровень проекта алгоритма разворачивается в последовательность базовых алгоритмов (рис. 2.9), где вычислительные блоки можно обозначить по принятой схеме: А4А0, В1А1 и т. п. Не помеченные на рис. 2.9 вычислительные блоки отсутствуют среди базовых алгоритмов и должны быть разработаны пользователем, обозначены в соответствии с принятой схемой и включены в состав базовых.
Таким образом, проект алгоритма первого уровня состоит в последовательном обращении к базовым алгоритмам и не содержит 2-й и 3-й логических схем в своей структуре.
