Тема № 3 Вспомогательный алгоритм - это алгоритм, при помощи которого в основном или в другом вспомогательном алгоритме решается какая-либо частная алгоритмическая задача. Он имеет имя и может иметь параметры, которые называются формальными параметрами. Имя служит для того чтобы можно было вызывать алгоритм для выполнения, а также отличить такой алгоритм от других алгоритмов. Формальные параметры, которые напоминают переменные математических функций, выполняют роль входных и выходных параметров. Формальные параметры должны быть выбраны таким образом, чтобы ими был исчерпан весь набор необходимых входных и выходных величин. Нередко один и тот же параметр может оказаться входным и выходным одновременно. Например, на вход такого алгоритма может быть подан массив для обработки, а на выходе алгоритма этот массив может предстать в измененном виде как, выходной параметр. Среди вспомогательных алгоритмов различают процедуры и функции . В последнем случае имя служит не только для вызова вспомогательного алгоритма, но предназначено также для определения результата работы алгоритма-функции. То есть имя функции в данном случае выступает в роли ячейки памяти, куда запишется результат после завершения работы такого алгоритма.3.1. Алгоритм с одной вспомогательной процедурой Рассмотрим задачу о перестановке элементов одномерного массива в противоположном порядке. Напомним, что массивом называется упорядоченная последовательность однотипных элементов. Всякий массив имеет размерность. Различают массивы одномерные, двумерные, трехмерные и т. д. На рис. 1. приведен пример одномерного числового массива q, состоящего из 8-ми элементов. В верхней части рисунка размещены порядковые номера элементов массива, которые называются индексами, в нижней - значения элементов.
Решить поставленную задачу можно перестановкой значений 1-го и 8-го элементов, 2-го и 7-го, 3-го и 6-го, 4-го и 5-го. Как видим, в данном случае необходимо выполнить несколько раз одни и те же действия, различие в которых состоит лишь в том, в каждом случае приходится переставлять значения элементов с другими индексами, а сходство в том, что приходится производить операции перестановки. Представим эти действия при помощи вспомогательного алгоритма перестановки значений двух переменных a и b. Блок-схема такого вспомогательного алгоритма показана на рис. 2.
Рис. 2. Вспомогательный алгоритм перестановки значений двух переменных Алгоритм имеет имя Perm (от английского permutation - перестановка) и два формальных параметра a и b. Для перестановки используется вспомогательная переменная c. В блоке 2 значение переменной a предварительно записывается в c. Затем в a копируется значение переменной b, и далее в b копируется сохраненное в c значение переменной a. В результате происходит обмен значениями переменных a и b. Теперь составим головной алгоритм, при помощи которого будет решена поставленная задача. Его блок-схема показана на рис. 3.
Рис. 3. Головной алгоритм перестановки элементов массива в противоположном порядке Сначала в блоке 2 вводятся данные в ячейки массива z. Далее с помощью цикла 3 - 5, выполняется разворот массива. Как видно из рисунка, переменная цикла i на каждом витке цикла последовательно меняет значения от 1 до 4. При каждом таком значение происходит обращение к вспомогательному алгоритму Perm. Обратите внимание, что обращение к вспомогательному алгоритму производится при помощи специального блока, который называется "Предопределенный процесс" (в Visio он называется "Заранее определенный процесс"). При этом на место формальных параметров a и b алгоритма подставляются фактические параметры - элементы массива z. При i = 1 будут подставлены элементы z[1] и z[8], после чего вспомогательный алгоритм выполнит перестановку их значений. Далее на новом витке цикла при i = 2 будут подставлены элементы z[2] и z[7] и выполнена перестановка их значений. Последней при i = 4 будут выполнена перестановка значений элементов z[4] и z[5]. В результате массив будет развернут, в чем можно будет убедиться при его выводе в блоке 6. Создайте блок-схемы алгоритмов при помощи программы Microsoft Visio. Реализуем вспомогательный и головной алгоритмы в среде Delphi. Запустим Delphi XE7 и создадим новое приложение. Положите на форму компонент TStringGrid и кнопу TButton, как показано на рис. 4. Сетка TStringGrid находится на закладке Additional. Её мы будем использовать для ввода элементов массива, а также для его вывода после перестановки элементов. С помощью кнопки будем запускать процесс разворота значений элементов массива.
Рис. 4. Окно приложения Delphi Дайте компоненту сетки TStringGrid имя Sg (свойство Name). Измените значения его свойства ColCount (количество столбцов) на 9, RowCount (количество строк) на 3, ColWidth (ширина столбца) на 40. Для того, чтобы иметь возможность вводить данные в ячейки сетки установите опцию Options goEditing в true. Перейдите в редактор кодов и добавьте в модуль текст процедуры Perm, как показано на рис. 5. Текст процедуры Perm открывается ключевым словом procedure. Далее расположено имя процедуры и в скобках указаны формальные параметры a и b. Эти параметры являются переменными, так как перед ними расположен описатель var. Переменные имеют тип Double - то есть вещественный тип. После заголовка процедуры объявлена вспомогательная переменная c, которая имеет тот же тип. Далее в теле процедуры, которое находите внутри блоков begin end, расположены операторы перестановки значений переменных. Текст процедуры вспомогательного алгоритма готов.
Рис. 5. Код модуля Unit1 Теперь, щелкнув дважды на кнопке, создадим для нее событие OnClick и вставим код, который также расположен на рис. 5 ниже текста процедуры Perm. После заголовка procedure обработчика события объявлено 2 переменные: целочисленная переменная i и одномерный массив z из 8 ячеек типа Double (вещественный). В теле процедуры сначала выполняется перенос данных их 1-й строки сетки Sg в массив z:
Как видим, счетчик цикла i будет меняться в нем от 1 до 8. При этом на каждом из 8-ми витков этого цикла будет взята строка символов Sg.Cells[i,1], которая расположена в ячейке на пересечении i-того столбца и 1-й строки сетки, далее при помощи оператора StrToFloat эта строка будет преобразована в вещественное число и передана в ячейку z[i]. В результате выполнения такого цикла данные из ячеек первой строки сетки Sg будут преобразованы и скопированы в массив z. Теперь массив можно разворачивать. Разворот массива производится циклом
Этот цикл совершает 4 витка. На каждом витке происходит обращение к процедуре Perm, которая производит перестановку соответствующих элементов массива. После того, как цикл выполнится, массив будет развернут в противоположном порядке. Занесем переставленный массив во 2-ю строку сетки Sg с тем, чтобы убедиться, что операции выполнены правильно. Для этого применим цикл
Этот цикл совершит 8 витков. В нем значение текущего числового элемента z[i] сначала будет преобразовано в строку символов и затем передано в соответствующую ячейку Sg.Cells[i,2] сетки Sg. Пример такой перестановки показан на рис. 6.
Рис. 6. Исходный массив
z и переставленный с помощью Таким образом, использование вспомогательного алгоритма позволяет не только упростить программирование головного алгоритма, но и найти применение ему в других алгоритмах, где он необходимо совершать перестановку элементов. 3.2. Алгоритм с несколькими вспомогательными процедурами Рассмотрим задачу. Имеется два одномерных числовых массива произвольной длины. Необходимо выполнить сортировку массивов в порядке возрастания значений их элементов. Задачу удобно решить посредством разработки и последующего применения нового вспомогательного алгоритма, предназначенного для сортировки таких массивов. Поскольку длины исходных массивов произвольны, то в качестве формального параметра в новой вспомогательной процедуре будет не только имя сортируемого массива, но и его длина. Будем сортировать массив "методом пузырька". Суть этого метода состоит в следующем. Совершается проход по всем парам соседних элементов массива. Если пара не отсортирована, то значения ее элемент ов меняются местами. Если при проходе была совершена хотя бы одна перестановка, то совершается новый проход и перестановка неотсортированных пар. Процесс производится до тех пор, пока при очередном проходе не будет выполнено ни одно перестановки. Это является сигналом, что массив отсортирован.Блок схема вспомогательного алгоритма сортировки массива показана на рис. 7.
Рис. 7. Вспомогательный алгоритм сортировки одномерного массива Процедура имеет имя Sort и два формальных параметра: n - длина массива, z - имя массива. Сортировка осуществляется при помощи структуры вложенных циклов. Наружным циклом являются блоки 2 - 8. Внутренний цикл образован блоками 3 - 7. Один виток наружного цикла представляет собой отдельный проход по массиву при сортировке. Внутренний блок предназначен для перебора соседних пар массива при таком проходе. В начале наружного цикла в блоке 2 логической переменной b присваивается значение true. Под этим мы будем понимать, что до прохода по парам, мы предполагаем, что массив отсортирован. Далее выполняется внутренний цикл блоков 3 - 7. В нем переменная цикла i меняется от 1 до n-1, поскольку, если число элементов равно n, то соседних пар будет n-1. Для каждой текущей пары соседних элементов z[i] и z[i+1] проверяется условие 4. Если оно выполняется, то значит эту пару надо переставлять и зафиксировать тот факт, что массив оказался неотсортированным, что фиксируется оператором блока 5. Перестановка пары происходит в блоке 6 посредством обращения к процедуре Perm. Если же условие не выполнилось, то пара отсортирована и операторы фиксации и перестановки надо обойти и уйти в конец цикла к блоку 7, который вернет управление к началу цикла 3. После выхода из цикла 3 - 7 в блоке 8 осуществляется проверка значения переменной b. Если она истинна, то в цикле не было перестановок, то есть массив отсортирован, и процедуру следует закончить. Если же b ложно, то имели место перестановки, и нужно совершать новый проход по парам, для чего следует отправить управление процессом на блок 2. Таким образом, за несколько проходов по массиву, он будет отсортирован. Теперь составим блок-схему головного алгоритма. Она показана на рис. 8.
Рис. 8. Головной алгоритм сортировки 2-х массивов В данном алгоритме сначала вводятся длины массивов n и m, затем сами массивы x и y. В блоке 3 обращением к процедуре Sort сортируется массив x, а в блоке 8 - массив y. В блоке 5 массивы выводятся на печать. Создайте блок-схемы алгоритмов при помощи программы Microsoft Visio. Реализуем вспомогательные и головной алгоритмы в среде Delphi. Запустим Delphi XE7 и создадим новое приложение. Положите на форму компонент TStringGrid и кнопу TButton, как показано на рис. 9. Задайте сетку из 6 строк и 9 столбцов, как показано на рис. 9.
Рис. 9. Окно сортировки массивов Перейдите в редактор кодов и вставьте в текст модуля код уже известной нам процедуры Perm. Под ней объявите тип динамического массива TArr, как показано на рис. 10.
Рис. 10. Код процедуры Perm и объявление типа числового динамического массива Ниже расположите текст процедуры Sort, как показано на рис. 11.
Рис. 11. Код процедуры Sort Дадим описание процедуры Sort. Она содержит 2 параметра: целочисленную переменную n и динамический массив z. В тексте процедуры содержится объявление двух переменных: логической переменной b и целочисленной переменной i. Наружный цикл представлен операторами repeat until, внутренний цикл - операторами for do. В наружном цикле переменной b присваивается истинное значение, затем в внутреннем цикле совершается проход по парам соседних элементов. Если пара неотсортирована, то переменной b присваивается ложное значение и с помощью процедуры Perm производится перестановка значений элементов неотсортированной пары. Процесс производится до тех пор пока b не останется истинной. Далее расположите текст еще одной процедуры, как показано на рис 12.
Рис. 12. Код процедуры SortSgArray Данная процедура предназначена для чтения массива длины m из строки с номером j сетки Sg, сортировки массива и последующего вывода отсортированного массива в строку с номером k сетки Sg. Именно эти параметры перечислены в заголовке процедуры SortSgArray. Внутри процедуры объявлена целочисленная переменная i и динамический массив z. Затем в теле процедуры при помощи оператора SetLength(z,m+1) в массив z добавляется m+1 ячейка. Перерь программа может оперировать ячейками z[0], z[1], z[2], ..., z[m]. Нам потребуются только ячейки z[1], z[2], ..., z[m]. В следующем за этим оператором цикле прочитаем из компонента Sg из его строки с номером j массив длины m и, преобразовав его в числовой тип, поместим эти данные в массив z. Далее, оператором обращения к процедуре Sort отсортируем этот массив. После сортировки выведем отсортированный массив z в компонент Sg в его строку с номером k. Последним оператором z:= Nil освободим память, занятую массивом z. Наконец, создадим событие для щелка на кнопке. Текст этой процедуры приведен на рис. 13. Рис. 13. Код обработчика события OnClick для кнопки Как видим, в тексте содержится два оператора обращения к процедуре SortSgArray. Первый оператор предназначен для чтения 6-ти элементов и 1-й строки сетки и вывода отсортированного массива в 4-ю строку сетки. Второй оператор читает массив из 4-х элементов, размещенных во 2-й строке сетки, и после сортировки выводит результат в 5-ю строку сетки. Запустите приложение, введите числа в 1-ю и 2-ю строки сетки, затем щелкните на кнопке. Получится результат, который показан на рис. 14.
Рис. 14. Результаты сортировки 2-х массивов Объясните получившийся результат. 3.3. Индивидуальные задания Разработайте блок-схему алгоритма и соответствующую программу на Delphi по своему индивидуальному варианту. Опишите блок-схему своего алгоритма и код программы. Варианты индивидуальных заданий приведены в таблице 2.
|
||||||||||||||||||||||||||||||||||||||||||||||||||
