Блок-схемы алгоритмов, содержащих команды обращения к вспомогательным алгоритмам

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

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

Использование вспомогательных алгоритмов вызывает необходимость оформлять их специальным образом, чтобы иметь возможность в дальнейшем ссылаться на них в основном алгоритме. Формальные способы оформления таких алгоритмов широко применяются в языках программирования, а сами вспомогательные алгоритмы, записанные на языках программирования, называют подпрограммами или процедурами. При использовании блок-схем полная формализация в оформлении вспомогательных алгоритмов, как правило, не производится. Однако, будем придерживаться некоторых принципов оформления. В заголовке вспомогательного алгоритма (блок «начало») за именем вспомогательного алгоритма будем указывать в круглых скобках список так называемых формальных параметров. В списке формальных параметров укажем имена входных и выходных данных (аргументов (арг) и результатов (рез)) алгоритма. Это необходимо для того, чтобы при ссылке на подчиненный алгоритм в основном алгоритме можно было задать значения аргументов, а после исполнения вспомогательного алгоритма, воспользоваться результатами – значениями соответствующих данных. Например, если алгоритм нахождения большего из двух чисел необходимо оформить как вспомогательный, где a и b – аргументы, а z – результат, то блок начала этого алгоритма оформим так:

БИД – имя алгоритма (большее из двух).

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

< имя вспомогательного алгоритма> (< список фактических параметров>).

На блок-схеме вызов вспомогательного алгоритма изобразим в виде геометрической фигуры , внутри которой запишем команду вызова вспомогательного алгоритма. Например, если в основном алгоритме необходимо найти большее из данных k и l, где переменной k было присвоено значение 45, а переменной l – значение 21, и результат присвоить переменной y, то обращение к вспомогательному алгоритму запишем так: , где k, l, y – фактические параметры.

Исполнение команды вызова вспомогательного алгоритма эквивалентно исполнению вспомогательного алгоритма с фактическими параметрами. Команда вызова вспомогательного алгоритма исполняется как один шаг основного алгоритма.

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

1. На время исполнения команды обращения к вспомогательному алгоритму выполнение основного алгоритма приостанавливается.

2. Формальным параметрам-аргументам вспомогательного алгоритма присваиваются значения фактических параметров, записанных в команде вызова вспомогательного алгоритма.

3. Исполняется вспомогательный алгоритм с полученными значениями аргументов.

4. Значения результатов-параметров вспомогательного алгоритма присваиваются соответствующим значениям параметров, записанных в команде вызова вспомогательного алгоритма.

5. Выполняется команда основного алгоритма, следующая за командой вызова вспомогательного алгоритма.

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

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

Задача 30. Наибольший общий делитель. Составьте блок-схему алгоритма нахождения z – наибольшего общего делителя четырех натуральных чисел a, b, c, d, используйте для решения задачи вспомогательный алгоритм нахождения наибольшего общего делителя t двух натуральных чисел m и n.

Решение. Смотри блок-схемы 1-2 алгоритма (задача 30).

Составим блок-схему вспомогательного алгоритма НОД, нахождения наибольшего общего делителя двух натуральных чисел m и n, значение наибольшего общего делителя двух натуральных чисел присвоим переменной t. Для решения поставленной задачи воспользуемся тремя предложениями (обозначим НОД (m, n) – наибольший общий делитель m и n):

1. НОД(m, n) = НОД(m - n, n), если m > n.

2. НОД(m, n) = НОД(m, n - m), если n > m.

3. НОД(m, n) = m, если m = n.

НОД(25, 15) = НОД(10, 15) (1);

НОД(10, 15) = НОД(10, 5) (2);

НОД(10, 5) = НОД(5, 5) (1);

НОД(5, 5) = 5 (3) => НОД(25, 15) = 5.

Блок-схема1 основного Блок-схема2 вспомогательного

алгоритма (задача 30): алгоритма (задача 30):

Задача 31. Числа Мерсенна. Числа вида 2 ^p -1, где p – простое число, называются числами Мерсенна[7]. Многие числа Мерсенна также являются простыми. Составьте алгоритм нахождения всех чисел Мерсенна, принадлежащих отрезку [2; n ].

Решение. Смотри блок-схемы 1-3 алгоритма (задача 31).

Для решения задачи будем получать числа вида 2 ^p -1, где p = 2, 3, …. Если p – простое, то 2 ^p -1 – число Мерсенна. Рассмотрим, как можно получить следующего кандидата в числа Мерсенна, если известен предыдущий проверенный кандидат:

Кандидат = 2 ^p -1,

где p = 2, 3, 4, 5, 6, …;

следующего кандидата обозначим Кандидат1:

Кандидат1 = 2 ^{p +1}-1;

