Что такое алгоритм?! Часть первая
Терзаем вместе основной кирпичик программиста — Алгоритм.
Проблема
Текущее состояние в области программирования — это обучение ремеслу по большей части личной практикой или разборами примеров стороннего кода, с которым по каким-то причинам приходится сталкиваться.
В результате программированию учишься по наитию. Лишь немного в этом труде помогают сборники алгоритмов, прикладных техник и шаблонов проектирования. Общая совокупность предлагаемых ими рецептов выстраивается длинным списком, и его длина грозит каждому из прочитанных приемов быть позабытым (как была забыта 53-яя личная группа в «телеге» до введения разбиения по каталогам). Но даже тот прием, который остался в памяти, чаще всего просто является описанием прикладной задачи, в которой было успешно его использование.
Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?
В личном опыте существования в профессии не раз отмечено, что каждый Junior борется с одинаковыми ветряными мельницами и постигает методы создания программ основываясь только на своих ошибках. Но ведь такие ошибки совершили уже очень многие. Почему до сих пор не создана система правил программирования, которая поможет обойти новоиспеченному кораблю-программисту подводные прибрежные камни? Ну, например, объяснение вреда использования метода «Copy-Paste» для развития кода. Если такие правила получится объяснить малым набором причин, их сформировавшим, то это объяснение обеспечит их запоминание и последующее использование в практике, тем самым поможет уклониться от бесчисленных грабель, разложенных тут и там.
Для компактного и полезного набора объяснений нужно:
Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.
Задуманная серия статей не претендует на полное решение указанной проблемы. Предпринимается небесспорная попытка сделать первый шаг на пути к этому решению. Этот шаг состоит в выделении структуры и свойств главного кирпичика программиста — Алгоритма.
Задача
Сформулируем основную задачу, которую хочется решить. Для этого сначала запишем операции над алгоритмами, которые программист выполняет в ходе написания своего проекта:
Рассмотрим существующие на текущий момент варианты значения слова «алгоритм» в поисках подсказок, о том как можно работать с алгоритмами.
Так, например, формулировка «конечная совокупность точно заданных правил решения произвольного класса задач» говорит что есть возможность как-то «точно задать правила» из них собрать «совокупность» и этой совокупностью «решить» некоторый «класс задач».
Сразу возникает масса вопросов к этому определению:
Другая формулировка «набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи» говорит что есть «исполнитель», который может выполнять некоторые «действия», и при некотором «порядке» выполнения этих «действий» «решается задача». Вопросов не стало меньше:
Перечислено много вопросов, но они мало помогают в поиске методов работы с алгоритмом. Поэтому поставим себе меньшую задачу, но тоже очень нам важную. Давайте попробуем сформулировать, что делает алгоритм способом решения наших задач, и какие процессы являются для него «действиями». Даже решение этой «маленькой» задачи оказывается очень объемным для одной статьи, поэтому будем его разбивать на части. И поэтому первую статью серии целиком посвятим только «Действию» и его признакам, которые опущены в указанных выше определениях алгоритма, но являются очень важными для ответов на все заданные вопросы.
Определение алгоритма
Рассмотрим определение алгоритма, говорящее, что он — приводящая к решению задачи последовательность действий. Как программисту мне приходится писать много кода. Этот код состоит из частей. Такими частями являются и функции, и классы, и модули. Когда я пишу текст функции — я занимаюсь написанием алгоритма.
Раньше алгоритм создавали в виде блок схем и полуавтоматически компилировали в машинные коды. Сейчас я избавлен от необходимости быть художником и компилятором для написания программы. Текст моей функции — это запись алгоритма в текстовом виде — его текстовая блок-схема. Здесь можно вспомнить Scratch, где используется визуальное создание блок-схемы алгоритма без написания текста. Способ записи алгоритма сейчас не так важен.
Важно, что в написании алгоритма функции я могу использовать вызовы других функции, которые я или другой программист уже написал до этого момента. Вспоминая фразу «последовательность действий, приводящая к решению задачи», можно отметить, что функции, написанные ранее, являются моими «действиями». То есть «действия» могут быть функциями. Если обобщать, то «действия» могут быть алгоритмами.
Если «действие = алгоритм», то определение можно попробовать переписать рекурсивно «алгоритм — это приводящая к решению задачи последовательность использования существующих алгоритмов». Рекурсивные определение не самое простое, что можно записать в словаре обычного человека. Но для программиста и математика эта форма знакома. Мы умеем с ней работать, и это даёт нам преимущество в рассмотрении разных задач, разбиваемых на подобные себе подзадачи. Так давайте воспользуемся этим преимуществом.
Чтобы разрешить рекурсию нам необходимо найти:
Действие
Для начала рассмотрим «действие» и попробуем найти причину, обеспечивающую возможность использования существующего «действия» для создания нового алгоритма.
Этой причиной является возможность повторного использования «действия» с получением тождественного результата. Только тогда разработанный с использованием этого «действия» алгоритм решения некоторой задачи будет одинаково решать эту задачу снова и снова. Мы нащупали важные законы нашего мира, в котором:
Какие признаки «действия» кроме повторимости делают возможным его использование в создании алгоритма? Что является терминальным неделимым «действием»? Чтобы ответить на этот вопрос стоит рассмотреть разные примеры «действий» из нашего опыта. Программисты встречали их много раз. Это и сложение, и умножение, и установка цвета пикселя на экране. Но мы знакомы с ними и вне программирования. Вся наука основывается на повторяемых явлениях.
Закон гравитации, описывающий повторяющееся явление падения яблока, тоже может стать действием. Ведь любое яблоко будет падать на землю? Значит этот процесс можно использовать в качестве «действия»! Например решая задачу прогнать Ньютона от яблони, на которую Вы случайно забрались ранее.
Рассмотрим, что происходит при выполнении «действия». Например, во время падения яблока с ветки яблони на землю. В этом процессе происходит несколько изменений. Если вспомнить школьную физику и рассмотреть ситуацию в системе отсчета, привязанной к Земле, то сила гравитации вызывает изменение скорости яблока, разгоняя его. При этом в процессе отмечается еще одно важное изменение — уменьшается расстояние между яблоком и Землей.
В рамках примера процесса «Земля-Яблоко» можно отметить у «действия» следующие признаки:
Рассмотрим с этими признаками разные области и процессы, выделяя в них примеры «действий» и контролируя особенности указанных признаков в описании структуры «действия».
Физические процессы
Для физических систем, процессы которых мы наблюдаем в нашем мире, характерные объекты и изменения опираются на фундаментальные взаимодействия и потому их достаточно просто выделить по аналогии с гравитационным взаимодействием Земли и яблока. Например, для системы из протона и электрона или системы двух протонов.
Отдельно от этих простых взаимодействий двух объектов стоят многокомпонентные процессы, например, ядерные реакции (по структуре «действия» близки к химическим процессам, рассматриваемым далее). Сложны и процессы описываемые суммарным взаимодействием большого числа элементов, например, «идеальный газ». Пока отложим их рассмотрение и сосредоточимся на самых простых примерах.
Химические процессы
Перейдем к следующей большой области — химическим процессам. Химические реакции (например, 
) по признаку своей повторимости так же являются «действиями». Объектами в них являются атомы и молекулы. Для описания происходящих изменений необходимо немного преобразовать «физические» изменения. Так изменения параметров движения в совокупности дают нам изменение температуры в ходе химической реакции. А среди изменений расстояний между молекулами мы, игнорируя броуновское движение, можем выделить фиксацию расстояния в виде повторимого формирования и разрушения связей между частями взаимодействующих молекул. Локальность для химической реакции тоже существует — это отсутствие реакции при нахождении гидроксида натрия и соляной кислоты в разных пробирках и наличие реакции при соприкосновении веществ. Конечно, в «химической» области «действий» есть особенности не сводящиеся к молекулам, например, фотохимические реакции, где к объектам необходимо добавить фотоны. Самые простые процессы выбраны для рассмотрения намеренно.
Математические процессы
Следующей областью выберем «действия» из известных нам абстрактных алгоритмов. Самые яркие их представители — математические процессы. В этой области есть действительно «сложные случаи», но для этой статьи достаточно хорошо знакомых примеров. Рассмотрим в качестве «действия» достаточно элементарную операцию — сложение. А примером этого «действия» выберем сложение математиком двух целых чисел.
В ситуации с математиком можно выделить много объектов, но с точки зрения «действия» («сложение математиком двух целых чисел»), объекта всего три: это объект «математик», объект «первое число» и объект «второе число». В отличие от всех рассмотренных ранее объектов числа являются обозначениями, то есть виртуальными объектами. И их преобразование в алгоритме более сложно устроено нежели изменение расстояния и параметров движения объектов, как это было для «химических» действий. Подробности такого преобразования — это тема отдельной увлекательной статьи. А в рамках текущей рассмотрим древнего математика, который складывает числа, используя кучки камешков (рим. ‘calculi’), и более «современного» математика, использующего абак. Абстракции таких способов вычисления суммы не так далеко отошли от физических и химических процессов, поэтому структура процессов их «действий» полностью описывается изменениями расстояний и связей.
Интересно, что на примере древнего математика становится понятен смысл слова «сложить», которое отсылает нас к действию «класть» и к фразе «положить вместе».
Сложение и древний математик
Для математика, оперирующего камешками, сумма это «действие» со следующими характеристиками.
Сложение и математик-абакист
У математика с абаком ситуация сложнее. Кучки разделены по значению на разрядные борозды.
Можно рассмотреть самый простой абак с двумя разрядами-бороздами. Пусть он будет десятичный. Тогда один камешек на борозде десятков соответствует десяти камешкам на борозде единиц. И 10 — это максимальное количество камешков на борозде единиц. По сравнению с действием первого математика меняется представление слагаемых. И в арсенале математика уже необходимы нескольких готовых «действий».
Локальность в этих математических «действиях» описывается отсутствием взаимодействия двух слагаемых, находящихся далеко от математика, и запуском процессов сложения когда все три объекта сложения «близко». Повторяемое изменение в математическом «действии» выражается в изменении связей между камнями и удерживающими их локациями (кучками, бороздами).
Сложение и машина Тьюринга
Можно пойти чуть дальше и заменить математика в таких «действиях» на «управляющее устройство» машины Тьюринга. Тогда «ячейки ленты» машины Тьюринга будут содержать слагаемые.
При этом остаётся и признак локальности как возможность взаимодействия управляющего устройства только с текущей ячейкой ленты, и признак изменения параметров объектов, который можно описать как изменение состояния ячеек.
Подробное описание исходных и результирующих состояний объектов, а так же «действий» производящих эти изменения для сложения, исполняемого машиной Тьюринга, оставим за рамками этой статьи. Но упомянем, что перейдя к машине мы снижаем требования к исполнителю «действия», что является главным способом для создания формальных методов работы с алгоритмом. Можно поставить себе целью упрощение каждой составляющей алгоритма до состояния, когда её выполнение можно будет поручить компьютеру. Тогда в определении алгоритма не останется тёмных мест, и многочисленные вопросы, перечисленные в начале, найдут свои ответы. Пока формализован только исполнитель. Скажем спасибо за это Тьюрингу и вспомним про «действие», формализация которого уже на пороге.
Выводы
Соберём всё, что мы отметили рассматривая разные примеры «действия»:
Признак Повторимости помогает нам в создании наших алгоритмов. С его использованием мы из всех процессов выделяем те, что являются «действием» и на их основе создаём новые алгоритмы. Более того этот признак достаточно прост и на основе его формализации можно снизить требования к системе обнаруживающей и создающей «действия» и поручить это нашему компьютеру.
Следующая статья серии (Часть 2) будет посвящена рассмотрению способов, с использованием которых «действия» могут быть сгруппированы в алгоритм. Этих способов достаточно много и есть предпосылки, что их описание не получится уместить в одну статью. Напишем — увидим.
Спасибо Вам за внимание.
Отзывы
Буду очень благодарен за отзывы и предложения, так как они помогают мне скорректировать направление развития работы в области.
Отдельное волнение у меня есть по стилю и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.
Что такое алгоритм управления последовательность команд
Пособие представляют собой руководство по составлении алгоритмов, которые являются необходимой составной частью контрольной и курсовой работы по дисциплине «Информатика».
Изложенный материал не претендует на полноту охвата всех сторон проблемы алгоритмизации при решении задач, возникающих на практике. Однако его вполне достаточно для того, чтобы разобраться и выполнить ту часть названных работ, которая необходима для составления алгоритмов и их описания.
Опыт показывает, что трудности, возникающие при составлении алгоритмов имеют как общий характер, когда студент не может уяснить принцип работы алгоритма вообще, так и частный, когда непонятным оказывается отдельный фрагмент алгоритма.
В любом случае рекомендуем обратить внимание на следующее. Разбирая или составляя алгоритм, нужно мысленно представить некоторый автомат по обработке данных (компьютер), который будет выполнять действия, предписанные этим алгоритмом. Без такого представления невозможно понять сам алгоритм. Ниже, при разборе примеров, станет понятно, что такой мысленный автомат совсем несложен. Во всяком случае он несравнимо пpoщe реального компьютера, хотя общие принципы их функционирования в основном одинаковы. Допустимо (например, при составлении описания) отождествлять работу такого автомата с работой самого алгоритма.
При изучении материала особенно первоначальном, следует подробно разобраться в каждом алгоритме, начиная с самого первого и самого простого. Начинать нужно с полного уяснения пяти самых простых и самых необходимая понятий: константа, переменная, ячейка памяти, запись константы в ячейку памяти, чтение константы из ячейки памяти. Не пренебрегайте этими советами, так как очень скоро убедитесь, что при разборе следующего алгоритма обязательно натолкнетесь не только на те же трудности, но присовокупите к ним новые. Более того, нередко полное понимание даже самого простого алгоритма дает намного больше пользы, чем поверхностное изучение десятка алгоритмов повышенной сложности.
Алгоритм – это инструкция для автомата о том, в какой последовательности нужно выполнить действия при переработке исходного материала в требуемый результат.
Наряду с понятием алгоритма используют термин алгоритмизация, под которой понимают совокупность приемов и способов составления алгоритмов для решения алгоритмических задач.
Часто алгоритм используется не как инструкция для автомата, а как схема алгоритмического решения задачи. Это позволяет оценить эффективность предлагаемого способа решения, его результативность, исправить возможные ошибки, сравнить его еще до применения на компьютере с другими алгоритмами решения этой же задачи. Наконец, алгоритм является основой для составления программы, которую пишет программист на каком-либо языке программирования с тем, чтобы реализовать процесс обработки данных на компьютере.
Неотъемлемым свойством алгоритма является его результативность, то есть алгоритмическая инструкция лишь тогда может быть названа алгоритмом, когда при любом сочетании исходных данных она гарантирует, что через конечное число шагов будет обязательно получен результат.
На практике получили известность два способа изображения алгоритмов:
в виде пошагового словесного описания;
Первый из этих способов получил значительно меньшее распространение из-за его многословности и отсутствия наглядности.
Второй, напротив, оказался очень удобным средством изображения алгоритмов и получил широкое распространение в научной и учебной литературе. Именно этот способ будет использован ниже при составлении и описании алгоритмов.
Блок-схема – это совокупность блоков, предписывающих выполнение определенных операций, и связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению. Конфигурация и размеры блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации. СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ, ДАННЫХ И СИСТЕМ. Условные обозначения и правила выполнения» [1]. В табл. 1 приведены наиболее часто используемые блоки, изображены элементы связей между ними и дано краткое пояснение к ним. Блоки и элементы связей называют символами блок-схем. Представленных в таблице символов вполне достаточно для изображения алгоритмов, которые необходимы при выполнении студенческих работ.
Таблица 1
О тображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, алгоритма).
Вычислительное действие или последовательность вычислительных действий
Проверка условия
Нижняя граница
Предопределенный процесс
О тображает процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле)
О тображает данные, представленные на носителе в удобочитаемой форме.
Будет использоваться нами как символ вывода данных
О тображает данные, представленные на носителе в виде карты (перфокарты, магнитные карты и др.).
Будет использоваться нами как символ ввода данных
Может использоваться для ввода/вывода данных
Отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте
И спользуют для добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний
Линии горизонтальных и вертикальных потоков, предназначенные для связей между символами
Слияние линий потоков
Межстраничный соединитель
При соединении блоков следует использовать вертикальные и горизонтальные линии потоков.
Горизонтальные потоки, имеющие направление справа налево, и вертикальные потоки, имеющие направление снизу вверх, должны быть обязательно помечены стрелками. Прочие потоки могут быть помечены или оставлены непомеченными.
Желательно чтобы линии потоков были параллельны линиям внешней рамки или границам листа.
Рекомендуется расстояние между параллельными линиями потоков устанавливать кратным 5 мм.
Горизонтальный и вертикальный размеры блока рекомендуется назначать кратно 5-ти мм.
Для размещения блоков рекомендуется поле листа разбивать на горизонтальные и вертикальные (для разветвлявшихся схем) зоны.
Для удобства описания блок-схемы каждый ее блок следует пронумеровать. Удобно использовать сквозную нумерации блоков. Номер блока располагают в разрыве в левой верхней части рамки блока или над ним.
По характеру связей между блоками различают алгоритмы линейной, разветвляющейся и циклической структуры.
Примеры, пояснявшие изложенное, можно найти в блок-схемах алгоритмов, которые будут приведены ниже.
Для того чтобы ясно представить как «работает» алгоритм, опишем простейший автомат, который предназначен для выполнения операций, предписанных этим алгоритмом.
В состав такого автомата входят:
Головка, получив указание от процессора, может записывать в ячейку или считывать из нее одну константу.
В простейшем случае константой является любое арифметическое число. Например, 12, 0.78, 0, –45.33 и т. д. ( Константами могут быть такие строки символов, структуры данных и др.).
Переменные имеют буквенно-символьное обозначение. Например, 1, n, a, a1, b, H2 – переменные. Одновременно обозначение переменной является индексом ячейки, в которую будут записываться константы. Любая из таких констант называется значением переменной. Например, Z является переменной и адресом ячейки Z одновременно. С алгоритмической точки зрения понятия “ переменная ” и “ адрес ячейки ” памяти являются идентичными.
Запись вида L = M следует понимать так: прочитать константу, расположенную по адресу M и скопировать эту константу в ячейку с адресом L (при этом константа из ячейки M не удаляется, а остается такой, какой она была до чтения). Произносить эту запись нужно так: «переменной L присвоить значение переменной M (или просто : L присвоить M)».
Одномерный массив – это последовательность ячеек, расположенных в одну линию. На рис. 1 приведен пример такого массива.
Рис. 1. Одномерный массив q
Рис.2. Двумерный массив d
Аналогично устроена структура массивов трех- и большей размерности.
Линейный алгоритм – это алгоритм, в котором блоки выполняются последовательно сверху вниз от начала до конца.
На рис. 3 приведен пример блок-схемы алгоритма вычисления периметра Р и площади S квадрата со стороной длины A.
Как видно из рис.3, блок 1 связан вертикальной линией потока с блоком 2. Эта линия не имеет стрелки, указывавшей направление потока. Следовательно, этот поток направлен вниз. Таким образом, после выполнения блока 1 управление будет передано на блок 2. Блок 2 «Перфокарта» ( см. табл. 1) показывает, что переменной A следует присвоить значение. Это означает, что в ячейку, отведенную автоматом под эту переменную, нужно поместить константу. На реальной компьютере эта константа может быть введена самыми разными способами. Способ зависит от того, как запрограммирован данный фрагмент. Можно, например, потребовать ввод константы с клавиатура или получить его из заранее подготовленного файла. Возможно эта константа будет получена через внешние источники данных, например, от физической установки, подключенной к компьютеру.
Рис. 3. Линейный алгоритм
Для данного примера способ передачи константы не имеет значения, важно лишь то, что при выполнении блока 2 в ячейку с адресом А будет занесена конкретная константа. Пусть такой константой является число 5.
Далее управление по линии потока передается к блоку 3 «Процесс». В этом блоке при выполнении размещенной в ней команды число 4 умножается на константу, помещенную в ячейку А (т. е. 5), и результат (т. е. 20) присваивается переменной Р (т. е. константа 20 записывается в ячейку по адресу Р). После выполнения этих операций управление передается к блоку 4.
В блоке 4 аналогичным образом производится умножение значений переменной А и результат (константа 25) присваивается переменной S (в ячейку по адресу S будет занесена константа 25). После этого выполняется переход к блоку 5.
При выполнении команд блока 5 выводятся (например, на экран, бумагу, во внешний файл и т. д.) значения переменных А, Р, S, которые сохранились в соответствующих ячейках к этому моменту. Понятно, что для конкретного примера А = 5 будут выведена константы 5, 20, 25, т. е. длина сторона квадрата, его периметр и площадь. Далее управление передается последнему блоку 6.
Понятно, что при новом запуске этого же алгоритма можно получить совсем другие числа. Так, если в блоке 2 переменной А присвоить значение 20, то алгоритм выдаст в блоке 5 константы 20, 80, 400.
Детальное описание алгоритма рис. 3 приведено для того, чтобы показать, в какой последовательности автомат выполняет предписанные операции и как при этом меняется состояние памяти автомата, т. е. для того, чтобы объяснить суть происходящих в автомате процессов. Из сказанного нужно уяснить, что автомат выполняет предписанную ему работу шаг за шагом. Всякий шаг обрабатывается процессором. Помимо вычислений процессор при необходимости отдает команды считывавшей/записывавшей головке, что и куда записывать, откуда читать. Конечный результат следует искать в ячейках памяти, каждая из которых до окончания алгоритма имеет известный адрес и хранит записанную в нее константу.
При выполнении контрольной или курсовой работы нет нужды давать столь подробное описание алгоритма. Тем не менее, описание должно быть выполнено с той степенью полноты, которая позволяет дать ясное представление о всех сторонах и особенностях алгоритмического процесса.
На практике алгоритмы линейной структуры встречается крайне редко. Чаще необходимо организовать процесс, который в зависимости от каких-либо условий проходит по той либо иной ветви алгоритма. Такой алгоритм называется разветвляющимся.
В блок-схемах ветвление начинается на выходах символа «Решение», с помощью которого в алгоритме выполняется проверка какого-либо условия. Количество ветвей тем больше, чем больше проверяемых условий.
Для пояснения рассмотрим решение задачи нахождения значения функции z = y/x.
На первый взгляд представляется, что алгоритм решения этой задачи имеет линейную структуру. Однако, если учесть, что делить на нуль нельзя из-за переполнения ячейки, то, во-первых, нужно из вычислений исключить вариант х = 0 и, во-вторых, проинформировать пользователя алгоритма о возникшей ошибке. Если этого не сделать, то при вычислениях может возникнуть аварийный выход до получения результата. В профессиональной практике аварийные завершения крайне нежелательны. т. к. к этому моменту уже может быть накоплено определенное количество результатов, которые окажутся необработанными и попросту пропадут. Можно привести другие примеры, когда аварийный останов компьютера может повлечь куда более серьезные последствия.
Решение задачи представлено блок-схемой рис. 4.
Она состоит из 7 блоков. После начала работы алгоритм в блоке 2 требует ввода аргументов X и Y. Затем в блоке 3 производится проверка условия X = 0. Здесь автомат проверяет равна ли нули константа, введенная в ячейку с адресом X. Результатом такой проверки является ответ «Да» или «Нет». В зависимости от этого ответа выполнение алгоритма пойдет по одной или другой ветви. Если результат проверки окажется отрицательным, то на х можно делить и управление передается блоку 4.
В блоке 4 будет получен результат Z, затем в блоке б значения всех трех переменных будут отпечатаны и в блоке 7 алгоритм закончит работу. Если же ответ окажется положительным, то управление будет передано блоку 4. Выполняя команду блока 4, автомат выведет сообщение «Ошибка» и затем закончит работу в том же блоке 7.
Часто при решении задач приходится повторять выполнение операций по одним и тем же зависимостям при различных значениях входящих в них переменных и производить многократный проход по одним и тем же участкам алгоритма. Такие участки называются циклами. Алгоритмы, содержащие циклы, называется циклическими. Использование циклов существенно сокращает объем алгоритма.
Различают циклы с наперед известным и наперед неизвестным количеством проходов.
Блок-схема алгоритма решения этой задачи приведена на рис. 5. Она состоит из восьми блоков.
На рис. 6. показана структура цикла, которая может быть использована, когда условие выхода из цикла определяется символом его начала или символом его конца. Наряду с этим в качестве заголовка цикла может быть использован и символ «Подготовка». Структура такого цикла показана на рис. 7.
Пример 2. Теперь приведем пример алгоритма, содержащего цикл с наперед известным количеством проходов (повторений). Алгоритм решает задачу накопления суммы положительных элементов одномерного массива Z длины N (под длиной массива понимается количество его элементов).
Следует подчеркнуть, что если бы ввод этих переменных в блоке 2 производился в противоположном порядке, то это привело бы к ошибке. Действительно, невозможно заполнить N ячеек массива Z, когда значение переменной N еще не известно.
Далее в блоке 3 переменной S присвоено начальное значение 0. Это сделано для того, чтобы приготовить ячейку к накоплению необходимой суммы.
Рис. 8. Циклический алгоритм
Тест на алгоритм Министерства образования и науки РФ
Таким образом, выделенный блок выполнится при x = 2; y = 4; z = 1 (вариант 2 ).
Нередко при алгоритмическом решении задачи возникает необходимость создания цикла, содержащего в своем теле другой цикл. Такие вложенные друг в друга циклы относятся к структурам вложенных циклов. Порядок вложенности циклов, когда в теле внутреннего цикла содержатся другие циклы, может быть достаточно большим. Этот порядок определяется методом, с помощью которого достигается решение поставленной задачи. Так, при обработке одномерных массивов, как правило, удается построить алгоритмическую схему без вложения циклов. Однако в ряде случаев при решении таких задач без вложенных циклов не обойтись.
Отметим, что все вложенные друг в друга циклы, включая наружный, должны иметь счетчики с различными именами. Вне этих циклов счетчики могут быть использованы как обычные переменные или как счетчики других циклов.
Пример 1. Рассмотрим задачу нахождения наименьшего элемента в двумерном массиве Z размером 8 х 6 .
После завершения работы внутреннего цикла произойдет возврат к заголовку наружного цикла, где значение переменной i увеличится на 1 и станет равным i = 2. Затем вновь выполнится весь внутренний цикл, что соответствует проходу по всем элементам второй строки массива Z.
Таким образом, после завершения наружного цикла будет совершен проход по всем элементам массива и в переменной S будет находиться константа, равная значению наименьшего элемента массива Z.
В блоке 10 будет выведено это значение и затем в блоке 11 алгоритм закончит свою работу.
Рис. 9. Алгоритм нахождения наименьшего элемента в двумерном массиве
Вспомогательный алгоритм является аналогом компьютерной подпрограммы. Он имеет имя и может иметь параметры, которые называются формальными параметрами. Имя служит для того чтобы отличить такой алгоритм от других алгоритмов, а формальные параметры, которые напоминают переменные математических функций, выполняют роль входных и выходных параметров.
Формальные параметры должны быть выбраны таким образом, чтобы ими был исчерпан весь набор необходимых входных и выходных величин. Нередко один и тот же параметр может оказаться входным и выходным одновременно. Например, на вход такого алгоритма может быть подан массив для обработки, а на выходе процедуры он может предстать в измененном виде как выходной параметр.
С помощью этого имени в алгоритме рис. 11 выполняется обращение к этой процедуре. Параметры, которые при вызове алгоритма подставляют на место формальных, называются фактическими параметрами.
Из схемы рис. 11 видно, что если при обращении к процедуре Warn на ее вход подать i = 0, то она в блоке 3 выдаст сообщение «Введите данные». При любом другом i будет выведено сообщение «Конец расчетов». Этим исчерпываются возможности процедура Warn.
Рис. 10. Процедура Warn
На рис. 11 дана схема головного алгоритма (первый блок имеет наименование «Начало»). Этот алгоритм в блоках 2 и 8 обращается к процедуре Warn (вызывает ее). Опишем последовательность и механизм обработки данных, которые предписаны алгоритмами рис. 10 и 11.
Выполнение алгоритмических действий всегда начинаются с головного алгоритма. Поэтому сначала будет выполнен блок 1 схемы рис. 11. Далее в блоке 2 головной алгоритм выполняет обращение к процедуре Warn при конкретном значении ее аргумента (0).
Далее в блоках 3-5 алгоритма рис. 11 выполняются уже понятные действия по вводу, суммированию и выводу переменных. Затем управление передается в блок б, который содержит новое обращение к процедуре Warn с фактическим параметром 1.
Снова управление переключается на схему рис. 10, где вместо формального параметра i всюду записывается фактический параметр – константа 1. Поскольку в блоке 2 условие 1 = 0 не выполнится, то будет выполнен блок 4 и алгоритм выведет сообщение «Конец расчетов».
После этого управление возвращается в головной алгоритм к блоку 7, где и будет окончательно завершен алгоритмический процесс.
Рис. 11. Головной алгоритм
Внешне такой процесс может выглядеть примерно так.
На экран выводится сообщение «Введите данные» и компьютер переходит в режим ожидания ввода двух констант с клавиатуры. Затем после их ввода на экране появляется три константы и надпись «Конец работы».
На первый взгляд может показаться, что процедуры лишь усложняют решение задачи.
Действительно, рассмотренную здесь задачу проще решить одним алгоритмом, не прибегая к составление процедуры. Однако при составлении алгоритма решения сложной задачи очень быстро становится ясно, что без использования процедур обойтись просто невозможно. На практике при решением серьезных алгоритмических задач часто одному программисту не под силу выполнить весь объем работ. Поэтому над ее решением работает обычно коллектив программистов под руководством координатора. Образно говоря, координатор здесь работает как головной алгоритм, а его программисты как процедуры. При этом каждый программист (часто независимо от других) получает от координатора задание по составление процедур определенного назначения. В результате такой организации работы задача получает разрешение.
Под декомпозицией алгоритма понимают разложение его o 6щeй алгоритмической схемы на вспомогательные алгоритмы (процедуры и функции) и головной алгоритм. Напомним, такая задача ставится перед студентом при выполнении курсовой или контрольной работы. Одним из условий, которое должно быть обязательно выполнено, является наличие в работе хотя бы одной процедуры или функции (кроме того, работа должна содержать текст описания всех вспомогательных алгоритмов и головного алгоритма).
Метод, при помощи которого обычно выполняется декомпозиция, достаточно прост. Сначала вычленяют основные этапы предстоящей работы. Наиболее сложные этапы оформляют в виде вспомогательных алгоритмов верхнего уровня. Затем, если необходимо, такие этапы делят на этапы более низкого уровня. Наиболее сложные из них также оформляют вспомогательными алгоритмами и т. д. Следуя методу «от сложного к простому», в конечном итоге получают решение поставленной задачи.
Приведем пример декомпозиции для решения задачи сортировки массива в порядке возрастания его элементов.
Решение задачи декомпозиции состоит из трех основных этапов: 1) ввода данных, 2) сортировки массива и 3) вывода отсортированного массива. Первый и третий этапы вследствие их простоты не нуждаются в декомпозиции, поэтому выполняются в головном алгоритме. Второй этап представляет достаточно сложный и самостоятельный фрагмент алгоритмической работы, поэтому его целесообразно выделить в отдельную процедуру, которой можно дать имя Sort.
Выполним далее сортировку массива в порядке возрастания его элементов «методом пузырька». Этот метод достаточно прост. Сначала совершают проход по всем соседним парам элементов массива и в случае, если они не отсортированы, то значения элементов всякой такой пары меняют местами. Если была совершена хотя бы одна перестановка, то такую процедуру повторяют до тех пор, пока при проходе по массиву не будет совершено ни одной перестановки. В результате массив будет отсортирован.
После сортировки в блоке 4 головного алгоритма отсортированный массив будет выведен и в блоке 5 алгоритм закончит свою работу.
Рис. 12. Процедура Perm
Рис. 13. Процедура Sort
Рис. 14. Головной алгоритм
В заключение приведем пример алгоритма-функции. Она похожа на вспомогательный алгоритм-процедуру, но в отличие от последней должна в своем теле содержать команду присваивания результата имени функции, т. к. результат после вычислений сохранится в переменной, представленной именем функции.
Обращение к функции в других алгоритмах (головных, процедурах, функциях) производится по ее имени.
При этом оно может входить в состав выражений. В качестве фактических параметров могут быть использованы как переменные, константы, так и целые выражения. Важно только, чтобы фактический параметр был совместим по типу с формальным, который содержится в заголовке описания алгоритма.
Рис. 15. Функция Fact
Рис. 16. Обращение к функции Fact
Тест на вспомогательный алгоритм
Если обратиться к алгоритму
при помощи оператора
