Глава 8. Технология программирования смешанных процессов
Смешанный – вычислительный процесс из совокупности стандартных компонентов (линейного, ветвящегося, циклического).
Смешанные вычисления характеризуются взаимодействием внешнего и внутреннего компонентов.
В качестве внешнего компонента в принципе возможно использование линейного и ветвящегося процесса. Однако в большинстве задач им является циклический вычислительный процесс.
В качестве внутренних компонентов рассматривается каждый из возможных внешних, позволяя сформулировать следующие комбинации:
цикл (внешний) с линейный процессом (внутренним);
цикл (внешний) с ветвлениями (внутренними);
цикл (внешний) с циклами (внутренними).
Графическая интерпретация этого варианта по критерию «внутренние компоненты» представлена на рис. 8.1.
Рис. 8.1. Взаимодействие компонентов смешанного процесса
Предлагаемые структуры позволяют реализовать типовые математические задачи:
вычисления накоплений;
поиск экстремальных значений;
расчет элементов многомерных матриц и ранжирование.
Классификация типовых вычислений с использованием смешанных вычислительных процессов представлена на рис. 8.2.
Рис. 8.2. Классификация смешанных задач
Программирование перечисленных задач с использованием смешанных вычислительных процессов рассматривается ниже.
Вычисление накоплений
Накопление – типовой вычислительный процесс последовательного увеличения (уменьшения) величины искомых данных.
Накопления реализуются вычислениями:
· увеличений (сумм, произведений);
· уменьшений (разностей, частных).
Граическая интерпретация возможных вариантов представлена на рис. 8.3.
Рис. 8.3. Классификация процессов накопления
Все компоненты нижнего уровня базируются на аналогичных закономерностях с некоторыми специфическими особенностями. Рассмотрим программирование основных вариантов накоплений детально.
Вычисление сумм в цикле
В ряде инженерных задач наряду с вычислениями текущих значений функции требуется получить их сумму. Это же требование может относиться и к текущим значениям аргументов, обуславливая необходимость разработки методик вычисления сумм любых изменяющихся в цикле величин.
В математике известны различные методы накоплений. Простейший – метод ручного счёта. Он на первом шаге предписывает вычисление и фиксацию всех текущих значений, подлежащих суммированию, а на втором – сложение уже полученных значений.
Для ЭВМ такой вариант малоприемлем, т.к., во-первых, предписывает формирование полученных слагаемых в массив для хранения, а во-вторых, требует записи в расчётной формуле всех подлежащих суммированию значений, что при большом их количестве приводит к увеличению объёма малопроизводительной работы программиста.
Технология машинного расчёта суммы основывается на идее последовательного накопления искомого значения из составляющих её элементов.
Рассмотрим технологию вычисления сумм подробно.
Задача вычисления суммы некоторого количества элементов-слагаемых математически выражается зависимостью
(
)
где S – искомое значение суммы;
ci – текущее значение слагаемого;
– символ операции сложения;
1, cн – нижняя граница счёта;
n, cк – верхняя граница счёта;
= – символ присваивания.
Представим зависимость в развёрнутом виде:
Обозначив искомую сумму S как Sn, а сумму без последнего слагаемого как Sn-1, получим Sn = Sn-1 + сn. Повторив рассуждения для вычисления Sn-1, запишем Sn-1 = Sn-2 + сn-1.
Аналогично Sn-2 = Sn-3 + сn-2
. . .
Si = Si-1 + сi
. . .
S3 = S2 + с3
S2 = S1 + с2
S1 = S0 + с1
Анализ зависимости S1 = S0 + с1 позволяет сделать вывод, что S1 может быть равна слагаемому с1 только при S0 = 0.
Таким образом, последовательное накопление суммы предполагает следующую методику вычислений:
· формирование (до начала вычислений) начального значения суммы S0 = 0;
· вычисление текущих значений суммы Si последовательным суммированием предыдущего значения суммы Si-1 с текущим значением слагаемого сi.
Инструментом для организации таких вычислений является смешанный вычислительный процесс (циклический, дополненный фрагментами линейного).
Предложенная методика последовательного получения суммы является универсальной и может использоваться с циклическими процессами любых классов и типов.
Выполнив подстановку полученных зависимостей в исходную формулу, получим:
Sn = (((. . .(S0 + с1) + с2) + с3) + . . . + сi-1) + сi) + . . . + сn-1) + сn
Формирование суммы может быть реализовано одним из вариантов:
· массивом для хранения всех текущих значений Si;
· двумя промежуточными переменными (Si и Si-1);
· одной текущей переменной Si.
Массив используют при необходимости долговременного хранения каждого из вычисляемых промежуточных значений суммы. При этом в оптимальном варианте размер создаваемого массива S(n+1) на единицу больше суммируемого S(n) за счёт дополнительного элемента S0.
Две промежуточные переменные (неиндексированные) применяют при желании на каждом шаге вычислений контролировать только смежные значения суммы – текущее (Si) и предыдущее (Si-1), например, для оценки их разности. Этот вариант предполагает до вычисления каждой текущей суммы обязательную операцию переприсваивания полученного значения предыдущему (Si-1 = Si), без чего накопление невозможно.
Одна переменная для организации суммы эффективна при отсутствии любых дополнительных требований, кроме получаемого результата. При этом она используется как хранилище каждого из текущих значений суммы, начиная с нулевого (S = 0), и, заканчивая искомым ( ).
Рассмотрим методики реализации на типовых примерах суммирования:
элементов массивов;
в вычислении полиномов;
в расчете степенных рядов.