Структуры алгоритмов

Структуры алгоритмов По характеру связей между символами различают алгоритмы линейной, разветвляющейся  и циклической структуры. Линейный алгоритм     – это алгоритм, в котором операции выполняются последовательно. Разветвляющийся алгоритм – это алгоритм, в котором последовательность выполнения  операций зависит от определенных условий. Если в алгоритме присутствует «действие1» и «действие2» (то есть ветвь 1 и ветвь 2), то  это разветвляющийся алгоритм с полной альтернативой. Если же вместо «действия2»  предусмотрен переход к выполнению операции «n», которая находится в общей  (основной) ветви, то такая форма записи называется неполной альтернативой. Циклический алгоритм –   это алгоритм, в котором многократно выполняются одни и те    же действия, например с целью многократного выполнения вычислений по одним и тем же зависимостям при различных значениях входящих в них переменных. Использование циклов существенно сокращает объем алгоритма. Можно выделить три основных типа циклических алгоритмов:  цикл с параметром (арифметический цикл или цикл со счетчиком);  цикл с предусловием;  цикл с постусловием. По способу определения числа повторений различают циклы с заранее неизвестным  количеством повторений и заранее известным количеством повторений (циклы с  параметром). Цикл с параметром       с параметром     пределенная последовательность операций выполняется  В   цикле несколько раз в зависимости от заданной величины, кот орая называется параметром  цикла. Цикл выполняется, пока параметр цикла принимает значения в заданном диапазоне с заданным шагом. Оператор цикла включает имя переменной, конечное значение и шаг. Цикл с условием Выделяют два типа циклов с условием: цикл с предусловием и цикл с постусловием. В циклах с предусловием условие проверяется на входе (до операций, выполняемых в  цикле). В циклах с постусловием условие проверяется после выполнения всех операций  внутри цикла. В этом случае операторы тела цикла будут реализованы хотя бы один раз  или до тех пор, пока не станет возможным условие выхода из цикла. В циклах с постусловием сначала выполняются все операции, включенные в цикл, и  только после этого проверяется заданное условие. В зависимости от результата проверки  осуществляется выход из цикла или его повторение. Цикл с условием называют также итерационным циклом. Внутри алгоритма циклической структуры может быть помещен другой цикл – вложенный цикл, при этом вложенный (внутренний) цикл должен полностью находиться  в области внешнего цикла. Базовые структуры алгоритмов     Базовые структуры алгоритмов — это определенный набор блоков и стандартных  способов их соединения для выполнения типичных последовательностей действий. К основным структурам относятся следующие: o линейные o разветвляющиеся o циклические     Линейными называются алгоритмы, в которых действия осуществляются  последовательно друг за другом. Стандартная блок­схема линейного алгоритма  приводится ниже:      Разветвляющимся называется алгоритм, в котором действие выполняется по одной из  возможных ветвей решения задачи, в зависимости от выполнения условий. В отличие от  линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или  невыполнения которого выполняется та или иная последовательность команд (действий).     В качестве условия в разветвляющемся алгоритме может быть использовано любое  понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не  соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и  формулой. Таким образом, алгоритм ветвления состоит из условия и двух  последовательностей команд.     В зависимости от того, в обоих ветвях решения задачи находится последовательность  команд или только в одной разветвляющиеся алгоритмы делятся на полные и не полные  (сокращенные). Стандартные блок­схемы разветвляющегося алгоритма приведены ниже:     Циклическим называется алгоритм, в котором некоторая часть операций (тело цикла  — последовательность команд) выполняется многократно. Однако слово «многократно»  не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности —  получения результата за конечное число шагов.     Перед операцией цикла осуществляются операции присвоения начальных значений тем  объектам, которые используются в теле цикла. В цикл входят в качестве базовых  следующие структуры: o блок проверки условия o блок, называемый телом цикла Существуют три типа циклов:  Цикл с предусловием  Цикл с постусловием  Цикл с параметром (разновидность цикла с предусловием) Если тело цикла расположено после проверки условий , то может случиться, что при  определенных условиях тело цикла не выполнится ни разу. Такой вариант организации  цикла, управляемый предусловием, называетсяциклом c предусловием.     Возможен другой случай, когда тело цикла выполняется по крайней мере один раз и  будет повторяться до тех пор, пока не станет ложным условие. Такая организация цикла,  когда его тело расположено перед проверкой условия, носит название цикла с  постусловием.     Цикл с параметром является разновидностью цикла с предусловием. Особенностью  данного типа цикла является то, что в нем имеется параметр, начальное значение  которого задается в заголовке цикла, там же задается условие продолжения цикла и закон изменения параметра цикла. Механизм работы полностью соответствует циклу с  предусловием, за исключением того, что после выполнения тела цикла происходит  изменение параметра по указанному закону и только потом переход на проверку условия. Стандартные блок­схемы циклических алгоритмов приведены ниже: Разновидности структур алгоритмов По структуре алгоритмы разделяют на линейные, разветвляющиеся и циклические. Линейными называют алгоритмы, в которых операции выполняются последовательно  одна за другой, в естественном и единственном порядке следования. В таких алгоритмах  все блоки имеют последовательное соединение логической связью передачи  информационных потоков. В них могут использоваться все блоки, за исключением блоков  проверки условия и модификации. Линейные алгоритмы, как правило, являются  составной частью любого алгоритмического процесса. Пример 1.1     Найти значение функции при значении аргумента x=1,5 и заданных а, b, с. Очевидно, что функцию Y целесообразно вычислять в такой последовательности:  предварительно введя исходные данные а, b, с и присвоив значение переменной х,вначале  найдем значение выражения (ах2+b)/с, которое обозначим переменной z. и далее  определим выражение arctg( + ln z). Используя общепринятые символы блоков (рис.1.1),  изобразим схему разрабатываемого алгоритма (рис. 1.2). При составлении схем алгоритмов часто возникает необходимость проведения анализа  исходных данных или промежуточных результатов вычислений и  определения дальнейшего порядка выполнения вычислительного процесса в зависимости  от результатов этого анализа. Алгоритмы, в которых в зависимости от выполнения  некоторого логического условияпроисходит разветвление вычислений по одному из  нескольких возможных направлений, называют разветвляющимися. Подобные  алгоритмы предусматривают выбор одного из альтернативных путей продолжения  вычислений. Каждое возможное направление вычислений называется ветвью. Логическое  условие называют простым, если разветвляющийся процесс имеет две  ветви, и сложным, ­если процесс разветвляется на три и более ветви. Любое сложное логическое условие может быть представлено в виде  простых.   Рассмотрим пример разветвляющегося алгоритма с простым логическим  условием.       Найти   Пример 1.2. Даны два числа а и b. Очевидно, что для определения ветви , по которому необходимо производить процесс  вычисления значения х, достаточно проверить выполнение одного из условий,  например а>b.Если условие а>b не выполняется, то очевидно и без дополнительной  проверки, что будет выполнено условие а < b. Следовательно, вариант схемы алгоритма  будет выглядеть следующим образом (рис 1.3).                 Рис 1.3. Схема простого разветвляющегося алгоритма Рассмотрим примеры алгоритмов разветвляющейся структуры в случаях необходимости  анализа более сложных логических условий. a / b, если а > 0 Пример 1.3. Даны два числа а и b. Найти х = ­ а ­ b, если а = 0. а + b, если а < 0 Из условия очевидно, что предполагаемый вычислительный процесс должен  предусматривать выбор одного из альтернативных путей вычислений в зависимости от  значения переменной а. При этом алгоритм может быть представлен в одном из двух вариантов: с разветвлением  по сложному логическому условию (рис 1.4а) и с разветвлением при разложении сложного логического условия на простые (рис. 1.46).   Пример 1.4. Вычислить значение Y при заданных значениях а, х. Рис 1.4, Схемы алгоритмов разветвляющейся структуры: а) ­ со сложным  логическим условием; б) ­ при разложении сложного логического условия на простые Несмотря на то что в примере предлагаются четыре логических условия, два из которых  сложные, при составлении алгоритмадостаточно организовать только три простых  сравнения. Остальные сравнения необязательны, поскольку соответствующие условия  и так являются единственно возможными при невыполнении предложенных  сравнений (рис. 1.5). Например,проверка логического условия х<=0 (блок 5) возможна  только при невыполнении условия х< ­2 (ветка "нет" блока 3), что в свою очередь  возможно только при х>= ­2. Рис /5. Схема разветвляющегося алгоритма решения примера 1.4 Пример 1.5. Даны три неравных между собой числа а, b, с. Определить наибольшее из  них. В алгоритме (рис. 1.6) вначале сравним между собой два первых числа а и b (блок 3).  Затем большее из них сравним с оставшимся третьим числом с (блок 4 или блок 5).  Большее число в этом сравнении и является наибольшим из трех. При увеличении числа переменных до 4 и более схема алгоритма потребует большого  числа сравнений, что усложнит анализ условий их выполнения и может привести к ошибкам при разработкеалгоритма. К тому же увеличится количество линий,  соединяющих эти блоки, что  усложнит читаемость алгоритма.   Рис. 1.6. Схема алгоритма поиска  наибольшего из трех чисел   Поэтому при решении подобных  задач рациональнее изменитьподход к  нахождению максимального значения. Пример 1.6. Заданы четыре неравные между собой величиныа, b, с, d. Определить  наибольшую из них. В алгоритме (рис. 1.7) переменной max оператором  присваивания задается первоначальное значение, равное  значению переменной а (блок Рис 3). Если при сравнении  значения переменнойmax со значением  остальныхпеременных b, с, d (блоки 4,6 и 8 соответственно)  найдется большее max число, то его значение станет новым  значением переменной max(блоки 5, 7, 9). Блок 10  осуществляет вывод наибольшего из чисел а, b,  с, d,присвоенного в качестве значения  переменной max.Пример 1.7. Даны три неравных между собой числа а, b, с.Вывести эти числа на печать в порядке убывания  их значений. Из анализа возможных вариантов ответа решения  поставленной задачи следует, что на первом месте может стоять любое наибольшее из  трех исходных чисел. Очевидно, что на втором месте должно следовать наибольшее из  двух оставшихся. Тогда возможно шесть вариантов ответа: а b с; а с b; b а с; b с а; с а b; с Ь а.   1.7. Схема алгоритма нахождения наибольшего из 4 заданных чисел Алгоритм решения приведенной задачи получим на базе алгоритма поиска наибольшего из трех чисел (рис 1.6), усложнив его дополнительными блоками проверки условия. В  результате получаем сложный алгоритм разветвляющейся структуры с шестью ветвями  для вывода требуемой последовательности чисел (рис.  1.8). Алгоритм циклической структуры предусматривает многократное повторение  действий в одной и той же последовательности по одним и тем же  математическим зависимостям, но при разных значениях некоторой  специально изменяемой величины. Циклические алгоритмы позволяют существенно  сократить объем программы за счет многократного выполнения группы повторяющихся  вычислений, так называемого тела цикла. Специально изменяемый по заданному закону  параметр, входящий в тело цикла, называется переменной цикла. Переменная цикла  используется для подготовки очередного повторения цикла и отслеживания условий его  окончания. В качестве переменной цикла используют любые переменные, индексы  массивов, аргументы вычисляемых функций и тому подобные величины. Во время  выполнения тела цикла параметры переменной цикла изменяются в интервале от  начального до конечного значения с заданным шагом. Следовательно, при организации  циклических вычислений необходимо предусмотреть задание начального значения  переменной цикла, закон ее изменения перед каждым новым повторением и ее конечное  значение, при достижении которого произойдет завершение цикла. Циклы, в теле которых нет разветвлений и других встроенных в них циклов,  называют простыми. В противном случае их относят к сложным. Циклические  алгоритмы разделяют надетерминированные и итерационные. Рис. 1.8. Схема алгоритма вывода на печать трех чисел в порядке убывания их  значений   Циклы, в которых число повторений  заранее известно из исходных данных или определено в ходе решения  задачи,  называютдетерминированными. Для организации  детерминированных циклов наиболее целесообразно использовать блок  модификации, внутри которого  указывается переменная цикла, ее начальное и конечное значения, а также шаг ее изменения (если шаг изменения равен 1, то  его допускается не указывать). Организовать подобный цикл возможно и при  использовании блока проверки условия вместо блока модификации, однако при этом  несколько усложняется алгоритм и теряется его рациональность.   Пример 1.8. Дано натуральное число N. Найти сумму первых N членов натурального  ряда. Варианты схемы алгоритма циклической структуры решения поставленной задачи  приведены на рис. 1.9. При этом в схеме на рис. 1.9а цикл организован с использованием  блока модификации, а на рис. 1.96 ­ блока проверки условия. В обоих  алгоритмах операция нахождения суммы, при предварительном обнулении значения  переменной S (блок 3), повторяется N раз. Рис. 1.9. Схема алгоритма циклической структуры для нахождения суммы N первых  членов натурального ряда: а) — с использованием блока модификации; б) — с использованием блока проверки  условия      В теле цикла использована операция присваивания S = S + I, по которой  и осуществляется вычисление суммы путем прибавления к предыдущему значению  переменной S всё новых значений переменной I.   Цикл_является детерминированным и количество его повторений заранее определено  (N раз). В качестве переменной цикла I принято текущее значение членов натурального  ряда.Использование алгоритма с блоком модификации предпочтительнее, так как он  обладает лучшей наглядностью. Циклы, в которых число повторений неизвестно из исходных данных и не определено по  ходу решения задачи, называют итерационными. В итерационных циклах для организации выхода из тела цикла предусматривается проверка некоторого заранее заданного условия, для чего используют блок проверки условия. В итерационных циклах невозможно использовать блоки модификации, так как при организации таких циклов  заранее неизвестно количество изменений переменной цикла и ее конечное значение. В зависимости от местонахождения блока проверки условия итерационные циклы могут  быть организованы как циклы с предусловием (блок проверки условия размещен перед  телом цикла) или с постусловием (блок проверки условия размещен после тела цикла).  Если в цикле с предусловием входящие в тело цикла команды могут не выполняться ни  разу (если начальное значение параметра цикла удовлетворяет условию выхода из цикла),  то в цикле с постусловием ­ выполняются как минимум один раз (даже если начальное  значение параметра цикла удовлетворяет условию выхода из него). Пример 1.9. Дан ряд натуральных чисел 1,2,3,..., ∞ и число N. Требуется найти сумму  первых членов ряда. Вычисление суммы прекратить, как только ее значение будет равно  или превыситзаданное N. Вариант схемы алгоритма решения задачи, включающей итерационный цикл с  постусловием, приведен на рис. 1.10а. Цикл организован в виде итерационного потому,  что число его повторений заранее неизвестно. В алгоритме выход из цикла или его  продолжение определяется выполнением (или невыполнением) условия S>=N в блоке 6.  Если условие не выполняется, то вычисление суммыпродолжается путем прибавления к  предыдущему значению суммы (переменной S) значения очередного члена ряда,  отслеживаемого переменной цикла I. Однако приведенный алгоритм дает неверное  решение при N=0, так как в этом случае не будет выполнено первое по порядку  сравнение S=N=0. Правильный алгоритм решения этой задачи с  использованием итерационного цикла с предусловием приведен на рис. 1.106. В  этом алгоритме тело цикла расположено после проверки условия выхода из него. В нем в  начале цикла осуществляется проверка S>=N (блок 5) и если N задано равным нулю, то  тело цикла не будет выполняться ни разу. Вид итерационного цикла (с пост­ или предусловием) определяется условием задачи и  допустимыми или возможными значениями исходных данных. Например, при решении  задачи 1.10возможно использование итерационного цикла только с нижним окончанием,  так как, для того чтобы выполнить проверку на окончание счета, необходимо сравнить  значения двух членов ряда. Рис. 1.10. Схема итерационного алгоритма нахождения суммы первых членов  натурального ряда: а) – с постусловием; б) ­ с предусловием             Пример 1.10. Дано натуральное N и первый член бесконечного ряда: Y1=1. Вычислить  сумму членов бесконечного ряда, образованного по следующему рекуррентному  соотношению: Y1 =2 • YI­1, (то есть S = 1+2+4+8+16+...). Вычисление суммы продолжать  до тех пор, пока соблюдается условие | Y1 ­ YI­1| 0 N!=l*2*3*...*N. Из пояснений к задаче следует, что в алгоритме необходима проверка условия N = 0. В  случае выполнения данного условия результирующая переменная Р должна получить  значение 1, в противном случае следует организовать цикл для перемножения элементов  натурального ряда чисел от 1 до N. Полученноепроизведение будет искомым значением  результирующей переменной Р. Схема алгоритма приведена на рис. 1.16.   Нахождение наибольшего  (наименьшего) значения  в последовательности  чисел.Приведенные ранее подходы  к нахождению наибольшего значения  нескольких неравных междусобой  переменных рациональны при  небольшом количестве последних  (рис. 1.6 и 1.7). Увеличение числа  исходных переменных до пяти и более приводит к все большему усложнению алгоритма и затруднению понимания  логики работы сложных  разветвляющихся структур, что противоречит одному из основных  правил программирования ­ не делать сложным то, что можно сделать просто. Как видим, некоторое упрощение уже достигнуто при переходе от алгоритма с анализом  всевозможных сравнений (рис. 1.6) к алгоритму с введением дополнительной  переменной max(рис. 1.7). Введение промежуточной переменной max позволило  организовать повторение по своей сути одинаковых блоков проверки условия (блоки 4,6 и 8) и присваивания (блоки 5,7 и 9), причем число этих повторений возрастает с увеличением числа исходных переменных. В  повторяющихся блоках проверки условия и присваивания меняются по очереди только  переменные Ь, с,.... Использование массивов позволяет осуществить дальнейшее упрощение алгоритма поиска наибольшего (наименьшего) значения в последовательности чисел, избавляясь от  сложной разветвляющейся структуры и переходя к алгоритмам более  простой циклической структуры. Для этого исходные простые переменные а, Ь, с, ... представим в виде элементов одномерного массива, например X, то есть: Х,=а, Х2=6,  Х3=с, ... После такой замены, используя простейший детерминированный цикл с  переменной цикла, отслеживающей изменение индексов массива X,  получаем сравнительно простой алгоритм поиска наибольшего значения  в последовательности чисел (рис. 1.17). Отметим, что в подобном алгоритме количество  блоков остается без изменений при любом увеличении количества исходных  переменных а, Ь,с,..., изменяется только размер массива X, то есть количество его  элементов X,, Х2, Х3,... В алгоритме наибольшее (наименьшее) значение элементов одномерного массива нахо­ дится путем сравнения каждого очередного элемента с наибольшим (наименьшим) из пре­ дыдущих. Если рассматриваемый элемент больше наибольшего (меньше наименьшего) из  предыдущих, то его значение следует считать новым значением  наибольшего (наименьшего). В противном случае значение наибольшего (наименьшего) не  изменится. Пример 1.13. Ежедневные замеры влажности почвы в  течение месяца дали следующие  результаты: V,, V2, ..., V31. Определить наименьшую  наблюдавшуюся влажность почвы и число  месяца, когда она была зарегистрирована в первый раз. Для решения задачи необходимо найти наименьший  элемент массива V,, V2, ..., V3| и его порядковый номер в массиве. Схема алгоритма приведена на рис. 1Л 8. В  алгоритме в качестве начального значения переменной М, отслеживающей наименьший элемент, принято  значение первого элемента массива и,  соответственно, переменная К, указывающая  месторасположение наименьшего элемента, принимает значение 1. Далее все элементы V, (со 2­го по 31­й) в  цикле сравниваются с М. При этом если очередной элемент массива меньше М, то  переменная М становится равной значению этого элемента, а номер его  месторасположения присваивается К. По завершении цикла переменной М  будет присвоено значение наименьшего элемента массива, а переменной К ­ номера  первого наименьшего элемента. Определение кратности чисел. Для определения кратности чисел какому­то заданному числу N используют проверку на равенство результатов, полученных при делении проверяемого числа на заданное число М (при N=2 в схеме обозначенное как 1/2) и при  целочисленном делении этих чисел (нахождении целой части числа, получаемого от  деления двух целых операндов, в схеме обозначенное как [1/2]). Если полученные  результаты совпадают, то проверяемое число кратно числу N, в противном случае ­ нет. Пример 1.14. Дан натуральный ряд чисел от 1 до N. Вычислить сумму четных и  произведение нечетных чисел этого ряда. Схема алгоритма представлена на рис. 1.19. Удаление и вставка членов последовательности. Как удаление, так и вставка членов последовательности заключается в их перестановке на другие (как правило, соседние) места с целью высвобождения места для вставляемого  элемента (случай вставки элемента или расширения последовательности) или  исключения места, где находится удаленный элемент последовательности (случай  удаления элемента или сжатия последовательности). В обоих вариантах изменяется  размер последовательности: в одном случае в сторону увеличения, а в другом ­  уменьшения. Пример 1.15. Дана последовательность натуральных  чисел X 1 X2 , ..., XN и натуральное число А. Найти и удалить из последовательности элементы, рапные А. Наиболее просто эта задача решается с  введением дополнительного индекса К, определяющего  новое место элементов последовательности после удаления  требуемых (рис. 1.20).   Пример 1.16. Дана упорядоченная по возрастанию  последовательность попарно различных натуральных чисел  Х1,X 2,..., X N и число А. Вставить в этупоследовательность  число А, не изменяя ее упорядоченности. Для решения задачи требуется организовать два цикла: один для определения места, куда  необходимо вставить число А, а второй ­для перестановки элементов с этого места и до  конца последовательности на соседние места. При этом необходимо обращать внимание на то,  чтобы не "затереть" нужные элементы последовательности, для чего следует  просматривать и раздвигать последовательность от последнего элемента. Схема алгоритма без использования специальных способов сокращения числа  сравнений (например, деления отрезка поиска пополам), приведена на рис. 1.21. Вычисление степенных многочленов (по схеме Горнера) типа Y = A1*XN + A2*XN­1+A3­ XN­2+... +AN­1*X2+AN­X + AN+1, (например, Y = 5Х4 ­ 8Х3 + ЗХ2 + 9Х ­ 4) часто приходится  производить при переводе чисел из одной системы счисления в другую с  основанием, большим исходного. Организация вычислений непосредственно  по приведенному выражению приводит к значительному накоплению ошибки результата  из­за многократного возведения в степень.Использование схемы Горнера значительно  уменьшает ошибку и сокращает количество операций, поскольку возведение  переменной X в любую степень  заменяется простым умножением. Схема Горнера основана на изменении  вида представления степенного  многочлена, исключающего операции  возведения в степень: Y = (... (A1*X + A2)*X + A3 )*X+... +AN.l)*X + AN)*X+AN+1 например, Y =  ((((5 *Х ­ 8)*X + 3)*X + 9)* X ­ 4).  Обозначив через Y арифметическое  выражение в любых внутренних  скобках и используя операцию  присваивания: Y= Y*X + А1, легко  получим выражение в смежных  внешних скобках. При этом для  получения результата приведенная  операция должна повториться в цикле  N раз при изменении переменной цикла I = 2,3,..., N+1 и начальном значении Y = A,.Схема  алгоритма вычисления значения степенного многочлена по схеме Горнера представлена на рис. 1.22. Здесь коэффициенты многочлена заданы в виде массива, содержащего N+1  элемент. Начальное значение переменной Y, определенное перед началом цикла, равно  коэффициенту А,. Если в многочлене отсутствуют члены с некоторыми степенями  переменной X, то соответствующие элементы массива коэффициентов задаются при  вводе равными нулю. Вычисление суммы членов бесконечного ряда с заданной точностью является  типичной задачей, алгоритм которой содержит итерационный цикл, поскольку заранее  неизвестно, какой член ряда будет добавлен последним для достижения нужной точности  вычислений.   Пример 1.17. Вычислить сумму членов бесконечного ряда         Вычисления прекратить, как только значение очередного члена ряда станет по  модулю меньше заданной заранее погрешности e. Вариант алгоритма решения задачи представлен на  рис.1.23. В алгоритме для получения требуемой суммы  вначале вычисляется значениеочередного члена ряда (h)  и, после его сравнения со значением заданной погрешности, с использованием операции  присваивания s =s + hприбавляется к сумме предыдущих  членов ряда. Вычисления прекращаются, как  только значение очередного члена ряда по абсолютной  величине окажетсяменьше заданной погрешности e. При вычислении в подобных алгоритмах целесообразно воспользоваться рекуррентным  соотношением, позволяющим очередное значение члена рядаhN определять из  предыдущего hN­1, путем его умножения на некоторое приращение Dh.  Приращение Dh несложно получить, разделив hN на hN­1. Например, для приведенного ряда имеем Учитывая, что N!=(N­1)!­N, xN=x(N­1)­x и (­1)N+1 = (­1)N *(­1), после элементарных  сокращений получаем Dh=­x/N. Следовательно, каждый последующий  член N рассматриваемого ряда может быть получен простым перемножением значения  предыдущего члена ряда на найденное приращение с использованием при этом операции  присваиваниях h= ­x/N*h. Как видим, эта операция избавила нас от необходимости  вычисления факториала N! и N­й степени числа XN, что существенно уменьшило  количество производимых операций и повысило точность вычислений. Организация вложенных циклов. Иногда цикл, называемый в данном случае внешним,  может содержать в себе один или несколько внутренних, образуя так называемые  вложенные циклы. Каждый из вложенных циклов, в свою очередь, может содержать  вложенные в него циклы. Как внешние, так и внутренние циклы организуются по общим  правилам организации циклических алгоритмов. Переменные внешнего и внутреннего  цикла должны быть разными и изменяться таким образом, чтобы для каждого значения  переменной внешнего цикла переменная внутреннего цикла приняла все оговоренные в  цикле значения. При организации вложенных циклов необходимо строго следить за тем,  чтобы цикл, начинающийся позже, заканчивался раньше. При этом передача управления  "вовнутрь" цикла запрещена. Выход из цикла возможен после его  естественного завершения или досрочно, например в результате проверки  некоторого условия. Пример 1.18. По окончании приемных экзаменов был составлен список группы  абитуриентов, содержащий 25 фамилий и экзаменационные оценки каждого абитуриента  по 5 дисциплинам.Требуется определить средний балл каждого абитуриента. Таблицу оценок 25 абитуриентов по 5 предметам представим в виде двумерного массива  А25;, содержащего 25 строк и 5 столбцов: Каждая строка массива содержит оценки соответствующего абитуриента по всем  дисциплинам, столбец ­ оценки всей группы по одной соответствующей дисциплине.  Элемент массива Ajt ­это оценка 1­го абитуриента по J­й дисциплине 1=1, 2,..., 25; J = 1,  2,..., 5.   Задача сводится к определению среднего  арифметического значения элементов каждой строки матрицы, для чего предварительно  необходимо вычислить сумму значений элементов 2,..., 25. Для вычисления суммы элементов одной строки организуем вложенный цикл  с переменной цикла J = 1, 2,..., 5.По завершении работы вложенного цикла  определим среднее арифметическое значение элементов строки. Повторяя приведенные  действия для каждой строки, вычислим все искомые значения среднего балла каждого  абитуриента. Для который будет внешним по отношению к вложенному циклу  спеременной.1. Схема  алгоритма приведена на рис. алгоритмав ЭВМ можно разбить на  описание задачи — создание задачи; решения задачи; 1.24.   Технология проектирования  Процесс решения задачи на ряд этапов: 1. постановка задачи; 2. математическое математической модели 3. составление алгоритма 4. составление программы; 5. разработка тестовой задачи; 6. отладка программы; 7. расчет на ЭВМ, получение и анализ результатов. Существенным шагом на пути снижения трудоемкости процесса программирования  стал структурный подход к проектированию алгоритмов. Его основным принципами яв­ ляются нисходящее проектирование и модульное программирование. Нисходящее  проектирование заключается в последовательном разбиении задачи на все более мелкие  участки, т.е. процесс программирования идет «сверху вниз». Модульное  программирование предполагает создание для каждого такого участка отдельной  автономной программы — модуля. Специально созданная программа объединяет все  модули в целое и управляет их работой. Процесс последовательного построения алгоритма может выглядеть следующим образом:  алгоритм сначала формулируется в самых «крупных» командах, при этом в записи ал­ горитма могут использоваться команды, выходящие за рамки возможностей исполнителя. Затем на каждом последующем этапе отдельные детали алгоритма уточняются, при этом  недоступные исполнителю команды записываются как вызов вспомогательных  алгоритмов. После этого строятся вспомогательные алгоритмы. Процесс продолжается до тех пор, пока все алгоритмы не будут состоять из команд, понятных исполнителю. Такой  способ построения алгоритма называется методом последовательного уточнения  алгоритма (пошаговой детализацией, нисходящей разработкой). Данный под ход к  проектированию алгоритмов позволяет повысить качество и надежность разрабатываемых программ. Кроме того, появляется возможность использовать отдельные модули  программы при решении других задач. На практике «чистую» нисходящую разработку осуществить практически невозможно,  так как выбор более конкретизированных элементов на каждой стадии должен произво­ диться на основе представления и понимания возможностей языка реализации. Однако  даже в данном случае на более поздней стадии часто обнаруживается, что некоторый  выбор, сделанный ранее, был неверным. Это приводит к необходимости разработки новых и корректировки уже имеющихся модулей. Другой подход к созданию программ называется восходящей разработкой. При этом  осуществляется последовательное построение программы из уже имеющихся элементов,  начиная с примитивов, предоставляемых выбранным языком программирования. Этот  процесс заканчивается получением требуемой готовой программы. На каждом этапе из  имеющихся элементов строятся новые более мощные (в контексте разрабатываемой  программы) элементы. Они в свою очередь используются на следующем этапе для  построения еще более сложных элементов и так далее до тех пор, пока не будут получены элементы, из которых можно непосредственно составить требуемую программу. На  практике восходящая разработка в чистом виде невозможна; построение каждого нового  элемента должно сопровождаться «просмотром вперед» с целью проверки, выполняются  ли все требования, предъявляемые к разрабатываемой программе. Но даже при таком  подходе на более позднем этапе часто обнаруживается, что использованная ранее  последовательность построения была выбрана неправильно и требует корректировки. Таким образом, на практике при разработке алгоритмов обычно используется сочетание  методов нисходящего и восходящего проектирования. Использование вышеназванных методов позволило создать огромное количество  разнообразных алгоритмов, и пришлось обратить серьезное внимание на вопросы их эф­ фективности. В значительной степени эффективность алго­ ритма зависит от его сложности — количественной характеристики, указывающей,  сколько времени работает алгоритм (временная сложность) либо какой объем памяти необходим для его выполнения (емкостная сложность). Сложность рассматривается в  основном для алгоритмических моделей, поскольку в них время и память присутствуют в  явном виде. Физическое время выполнения алгоритма — это величина, равная  произведению n и t, где и число действий (элементарных шагов, команд); t — среднее  время выполнения одного действия. Число шагов и определяется описанием алгоритма в  данной алгоритмической модели и не зависит от физической реализации модели; t—  величина физическая и зависит от скорости сигналов в элементах и узлах ЭВМ, Поэтому  объективной математической характеристикой трудоемкости алгоритма (его временной  сложности) в данной модели является число действий. Емкостная сложность алгоритма определяется числом ячеек памяти, используемых в  процессе его исполнения. Эта величина не может превосходить числа действий п, умно­ женного на определенную константу (число ячеек, используемых в данной модели на  одном шаге). В свою очередь число шагов может сколь угодно сильно превосходить  объемпамяти (за счет циклов по одним и тем же ячейкам). Следует отметить, что  проблемы памяти технически преодолеваются легче, чем проблемы быстродействия,  которое имеетфизический предел — скорость распространения физических сигналов (300 тыс. км/с). Поэтому трудоемкость (временная сложность) считается более существенной  характеристикойалгоритма. Трудоемкость алгоритма, как и другие виды сложности, не является постоянной  величиной, а зависит от размерности задачи. Под размерностью задачи понимается либо  объем памяти, необходимой для записи данных, либо характеристики задачи, от которых  зависит этот объем. В задачах обработки графов размерностью может считаться  число вершин или дуг графа, в задачах преобразования логических выражений — число  букв в выражении и т. д. Например, сложность простейшего алгоритма сложения двух  чисел зависит от длины слагаемых. При сложении столбиком количество элементарных  действий (сложений цифр) пропорционально количеству разрядов. При сложении в ЭВМ,  использующей параллельный сумматор, трудоемкость сложения равна 1 (одна машинная  команда сложения) до тех пор, пока каждое слагаемое умещается в одной ячейке. Для больших чисел она  пропорциональна числу ячеек, необходимых для размещения слагаемых. Наиболее часто используют два способа определения функции сложности: 1.         ее значением является сложность худшего случая (минимальное число действий,  достаточное для обработки алгоритмом любых данных размерности n); 2.         значением является средняя сложность, взятая по всем данным размерности n.   Рассмотрим определение сложности на конкретных примерах алгоритмов поиска и  сортировки. Задачи поиска Основной вопрос задач поиска — определение в таблице места расположения элемента,  обладающего нужным свойством. Большинство задач поиска сводится к простейшей —  найти в таблице элемент с заданным значением. Предположим, что о расположении данных в таблице нет никаких сведений. Тогда  проверка одного элемента не дает никакой информации об остальных. Самый разумный  способпоиска в этом случае — последовательный перебор: алг поиск (арг цел N, арг вещ таб a[1: N], арг вещ х, рез цел k) нач k:=1 нц пока k<=N и_ a[k]<>x k:=k+1 кц если k>N то k:=0 все кон Алгоритм поиска объекта во множестве, состоящем из n объектов, последовательно  перебирает объекты множества. Сложность худшего случая равна n (искомый объект может оказаться последним);  средняя продолжительность поиска равна сумме всех номеров от 1 до n, деленной на n,  чтосоставляет (n+1)/2. В обоих случаях функция сложности имеет вид a*n+b, т. е.  является линейной. 2.Поиск максимального элемента Дано n чисел. Требуется найти в этой последовательности максимальное число. Алгоритм метода решения сформулируем в следующем виде: 1.         в некоторой памяти М запоминаем первое число; 2.         следующие числа последовательности сравниваем с числом, хранящимся в М, и  записываем в М большее из этих чисел (т. е. прежнее число, если оно окажется больше,  либо вместо него следующее число); 3.         повторяем второй шаг до конца данной последовательности. Сложность приведенного алгоритма также линейна (каждое из и чисел просматривается  только один раз, и при этом совершается не более пяти операций). 3.Упорядочение последовательности С помощью предыдущего алгоритма можно построить алгоритм упорядочения  последовательности чисел. Для этого найдем наибольшее число в исходной  последовательности из n чисел, вы пишем его и удалим из последовательности. Далее  определим наибольшее число в оставшейся последовательности из n­1 чисел, припишем  его справа к найденному ранее числу и вычеркнем из исходной последовательности и т. д.  Трудоемкость этого алгоритма равна многочлену второй степени. 4.Поиск в упорядоченной последовательности Поскольку для решения некоторой задачи могут использоваться разные алгоритмы,  естественно искать для нее алгоритм с наименьшей сложностью и определять сложность  задачи как минимум среди всех сложностей алгоритмов, решающих данную задачу. С этой точки зрения некоторые из приведенных выше алгоритмов не являются оптимальными.  Например, в упорядоченном множестве поиск можно осуществить гораздо быстрее, чем  за п шагов. Этот быстрый алгоритм, называемый алгоритмом двоичного поиска, работает так.  Возьмем средний элемент множества. Если искомый элемент меньше среднего, берем  середину меньшей части множества. Если же искомый элемент больше среднего, обращаемся к середине большей части — и так до тех  пор, пока очередная середина не совпадет с искомым элементом. Ниже приведен фрагмент реализации бинарного поиска элемента X в таблице a[1:N): нач L:=l {на первом шаге рассматривается весь массив} R:=N F:= О {признак результативности поиска: F=l, если X найден, и 0 —в противном случае} нц пока L<=R и F=0 {условия продолжения поиска} М:= div (L+R, 2) {выбор среднего элемента} если А[М}=Х то F:=l {элемент найден, поиск надо прекратить} иначе если А[М]<Х то L:=M+i {отбрасывается левая часть} иначе R:=M­i {отбрасывается правая часть} все все кц кон Поскольку на каждом шаге длина последовательности, в которой происходит поиск,  уменьшается вдвое, общая трудоемкость этого алгоритма имеет порядок Log2 x*п. Столь высокая скорость данного алгоритма возможна только для упорядоченных  множеств и лишний раз говорит о том, как важен порядок там, где хочешь быстро найти  то, что нужно. Так мы ищем слова в словарях, книги в каталогах, телефоны в справочниках и т. д. Алгоритмы сортировки Из решения предыдущей задачи вытекает, что чрезвычайно важно иметь хорошие алго­ ритмы упорядочения элементов последовательности. В программировании для задач  упорядочения обычно используют термин сортировка. Описанный выше алгоритм сортировки (см. задачу 3) не является оптимальным. Известны алгоритмы сортировки со  сложностью в худшем случае порядка и n*log n. К ним относится обменная сортировка с  разделением, которая заключается в следующем: 1.         в исходном неотсортированном массиве выбрать некоторый элемент x = a[i]; 2.         переставить элементы массива таким образом, чтобы слева от х оказались  элементы массива, меньшие или равные х, а справа — элементы массива,  большие х. Пусть при этом элемент х попадает в позицию с номером k, тогда  массив будет иметь вид ( a[1], а[2],...,a[k­1], a[k], a[k+1],…,a[n] ). Каждый из элементов а[1], а[2],..., a[k­1] меньше либо равен a[k], каждый из  элементов а[k+1],..., а[n] больше a[k]. Отсюда можно сделать вывод, что  элемент a[k] стоит на своем месте. А исходный массив при этом разделился на две  неотсортированные части, барьером между которыми является элемент a[k], 3) далее необходимо применить шаги 1 и 2 для каждой из двух неотсортированных частей. И так до тех пор, пока не останутся подмассивы, состоящие из одного элемента, т. е. пока не будет отсортирован весь массив. Выбор алгоритма сортировки зависит от структуры обрабатываемых данных. Поэтому  соответствующие методы были разбиты на два класса: сортировка массивов  (таблиц) исортировка файлов (последовательностей). Иногда эти методы  называют внутренней и внешней сортировкой, поскольку массивы • хранятся во  внутренней, оперативной, памяти машины, а файлы — в более медленной внешней  памяти. Если данные «выстроены» в виде массива, то доступ имеется ко всем его  элементам. Если же данные образуют файл, то доступ имеется только к одной величине из множества элементов, записанных в файл. Основное условие для сортировки массивов заключается в следующем: выбранный метод  сортировки должен обеспечивать экономное расходование доступной памяти. Это оз­ начает, что перестановки, приводящие элементы в порядок, должны выполняться «на том  же месте», т. е. методы, в которых элементы из массива А передаются в  результирующиймассив В, представляют существенно меньший интерес. Сортировать элементы можно по неубыванию (a1<=a2<=...<=an) и по  невозрастанию (at>=a2>=an). Методы сортировки «на том же месте» можно разбить на три основные категории. 1.Сортировки с помощью выбора Алгоритм метода заключается в следующем: находят элемент массива,  имеющий наименьшее значение, меняют местами его и первый элемент, затем выполняют  то же самое, начав со второго элемента, и т. д. 2.Сортировки с помощью включения Алгоритм метода состоит в следующем: последовательно просматривают  элементы a1,a2,...,an и каждый новый элемент ai вставляют на подходящее место в уже  упорядоченную совокупность ai­1. Это место определяется последовательным  сравнением ai с упорядоченными элементами a1 …, ai­1. 3.Сортировки с помощью обменов Алгоритм метода таков: последовательным просмотром элементов a1,a2,...,an находят  наименьшее i такое, что ai>ai+1. Затем меняют ai и ai+1 местами и возобновляют просмотр с ai+1 элемента и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры  опять начинают с начала последовательности, уменьшая количество  просматриваемых элементов на 1. Массив будет упорядочен после просмотра, в котором  участвовали только первый и второй элементы. Три перечисленных метода часто называют прямыми. В них требуется  порядка n*n сравнений. Задание для самостоятельной работы  1.         Записать алгоритм поиска максимального элемента и его номера в таблице  чисел A [1: n]. 2.         Записать алгоритмы сортировки в таблице чисел A [1: n]: а) методом выбора; б) методом включений; в) методом обменов. 3.         Записать алгоритм подсчета в таблице чисел A[i: n] наибольшего количества  расположенных последовательно положительных элементов. 4.         Записать алгоритм, проверяющий, является ли последовательность  чисел A [1: n] перестановкой чисел 1, 2, ..., n. 5.         Дана упорядоченная таблица чисел A [1: n], которая может содержать элементы с  одинаковыми значениями. Записать алгоритм, для выяснения того, имеется ли в  таблице заданное число К. Если такое число имеется, то найти количество элементов  таблицы, равных ему. 6.         Дана прямоугольная таблица чисел A[1: n, 1: m]. Составить алгоритм, который  определял бы номера строк таблицы, начинающихся с одинаковых чисел, и подсчитывал  бы сумму элементов в этих строках. 7.         Дана прямоугольная таблица чисел A[1: n, 1: m]. Выяснить, есть ли в этой таблице  строки, все элементы которых совпадают. Предисловие Данный материал представляет собой справочное руководство по составлении  алгоритмов, которые являются необходимой составной частью контрольной и курсовой  работы по дисциплине "Информатика". Изложенный материал не претендует на полноту охвата всех сторон проблемы  алгоритмизации при решении задач, возникающих на практике. Однако его вполне  достаточно для того, чтобы разобраться и выполнить ту часть названных работ, которая  необходима для составления алгоритмов и их описания. Опыт показывает, что трудности, возникающие при составлении алгоритмов имеют как  общий характер, когда студент не может уяснить принцип работы алгоритма вообще, так  и частный, когда непонятным оказывается отдельный фрагмент алгоритма. В любом случае рекомендуется обратить внимание на следующее. Разбирая или составляя алгоритм, нужно мысленно представить некоторый автомат по обработке данных  (компьютер), который будет выполнять действия, предписанные этим алгоритмом. Без  такого представления невозможно понять сам алгоритм. Ниже, при разборе примеров,  станет понятно, что такой мысленный автомат совсем несложен. Во всяком случае он  несравнимо проще реального компьютера, хотя общие принципы их функционирования в  основном одинаковы. Допустимо (например, при составлении описания) отождествлять  работу такого автомата с работой самого алгоритма. При изучении материала особенно первоначальном, следует подробно разобраться в  каждом алгоритме, начиная с самого первого и самого простого. Начинать нужно с полного уяснения пяти самых простых и самых необходимых понятий: константа,  переменная, ячейка памяти, запись константы в ячейку памяти, чтение константы из  ячейки памяти . Не пренебрегайте этими советами, так как очень скоро убедитесь, что  при разборе следующего алгоритма обязательно натолкнетесь не только на те же  трудности, но присовокупите к ним новые. Более того, нередко полное понимание даже  самого простого алгоритма дает намного больше пользы, чем поверхностное изучение  десятка алгоритмов повышенной сложности. 1.  Алгоритм и алгоритмизация Алгоритм – это инструкция о том, в какой последовательности нужно выполнить  действия при переработке исходного материала в требуемый результат. [ последователь­ ность точных предписаний, понятных исполните лю (компьютеру, роботу и пр.),  совершить последо вательность действий, направленных на достиже ние конкретного  результата. ] Наряду с понятием алгоритма используют термин алгоритмизация , под которой  понимают совокупность приемов и способов составления алгоритмов для решения  алгоритмических задач. Часто алгоритм используется не как инструкция для автомата, а как схема  алгоритмического решения задачи. Это позволяет оценить эффективность предлагаемого  способа решения, его результативность, исправить возможные ошибки, сравнить его еще  до применения на компьютере с другими алгоритмами решения этой же задачи. Наконец,  алгоритм является основой для составления программы, которую пишет программист на  каком­либо языке программирования с тем, чтобы реализовать процесс обработки данных на компьютере. Неотъемлемым свойством алгоритма является его результативность , то есть  алгоритмическая инструкция лишь тогда может быть названа алгоритмом, когда при  любом сочетании исходных данных она гарантирует, что через конечное число шагов  будет обязательно получен результат. На практике получили известность два способа изображения алгоритмов: в виде пошагового словесного описания; в виде блок­схем. Первый из этих способов получил значительно меньшее распространение из­за его  многословности и отсутствия наглядности. Второй, напротив, оказался очень удобным  средством изображения алгоритмов и получил широкое распространение в научной и  учебной литературе. Именно этот способ будет использован ниже при составлении и  описании алгоритмов. 2. Блок­схема и ее элементы Блок­схема – это последовательность блоков, предписывающих выполнение  определенных операций, и связей между этими блоками. Внутри блоков указывается  информация об операциях, подлежащих выполнению. Конфигурация и размеры блоков, а  также порядок графического оформления блок­схем регламентированы ГОСТ 19002­80 и ГОСТ 19003­80 "Схемы алгоритмов и программ". В табл. 1 приведены наиболее часто используемые блоки, изображены элементы связей  между ними и дано краткое пояснение к ним. Блоки и элементы связей называют  элементами блок­схем. Представленных в таблице элементов вполне достаточно для изображения алгоритмов,  которые необходимы при выполнении студенческих работ. При соединении блоков следует использовать только вертикальные и горизонтальные  линии потоков. Горизонтальные потоки, имеющие направление справа налево, и вертикальные потоки,  имеющие направление снизу вверх, должны быть обязательно помечены стрелками. Прочие потоки могут быть помечены или оставлены непомеченными. Линии потоков должны быть параллельны линиям внешней рамки или границам листа Таблица 1 Название Процесс Элемент Комментарий Вычислительное действие или  последовательность  вычислительных действий Решение Проверка условия Модификация Заголовок цикла Предопределенный  процесс Документ Перфокарта Ввод/Вывод Соединитель Начало, Конец Комментарий Горизонтальные и  вертикальные потоки Слияние Межстраничный  соединитель Обращение к процедуре Вывод данных, печать данных Ввод данных Ввод/Вывод данных Разрыв линии потока Начало, конец, пуск, останов,  вход и выход во  вспомогательных алгоритмах Используется для размещения  надписей Линии связей между блоками,  направление потоков Слияние линий потоков Нет Расстояние между параллельными линиями потоков должно быть не менее 3 мм , между  остальными элементами схемы – не менее 5 мм . Горизонтальный и вертикальный размеры блока должны быть кратны 5 мм (делиться на 5  нацело). Отношение горизонтального и вертикального размеров блока b/а = 1.5 является  основным. При ручном выполнении блока допустимо отношение b/а = 2. Блоки "Начало", "Конец" и "Соединитель" имеют высоту а/2, т. е. вдвое меньше основной  высоты блоков. Для размещения блоков рекомендуется поле листа разбивать на горизонтальные и  вертикальные (для разветвлявшихся схем) зоны. Для удобства описания блок­схемы каждый ее блок следует пронумеровать. Удобно  использовать сквозную нумерации блоков. Номер блока располагают в разрыве в левой  верхней части рамки блока. По характеру связей между блоками различают алгоритмы линейной, разветвляющейся и  циклической структуры. Примеры, пояснявшие изложенное, можно найти в блок­схемах алгоритмов, которые  будут приведены ниже. 3. Константы, переменные и ячейки памяти Для того чтобы ясно представить как "работает" алгоритм, опишем простейший  автомат,  который предназначен для выполнения операций, предписанных этим алгоритмом. В состав такого автомата входят: память, состоящая из отдельных ячеек; считывающая/записывающая головка; процессор, т. е. устройство, способное выполнять операции, в том числе математические,  и отдавать  головке указания читать данные из ячеек или записывать данные в ячейки  памяти автомата. Головка, получив указание от процессора, может записывать в ячейку или считывать из  нее одну константу . В простейшем случае константой является любое арифметическое число. Например, 12,  0.78, 0, –45.33 и т. д. ( Константами могут быть такие строки символов, структуры данных и др.). Под простой переменной , или просто переменной будем понимать некоторую ячейку  памяти, т. е. отдельное место для хранение одной константы. В отдельной ячейке за время работы алгоритма может побивать множество различных констант (отсюда название –  переменная). Такими ячейками (электронными, магнитными, оптическими) снабжен  реальный компьютер. Переменные имеют буквенно­символьное обозначение. Например, 1, n, a, a1, b , H2 –  переменные. Одновременно обозначение переменной является индексом ячейки, в  которую будут записываться константы. Любая из таких констант называется значением  переменной . Например, Z является переменной и адресом ячейки Z одновременно. С  алгоритмической точки зрения понятия “переменная” и “адрес ячейки” памяти являются  идентичными. Запись вида Y = 5.5 следует понимать так: записать константу 5.5 в ячейку с адресом Y  (если до этой операции в ячейку была записана константа, то она будет затерта, а на ее  место будет помещена константа 5.5). Произносить эту запись следует так: “переменной  Y присвоить значение 5.5” . Запись вида L = M следует понимать так: прочитать константу, расположенную по адресу  M и скопировать эту константу в ячейку с адресом L (при этом константа из ячейки M не  удаляется, а остается такой, какой она была до чтения). Произносить эту запись нужно  так: "переменной L присвоить значение переменной M (или просто: L присвоить M)". 4. Массивы Другой разновидностью переменных являются так называемые индексированные  переменные или массивы . Массив – это некоторая совокупность ячеек, объединенная  одним обозначением (массивом может быть одна ячейка). Всякий массив обязательно  имеет размерность. Массивы бывают одномерными, двумерными, трехмерными и т. д. Одномерный массив – это последовательность ячеек, расположенных в одну линию. На  рис. 1 приведен пример такого массива. Массив имеет имя q. Для того чтобы можно было отличить одну ячейку массива от  другой ячейки этого же массива, их нумеруют. Нумерация ячеек обычно начинается с 1.  Номер ячейки массива называется его индексом , а константа в ячейке – элементом  массива. Теперь становится возможной работа с отдельной ячейкой такого массива.  Например, команда q 7 = 8.2 означает, что в 7­ю ячейку массива q надлежит записать  константу 8.2. Команда r 41 = q 2 + q 5 означает, что нужно сложить константы,  записанные во 2­ю и 5­ю ячейки массива q, и результат записать в 41­ю ячейку  одномерного массива r. Эту же операцию можно описать другими словами: 41­му  элементу массива r присвоить значение суммы 2­го и 5­го элементов массива q. Двумерный массив по расположению ячеек напоминает математическую матрицу ( рис.  2 ). Элемент такого массива характеризуется двумя индексами: первый показывает  строку, в которой расположена ячейка, второй – ее столбец. Например, команда d 2, 5 =  43 означает, что в ячейку, размещенную на пересечении 2­й строки и 5­го столбца  двумерного массива d, нужно записать константу 43.                                                                                            Аналогично устроена структура массивов трех­ и большей размерности. 5. Линейные алгоритмы Линейный алгоритм – это алгоритм, в котором блоки выполняются последовательно  сверху вниз от начала до конца. На рис. 3 приведен пример блок­схемы алгоритма вычисления периметра Р и площади S  квадрата со стороной длины A. Рис. 3. Линейный алгоритм Блок­схема алгоритма состоит из шести блоков. Выполнение алгоритма начинается с  блока 1 "Начало". Этот блок символизирует включение автомата, настройку его на  выполнение алгоритма и выделение памяти под все переменные, которые задействованы в  алгоритме. В алгоритме рис. 3 таких переменных три:  A, Р, S. Следовательно, под  каждую из них алгоритмом будет выделено по одной ячейке памяти. На этом блок 1  будет отработан. Как видно из рис.3, блок 1 связан вертикальной линией потока с блоком 2. Эта линия не  имеет стрелки, указывавшей направление потока. Следовательно, этот поток направлен  вниз. Таким образом, после выполнения блока 1 управление будет передано на блок 2.  Блок 2 "Перфокарта" ( см. табл. 1) показывает, что переменной A следует присвоить  значение. Это означает, что в ячейку, отведенную автоматом под эту переменную, нужно  поместить константу. На реальной компьютере эта константа может быть введена самыми разными способами. Способ зависит от того, как запрограммирован данный фрагмент.  Можно, например, потребовать ввод константы с клавиатура или получить его из заранее  подготовленного файла. Возможно эта константа будет получена через внешние  источники данных, например, от физической установки, подключенной к компьютеру. Для данного примера способ передачи константы не имеет значения, важно лишь то, что  при выполнении блока 2 в ячейку с адресом А будет занесена конкретная константа.  Пусть такой константой является число 5. Далее управление по линии потока передается к блоку 3 "Процесс". В этом блоке при  выполнении размещенной в ней команды число 4 умножается на константу, помещенную в ячейку А (т. е. 5), и результат (т. е. 20) присваивается переменной Р (т. е. константа 20  записывается в ячейку по адресу Р). После выполнения этих операций управление  передается к блоку 4. В блоке 4 аналогичным образом производится умножение значений переменной А и  результат (константа 25) присваивается переменной S (в ячейку по адресу S будет  занесена константа 25). После этого выполняется переход к блоку 5. При выполнении команд блока 5 выводятся (например, на экран, бумагу, во внешний файл и т. д.) значения переменных А, Р, S, которые сохранились в соответствующих ячейках к  этому моменту. Понятно, что для конкретного примера А = 5 будут выведена константы  5, 20, 25, т. е. длина сторона квадрата, его периметр и площадь. Далее управление  передается последнему блоку 6. В блоке б “Конец” производится освобождение ячеек памяти, которые были  зарезервированы под переменные А, P, S, и алгоритм заканчивает работу. Понятно, что при новом запуске этого же алгоритма можно получить совсем другие  числа. Так, если в блоке 2 переменной А присвоить значение 20, то алгоритм выдаст в  блоке 5 константы 20, 80, 400. Детальное описание алгоритма рис. 3 приведено для того, чтобы показать, в какой  последовательности автомат выполняет предписанные операции и как при этом меняется  состояние памяти автомата, т. е. для того, чтобы объяснить суть происходящих в  автомате процессов. Из сказанного нужно уяснить, что автомат выполняет предписанную  ему работу шаг за шагом. Всякий шаг обрабатывается процессором. Помимо вычислений  процессор при необходимости отдает команды считывавшей/записывавшей головке, что и  куда записывать, откуда читать. Конечный результат следует искать в ячейках памяти,  каждая из которых до окончания алгоритма имеет известный адрес и хранит записанную в нее константу. При выполнении контрольной или курсовой работы нет нужды давать столь подробное  описание алгоритма. Тем не менее, описание должно быть выполнено с той степенью  полноты, которая позволяет дать ясное представление о всех сторонах и особенностях  алгоритмического процесса. 6. Разветвляющиеся алгоритмы На практике алгоритмы линейной структуры встречается крайне редко. Чаще необходимо организовать процесс, который в зависимости от каких­либо условий проходит по той  либо иной ветви алгоритма. Такой алгоритм называется разветвляющимся. В блок­схемах ветвление начинается на выходах элемента "Решение", с помощью  которого в алгоритме выполняется проверка какого­либо условия. Количество ветвей тем больше, чем больше проверяемых условий. Для пояснения рассмотрим решение задачи нахождения значения функции z = y/x. На первый взгляд представляется, что алгоритм решения этой задачи имеет линейную  структуру. Однако, если учесть, что делить на нуль нельзя из­за переполнения ячейки, то,  во­первых, нужно из вычислений исключить вариант х = 0 и, во­вторых,  проинформировать пользователя алгоритма о возникшей ошибке. Если этого не сделать,  то при вычислениях может возникнуть аварийный выход до получения результата. В  профессиональной практике аварийные завершения крайне нежелательны. т. к. к этому  моменту уже может быть накоплено определенное количество результатов, которые  окажутся необработанными и попросту пропадут. Можно привести другие примеры,  когда аварийный останов компьютера может повлечь куда более серьезные последствия. Решение задачи представлено блок­схемой рис. 4.                                                                                                                                                                                              Рис. 4. Разветвляющийся алгоритм Она состоит из 7 блоков. После начала работы алгоритм в блоке 2 требует ввода  аргументов X и Y. Затем в блоке 3 производится проверка условия X = 0. Здесь автомат  проверяет равна ли нули константа, введенная в ячейку с адресом X. Результатом такой  проверки является ответ "Да" или "Нет". В зависимости от этого ответа выполнение  алгоритма пойдет по одной или другой ветви. Если результат проверки окажется  отрицательным, то на х можно делить и управление передается блоку 4. В блоке 4 будет получен результат Z, затем в блоке б значения всех трех переменных  будут отпечатаны и в блоке 7 алгоритм закончит работу. Если же ответ окажется положительным, то управление будет передано блоку 4. Выполняя команду блока 4,  автомат выведет сообщение "Ошибка" и затем закончит работу в том же блоке 7. 7. Циклические алгоритмы Часто при решении задач приходится повторять выполнение операций по одним и тем же  зависимостям при различных значениях входящих в них переменных и производить  многократный проход по одним и тем же участкам алгоритма. Такие участки называются  циклами . Алгоритмы, содержащие циклы, называется циклическими . Использование  циклов существенно сокращает объем алгоритма. Различают циклы с наперед известным и наперед неизвестным количеством проходов. Пример 1. Рассмотрим пример алгоритма с циклом, имеющим наперед неизвестное  количество проходов. Для этого решим следующую задачу. Указать наименьшее  количество членов ряда натуральных чисел 1, 2, 3, ..., сумма которых больше числа К.                                                                                                                                                                                  Рис. 5. Разветвляющийся алгоритм Блок­схема алгоритма решения этой задачи приведена на рис. 5. Она состоит из восьми  блоков. После начала работы в блоке 2 вводится значение числа К. Далее в блоке 3 переменная i  получает значение 1, т. е. значение, с которого начнется отсчет натуральных чисел.  Переменная S, предназначенная для накопления сумма этих чисел, перед началом  суммирования получает значение 0. После этого управление передается блоку 5. В нем при выполнении команды S = S + i производится сложение содержимого ячеек S и i, а результат записывается в ячейку S. Поскольку до операции сложения было S = 0, i = 1,  то после операции будет S = 1. При записи нового значения старое содержимое ячейки S  (нуль) стирается, а на его место записывается число 1. Нужно обратить внимание на то, что если бы до этой операции в блоке 3 не была  выполнена команда S = 0 (записать нуль в ячейку S ), то при нахождении суммы S + 1  возникла бы ошибка, поскольку из ячейки S была бы извлечена константа, которая  оказалась там после распределения памяти. После суммирования первого члена последовательности в блоке 6 выполняется проверка  условия о превышении суммы S заданного числа К. Если условие 6 не выполнится, то производится переход к блоку 4, где при выполнении  операции значение переменной увеличивается на 1 и становится равным 2. Теперь  алгоритм вновь вернется к блоку 5 и к старому значении суммы добавит новый член 2.  После этого сумма станет равной 3. В блоке б вновь проверяется условие получения  требуемой суммы и т. д. Цепочка блоков 5­4 будет обрабатываться вновь и вновь до того  момента, когда однажды при определенном значении переменной i, наконец, выполнится  условие S > К, т. е. когда накапливаемая в таком цикле сумма впервые превысит заданное  значение К. Переменная i, значение которой при очередном проходе цепочки этих блоков  увеличивается на 1, играет роль счетчика этого цикла. Далее производится переход к блоку 7, где отпечатается значение количества членов ряда (извлечено и отпечатано число из ячейки i, которое там хранится в момент выполнения  условия), суммы S и в блоке 8 алгоритм закончит работу. Пример 2. Теперь приведем пример алгоритма, содержащего цикл с наперед известным  количеством проходов (повторений). Алгоритм решает задачу накопления суммы  положительных элементов одномерного массива Z длины N ( под длиной массива  понимается количество его элементов ). Блок­схема алгоритма дана на рис. 6. Рис. 6. Циклический алгоритм Вначале в блоке 2 производится ввод двух переменных N и Z. Первая из них представляет одну ячейку. В нее записывается одна константа – число, равное количеству элементов  массива Z. Именно такое количество ячеек объединяет другая переменная – Z. Следует подчеркнуть, что если бы ввод этих переменных в блоке 2 производился в  противоположном порядке, то это привело бы к ошибке. Действительно, невозможно  заполнить N ячеек массива Z, когда самое N еще не известно (оно будет введено позже Z). Далее в блоке 3 переменной S присвоено начальное значение 0. Это сделано для того,  чтобы приготовить ячейку к дальнейшему накоплению необходимой суммы. Блоки 4­6 представляет собой сам цикл, в котором накапливается сумма. Для того чтобы понять, как функционирует не только этот, а и любой другой цикл,  обратимся к рис. 7, 8. На них показана общая структура цикла и его важнейшие  параметры. Как видно из рис. 7, цикл состоит из заголовка и тела. Всякий цикл обязательно имеет  свой счетчик. На рис. 8, где показана структура и параметры заголовка цикла, роль такого счетчика  выполняет переменная i. Внутри заголовка после счетчика и символа "=" через запятую  указывает начальное и конечное значения счетчика и шаг его изменения (на рис. 8 их роль  выполняют переменные j, k, l соответственно). Если значение шага l = l, то его можно не  указывать. Сначала производится вход в цикл. После этого начинается его выполнение.                                                                                                                   Рис. 7. Структура цикла                               Рис. 8.  Структура заголовка цикла Внутри заголовка счетчику первоначально присваивается значение i = j. Затем  выполняется блоки, образующие тело цикла. Обработка блоков внутри цикла  производится по часовой стрелке. В результате после первого выполнения тела цикла  управление вновь передается заголовку. Здесь к текущему значению счетчика добавится  шаг. Теперь, если новое значение счетчика не вышло за свои пределы (т. е. не стало  больше своего конечного значения при положительном шаге или меньше конечного  значения – при отрицательном шаге), то снова выполняется тело цикла, вновь после  возврата к заголовку к счетчику добавляется шаг. Так цикл будет выполняться до тех  пор, пока значение счетчика однажды не выйдет за предписанный предел. Как только  такой предел будет преодолен, произойдет выход из цикла и управление будет передано  блоку, который следует сразу за циклом. Вернемся к блок­схеме рис. 6. Заголовок ее цикла представлен блоком 4. Роль счетчика  цикла играет переменная i, которая должна в цикле изменяться от 1 до N. Поскольку шаг  явно не указан, то по умолчанию он подразумевается равным 1. Тело цикла образуют  блоки 5 и 6. Сразу после входа в цикл переменная i примет начальное значение  i = 1. Далее в блоке 5  выполняется проверка положительности первого элемента массива Z (т. к. i = 1). Если  этот элемент действительно положителен, то в блоке б он будет добавлен к переменной S, после чего выполняется возврат к заголовку цикла. Если этот элемент не положителен (т. е. нуль или отрицательный), то будет выполнен переход сразу к заголовку цикла, минуя  блок суммирования 6. На втором круге цикла счетчик i в заголовке увеличится на 1 и станет равным 2. Теперь,  при новом выполнении тела цикла, в блоке 5 проверяется на положительность второй  элемент массива Z и, если он положителен, то добавляется в сумму и т. д. Последний раз  тело цикла выполнится при i = N. При этом значении счетчика проверяется последний  элемент массива. Наконец, в заголовке цикла i примет значение N+1. Это значение  выходит за предписанный предел, следовательно, произойдет выход из цикла и  управление перейдет блоку 7. В этом блоке выводится накопленная сумма и алгоритм  закончит работу. 8. Алгоритмы со структурами вложенных циклов Нередко при алгоритмическом решении задачи возникает необходимость создания цикла,  содержащего в своем теле другой цикл. Такие вложенные друг в друга циклы относятся к  структурам вложенных циклов . Порядок вложенности циклов, когда в теле внутреннего  цикла содержатся другие циклы, может быть достаточно большим. Этот порядок  определяется методом, с помощью которого достигается решение поставленной задачи.  Так, при обработке одномерных массивов, как правило, удается построить  алгоритмическую схему без вложения циклов. Однако в ряде случаев при решении таких  задач без вложенных циклов не обойтись. Рис. 9. Алгоритм сортировки массива Отметим, что все вложенные друг в друга циклы, включая наружный, должны иметь  счетчики с различными именами. Вне этих циклов счетчики могут быть использованы как  обычные переменные или как счетчики других циклов. Пример 1. Рассмотрим задачу сортировки одномерного массива Z длины N.  Отсортировать массив – значит расположить его элементы в порядке роста или убывания. Опишем метод сортировки массива в порядке роста. Сначала выполняется проход по  массиву с целью определения в нем наименьшего элемента. Затем производится  перестановка этого элемента с первым. Далее совершается второй проход по массиву,  начиная со второго элемента. Найденный наименьший элемент переставляется со вторым  и т. д. После (N­1)­го прохода с выполнением названных операций массив окажется  отсортированным. Блок­схема этого алгоритма сортировки показана на рис. 9. Она включает 12 блоков.  После начала работы в блоке 2 переменная N и массив Z заполняются константами. Затем в блоке 3 проверяется условие о том, нужно ли сортировать массив. Это сводится к установлению факта наличия в массиве нескольких элементов, т. к.  массив из одного элемента всегда отсортирован. Если этот факт установлен, то алгоритм приступает к сортировке. Процедура сортировки выполняется в цикле, объединяющем  блоки 4­10. В теле этого цикла содержится другой цикл, который образован блоками 6­8.  Его назначение станет ясно из дальнейшего разбора алгоритма. После входа в наружный цикл его счетчик i примет значение 1, что в рамках нашего  метода подразумевает первый проход по массиву. Далее будут выполнены блоки 5­10, составляющие тело наружного цикла. В блоке 5  размещены две вспомогательные переменные V и L. Первая из них предназначена для  фиксирования наименьшего элемента, а вторая – для запоминания его индекса. Так как i  = 1, то при первом проходе в блоке 5 V примет значение первого элемента, а L значение 1. Затем во внутреннем цикле, образованном блоками 6­8, где его счетчик j будет  изменяться от 2 до N, последовательно проводится сравнение соответствующих  элементов массива Z со значением переменной V. При этом всякий раз, как будет найден  меньший чем v элемент, значение V будет заменено на значение этого элемента, а в  переменной L будет зафиксирован его индекс. Понятно, что после выполнения  внутреннего цикла в переменной V будет содержаться значение, равное наименьшему  элементу, а в L – индекс этого элемента. В блоке 9 далее проверяется, не является ли  наименьший элемент первым элементом массива. Если это не так, то в блоке 10 на место  наименьшего элемента (его номер L) запишется первый (т. к. при первом проходе L =1 ), а на место первого элемента – наименьший (он равен V). После этого произойдет возврат  управления к заголовку наружного цикла блоку 4. В нем значение счетчика станет равным i = 2. Затем вновь выполняется его тело, но уже для нового значения счетчика i. Теперь с  помощью блоков 5­10 отыскивается наименьший элемент массива начиная с номера 2.  Затем в блоках 9­10 он займет второе место в массиве и т. д. Когда тело наружного цикла  выполнится (N­1), раз массив будет отсортирован. В блоке 12 отсортированный массив будет выведен и в блоке 13 алгоритм окончит работу. Алгоритмы со структурами вложенных циклов часто используют при решении задач  обработки двумерных массивов. В таких алгоритмах счетчики циклов используются для  манипуляции с индексами массивов. Пример 2. Дан двумерный квадратный массив Z, состоящий из N строк и N столбцов.  Необходимо найти среднее арифметическое S его отрицательных элементов и заменить  положительные элементы побочной диагонали массива средним арифметическим S. Рис. 10. Блок­схема алгоритма Блок­схема алгоритма показана на рис. 10. Она состоит из 13 блоков. В блоке 2  переменная N и весь массив Z заполняются константами. В блоке 3 рабочие переменные S и К получает значение нуль. Переменная S сначала будет играть роль сумматора  отрицательных элементов массива, затем после накопления суммы она примет значение  среднего арифметического. Переменная К нужна для подсчета количества отрицательных элементов массива. В блоках 4­7 выполняется накопление суммы отрицательных элементов массива. Эти блоки образует два вложенных цикла, причем внутренний цикл со счетчиком j  является телом наружного цикла со счетчиком i. Проанализируем работу этой структуры. После входа в наружный цикл в блоке 4 переменная i примет значение i = 1. Далее будет  выполнено его тело ( блоки 5­7 ), которое, в свою очередь, также является циклом. После  входа во внутренний цикл в блоке 5 переменная j примет значение j = 1. Затем в блоке 6  проверяется на отрицательность элемент массива Z, расположенный в первой строке и  первом столбце, т. к. i = 1 и j = 1. Если он окажется отрицательным, то в блоке 7 переменная К увеличится на 1, а к S  добавляется значение этого элемента. После этого выполняется возврат к блоку 5, т. е. к  заголовку внутреннего цикла. Здесь j увеличится на 1, станет равной j = 2 и управление  перейдет к блоку 6. В нем проверяется элемент, стоящий все в той же первой строке, но  во втором столбце (i = 1, j = 2). Если он окажется отрицательным, то К снова увеличится  на 1, а к накопленному к этому времени S добавляется значение этого элемента и т.д.  Когда полностью выполнится внутренний цикл, т. е. переменная j "пробежит" от 1 до N, в  переменную S накопится сумма всех отрицательных элементов первой строки массива, а в К – их количество. Теперь управление передается к блоку 4 заголовка наружного цикла,  где i станет равной i = 2. Снова будет отработано его тело, т. е. цикл 5­7. При этом будет  найдена уже сумма отрицательных элементов первых двух строк массива, а в К  сохранится количество этих элементов. Когда выполнится весь наружный цикл, в S будет  константа, равная сумме отрицательных элементов всего массива, а в К – их количество.  Теперь управление перейдет к блоку 8. Если окажется, что в массиве есть отрицательные  элементы (К>0), то в блоке 9 вычисляется среднее арифметическое как отношение суммы элементов к их количеству. Результат помещается а ту же переменную S. Отметим, что  если бы блок 8 проверки отсутствовал, то при К = 0 (в массиве нет ни одного  отрицательного элемента) в блоке 9 из­за деления на нуль возникла бы ошибка. Эта  ошибка повлекла бы аварийное завершение вычислений до окончания работы алгоритма. Далее выполняется блоки 10­11, которые также образует цикл. В нем производится  замена элементов побочной диагонали на среднее арифметическое S (побочной  диагональю является прямолинейная цепочка ячеек в диапазоне от нижнего левого угла  до верхнего правого угла массива). Обратите внимание, на то что переменная i, которая  использовалась ранее, в целях экономии памяти применяется вновь. Проследим работу этого цикла. После входа в блок 10 счетчик примет значение i = 1.  Затем в блоке 11 при этом значении будет вычислен индекс столбца элемента N – 1 + i =  N. Таким образом, элемент с индексами (1, N) станет равным S. На втором круге цикла i  увеличится на 1 и станет i = 2. Нетрудно видеть, что теперь элемент (2, N­1) станет  равным S и т. д. На последнем круге цикла элемент (N, 1) получит значение S, что  завершит изменение значений всех элементов побочной диагонали на среднее  арифметическое S. Наконец, в блоке 12 измененный массив будет выведен и в блоке 13 алгоритм закончит  работу. 9. Вспомогательные алгоритмы Вспомогательный алгоритм является аналогом языковой подпрограммы. Он имеет имя и  может иметь параметры, которые называются формальными параметрами . Имя служит  для того. чтобы отличить его от других алгоритмов, а формальные параметры, которые  напоминают переменные математических функций, выполняют роль входных и выходных  параметров. Формальные параметры должны быть выбраны таким образом, чтобы ими был исчерпан  весь набор необходимых входных и выходных величин. Нередко один и тот же параметр  может оказаться входным и выходным одновременно. Например, на вход такого  алгоритма может быть подан массив для обработки, а на выходе процедуры он может  предстать в измененном виде как выходной параметр. Среди вспомогательных алгоритмов различают процедуры и функции .                                                                                                                                                                                                Рис. 11. Процедура Warn Первый блок схемы рис. 11 в отличие от ранее рассмотренных примеров, где этот блок  имел наименование “Начало”, включает имя процедуры Warn и один формальный  параметр i. С помощью этого имени в алгоритме рис. 12 выполняется обращение именно к этой процедуре. Из схемы видно, что если на вход процедуры Warn подать i = 0, то она в блоке 3 выдаст  сообщение "Введите данные". При любом другом i будет выведено сообщение "Конец  расчетов". Этим исчерпываются возможности процедура Warn. На рис. 12 дана схема головного алгоритма ( первый блок имеет наименование "Начало" ). Этот алгоритм в блоках 2 и 8 обращается к процедуре Warn. Опишем последовательность и механизм обработки данных, которые предписаны  алгоритмами рис. 11 и 12. Рис. 12. Головной алгоритм Выполнение алгоритмических действий всегда начинаются с головного алгоритма.  Поэтому сначала будет выполнен блок 1 схемы рис. 12. Далее в блоке 2 головной  алгоритм выполняет обращение к процедуре Warn при конкретном значении ее аргумента  (0). Это конкретное значение называется фактическим параметром процедуры. Теперь управление временно переходит в алгоритм рис. 11 процедуры Warn. Здесь и  далее по всей процедуре Warn формальный параметр i заменяется на фактический  параметр 0 (нуль) всюду, где он встречается. Далее обрабатывается блок 2 процедуры, где с учетом сказанного проверяется условие 0  = 0. Результатом проверки станет перевод управления к блоку 3, в котором выводится  сообщение "Введите данные". На этом   процедура заканчивается и управление вновь  передается в головной алгоритм к блоку 3. Далее в блоках 3­5 алгоритма рис. 12 выполняются уже понятные действия по вводу,  суммированию и выводу переменных. Затем управление передается в блок б, который  содержит новое обращение к процедуре Warn с фактическим параметром 1. Снова управление переключается на схему рис. 11, где вместо формального параметра i  всюду записывается фактический параметр – константа 1. Поскольку в блоке 2 условие 1  = 0 не выполнится, то будет выполнен блок 4 и алгоритм выведет сообщение "Конец  расчетов". После этого управление возвращается в головной алгоритм к блоку 7, где и  будет окончательно завершен алгоритмический процесс. Внешне такой процесс может выглядеть примерно так. На экран выводится сообщение  "Введите данные" и компьютер переходит в режим ожидания ввода двух констант с клавиатуры. Затем после их ввода на экране появляется три константы и надпись "Конец  работы". На первый взгляд может показаться, что процедуры лишь усложняют решение  задачи. Действительно, рассмотренную здесь задачу проще решить одним алгоритмом, не  прибегая к составление процедуры. Однако при составлении алгоритма решения сложной  задачи очень быстро становится ясно, что без использования процедур обойтись просто  невозможно. На практике при решением серьезных алгоритмических задач часто одному  программисту не под силу выполнить весь объем работ. Поэтому над ее решением  работает обычно коллектив программистов под руководством координатора. Образно  говоря, координатор здесь работает как головной алгоритм, а его программисты как  процедуры. При этом каждый программист (часто независимо от других) получает от  координатора задание по составление процедур определенного назначения. В результате  такой организации работы задача получает разрешение. 10. Декомпозиция алгоритма Под декомпозицией алгоритма понимают разложение его o6щeй алгоритмической схемы  на вспомогательные алгоритмы (процедуры и функции) и головной алгоритм. Напомним,  такая задача ставится перед студентом при выполнении курсовой или контрольной  работы. Одним из условий, которое должно быть обязательно выполнено, является  наличие в работе хотя бы одной процедуры или функции (кроме того, работа должна  содержать текст описания всех процедур и головного алгоритма). Метод, при помощи которого обычно выполняется декомпозиция, достаточно прост.  Сначала вычленяют основные этапы предстоящей работы. Наиболее сложные этапы  оформляет в процедуры или функции верхнего уровня. Затем, если необходимо, такие  этапы делят на этапы более низкого уровня. Наиболее сложные из них также оформляют  процедурами или функциями и т. д. Следуя методу "от сложного к простому", в конечном итоге достигают решения поставленной задачи. Приведем пример декомпозиции для  решения задачи сортировки массива. Эта задача была решена ранее в разд. 8 (рис. 9) без  использования вспомогательных алгоритмов. Решение задачи декомпозиции состоит из  трех основных этапов: 1) ввода данных, 2) сортировки массива и 3) вывода  отсортированного массива. Первый и третий этапы вследствие их простоты не нуждаются в дальнейшей декомпозиции, поэтому выполняются в головном алгоритме. Второй этап  представляет достаточно сложный и самостоятельный фрагмент вычислений, поэтому его целесообразно выделить в отдельную процедуру, которой можно дать имя Sort. Этап сортировки, в свои очередь, состоит из двух этапов: 1) установления необходимости сортировки и (N–1) – кратного прохода по массиву и 2) нахождения наименьшего  элемента во фрагменте массива и перестановки этого элемента с начальным элементом  фрагмента. Поскольку последний этап многократно повторяется при выполнении первого этапа, то его можно оформить в отдельную процедуру. Этой процедуре можно дать имя  Tra (от английского transposition – перестановка). Блок­схемы головного алгоритма,  процедуры Sort и процедуры Тrа показаны на рис. 13­15 соответственно.                                                                                                                                                            Рис. 13. Головной алгоритм       Рис. 14.  Процедура Sort Дадим краткое, описание взаимодействия этих алгоритмов в ходе решения задачи  сортировки.                                                                                                                                                                                                            Рис. 15. Процедура Tra Выполнение начинается с головного алгоритма (рис. 13). В блоке 2 вводятся исходные  данные, затем в блоке 3 выполняется сортировка массива. В блоке 4 отсортированный массив выводится и алгоритм заканчивает работу. Сортировка массива в блоке 3  головного алгоритма выполняется обращением к процедуре Sort, показанной на рис. 14.  Переменные A и N являются фактическими параметрами, Переменные А и N, которые  использованы в блок­схеме алгоритма Sort, является формальными параметрами. При обращении к процедуре Sort на вход подаются параметры A и N. В результате в теле  процедуры производится замена формального параметра R на фактический параметр A,  аналогично формальный K заменяется на фактический N. Далее в блоке 2 проверяется необходимость сортировки массива R. Затем, если такая  необходимость будет установлена, в цикле 3­4 будет выполняется сортировка массива.  При всяком значении счетчика цикла в его теле производится нахождение наименьшего  элемента фрагмента и его перестановка с начальным элементом этого фрагмента. Эти  операции выполняются отдельно с помощью процедуры Tra. Как видно из рис. 15, на вход  процедуры Tra нужно подать имя массива (A), количество элементов (N) и номер  элемента (i), которым начинается фрагмент. В теле процедуры в блоках 2­5 отыскивается  наименьший элемент фрагмента (v) и его номер (k). Затем в блоке 6 выполняется  вышеназванная перестановка элементов. Таким образом, весь процесс управляется головным алгоритмом, который выполняет  сортировку посредством обращения к вспомогательному алгоритму – процедуре Sort. Тот, реализуя решение своей задачи, в своя очередь несколько раз вымывает еще более  простой вспомогательный алгоритм процедуру Tra. В результате такого взаимодействия  достигается решение задачи в целом. В заключение приведем пример алгоритма­функции . Она похожа на процедуру, но в  отличие от последней должна в теле алгоритма еще содержать команду присваивания  результата имени функции , т. к. результат после вычислений сохранится в переменной,  представленной именем функции. Рассмотрим задачу вычисления факториала числа N! = 1 . 2 . 3 . . . N. Результатом будет  одно число, поэтому лучше алгоритм оформить в виде функции. Рис. 16. Функция Fact Ее блок­схема показана на рис. 16. Переменная К используется для накопления  произведения и, поскольку 0! = 1 и1! = 1, то в блоке 2 ей сразу присваивается значение 1.  Далее, если N>1, то в цикле, образованном блоками 4­5, накапливается искомое  произведение и помещается в переменную К. В блоке 6 имя Fact функции получает  значение вычисленного произведения из ячейки К. Для процедур действия, размещенного  в блоке 6, не может быть, а для функций оно должно быть обязательно, поскольку иначе  значение функции на выходе окажется неопределенным. Обращение к функции в других алгоритмах (головных, процедурах, функциях)  производится по ее имени. При этом оно может входить в состав выражений. В качестве фактических параметров  могут быть использованы как переменные, константы, так и целые выражения. Важно  только, чтобы фактический параметр был совместим по типу с формальным, который  содержится в заголовке описания алгоритма.   Пример использования функции Fact показан на рис. 17. В операторе присваивания  используется обращение к функции для N = 6. После передачи этого значения в алгоритм  рис. 16 и   вычислений внутри него результат будет сначала присвоен имени функции, т. е. переменной Fact, а затем в операторе присваивания ­ переменной L. Рис. 17. Обращение к функции Fact