2. Разработка схемы алгоритма

2.1. Разветвляющиеся вычислительные процессы

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

Пример 1. Составить схему вычисления Z = max(X,Y).

В рассматриваемом примере возможно два варианта ответа: X или Y. Выбор варианта будет проведён по результату проверки: x > y ? Для однозначности решения считаем, что при Х = Y max = X. В общем случае местоположения знака равенства определяется постановкой самой задачи.

Алгоритм вычисления будет иметь вид:

Фрагмент схемы вычисления представлен на рис.1. Фрагмент, так как в схеме не указаны символы действий Начало, Останов, Ввод исходных данных X, Y.

Рис.1. Фрагмент схемы вычисления Z = max(X,Y)

Пример 2. Составить схему вычисления Z = min(X,Y).

Как и в предыдущем примере будет два варианта ответа и алгоритм можно записать следующим образом:

Фрагмент схемы вычисления представлен на рис. 2.

Рис.2. Фрагмент схемы вычисления Z= min(X,Y)

Оба алгоритма имеют две ветви вычисления Z. Правая ветвь работает, если условие выполнено, т.е. Да. Левая ветвь работает, если условие нарушено, т.е. Нет. Одновременно обе ветви никогда не будут работать.

Пример 3. Составить схему вычисления Z = max(А,В,С). В данном примере возможны три варианта ответа: или А , или В , или С . Выбор может быть выполнен только по результатам проверки не менее двух условий, если при решении задачи используется промежуточная переменная. Следовательно, схема вычисления должна содержать следующие символы действий:

Начало и Останов;

Ввод данных А, В,С;

Два символа Решение, проверяющие условия;

Три символа Процесс, которые присваивают Z определённое значение;

Документ.

Введем промежуточную переменную R и следующие обозначения.

R = max (A, B), тогда

Z = max(R, C)

Алгоритм выбора max из двух переменных рассмотрен в примере 1. Если в примере 1 рассматривались исходные данные и ответ, то в этом примере введена дополнительная рабочая переменная R. Число вводимых рабочих переменных в любой программе не ограничено.

Алгоритм вычисления будет иметь вид:

Схема вычисления представлена на рис. 3

Рис. 3. Схема вычисления Z=max(A,B,C). Способ с использованием промежуточной переменной

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

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

Z = max(A,B), Z = max(Z,C)

Изменить схему предлагается самостоятельно.

2.2. Циклические вычислительные процессы

Большинство задач, решаемых в инженерной практике, имеют циклическую структуру. Циклический вычислительный процесс – это процесс, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий при различных значениях входящих в них величин.

Многократно повторяющиеся участки называют циклами. Циклическая структура позволяет существенно сократить объём алгоритма и программы. Переменная алгоритма, которая при каждом выполнении цикла принимает новое значение, называется параметром цикла.

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

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

Если в цикле изменяется простая переменная, то параметром цикла является эта переменная. Для переменных с индексом (массивов) параметром цикла является индекс переменной.

В контрольном задании №3 представлены задачи циклической структуры типа арифметической прогрессии.

Рассмотрим наиболее типичные алгоритмы циклической структуры.

Пример 4. Задан массив по имени А, состоящий из 20 элементов, A_i , i=1,..,20. Составить схему вычисления суммы и произведения элементов этого массива.

При вычислении суммы используется приём накопления – новое слагаемое прибавляется к сумме предыдущих. При выполнении при каждом цикле нужно накапливать сумму, прибавляя очередное слагаемое к этой сумме. Для этого необходимо перед циклом задать начальное значение суммы равное 0. В данном примере параметром цикла будет индекс i, который изменяется от 1 до 20 с шагом равным 1.

Тот же приём используется и при накоплении произведения. В алгоритмических языках Фортран и Бейсик, если переменная не определена, то ей присваивается значение 0, следовательно, произведение значений функции вычисляться не будет, поэтому перед циклом задаётся начальное значение произведения, равное 1. Внутри цикла вычисляется очередной сомножитель и умножается на произведение.

В соответствии со смыслом описываемых величин выбираем имя переменных: для суммы – S, произведения – P.

Схема вычисления будет состоять из следующих символов действий.

1. Начало.

2. Ввод массива A_i, i=1,..,20.

3. Процесс. Переменным S и P задаются начальные значения S=0, P=1.

