Алгоритм и его свойства. Способы записи алгоритма

      Если  решение задачи сложное и достаточно длинное, то алгоритм может получиться очень большим. Избежать этого можно, заменив некоторую законченную последовательность шагов алгоритма блоками, которые будут являться вспомогательными алгоритмами. Блок обычно не элементарен, его размеры выбираются в зависимости от необходимости, однако если он правильно составлен, то обладает всеми необходимыми признаками алгоритмического шага: имеет точку входа (четко выделенное начало) и может быть условным или безусловным. Разные блоки алгоритма связаны друг с другом только через точки входа и выхода, поэтому если блок верно решает свою задачу, то его внутренняя структура несущественна для остальной части алгоритма. Такое блочное представление особенно удобно на первых этапах решения сложных задач, когда детализация блоков производится позднее и, возможно, другими разработчиками.

2. Линейная алгоритмическая  структура. 

      Алгоритмы могут отличаться не только по способу  записи, но и по структуре. Алгоритмические  структуры различаются на:

1. линейные (следования);
2. разветвляющиеся (выбора);
3. циклические повторения).

      Рассмотрим данные алгоритмические структуры подробнее.

      Для решения любых задач достаточно этих трех видов структур.

      Линейный (последовательный) алгоритмическая структура - описание действий, которые выполняются однократно в заданном порядке.

      Линейными являются алгоритмы отпирания дверей, заваривания чая, приготовления одного бутерброда. Линейный алгоритм применяется при вычислении арифметического выражения, если в нем используются только действия сложения и вычитания.

      Программа имеет линейную структуру, если все операторы (команды) выполняются последовательно  друг за другом.

      Каждое  указание алгоритма предписывает исполнителю  выполнить одно конкретное законченное действие. Исполнитель не может перейти к выполнению следующей операции, не закончив полностью выполнения предыдущей. Предписания алгоритма надо выполнять последовательно одно за другим, в соответствии с указанным порядком их записи. Выполнение всех предписаний гарантирует правильное решение задачи.  

    
 
 
 
 
 
 
 

      Приведем  пример записи линейной алгоритмической структуры в виде блок-схемы, псевдокодов и на языке Паскаль.

  

      Но  линейные алгоритмы встречаются очень редко. Часто возникает условие, которое надо либо выполнять, либо нет. Порядок выполнения действий будет зависеть от выполнения некоторого условия. И появляется еще одна графическая структура. Алгоритмы с такой структурой называются разветвляющимися. 

3. Разветвляющаяся алгоритмическая структура. 

      Разветвляющийся алгоритмическая структура – алгоритмическая структура, в которой в зависимости от условия выполняется либо одна, либо другая последовательность действий.

      Ветвление - это такая форма организаций  действий, при которой в зависимости  от выполнения или невыполнения некоторого условия совершатся либо одна, либо другая последовательность действий.

      Условие — выражение, находящееся между словом «если» и словом «то» и принимающее значение «истина» или «ложь».

      Примеры разветвляющих алгоритмов: если пошел  дождь, то надо открыть зонт; если болит горло, то прогулку следует отменить; если билет в кино стоит не больше десяти рублей, то купить билет и занять свое место в зале, иначе (если стоимость билета больше 10 руб.) вернуться домой.

    
 
 
 
 
 
 
 
 
 
 
 

      Приведем  пример записи алгоритма в виде блок-схемы, псевдокодов и на языке Паскаль. Приведем пример записи разветвляющегося алгоритма для нахождения наибольшего из двух чисел.

  

      В общем случае схема разветвляющего алгоритма будет выглядеть так: «если условие, то..., иначе...». Такое представление алгоритма получило название полной формы.

      Неполная форма, в которой действия пропускаются: «если условие, то...».

      Вспомогательный алгоритм — алгоритм, который можно использовать в других алгоритмах, указав только его имя.

      Например: вы в детстве учились суммировать  единицы, затем десятки, чтобы суммировать  двузначные числа содержащие единицы  вы не учились новому методу суммирования, а воспользовались старыми методами.

      Алгоритмы, при исполнении которых порядок  следования команд определяется в зависимости  от результатов проверки некоторых  условий, называют разветвляющимися. Для  их описания в алгоритмическом языке  используют специальную составную  команду - команда ветвления. Она соответствует блок-схеме «альтернатива» и также может иметь полную или сокращенную форму. Применительно к исполнителю-роботу условием может быть проверка нахождения робота у края рабочего поля (край/не_край); проверка наличия объекта в текущей клетке (есть/нет) и некоторые другие:  
 
 
 

