Алгоритмы


Виды алгоритмов

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

          Итак, рассмотрим три основных типа алгоритмов, которые используются при написании программ.

  1. Линейный алгоритм, в котором действия производятся в строгом порядке, одно за другим, без возможных отклонений.
  2. Разветвляющийся алгоритм (ветвление). В нём присутствуют несколько авриантов последующего выполнения - в зависимости от выполнения или невыполнения определённого условия. Пример из жизни - мы подошли к перекрёстку, смотрим на светофор и думаем: "Ага, если красный цвет - стою, зелёный - пойду". Затем делаем что-то одно - стоим или идём.
  3. Циклический алгоритм (цикл) содержит повторяющиеся действия, опять же, в зависимости от условия. При чём величина, которая постоянно изменяется при выполнении цикла, называется параметром. И опять же - пример из жизни. Кто-нибудь загадал загадку и хочет, чтобы Вы решили её с трёх попыток. Вы решаете её до тех пор, пока не решите или все три попытки не кончатся. Вот так.
          Теперь рассмотрим каждый вид алгоритма подробнее.

Вверх


Линейные алгоритмы

          В общем, мы уже готовы для написания линейных алгоритмов. Пока что других видов мы просто не знали и, тем более, не могли написать программ с этими видами - только линейные, только строго определённые действия. Нам уже известно, как запросить имя пользователя после очистки экрана (если не известно, советую перечитать прошлый раздел), запросить у него необходимые данные, и, после определённых вычислений, вывести строго определённые результаты на экран. Ничего сложного, поупражняйтесь. Если Вы ещё не усвоили что-нибудь, то просто перечитайте темы, которые не поняли, только при полном понимании предыдущих тем, читайте дальше!

Вверх


Ветвление

          Что такое ветвление, думаю, вы уже поняли - я разъяснил это в позапрошлой теме. Ветвление в алгоритме и программе осуществляется двумя способами:
  • на основе безусловного перехода;
  • на основе условного перехода.
          Начнём с первого.

Вверх


Безусловный переход

          Безусловный переход осуществляется операторами GOTO и GotoLabel. При выполнении этих операторов, интерпритаторы начнут выполнение программы уже с заданной строки, номер которой указан в них. В бейсике метки ставятся либо перед строками программы (разделяются от операторов пробелами или символами ":"), либо на отдельных строках опять же перед строками (хотя удобнее ставить непосредственно перед строкой). В паскале каждую метку надо описывать. Делается это в Var'е - пишется "Label ", и, через запятую, перечисляются все номера возможных меток (описать можно до 9999 меток, а использовать ни одной, так что лучше описывать только те метки ,которые наверняка будут использованы в программе). Рассмотрим примеры простейших программ, которые будут выводить на экран символы "*" - бесконечно (чтобы выйти из бесконечного цикла, просто нажмите сочетание Ctrl+Break - это, кстати, принудительное завершение программы).

          Некоторое отступление от темы. Эти примеры наглядно показывают, насколько бейсик отличается от паскаля объёмом программ. Насколько я помню, паскаль был создан гораздо раньше бейсика, поэтому бейсик был как бы упрощённой его версией. Однако, люди, знающие паскаль хорошо и имеющие хоть немного представления о бейсике, утверждают, что бейсик создан для ленивых людей. Конечно, лучше знать оба языка, а на каком из них вам писать программы (хотя бы на начальном уровне своей "карьеры программиста"). Для изучения обоих языков я и пишу этот самый учебник.

          Так вот. На этих примерах показаны программы заполнения экрана сплошь звёздами "*". Сначала программа пишет один символ, оставляя курсно на данной строке. Затем, переходя на следующую строку, переходит на эту же строку с печатью символа "*" и печатает его за предыдущем и так далее. Замечу, что когда строка заканчивается, то ничто не заставит курсор остаться на этой строке - он неизбежно перейдёт на следующую строку.

          Строго говоря, серьёзное программирование "не любит" операторы безусловного перехода, так как считается, что они запутывают программу, циклируют её, часто просто приводят к зависанию компьютера. Вообще, лучше пользоваться условным переходом. Безусловным желательно прользоваться только в тех случаях, когда метка, на которую ссылается оператор, стоит после этого оператора, тогда при выполнении следующих строк программы, интерпритатор снова не наткнётся на эту строку со ссылкой на ту же метку, и не будет бесконечного цикла. Ладно, теперь поговорим об условном переходе.

