Пример линейного алгоритма в виде блок схемы

Справочное руководство по составлении алгоритмов Предисловие Данный материал представляет собой справочное руководство по составлении алгоритмов, которые являются необходимой составной частью контрольной и курсовой работы по дисциплине "Информатика". Изложенный материал не претендует на полноту охвата всех сторон проблемы алгоритмизации при решении задач, возникающих на практике. Однако его вполне достаточно для того, чтобы разобраться и выполнить ту часть названных работ, которая необходима для пример линейного алгоритма в виде блок схемы алгоритмов их описания. Опыт показывает, что трудности, возникающие при составлении алгоритмов имеют как общий характер, когда студент не может уяснить принцип работы алгоритма вообще, так и частный, когда непонятным оказывается отдельный фрагмент алгоритма. В любом случае рекомендуется обратить внимание на следующее. Разбирая или составляя алгоритм, нужно мысленно представить некоторый автомат по обработке данных компьютеркоторый будет выполнять действия, предписанные этим алгоритмом. Без такого представления невозможно понять сам пример линейного алгоритма в виде блок схемы. Ниже, при разборе примеров, станет понятно, что такой мысленный автомат совсем несложен. Во всяком случае он несравнимо проще реального компьютера, хотя общие принципы их функционирования в основном одинаковы. Допустимо например, при составлении описания отождествлять работу такого автомата с работой самого алгоритма. При изучении материала особенно первоначальном, следует подробно разобраться в каждом алгоритме, начиная с самого первого и самого простого. Начинать нужно с полного уяснения пяти самых простых и самых необходимых понятий: константа, переменная, ячейка памяти, запись константы в ячейку памяти, чтение константы из ячейки памяти. Не пренебрегайте этими советами, так как очень скоро убедитесь, что пример линейного алгоритма в виде блок схемы разборе следующего алгоритма обязательно натолкнетесь не только на те же трудности, но присовокупите к ним новые. Более того, нередко полное понимание даже самого простого алгоритма дает намного больше пользы, чем поверхностное изучение десятка алгоритмов повышенной сложности. Алгоритм — это инструкция о том, в какой последовательности нужно выполнить действия при переработке исходного материала в требуемый результат. Пример линейного алгоритма в виде блок схемы алгоритм используется не как инструкция для автомата, а как схема алгоритмического решения задачи. Это позволяет оценить эффективность предлагаемого способа решения, его результативность, исправить возможные ошибки, сравнить его еще до применения на компьютере с другими алгоритмами решения этой же задачи. Наконец, алгоритм является основой для составления программы, которую пишет программист на каком-либо языке программирования с тем, чтобы реализовать процесс обработки данных на компьютере. Неотъемлемым свойством алгоритма является его результативностьто есть алгоритмическая инструкция лишь тогда может быть названа алгоритмом, когда при любом сочетании исходных данных она гарантирует, что через конечное число шагов будет обязательно получен результат. На практике получили известность два способа изображения алгоритмов: в виде пошагового словесного описания; в виде блок-схем. Первый из этих способов получил значительно меньшее распространение из-за его многословности и отсутствия наглядности. Второй, напротив, оказался очень удобным средством изображения алгоритмов и получил широкое распространение в научной и учебной литературе. Именно этот способ будет использован ниже при составлении и описании алгоритмов. Блок-схема — это последовательность блоков, предписывающих выполнение определенных операций, и связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению. Конфигурация и размеры блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19002-80 и ГОСТ 19003-80 "Схемы алгоритмов и программ". Блоки и элементы связей называют элементами блок-схем. Представленных в таблице элементов вполне достаточно для изображения алгоритмов, которые необходимы при выполнении студенческих работ. При соединении блоков следует использовать только вертикальные и горизонтальные линии потоков. Горизонтальные потоки, имеющие направление справа налево, и вертикальные потоки, имеющие направление снизу вверх, должны быть обязательно помечены стрелками. Прочие потоки могут быть помечены или оставлены непомеченными. Горизонтальный и вертикальный размеры блока должны быть кратны 5 мм делиться на 5 нацело. Для размещения блоков рекомендуется поле листа разбивать на горизонтальные и вертикальные для разветвлявшихся схем зоны. Для удобства описания блок-схемы каждый ее блок следует пронумеровать. Удобно использовать сквозную нумерации блоков. Номер блока располагают в разрыве в левой верхней части рамки блока. По характеру связей между блоками различают алгоритмы линейной, разветвляющейся и циклической структуры. Примеры, пояснявшие изложенное, можно найти в блок-схемах алгоритмов, которые будут приведены ниже. Для того чтобы ясно представить как "работает" алгоритм, опишем простейший автомат, который предназначен для выполнения операций, предписанных этим алгоритмом. Головка, получив указание от процессора, может записывать в ячейку или считывать из нее одну константу. В простейшем случае константой является любое арифметическое число. Константами могут быть такие строки символов, структуры данных и др. Под простой переменнойили просто переменной будем понимать некоторую ячейку памяти, т. В отдельной ячейке за время работы алгоритма может побивать множество различных констант отсюда название — переменная. Такими ячейками электронными, магнитными, оптическими снабжен реальный компьютер. Переменные имеют буквенно-символьное обозначение. Например, 1, n, a, a1, bH2 — переменные. Одновременно обозначение переменной является индексом ячейки, в которую будут записываться константы. Любая из таких констант называется значением переменной. Например, Z является переменной и адресом ячейки Z одновременно. Произносить эту запись нужно так: "переменной L присвоить значение переменной M или просто: L присвоить M ". Другой разновидностью переменных являются так называемые индексированные переменные или массивы. Массив — это некоторая совокупность ячеек, объединенная одним обозначением массивом может быть одна ячейка. Всякий массив обязательно имеет размерность. Пример линейного алгоритма в виде блок схемы бывают одномерными, двумерными, трехмерными и т. Одномерный массив — это последовательность ячеек, расположенных в одну линию. Массив имеет имя q. Для того чтобы можно было отличить одну ячейку массива от другой ячейки этого же массива, их нумеруют. Нумерация ячеек обычно начинается с 1. Номер ячейки массива называется его индексома константа в ячейке — элементом массива. Теперь становится возможной работа с отдельной ячейкой такого массива. Эту же операцию можно описать другими словами: 41-му элементу массива r присвоить значение суммы 2-го и 5-го элементов массива q. Двумерный массив по расположению ячеек напоминает математическую матрицу рис. Элемент такого массива характеризуется двумя индексами: первый показывает строку, в которой расположена ячейка, второй — ее столбец. Аналогично устроена структура массивов трех- и большей размерности. Линейный алгоритм — это пример линейного алгоритма в виде блок схемы, в котором блоки выполняются последовательно сверху вниз от начала до конца. Линейный алгоритм Блок-схема алгоритма состоит из шести блоков. Выполнение алгоритма начинается с блока 1 "Начало". Этот блок символизирует включение автомата, настройку его на выполнение алгоритма и выделение памяти под все переменные, которые задействованы в алгоритме. Следовательно, под каждую из них алгоритмом будет выделено по одной ячейке памяти. На этом блок 1 будет отработан. Как видно из рис. Эта линия не имеет стрелки, указывавшей направление потока. Следовательно, этот поток направлен вниз. Таким образом, после выполнения блока 1 управление будет передано на блок 2. Блок 2 "Перфокарта" см. Это означает, что в ячейку, отведенную автоматом под эту переменную, нужно поместить константу. На реальной компьютере эта константа может быть введена самыми разными способами. Способ зависит от того, как запрограммирован данный фрагмент. Можно, например, потребовать ввод константы с клавиатура или получить его из заранее подготовленного файла. Возможно эта константа будет получена через внешние источники данных, например, от физической установки, подключенной к компьютеру. Для данного примера способ передачи константы не имеет значения, важно лишь то, что при выполнении блока 2 в ячейку с адресом А будет занесена конкретная константа. Пусть такой константой является число 5. Далее управление по линии потока передается к блоку 3 "Процесс". В этом блоке при выполнении размещенной в ней команды число 4 умножается на константу, помещенную в ячейку А т. После выполнения пример линейного алгоритма в виде блок схемы операций управление передается к блоку 4. В блоке 4 аналогичным образом производится умножение значений переменной А и результат константа 25 присваивается переменной S в ячейку по адресу S будет занесена константа 25. После этого выполняется переход к блоку 5. При выполнении команд блока 5 выводятся например, на экран, бумагу, во внешний файл и т. Далее управление передается последнему пример линейного алгоритма в виде блок схемы 6. Понятно, что при новом запуске этого же алгоритма можно получить совсем другие числа. Так, если в блоке 2 переменной А присвоить значение 20, то алгоритм выдаст в блоке 5 константы 20, 80, 400. Детальное описание алгоритма рис. Из сказанного нужно уяснить, что автомат выполняет предписанную ему работу шаг за шагом. Всякий шаг обрабатывается процессором. Конечный результат следует искать в ячейках памяти, каждая из которых до окончания алгоритма имеет известный адрес и хранит записанную в нее константу. Пример линейного алгоритма в виде блок схемы выполнении контрольной или курсовой работы нет нужды давать столь подробное описание алгоритма. Тем не менее, описание должно быть выполнено с той степенью полноты, которая позволяет дать ясное представление о всех сторонах и особенностях алгоритмического процесса. На практике алгоритмы линейной структуры встречается крайне редко. Чаще необходимо организовать процесс, который в зависимости от каких-либо условий проходит по той либо иной ветви пример линейного алгоритма в виде блок схемы. Такой алгоритм называется разветвляющимся. В блок-схемах ветвление начинается на выходах элемента "Решение", с помощью которого в алгоритме выполняется проверка какого-либо условия. Количество ветвей тем больше, чем больше проверяемых условий. На первый взгляд представляется, что алгоритм решения этой задачи имеет линейную структуру. Если этого не сделать, то при вычислениях может возникнуть аварийный выход до получения результата. В профессиональной практике аварийные завершения крайне нежелательны. Можно привести другие примеры, когда аварийный останов компьютера может повлечь куда более серьезные последствия. Решение задачи представлено блок-схемой рис. Разветвляющийся алгоритм Она состоит из 7 блоков. После начала работы алгоритм в блоке 2 требует ввода аргументов X и Здесь автомат проверяет равна ли нули константа, введенная в ячейку с адресом Результатом такой проверки является ответ "Да" или "Нет". В зависимости от этого ответа выполнение алгоритма пойдет по пример линейного алгоритма в виде блок схемы или другой ветви. Если результат проверки окажется отрицательным, то на х можно делить и управление передается блоку 4. В блоке 4 будет получен результат Z, затем в блоке б значения всех трех переменных будут отпечатаны и в блоке 7 алгоритм закончит работу. Если же ответ окажется положительным, то управление будет передано блоку 4. Выполняя команду блока 4, автомат выведет сообщение "Ошибка" и затем закончит работу в том же блоке 7. Часто при решении задач приходится повторять выполнение операций по одним и тем же зависимостям при различных значениях входящих в них переменных и производить многократный проход по одним и тем же участкам алгоритма. Такие участки называются циклами. Алгоритмы, содержащие циклы, называется циклическими. Использование циклов существенно сокращает объем алгоритма. Различают циклы с наперед известным и наперед неизвестным количеством проходов. Рассмотрим пример алгоритма с циклом, имеющим наперед неизвестное количество проходов. Для этого решим следующую задачу. Указать наименьшее количество членов ряда натуральных чисел 1, 2, 3. Разветвляющийся алгоритм Блок-схема алгоритма решения этой задачи приведена на рис. Она состоит из восьми блоков. После начала работы в блоке 2 вводится значение числа Далее в блоке 3 переменная i получает значение 1, т. Переменная S, предназначенная для накопления сумма этих чисел, перед началом пример линейного алгоритма в виде блок схемы получает значение 0. После этого управление передается блоку 5. При записи нового значения старое содержимое ячейки S нуль стирается, а на его место записывается число пример линейного алгоритма в виде блок схемы. После суммирования первого члена последовательности в блоке 6 выполняется проверка условия о превышении суммы S заданного числа Если условие 6 не выполнится, то производится переход к блоку 4, где при выполнении операции значение переменной увеличивается на 1 и становится равным 2. Теперь алгоритм вновь вернется к блоку 5 и к старому значении суммы добавит новый член 2. После этого сумма станет равной 3. В блоке пример линейного алгоритма в виде блок схемы вновь проверяется условие получения требуемой суммы и т. Переменная i, значение которой при очередном проходе цепочки этих блоков увеличивается на 1, играет роль счетчика этого цикла. Далее производится переход к блоку 7, где отпечатается значение количества членов ряда извлечено и отпечатано число из ячейки i, которое там хранится в момент выполнения условиясуммы S и в блоке 8 алгоритм закончит работу. Теперь приведем пример алгоритма, содержащего цикл пример линейного алгоритма в виде блок схемы наперед известным количеством проходов повторений. Алгоритм решает задачу накопления суммы положительных элементов одномерного массива Z длины N под длиной массива понимается количество пример линейного алгоритма в виде блок схемы элементов. Блок-схема алгоритма дана на рис. Циклический алгоритм Вначале в блоке 2 производится ввод двух переменных N и Первая из них представляет одну ячейку. В нее записывается одна константа — число, равное количеству элементов массива Именно такое количество ячеек объединяет другая переменная — Следует подчеркнуть, что если бы ввод этих переменных в блоке 2 производился в противоположном порядке, то это привело бы к ошибке. Действительно, невозможно заполнить N ячеек массива Z, когда самое N еще не известно оно будет введено позже Далее в блоке 3 переменной S присвоено начальное значение 0. Это сделано для того, чтобы приготовить ячейку к дальнейшему накоплению необходимой суммы. Блоки 4-6 представляет собой сам цикл, в котором накапливается сумма. Для того чтобы понять, как функционирует не только этот, а и любой другой цикл, обратимся к рис. На них показана общая структура цикла и его важнейшие параметры. Как видно из рис. Всякий цикл обязательно имеет свой счетчик. Сначала производится вход в цикл. После этого начинается его выполнение. Затем выполняется блоки, образующие тело цикла. Обработка блоков внутри цикла производится по часовой стрелке. В результате после первого выполнения тела цикла управление вновь передается заголовку. Здесь к текущему значению счетчика добавится шаг. Теперь, если новое значение счетчика не вышло за свои пределы т. Так цикл будет выполняться до тех пор, пока значение счетчика однажды не выйдет за предписанный предел. Как только такой предел будет преодолен, произойдет выход пример линейного алгоритма в виде блок схемы цикла и управление будет передано блоку, который следует сразу за циклом. Вернемся к блок-схеме рис. Заголовок ее цикла представлен блоком 4. Роль счетчика цикла играет пример линейного алгоритма в виде блок схемы i, которая должна в цикле изменяться от 1 до Поскольку шаг явно не указан, то по умолчанию он подразумевается равным 1. Тело цикла образуют блоки 5 и 6. Далее в блоке 5 выполняется проверка положительности первого элемента массива Z т. Если этот элемент действительно положителен, то в блоке б он будет добавлен к переменной S, после чего выполняется возврат к заголовку цикла. Если этот элемент не положителен т. На втором круге цикла счетчик i в заголовке увеличится на 1 и станет равным 2. Теперь, при новом выполнении тела цикла, в блоке 5 проверяется на положительность второй элемент массива Z и, если он положителен, то добавляется в сумму и т. При этом значении счетчика проверяется последний элемент массива. Наконец, в заголовке цикла i примет значение N+1. Это значение выходит за предписанный предел, следовательно, произойдет выход из цикла и управление перейдет блоку 7. В этом блоке выводится накопленная сумма и алгоритм закончит работу. Нередко при алгоритмическом решении задачи возникает необходимость создания цикла, содержащего в своем теле другой цикл. Такие вложенные друг в друга циклы относятся к структурам вложенных циклов. Порядок вложенности циклов, когда в теле внутреннего цикла содержатся другие циклы, может быть достаточно большим. Этот порядок определяется методом, с помощью которого достигается решение поставленной задачи. Так, при обработке одномерных массивов, как правило, удается построить алгоритмическую схему без вложения циклов. Однако в ряде случаев при решении таких задач без вложенных циклов не обойтись. Алгоритм сортировки массива Отметим, что все вложенные друг в друга циклы, включая наружный, пример линейного алгоритма в виде блок схемы иметь счетчики с различными именами. Вне этих циклов счетчики могут быть использованы как обычные переменные или как счетчики других циклов. Рассмотрим задачу сортировки одномерного массива Z длины Отсортировать массив — значит расположить его элементы в порядке роста или убывания. Опишем метод сортировки массива в порядке роста. Сначала выполняется проход по массиву с целью определения в нем наименьшего элемента. Затем производится перестановка этого элемента с первым. Далее совершается второй проход по массиву, начиная со второго элемента. Найденный наименьший элемент переставляется со вторым и т. После N-1 -го прохода с выполнением названных операций массив окажется отсортированным. Блок-схема этого алгоритма сортировки показана на рис. Она включает 12 блоков. После пример линейного алгоритма в виде блок схемы работы в блоке 2 переменная N и массив Z заполняются константами. Затем в блоке 3 проверяется условие о том, нужно ли сортировать массив. Это сводится к установлению факта наличия в массиве нескольких пример линейного алгоритма в виде блок схемы, т. Если пример линейного алгоритма в виде блок схемы факт установлен, то алгоритм приступает к сортировке. Процедура сортировки выполняется в цикле, объединяющем блоки 4-10. В теле этого цикла содержится другой цикл, который образован блоками 6-8. Его назначение станет ясно из дальнейшего разбора алгоритма. После входа в наружный цикл его счетчик i примет значение 1, что в рамках нашего метода подразумевает первый проход по массиву. Далее будут выполнены блоки 5-10, составляющие тело наружного цикла. В блоке 5 размещены две вспомогательные переменные V и Первая из них предназначена для фиксирования наименьшего элемента, а вторая — для запоминания его индекса. Затем во внутреннем цикле, образованном пример линейного алгоритма в виде блок схемы 6-8, где его счетчик j будет изменяться от 2 до N, последовательно проводится сравнение соответствующих элементов массива Z со значением переменной При этом всякий раз, как будет найден меньший чем v элемент, значение V будет заменено на значение этого элемента, а в переменной L будет зафиксирован его индекс. Понятно, что после выполнения внутреннего цикла в переменной V будет содержаться значение, равное наименьшему элементу, а в L — индекс этого элемента. В блоке 9 далее проверяется, не является ли наименьший элемент первым элементом массива. Если это не так, то в блоке 10 на место наименьшего элемента его номер L запишется первый т. После этого произойдет возврат управления к заголовку наружного цикла блоку 4. Затем вновь выполняется его тело, но уже для нового значения счетчика i. Теперь с помощью блоков 5-10 отыскивается наименьший элемент массива начиная с номера 2. Затем в блоках 9-10 он займет второе место в массиве и т. Когда тело наружного цикла выполнится N-1раз массив будет отсортирован. В блоке 12 отсортированный массив будет выведен и в блоке 13 алгоритм окончит работу. Алгоритмы со структурами вложенных циклов часто используют при решении задач обработки двумерных массивов. В таких алгоритмах счетчики циклов используются для манипуляции с индексами массивов. Дан двумерный квадратный массив Z, состоящий из N строк и N столбцов. Необходимо найти среднее арифметическое S его отрицательных элементов и заменить положительные элементы побочной диагонали массива средним арифметическим Блок-схема алгоритма Блок-схема алгоритма показана на рис. Она состоит из 13 блоков. В блоке 2 переменная N и весь массив Z заполняются константами. В блоке 3 рабочие переменные S и К получает значение нуль. Переменная S сначала будет играть роль сумматора отрицательных элементов массива, затем после накопления суммы она примет значение среднего арифметического. Переменная К нужна для подсчета количества отрицательных элементов массива. В блоках 4-7 выполняется накопление суммы отрицательных элементов массива. Эти блоки образует два вложенных цикла, причем внутренний цикл со счетчиком j является телом наружного цикла со счетчиком i. Проанализируем работу этой структуры. Далее будет выполнено его тело блоки 5-7которое, в свою очередь, также является циклом. Затем в блоке 6 пример линейного алгоритма в виде блок схемы на отрицательность элемент массива Z, расположенный в первой строке и первом столбце, т. Если он окажется отрицательным, то в блоке 7 переменная К увеличится на 1, а к S добавляется значение этого элемента. После этого выполняется возврат к блоку 5, т. Если он окажется отрицательным, то К снова увеличится на 1, а к накопленному к этому времени S добавляется значение этого элемента и т. Когда полностью выполнится внутренний цикл, т. Снова будет отработано его тело, т. При этом будет найдена уже сумма отрицательных элементов первых двух строк массива, а в К сохранится количество этих элементов. Когда выполнится весь наружный цикл, в S будет константа, равная сумме отрицательных элементов всего массива, а в К — их количество. Теперь управление перейдет к блоку 8. Результат помещается а ту же переменную Эта ошибка повлекла бы аварийное завершение вычислений до окончания работы алгоритма. Далее выполняется блоки 10-11, которые также образует цикл. В нем производится замена элементов побочной диагонали на среднее арифметическое S побочной диагональю является прямолинейная цепочка ячеек в диапазоне от нижнего левого угла до верхнего правого угла массива. Обратите внимание, на то что переменная i, которая использовалась ранее, в целях экономии памяти применяется вновь. Проследим работу этого цикла. Таким образом, элемент с индексами 1, N станет равным Нетрудно видеть, что теперь элемент 2, N-1 станет равным S и т. На последнем круге цикла элемент N, 1 получит значение S, что завершит изменение значений всех элементов побочной диагонали на среднее арифметическое Наконец, в блоке 12 измененный массив будет выведен и в блоке 13 алгоритм закончит работу. Вспомогательный алгоритм является аналогом языковой подпрограммы. Он имеет имя и может иметь параметры, которые называются формальными параметрами. Имя служит для пример линейного алгоритма в виде блок схемы. Формальные параметры должны быть выбраны таким образом, чтобы ими был исчерпан весь набор необходимых входных и выходных величин. Нередко один и тот же параметр может оказаться входным и выходным одновременно. Например, на вход такого алгоритма может быть подан массив для обработки, а на выходе процедуры он может предстать в измененном виде как выходной параметр. Среди вспомогательных алгоритмов различают процедуры и функции. Процедура Warn Первый блок схемы рис. С помощью этого имени в алгоритме рис. При любом другом i будет выведено сообщение "Конец расчетов". Этим исчерпываются возможности процедура Warn. Этот алгоритм в блоках 2 и 8 обращается к процедуре Warn. Опишем последовательность и механизм обработки данных, которые предписаны алгоритмами рис. Головной алгоритм Пример линейного алгоритма в виде блок схемы алгоритмических действий всегда начинаются с головного алгоритма. Поэтому сначала будет выполнен блок 1 схемы рис. Далее в блоке 2 головной алгоритм выполняет обращение к процедуре Warn при конкретном значении ее аргумента 0. Это конкретное значение называется фактическим параметром пример линейного алгоритма в виде блок схемы. Теперь управление временно переходит в алгоритм рис. Здесь и далее по всей процедуре Warn формальный параметр i заменяется на фактический параметр 0 нуль всюду, где он встречается. Результатом проверки станет перевод управления к блоку 3, в котором выводится сообщение "Введите данные". На этом процедура заканчивается и управление вновь передается в головной алгоритм к блоку 3. Далее в блоках 3-5 алгоритма рис. Затем управление передается в блок б, который содержит новое обращение к процедуре Warn с фактическим параметром 1. Снова управление переключается на схему рис. После этого управление возвращается в головной алгоритм к блоку 7, где и будет окончательно завершен алгоритмический процесс. Внешне такой процесс может выглядеть примерно так. На экран выводится сообщение "Введите пример линейного алгоритма в виде блок схемы и компьютер переходит в режим ожидания ввода двух констант с клавиатуры. Затем после их ввода на экране появляется три константы и надпись "Конец работы". На первый взгляд может показаться, что процедуры лишь усложняют решение задачи. Действительно, рассмотренную здесь задачу проще решить одним алгоритмом, не прибегая к составление процедуры. Однако при составлении алгоритма решения сложной задачи очень быстро становится ясно, что без использования процедур обойтись просто невозможно. На практике при решением серьезных алгоритмических задач часто одному программисту не под силу выполнить весь объем работ. Поэтому над ее решением работает обычно коллектив программистов под руководством координатора. Образно говоря, координатор здесь работает как головной алгоритм, а его программисты как процедуры. При этом каждый программист часто независимо от других получает от координатора задание по составление процедур определенного назначения. В результате такой организации работы задача получает разрешение. Под декомпозицией алгоритма понимают разложение его o6щeй алгоритмической схемы на вспомогательные алгоритмы процедуры и функции и головной алгоритм. Напомним, такая задача ставится перед студентом при выполнении курсовой или контрольной работы. Одним из условий, которое должно быть обязательно выполнено, является наличие в работе хотя бы одной процедуры или функции кроме того, работа должна содержать текст описания всех процедур и головного алгоритма. Метод, при помощи которого обычно выполняется декомпозиция, достаточно прост. Сначала вычленяют основные этапы предстоящей работы. Наиболее сложные этапы оформляет в процедуры или функции верхнего уровня. Затем, если необходимо, такие этапы делят пример линейного алгоритма в виде блок схемы этапы более низкого уровня. Наиболее сложные из них также оформляют процедурами или функциями и т. Следуя методу "от сложного к простому", в конечном итоге достигают решения поставленной задачи. Приведем пример декомпозиции для решения задачи сортировки массива. Эта задача была решена ранее в разд. Решение задачи декомпозиции состоит из трех основных этапов: 1 ввода данных, 2 сортировки массива и 3 вывода отсортированного массива. Первый и третий этапы вследствие их простоты не нуждаются в дальнейшей декомпозиции, поэтому выполняются в головном алгоритме. Второй этап представляет достаточно сложный и самостоятельный фрагмент вычислений, поэтому его целесообразно выделить в отдельную процедуру, которой можно дать имя Sort. Этап сортировки, в свои очередь, состоит из двух этапов: 1 установления необходимости сортировки и N—1 — кратного прохода по массиву и 2 нахождения наименьшего элемента во фрагменте массива и перестановки этого элемента с начальным элементом фрагмента. Поскольку последний этап многократно повторяется при выполнении первого этапа, то его можно оформить в отдельную процедуру. Этой процедуре можно дать имя Tra от английского transposition — перестановка. Блок-схемы головного алгоритма, процедуры Sort и процедуры Тrа показаны на рис. Процедура Sort Дадим краткое, описание взаимодействия этих пример линейного алгоритма в виде блок схемы в ходе решения задачи сортировки. Процедура Tra Выполнение начинается с головного алгоритма рис. В блоке 2 вводятся исходные данные, затем в блоке 3 выполняется сортировка массива. В блоке 4 отсортированный массив выводится и алгоритм заканчивает работу. Сортировка массива в блоке 3 головного алгоритма выполняется обращением к процедуре Sort, показанной на рис. Переменные A и N являются фактическими параметрами, Переменные А и N, которые использованы в блок-схеме алгоритма Sort, является формальными параметрами. При обращении к процедуре Sort на вход подаются параметры A и В пример линейного алгоритма в виде блок схемы в теле процедуры производится замена формального параметра R на фактический параметр A, аналогично формальный K заменяется на фактический Пример линейного алгоритма в виде блок схемы в блоке 2 проверяется необходимость сортировки массива Затем, если такая необходимость будет установлена, в цикле 3-4 пример линейного алгоритма в виде блок схемы выполняется сортировка массива. При всяком значении счетчика цикла в его теле производится нахождение наименьшего элемента фрагмента и его перестановка с начальным элементом этого фрагмента. Эти операции выполняются отдельно с помощью процедуры Tra. Как видно из рис. В теле процедуры в блоках 2-5 пример линейного алгоритма в виде блок схемы наименьший элемент фрагмента v и его номер k. Затем в блоке 6 выполняется вышеназванная перестановка элементов. Таким образом, весь процесс управляется головным алгоритмом, который выполняет сортировку посредством обращения к вспомогательному алгоритму — процедуре Sort. Тот, реализуя решение своей задачи, в своя очередь несколько раз вымывает еще более простой вспомогательный алгоритм процедуру Tra. В результате такого взаимодействия достигается решение задачи в целом. В заключение приведем пример алгоритма-функции. Она похожа на процедуру, но в отличие от пример линейного алгоритма в виде блок схемы должна в теле алгоритма еще содержать команду присваивания результата имени функциит. Рассмотрим задачу вычисления факториала числа N! Результатом будет одно число, поэтому лучше алгоритм оформить в виде функции. Функция Fact Ее блок-схема показана на рис. Переменная К используется для накопления произведения и, поскольку 0! В блоке 6 имя Fact функции получает значение вычисленного произведения из ячейки Для процедур действия, размещенного в блоке 6, не может быть, а для функций пример линейного алгоритма в виде блок схемы должно быть обязательно, поскольку иначе значение функции на выходе окажется неопределенным. Обращение к функции в других алгоритмах головных, процедурах, функциях производится по ее имени. При этом оно может входить в состав выражений. В качестве фактических параметров могут быть использованы как переменные, константы, так и целые выражения. Важно только, чтобы фактический параметр был совместим по типу с формальным, который содержится в заголовке описания алгоритма. Пример использования функции Fact показан на рис. После передачи этого значения в алгоритм рис. Обращение к функции Fact.

Карта сайта

1 2 3 4 5 6