4. Начало цикла. Указывается параметры цикла: начальное и конечное значение параметра i и шаг цикла, равный 1.

5. Процесс. Происходит накопление суммы S и произведения P.

S=S+A_i

P=P*A_i

6. Конец цикла по параметру i. Цикл, т.е. вычисление S и P выполняется до тех пор, пока параметр i меньше или равен конечному значению. Как только параметр будет больше конечного значения, то цикл заканчивается и следующим будет выполняться печать результатов.

7. Документ, который выводит на печать вычисленные сумму S и произведение P.

8. Останов.

Схема вычисления представлена на рис. 4.

Рис. 4. Схема вычисления суммы и произведения элементов массива.

Пример 5. Задан массив по имени Х, состоящий из 10 элементов, Х_j, j=1,..,10. Составить схему вычисления произведения положительных элементов этого массива.

Для вычисления произведения используем приём накопления, который был подробно описан выше. Но в данном примере вычисляется произведение только положительных элементов, поэтому внутри цикла нужно выполнить проверку очередного элемента массива Х_j на знак. Если элемент положителен, то он умножается на произведение, если нет – то он не рассматривается.

Параметром цикла будет индекс j, который изменяется от 1 до 10 с шагом равным 1. Переменную произведения обозначим через P.

Схема вычисления будет состоять из следующих символов действий.

1. Начало.

2. Ввод массива Хj, j=1,..,10.

3. Процесс. Переменной P задаётся начальное значение равное 1.

4. Начало цикла. Указывается начальное и конечное значение параметра цикла j и шаг цикла.

5. Решение. Очередной элемент массива проверяется на знак. Хj >0?

6. Процесс, вычисляющий произведение P=P*Хj

7. Конец цикла по параметру j. Цикл выполняется до тех пор, пока параметр j меньше или равен конечному значению, иначе цикл будет закончен и следующим будет выполняться Документ.

8. Документ, выводящий на печать вычисленное произведение Р.

9. Останов.

Схема вычисления представлена на рис. 5.

Рис. 5. Схема вычисления произведения положительных элементов.

При вычислении произведения отрицательных элементов массива в схеме изменится только содержание п.5 Решение.

Пример 6. Задан массив Х, состоящий из 20 элементов, Х_i, i=1,..,20. Составить схему вычисления суммы и количества положительных элементов массива.

Приём вычисления суммы S описан в примере 4. тот же приём используется и при вычислении количества элементов. Обозначим через k – накопленное количество элементов. Такую переменную k называют счётчиком. Перед входом в цикл k нужно «почистить», т.е. присвоить 0. И при каждом цикле увеличивать счётчик на 1.

В данном примере вычисляется сумма и количество только положительных элементов, следовательно, внутри цикла нужно сделать проверку очередного элемента массива Х_i на знак, как это было сделано в примере 5. Параметр цикла – индекс i, изменяющийся от 1 до 20 с шагом 1.

Схема вычисления будет состоять из следующих символов действий.

1. Начало.

2. Ввод массива Х_i , i=1,..,20.

3. Процесс. Переменным S и K задаются начальные значения S=0, K=0.

4. Начало цикла. Задаётся начальное и конечное значение параметра i и шаг цикла.

5. Решение. Проверяется положительность очередного элемента массива, т.е. Х_i >= 0?

6. Процесс. Происходит процесс накопления суммы S и увеличения счетчика К на 1, т.е. S=S+X_i , К=К+1.

7. Конец цикла по параметру i. Цикл повторяется до тех пор, пока параметр i меньше или равен 20. Если i больше, то следующим выполняется Документ.

8. Документ. Печатаются значения S и К.

9. Останов

Схема вычисления представлена на рис.6

Пример 7. Для массива Х, описанного в примере 6, вычислить среднее арифметическое значение положительных элементов.

Схема вычисления будет совпадать с предыдущей до п.7. Конец цикла.

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

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

8. Решение. Проверка числа элементов К=0? Если Да – печать с сообщением ‘K=0’, если Нет – переход на вычисление R.

9. Документ, в котором на печать выводится сообщение ‘Положительных элементов нет’, и переход к символу Останов.

Рис. 6. Схема вычисления суммы и количества положительных элементов массива.

10. Процесс. Вычисляется R=S:K.

11. Документ, в котором печатается значение R.

12. Останов.

Схема вычисления представлена на рис.7.