Вверх


Условный переход

          Условный переход, как я уже сказал, предполагает выполнение или невыполнение какого-либо условия и выполнения определённых операторов относительно возникшей ситуацией с условием. В паскале и бейсике к тому же существуют несколько конструкция для выполнения условного перехода. Начнём с классической конструкции. Это IF ... THEN ... ELSE - говоря по-русски, ЕСЛИ ... ТО ... ИНАЧЕ.

!

В паскале блок операторов, который идёт после условия, естественно сдвигается на ступень вправо и выделяется логическими скобками Begin и End; (End именно с точной с запятой). Это делается в блоке операторов при выполнении условия и в блоке его невыполнения (Else - Иначе). Если же там или там оператор только один (под фразой "один оператор" подразумевается и одна строка, и оператор условия, содержащий много строк, и циклы и т.п.), то ставть Begin и End; не надо. В бейсике всё так же, только начальной логической скобки ставить не надо, а конечную заменяет слово ENDIF.

          В записи условия можно использовать следующие символы:

  • = (равно);
  • > (больше);
  • < (меньше);
  • <> или >< (не равно);
  • <= или =< (меньше или равно);
  • >= или => (больше или равно);
          По идее, всё должно быть понятно уже на этой стадии объяснения из самой конструкции оператора условия. Рассмотрим оператор условного перехода на конкретной задаче. Допустим, в одной стране, где люди говорят только правду. Для продажи сигарет стоит автомат, который запрашивает возраст покупателя и выдаёт разный результат в зависимости от введённого возраста. Прогаммы будут выглядеть следующим образом:
          Элементарная программка - мы вводим число (как бы возраст), и интерпритатор выводит первую фразу если это число меньше 18, иначе - вторую. Понятно? Дальше. Конструкция, которая была только что представляла полную форму условоного оператора, то есть одно из условий будет выпоняться при любом введённом значении (исключения составляют слишком большие числа. Если мы введём очень большое число, программа даст нам об этом знать и завершит работу. Но, это из другого раздела). Вот конструкция неполного оператора условия: IF ... THEN ... - всё. Нет ветви "ИНАЧЕ", поэтому если условие выполняться не будет, то интерпритатор просто "пройдёт мимо" оператора условия, не выполняя абсолютно ничего из блока операторов в теле оператора условия. Думаю, понятно. Кстати, если поставить оператор END в блоке операторов какого-либо условия, то программа выполнит все операторы до него и закончит работу независимо от следующих строк. Вообще, можно писать этот оператор в конце программы бейсика, а можно не писать. Я, например, пишу его всегда. Ах да, если что, то отступы вправо в этих примерах - это не операторы (конечно же!), а просто та же строка, то есть оператор IF заисан в одну строку с операторами вывода фраз, а также с THEN и ELSE, само собою.

!

В бейсике для безусловного перехода в условии можно писать так: IF K>=N THEN 2 (то же самое, что и IF K>=N THEN GOTO 2).

Вверх


