АЛГОРИТМИЗАЦИЯ ТИПИЧНЫХ ЗАДАЧ

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

3.3. Алгоритмы основных видов вычислительных процессов

3.3.1. Общие положения

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

● простые (линейные) вычислительные;

● разветвлены вычислительные;

● циклические обчислювальніи.

3.3.2. Простой (линейный) неразветвлен вычислительный процесс

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

Пример 3.1.Записать алгоритм вычисления значения величины Y определяемого следующей формулой:

Y = 150 + a·x.

Схема алгоритма подано на рис. 3.1.

3.3.3. Разветвленные вычислительные процессы

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

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

Рис. 3.1. Схема алгоритма простого (линейного) процесса

Пример 3.2.Записать в виде схемы следующийалгоритм вычисления :

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

● в разных ветках можно использовать и те же обозначения переменных величин;

● вычисление или процессы, которые повторяются в разных ветках схемы алгоритма, выносятся за пределы разветвления (в нашем примере это вычисление выражения k · х ( і);

● сложные условия вычислений разбиваются на ряд простых.

Решение задачи будет иметь вид, поданный на рис. 3.2.

Рис. 3.2. Схема алгоритма простого разветвленного вычислительного процесса

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

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

Например, при вычислении выражения в = а^х, операция умножения повторяется х раз. Если х = 5, то операция умножения повторяется 5 раз, то есть в = а·а·а·а·а, а когда х = 100, то умножение повторяется 100 раз.

Таким образом, циклический вычислительный процесс - это последовательность действий, которая предусматривает повторяемые n раз этапы обработки информации.

Цикл должен длиться до тех пор, пока не выполнится некоторое условие выхода из него.

Пример 3.3.Составить схему алгоритма для вычисления такого выражения

,

при этом параметр цикла изменяется до x_п с шагом h. Такие вычисления значений заданной функции называются табулированием.

Выполняя табулирование, необходимо последовательно перебрать все значения параметра цикла х в отмеченном диапазоне его величин. Как только эту условие будет нарушено, следует прекратить вычисление. Схема алгоритма подается на рис. 3.3.

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

Кроме того, стоит обратить внимание, что в первый символ вводятся отдельные переменные, а несколько однотипных операций введения или выведения данных должны входить в цикл как многократно повторяемые

Циклические процессы можно классифицировать в зависимости от количества и сложности входных циклов на простые (один цикл) и сложные (цикл в цикле или разветвление в цикле). В свою очередь простые циклы разделяются в зависимости от способа выхода из цикла на арифметические и итерационные. Рассмотрим каждый из таких циклов.

Рис. 3.3. Схема алгоритма простого циклического вычислительного процесса

3.3.5. Арифметические циклы

Циклический процесс, в котором загодя известно количество повторений цикла, называется арифметическим циклом.

Например, решение уравнения величины в = ах при заданном значении х или в = n! при заданном значении n, реализуется с помощью арифметических циклических процессов. Количество повторений цикла в них задает величины х и n соответственно.

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

3.3.6. Итерационные циклы

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

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

3.3.7. Сложные циклы

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

Контрольные вопросы

1. Назовите этапы подготовки к решению задач на ПК, что выполняются без применения компьютера.

2. Какие основные свойства алгоритмов вычислительных процессов?

3. Какие процессы могут описывать алгоритмы?

4. С какой целью строят графические схемы алгоритмов?

5. По каким правилам складывают блок-схемы алгоритмов?

6. Какие виды блоков используют в блок-схемах?

7. С учетом каких правил складывают структурные схемы алгоритмов?