4. Циклические алгоритмические структуры. 
 

      Алгоритмы, при исполнении которых отдельные  команды или серии команд выполняются  неоднократно, называют циклическими. Для организации циклических  алгоритмов в алгоритмическом языке используют специальную составную команду цикла. Она соответствует блок-схемам типа «итерация»

 
 
 
 
 
 
 
 
 
 
 
 
 
 

      Циклический алгоритм — описание действий, которые должны по вторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называется телом цикла.

      Многие  процессы в окружающем мире основаны на многократном повторении одной и  той же последовательности действий. Каждый год наступают весна, лето, осень и зима. Жизнь растений в  течение года проходит одни и те же циклы. Подсчитывая число полных поворотов минутной или часовой стрелки, человек измеряет время.

      Условие — выражение, находящееся между словом «если» и словом «то» и принимающее значение «истина» или «ложь».

      Рассмотрим  алгоритм нахождения суммы первых натуральных нечетных чисел до n.

     В схеме циклического процесса блоки имеют следующее назначение:

     1 - блок задания начального значения  параметра цикла;

     2 - тело цикла, то есть участок вычислительного процесса, который многократно повторяется;

     3 - блок изменения параметра цикла;

     4 - блок проверки условия выхода  из цикла.

      Цикл  программы – последовательность команд (серия, тело цикла), которая  может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия. 

  5. Основные операторы  циклов и ветвлений. 

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

      Циклом  называется многократно выполняемая  последовательность действий (операторов).

      Операторы цикла предназначены для многократного  повторения одних и тех же операций (операторов) в программе. Цикл завершается после выполнения условий окончания цикла, после чего следуют остальные операторы алгоритма. Если выхода из цикла нет, то говорят, что программа «зацикливается».

      Имеется 3 вида циклов:

• Цикл с предварительным условием (с предусловием);
• Цикл с последующим условием (с постусловием);
• Цикл с параметром.

1. Операторы с предусловием.

1. Оператор  цикла «Пока» (с предусловием).

      Самым «строгим» циклом (в смысле его  соответствия правилам структуры программирования) является цикл «Пока». Его синтаксис следующий:

      while <условие> do <оператор>,

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

      <оператор> - любой допустимый оператор или блок операторов языка программирования.

      Приведем  схему выполнения оператора «while».

1. Вычисляется выражение-условие ВЫРАЖЕНИЕ.
2. Если оно истинно, то выполняются операторы блока БЛОК и осуществляется возврат к пункту 1.
3. Если выражение-условие ложно, то оператор цикла завершает свою работу и передает управление следующему после него оператору программы.

      Таким образом, оператор цикла «while» является управляющей конструкцией цикла с предусловием: сначала проверяется условие завершения цикла, и потом только выполняется тело цикла, определяемое блоком БЛОК. Поэтому может оказаться, что тело цикла не будет выполнено ни одного раза, если при первом вхождении в цикл условие окажется ложным. Это обстоятельство следует учитывать при программировании с циклом «while».

      Для корректной работы цикла «while» необходимо, чтобы на каждом шаге цикла изменялось выражение-условие, иначе мы получим бесконечный цикл, если при вхождении в него это выражение истинно. Изменение выражения-условия на каждой итерации цикла можно реализовать либо непосредственно в самом выражении, например, использовать операцию чтения из стандартного входного потока <>, либо при выполнении операторов блока БЛОК обеспечить изменение значений переменных, входящих в выражение-условие.

      На  блок-схеме оператор цикла «Пока» - имеет вид, приведенный на рис.5.1.:

 

      Рис. 5.1. Оператор цикла «пока» на блок-схеме.  

      Для реализации цикла «пока» должны быть выполнены следующие условия:

• условие входа в цикл;
• условие выхода из цикла;
• последнее условие должно меняться в теле цикла.

1.2. Оператор цикла  «До … пока»  (с предусловием).

      Этот  оператор аналогичен оператору цикла  «пока», за исключением того, что  операторы в теле цикла будут  исполняться минимум один раз. Синтаксис этого оператора следующий:

      do <оператор> while <условие>

      где <условие> - условие окончания цикла (в случае несовпадения значения выражений этому условию продолжения цикла). Условием может быть переменная логического типа, или операция отношения между целыми, вещественными, символьными константами и переменными, и выражений с ними), а

      <оператор> - любой допустимый оператор или блок операторов языка программирования, который выполняется определенное число раз («тело цикла»). В теле цикле должно находиться условие, прекращающее цикл. В противном случае цикл будет повторяться бесконечное число раз (будет «зацикливаться»).

      На  блок-схеме цикл «До … пока» имеет следующий вид, изображенный на рис.5.2.: 

 

      Рис. 5.2. Оператор цикла «До … пока» на блок-схеме.

2. Оператор цикла с постусловием («repeat»).