Сложные условия

          Например, нам нужно одновременное выполнение несколькоих условий. Что делать? Конечно, можно открыть оператор словия с первым условием в операторе условия со строым условием в операторе условия... А можно поступить экономнее. В таких случаях несколько условий объединяются логическими связками "И" или "ИЛИ". Разберёмя с каждым. "И" (AND) означает, что два условия, объёдинённые связкой, строго должны выполняться - если хоть одно не выполняется, то всё - не катит. (: А вот связка "ИЛИ" (OR) выполняет последующие операторы, если выполняется хотя бы одно условие из тех, которые связаны ею. Конечно, несколько условий можно связывать несколькими связками сразу. Рассмотрим конструкции условных операторов (заодно с исаользованием блоков операторов). Слово "условие" я запишу как просто У.

          В первом случае использована связка "И", во втором - "ИЛИ". То есть в первом должны выполниться все два условия, во втором хотя бы одно. Условия, кстати, можно заключать в скобки.

Вверх


Дополнительные ветви

          Если сложное условие действительно сложное, то ветвление с дополнительными ветвями - ещё сложнее. (: А поскольку это не так уж и сложно (на самом деле), то приступим. Допустим, нам надо в одном операторе условия выполнить несколько блоков операторов, каждый из которых будет выполняться в зависимости от условий. Допустим, у нас есть четыре варианта действий, каждый из которых пронумерован от 1 до 4; надо ввести номер, а програама чтобы выполнила некоторые действия относительно этого номера. Что делаем? А делаем мы вот что: добавляем ещё одно определение для оператора условия. Это - ELSEIF (или ELSE IF. Просто если написать ELSEIF, то бейсик разделит это на два слова - ELSE и IF). Это в бейсике, а в паскале такого нет - там надо будет открывать новый оператор условия по ветви "ИНАЧЕ" для каждого нового условия. Замечу, что ELSEIF пишется ТОЛЬКО на новой строке. После него указывается новое условие, а затем идёт блок операторов. Итак, общая конструкция Условного оператора с дополнительными ветвями условий - это IF ... THEN ... ELSEIF ... ELSEIF ... ELSEIF (сколько угодно ELSEIF) ... ELSE ... - строка длинная, а запомнить несложно. Смотрим, как это осуществляется в бейсике:

          Существует также альтернативное ветвление. О нём и поговорим.

Вверх


Альтернативное ветвление (оператор выбора)

          У альтернативного ветвления функции те же, что и у обычного ветвления, просто оно сразу расчитано на большое количество ветвей. Операторы SELECT CASE и просто Case записываются следующим образом:

          "Список выражений" в первом случае - это все условия со связками, при выполнении которых будет осуществляться блок операторов. Во втором случае - У1 и У2 (условия 1 и 2) - это те же самые списки выражений. В условиях (SELECT CASE в бейсике) можно писать следующее:

  • выражение[, выражение, выражение]... (перечисление вариантов);
  • выражение TO выражение (если число находится в диапозоне от ... до ...);
  • IS оператор_отношения выражение (отношение - если число больше/меньше/больше либо равно/меньше либо равно другому числу).
          Очень важно! слово "TO" означает не ELSE, а именно "до". Ладно, выбирайте сами, каким способом ветвления Вам пользоваться. Тперь перейдём к циклам.

Вверх


Циклы: Счётчик

          Допустим, нам надо выполнить какое-то действие (или блок действий) определённое количество раз. Для этого понадобится счётчик FOR ... NEXT. Правила использования этого самого счётчика:
  • Рассмотреть повторяющиеся действия и выделить в них равномерно изменяющуюся величину (параметр);
  • Дать параметру имя;
  • Определить начальное и конечное значения параметра, а также шаг изменения параметра - насколько параметр будет изменяться при запуске нового витка цикла.
  • Написать оператор цикла, который состоит из трёх частей:
    • FOR параметр=начальное_значение TO конечное значение STEP шаг
    • тело цикла (в нём указывается блок операторов для циклического повторения)
    • NEXT параметр
          Это была конструкция для бейсика. Кстати, если шаг равен 1, то STEP 1 можно не писать. Также можно указать начальное и конечное значения, обозначив их переменными. Для паскаля всё немножечко по-другому. Давайте посмторим - нектороые пункты останутся неизменными:
  • For параметр:=начальное_значение To конечное значение Do
  • тело цикла (как было говорено уже не рас, может быть в логических скобках)
  • Если выполняется не один параметр, то End;
          Давайте разберёмся. Ну, во-первых, после параметра ставится не "=", а ":=", затем обязательно слово Do. Дальше всё по правилам заключения блока операторов в скобки. Примеры мы рассмотрим после изучения всех видов циклов. Кстати, в паскале понятия "шаг" вообще не существует. В таком случае, если шаг не равен единице, то его следует изменять в теле цикла. Например, если параметр i следует изменять не на 1, а на 3, то в тело цикла следует вписать строку "i:=i+2;", а если на -30, то строчку "i=i-31;". Также цикл счётчика может содержать в своём теле другой цикл счётчика, и это означает, что при изменении первого параметра, который описыватся в первом цикле, каждый раз от начала до конца будет выполняться вложенный цикл. Подробнее рассмотрим этот случай в разделе "Двумерные массивы".

Вверх


Циклы: Счётчик с неизвестным количеством повторений

          "А ведь иногда бывает так, что неизвестно, сколько раз надо повторять действия до достижения какого-либо результата" - скажете Вы. А я возьму и отвечу: "Ерунда! Используем цикл "ПОКА"!". Выглядит этот цикл так: WHILE ... WEND. Этот оператор сочетает свойства условного оператора и оператора цикла. С помощью этого оператора можно выполнять действия с заранее нееихвестным количеством повторений. Работает оператор так: сначала проверяется условие "ПОКА" (пока это условие истинно, выполнять...), затем в зависимости от этого условия выполняются или не выполняются действия в теле оператора, а затем идёт ключевое слово WEND, которое аналогично слову NEXT в уикле счётчика. Если условие истинно, то, после выполнения операторов внутри цикла, программа заново проверяет условие, затем если оно опять верно, опять выполняет операторы, и т.д. Когда же условие не истинно (ложно), то повторение прекращается и программа идёт дальше. Опять же, правила использования этого цикла:
  • Рассмотреть повторяющиеся действия и выделить в них изменяющуюся величину (параметр);
  • Определить условие выполнения цикла;
  • Написать оператор цикла, который состоит из трёх частей:
    • WHILE условие (так же, как и в операторе условия IF)
    • тело цикла (в нём указывается блок операторов для циклического повторения) с изменяющимся параметром
    • WEND
          В паскале всё пишется потти так же - "While ... Do Begin ... End;" - после While пишется условие, затем после Begin - тело цикла. Кстати, ключевое слово Do определяет конец условия цикла и начало выполнения его тела. Понятно? Примеры цикла будут потом, давайте сначала разберём все виды циклов.

Вверх


Циклы: DO ... LOOP, Repeat

          Цикл DO ... LOOP в общем похож на оператор WHILE, только его отличие состоит в том, что условие можно записывать в конце тела цикла - в таком случае его тело будет выполняться хотя бы один раз как минимум. Итак, в бейсике возможно четыре (!) варианта написания этого оператора цикла:
  1. DO UNTIL условие тело_цикла LOOP
  2. DO WHILE условие тело_цикла LOOP
  3. DO тело_цикла LOOP UNTIL условие
  4. DO тело_цикла LOOP WHILE условие
          Точнее, первые два варианта будут выполнять тело цикла только при истинности выполнения условия - могут и вообще не выполнять. А вторые два варианта, как я уже сказал, будут выполнять тело цикла как минимум один раз. При чём ключевое слово WHILE означает, что тело цикла будет выполняться только в случае истинности выражения, а UNTIL - наоборот, когда условие ложно.

          Теперь оператор Repeat. Он делает то же, что и третья и четвёртая строки. Пишется так: Repeat ... Until ... - вообще, странноватый оператор. Нетипичный для циклов, я бы так сказал. Во-первых, нет ключевого слова Do, во-вторых, в любом случае не ставятся Begin и End;! Интересно... Ну, ладно. Перейдём к конструкциям, которых все так ждали.

Вверх


Циклы: Конструкции

          Вот таблица конструкций всех рассмотренных циклов.

Циклы
Бейсик
Паскаль
Счётчик
FOR переменная=нач.зн TO кон.зн.
тело_цикла NEXT переменная
For переменная:=нач.зн. To кон.зн.
Begin тело_цикла End;
С неизвестным
количеством
повторений
WHILE условие
тело_цикла
WEND
While условие Do
Begin тело_цикла End;
DO...LOOP
Repeat
  1. DO UNTIL условие тело_цикла LOOP
  2. DO WHILE условие тело_цикла LOOP
  3. DO тело_цикла LOOP UNTIL условие
  4. DO тело_цикла LOOP WHILE условие
Repeat
тело_цикла
Until условие;

          Итак, наконец-то мы закончили со вторым разделом. Смело - в следующий раздел!

Перейти к решению задач
Вверх
Hosted by uCoz