Разработка машинно-ориентированного алгоритма.

Под машинно-ориентированным понимается алгоритм, удобный для решения данной задачи на ЭВМ. Это очень важный этап, так как алгоритм определяет логическую структуру программы. Алгоритм может быть описан словесно или графом (называемым блок-схемой), что строже и нагляднее. Словесное описание применяется обычно для разрешения затруднений при построении графа. Граф состоит из вершин (блоков), объединенных ребрами. Типы блоков представлены в таблице 0.0.1.

К вершинам типа 1 и 3 подходят два ребра (одно входящее и одно выходящее). К вершинам типа 4 и 5 - лишь одно ребро (либо входящее, либо выходящее). В таблице для типа 4 представлен вариант блока "Начало". К вершинам типа 2 подходят три ребра (одно входящее и два выходящих – для "да" и "нет"), причем одно из выходящих может начинаться из нижнего угла ромба. Таким образом, вершине типа 2, в зависимости от расположения выходящих ребер и сопоставленных им "да" и "нет", соответствует 6 вариантов. Вершины типа 1 – 3 в блок-схеме обычно нумеруются. Движение по графу подразумевается сверху – вниз. При соблюдении этого правила стрелки не используются, а иное направление указывается ребром со стрелкой.

В соответствии с основной теоремой структурного программирования, доказанной Э.Дейкстрой, алгоритм любой сложности можно реализовать, используя только три конструкции: следование (оператор за оператором), повторение (цикл), выбор (альтернатива). Первой конструкции соответствует линейная программа (пример алгоритма которой приведен на рисунке слева), второй – циклическая (на рисунке справа), третьей – с разветвлениями (в середине).

В укрупненном виде алгоритм состоит из:

а) ввода входных данных

б) собственно алгоритма программы, представляющего собой необходимую комбинацию из трех конструкций

в) вывода результата

Ввод входных данных и вывод результата тоже могут иметь сложную структуру.

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

После блока 1, реализующего ввод размерности (длины) последовательности, организуем цикл из блоков 2-7 для ввода элементов последовательности,

причем сначала рисуется тело цикла - блоки 3-5, которые затем обрамляются блоками 2, 6, 7, обеспечивающими выполнение цикла. Блок 3 задает выбор: ввод элементов последовательности с помощью генератора случайных чисел (блок 4) или с клавиатуры (блок 5). Блок 2 определяет начальное значение счетчика цикла, блок 6 – конечное, реализуя при этом условие окончания цикла, а блок 7 увеличивает значение счетчика цикла. Аналогично организуется цикл из блоков 8-14, тело которого составляют блоки

10-12. Блоки 10-11 обеспечивают проверку на четность, а блок 12 – вычисление произведения нечетных чисел последовательности. Блок 8 задает начальное значение для вычисления произведения P1 = 1. Блок 15 служит для вывода результата на экран.

Хорошо составленный алгоритм позволяет проверять правильность работы программы без компьютера. Для этого необходимо добросовестно пройтись по блокам алгоритма. Например:

Бл.1: вводим n = 4. Начинается цикл по вводу. Бл.2: i = 1.

Шаг 1: Бл.3: по "нет" выбираем ввод с клавиатуры. Бл.5: вводим a(1) = 5. Бл.6: проверка (i = 1) < (n = 4), по "да". Бл.7: i = 1+1=2.

Шаг 2: Бл3: по "нет". Бл.5: вводим a(2) = 4. Бл.6: (i = 2) < (n = 4), по "да". Бл.7: i = 2 + 1 = 3.

Шаг 3: Бл.3: по "нет". Бл.5: вводим a(3) = 2. Бл.6: (i = 3) < (n = 4), по "да". Бл.7: i = 3 + 1 = 4.

Шаг 4: Бл.3: по "нет". Бл.5: a(4) = 7. Бл.6: (i = 4) = (n = 4), по "нет". Завершен цикл по вводу, начинается цикл по вычислению произведения. Бл.8: Р1 = 1. Бл.9: j = 1

Шаг 1: Бл.10: деление (a(1) = 5) / 2 = 2.5. Бл.11: деление не нацело, по "нет". Бл.12: Р1 = 1 * a(1) = 1*5 = 5. Бл.13: проверка (j = 1) <

< (n = 4), по "да". Бл.14: j = 1 + 1 = 2.

Шаг 2: Бл.10: (a(2) = 4) / 2 = 2. Бл.11: деление нацело, по "да". Бл.13: (j = 2) < (n = 4), по "да". Бл.14: j = 2 + 1 = 3

Шаг 3: Бл.10: (a(3) = 2) / 2 = 1. Бл.11: деление нацело, по "да". Бл.13: (j = 3) < (n = 4), по "да". Бл.14: j = 3 + 1 = 4

Шаг 4: Бл.10: (a(4) = 7) / 2 = 3.5. Бл.11: деление не нацело, по "нет". Бл.12: Р1 = 5*а(4) = 5*7 = 35. Бл.13: (j = 4) = (n = 4), по "нет".

Завершен цикл. Бл.15: вывод на экран Р1 = 35.

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