Если будет вычисляться среднее арифметическое всех элементов массива, то в схеме не будет проверки очередного элемента массива на знак, т.е. не будет п.5 Решение.

При вычислении среднего арифметического отрицательных элементов массива в п.5 Решение будет проверка условия Х_i<0? Остальные пункты останутся без изменения.

Пример 8. Заданы два массива А_i , i=1,…,25 и В_j , j=1,…,30 . Составить схему вычисления положительных элементов в каждом массиве. Определить в каком массиве больше положительных элементов.

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

Рис.7. Схема вычисления среднего арифметического значения положительных элементов массива.

Обозначим через КА–количество положительных элементов в массиве А, КВ–количество положительных элементов в массиве В.

Схема вычисления будет состоять из следующих действий.

1. Начало.

2. Ввод массивов А_i , i=1,…,25 и В_j , j=1,…,30 .

3. Процесс. “Обнуление” счетчиков КА и КВ, т.е. КА=0, КВ=0.

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

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

12. Документ. Печать КА и КВ.

13. Решение. Проверка, где больше положительных элементов в массиве А и В. Или количество элементов совпадает? Если КА>КВ, то выполняется п.14, если КА<КВ – то п.15, а если КА=КВ, то п.16.

14. Документ. Печать сообщения ‘В массиве А больше положительных элементов’. Переход на п.17. Останов.

15. Документ. Печать сообщения ‘ В массиве В больше положительных элементов’. Переход на п.17. Останов.

16. Документ. Печать сообщения ‘Количество элементов совпадает’.

17. Останов

Схема вычисления представлена на рис.8

Пример 9. Задан массив Y_j, j = 1,..,30. Найти максимальный (наибольший) элемент этого массива.

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

После окончания цикла значение Ymax будет максимальным из всех рассмотренных значений Y_j.

Для применения указанной формулы необходимо перед началом цикла задать начальное значение Ymax. Обычно в качестве Ymax берут очень маленькое число. Тогда после первого выполнения цикла Ymax примет значение Y₁. При втором выполнении цикла Ymax будет сравниваться с Y₂ и находится наибольшее из Y₁ и Y₂ и т.д.

Если выбирается максимальный элемент массива, как в нашем примере, то в качестве наибольшего значения Ymax берется значение первого элемента массива, а в цикле поиск максимального элемента начинается со второго элемента массива.

Схема вычисления будет состоять из следующих действий.

1. Начало

2. Ввод массива Yj; j = 1,..,30

3. Процесс. Присвоение начального значения Ymax = Y₁.

4. Начало цикла. Задается начальное и конечное значение параметра цикла j и шаг цикла.

5. Решение. Сравнение значения j-го элемента массива и Ymax, т. е. Y_j > Ymax? Если значение Y_j больше значения Ymax, то следующим будет выполнятся п. 6. Процесс. Если – нет, то переход на Конец цикла.

6. Процесс. Присвоим Ymax значение j –го элемента

7. Конец цикла по параметру j.

8. Документ. Печать Ymax.

9. Останов.

Схема вычислений представлена на рис. 9.

Рис. 8. Схема вычисления положительных элементов двух массивов и определение их числового соотношения.

Рис.9. Схема вычисления максимального элемента массива.

Если надо найти минимальный (наименьший) элемент массива, то для выбора минимального элемента используется формула

И алгоритм выбора аналогичен рассмотренному выше.

Как и в предыдущем примере в качестве начального значения Ymin берётся значение первого элемента массива и цикл начинается со второго элемента массива.

Пример 10. для массива Y, заданного в примере 9, найти минимальный элемент Ymin и его порядковый номер.

Особенностью данного примера является то, что нужно найти не только минимальный элемент, но и его порядковый номер. Для этого каждый раз, когда в цикле будет выполняться условие Y_j < Ymin, нужно будет выполнить два присвоения: Ymin присвоить значение j-го элемента Y_j, и переменной jmin, обозначающий порядковый номер Ymin, присвоить значение параметра j, т.е. jmin= j.

Так как цикл начнёт выполнятся со второго элемента, то может оказаться, что первый элемент Y₁ будет минимальным. Поэтому перед циклом нужно задать не только начальное значение Ymin = Y₁ , но и jmin = 1.

На печать в п. Документ следует выводить jmin и Ymin. Схема вычисления аналогична схеме на рис.9 с соответствующими дополнениями.