2 ^{p +1}-1 = 2*2 ^p -1 = 2*(2 ^p -1) + 1; Кандидат1 = 2 * Кандидат + 1.

Нового кандидата в числа Мерсенна будем проверять осторожно, чтобы не было превышено n. Если проверяемых кандидатов на отрезке [2; n ] больше нет, то флажку fl будем присваивать значение «да». До проверки первого кандидата флажку fl присвоим значение «нет». Найдем n 1 = n /2:

если Кандидат£ n 1, то Кандидат1: =2*Кандидат, иначе fl: =да;

если Кандидат1< n, то Кандидат1: =Кандидат1+1, иначе fl: =да.

Легко проверить, что число 2²-1, равное 3 – число Мерсенна. Проверку высказывания «p – число простое» оформим в виде одного из вспомогательных алгоритмов простое (арг a, рез fl1) или простое1 (арг a, рез fl1).

Составим блок-схему вспомогательного алгоритма простое1 (арг a, рез fl1), алгоритма проверки является ли число a простым числом. Заметим, что все четные числа, большие 2 являются составными. Проверим, имеет ли число а (нечетное, большее 2) делители, отличные от 1 и самого себя. Исследуем числа от 2 до [ a /2]+1, где [ a /2] – целая часть частного a /2 (a > 0). На отрезке [[ a /2]+1; a -1] не могут находиться делители числа a. Делителями нечетного числа а могут быть только нечетные числа k, меньшие [ a /2]+1. Будем их получать так:

k: =[a/2]+1-2; k: =k-2

и т.д. до тех пор, пока k < > 1. Проверку реализуем в виде цикла. Из цикла выйдем, если k является делителем числа а (k =1 или k < > 1). По окончании цикла проверим значение k: если k =1, то число простое и fl 1: =да, иначе число составное и fl 1: =нет.

Числа Мерсенна: 3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647, …

Задача 32. Наибольший элемент в массиве. Составьте алгоритм поиска наибольшего элемента t в линейной таблице из n чисел a(1: n), используя алгоритм БИД (нахождения большего из двух чисел), как вспомогательный.

Решение. Смотри блок-схемы 1-2 алгоритма (задача 32).

Блок-схема1 вспомогательного алгоритма (задача 32):

Блок-схема2 основного Блок-схема алгоритма

алгоритма (задача 32): (задача 33):

Задача 33.Близнецы. Два нечетных простых числа, отличающихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. Составьте блок-схему нахождения близнецов на отрезке от 2 до n.

Решение. Смотри блок-схему алгоритма (задача 33).

Будем определять является ли число p Î [2; n ] простым, если p – простое, то проверяем простое ли число p +2, если p и p +2 простые, то их выводим; далее исследуем числа p +1 и p +3 и т.д. Для определения является ли число p простым воспользуемся вспомогательным алгоритмом простое (арг a, рез fl1) или простое1 (арг a, рез fl1) (стр. 60-61, задача 31).

Задача 34. Сумма чисел Фибоначчи. Представьте число m в виде суммы наибольших чисел Фибоначчи. Составьте блок-схему алгоритма решения поставленной задачи.

Решение. Смотри блок-схемы 1-2 алгоритма (задача 34).

Для решения поставленной задачи воспользуемся алгоритмом задачи 18, стр. 42, как вспомогательным.

Блок-схема1 вспомогательного Блок-схема2 основного

алгоритма (задача 34): алгоритма (задача 34):

Задача 35. Сдвиг1 элементов в массиве. Составьте алгоритм циклической перестановки элементов массива B(1: n) на заданное число k шагов так, чтобы элемент B(i) переместился на место B(i + k), а последние k элементов массива, которым «не хватило места», переместились, соответственно, на первые k мест, освободившихся при сдвиге. (Массив B(1), B(2), …, B(n) преобразовался в массив B(n - k +1), …, B(n -1), B(n), B(1), B(2), …, B(n - k).) Составьте блок-схему алгоритма решения поставленной задачи.

Решение. Смотри блок-схемы 1-2 алгоритма (задача 35).

Для решения поставленной задачи воспользуемся составленным алгоритмом задачи 26, стр. 51, как вспомогательным.

Задача 36. Кратные пары. Заданы два массива A(1: n) и B(1: n) натуральных чисел. Подсчитайте число k пар (a_i, b_i), 1£ i £ n, соответствующих друг другу кратных чисел этих массивов и найдите сумму частных от деления большего числа каждой такой пары на меньшее. Составьте блок-схему алгоритма решения поставленной задачи.

Решение. Смотри блок-схемы 1-2 алгоритма (задача 36).

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

Блок-схема1 основного алгоритма Блок-схема2 вспомогательного

(задача 36): алгоритма (задача 36):