Алгоритмизация. Основные виды алгоритмов и способы их записи.
план-конспект урока по информатике и икт (8 класс)

Алгоритмизация. Основные виды алгоритмов и способы их записи.

Цель ……………………………………………………………………………………..

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

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

      Разветвляющийся алгоритм……………………………………………..….….2

      Циклический алгоритм………………………………………………….………5

Контрольные задания………………………………….…………………………….8

Домашние задания…………………………..………………………………………..9

Цель: Усвоить основные структуры алгоритмов и способы их записи. Научиться записывать  алгоритмы, используя данные структуры.

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

Прежде чем приступить к изучению основных видов структур алгоритмов

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

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

Рассмотрим подробнее каждый из видов алгоритмов.

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

Описание действий в таком алгоритме действуют друг за другом.

Предположим требуется составить алгоритм  копирования файлов на дискетку. Наши действия будут следующими:

1. Вставить дискету;
2. Выделить нужные файлы;
3. Поместить  их в буфер обмена (копировать);
4. Открыть диск 3,5;
5. Вставить из буфера;

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

Структура данных алгоритмов выглядит следующим образом:

Дадим понятие линейного алгоритма:

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

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

Рассмотрим составление схем линейных алгоритмов на конкретных примерах.

Пример 1. Даны переменные А и В. Требуется обменять их значения, т.е переменная А должна получить значение В, а В-значение А.

Решение:

В нашей задаче исходные данные будут А и В, а результатом новые значения А и В.

Данная задача аналогична такой жизненной ситуации. Имеются две клетки А и В, в одной находится волк, а в другой – заяц. Требуется поменять их местами , т.е пересадить их из одной клетки в другую. Естественно в одну клетку мы их посадить не можем, поэтому мы возьмем  другую дополнительную клетку – С. Наши действия будут следующими:

Составим блок схему для данной задачи.

     Исполнитель алгоритма

1. Ввод А=10; В=20;

2. C=10
3. A=20
4. B=10

5. Вывод А=20; В=10;

6. Конец.

1.2.  Разветвляющийся алгоритм.

Вспомним сюжет  из русской сказки.

Царевич останавливается у развилки дороги и видит камень с надписью :

"На право пойдешь - коня потеряешь, на лево пойдешь сам пропадешь.. "

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

Если пошел дождь, то надо открыть зонт.

Если болит горло, то прогулку следует отменить.

Если прозвенел будильник, то надо вставать и идти в школу и т.д.

Если билет в кино стоит не больше 10 рублей, то купить билет и занять свое место в зале, иначе (если стоимость билета больше 10 рублей) вернуться домой.

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

Например, в предложении "Если пошел дождь, то надо открыть зонт" условие "пошел дождь" может быть истинным или ложным.

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

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

Пример2. Вернемся к алгоритму копирования файлов на дискетку. При копировании файлов одной дискетки может не хватить. Тогда, наш алгоритм изменится следующим образом:

1.   Вставить дискету;

2. Выделить нужные файлы;
3. Поместить  их в буфер обмена (копировать);
4. Открыть диск 3,5;

6. Вставить из буфера;

5. Если места на дискетке  нет, то вставить следующую дискетку.

В данном случае условие – “место на диске  нет?”, если это условие выполняется, то мы вставляем следующую дискетку, а  если условие не выполняется , то ничего не делаем.  

Логический блок.

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

Он изображается ромбом, внутри которого указывается проверяемое условие(отношение), и имеет два выхода : Да и Нет. 

Если условие (отношение)истинно (выполняется), то выходим из блока по выходу ДА; если ложно(не выполняется)- по выходу нет.

Структура ветвление и ее запись на алгоритмическом языке:

1. если-то-иначе (полная форма);

                                                                  Если     условие

То         действия 1

Иначе  действия 2

2. если-то (не полная форма);

  Если  условие

То  действия

3. Выбор.

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

выбор 

   при условие 1: действия 1

   при условие 2: действия 2

   . . . . . . . . . . . .

   при условие N: действия N

   иначе действия N+1

 все 

Например, составим алгоритм к следующей задаче:

Царевич останавливается у развилки дороги и видит камень с надписью :

"На право пойдешь - коня потеряешь, на лево -  сам пропадешь, прямо пойдешь - счастье найдешь"

В данной задаче, выбор наших действий зависит от направления (прямо, на лево, на право ):

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

  “прямо”       :   вывод  “Счастье найдешь”

  “на лево”     :   вывод  “Сам пропадешь”

  “на право”   :   вывод  “Коня потеряешь”

 все 

Рассмотрим составление разветвляющихся алгоритмов на конкретных примерах:

Пример 3: Найти наибольшее из двух не равных чисел а и b;

                                                              Исполнитель алгоритма

                                                             1. Ввод а=19, b=18

                                                             2. 19>18  (условие истинно , значит идем по ветке "Да")

                                                             3. С:=19

                                                            4. Вывод С=19        

                                                           5. Конец

Пример 4:

Вывести название месяца по его номеру.

Ввод N

 выбор  N

   1: вывод “январь“

   2: вывод “февраль”

   . . . . . . . . . . . .

   12: вывод “декабрь”

   иначе вывод “Такого номера месяца нет”

 все 

 1.3. Циклический алгоритм.

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

Допустим, нам требуется отформатировать дискетки , сколько их не известно. Для этого можно составить следующий алгоритм:

1. Взять коробку с дискетками.
2. Взять дискету из коробки.
3. Отформатировать дискетку.

3. Перейти к действию 2.

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

1. Взять коробку с дискетами
2.  Если в коробке есть дискеты

3.               то

                         Взять дискету из коробки

                        Отформатировать дискету

                        Отложить отформатирован

                       ную дискету в сторону

                       Перейти к действию 1

 4. Завершить работу (выполнится если дискеты в коробочке закончатся).

Как работает данный алгоритм? Предположим, в коробке одна дискета. В этом случае на вопрос :"В коробке есть дискеты отвечаем "Да" и выполняем команды:  "Взять дискету из коробки", "Отформатировать дискету", "Отложить отформатированную дискету в сторону". Затем еще раз задаем вопрос, на который уже отвечаем "Нет" и на этом алгоритм заканчивается.

Если же в коробке еще есть дискеты, отвечаем на вопрос "Да" и выполняем команды и т.д.

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

Цикл -это повторяющееся исполнение одних и тех же действий.

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

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

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

Цикл с предусловием может, не выполнится ни разу, так как в начале проверяется условие, а затем выполняется действие. Например, если в коробке нет дискет, тогда на вопрос "Есть дискеты" отвечаем- "нет", и на этом алгоритм заканчивается.

Блок схема цикла с предусловием и ее запись на алгоритмическом языке.

Пока условие(истинно)                                     

Нч

  Тело цикла(последовательность действий)

кн

Рассмотрим следующий вид циклического алгоритма цикл с постусловием, на этом же примере.

Как работает данный алгоритм? Предположим, в коробке одна дискета. В этом случае в начале выполняем команды "Взять дискету из коробки", "Отформатировать дискету", "Отложить отформатированную дискету в сторону". Затем на вопрос "В коробке дискет  нет “ отвечаем "Да" и на этом алгоритм заканчивается.

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

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

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

Блок схема цикла с постусловием и ее запись на алгоритмическом языке.

Нач

  Тело цикла (последовательность действий)

Пока   условие (ложно)                                     

кон

Следующий вид циклического алгоритма, который мы рассмотрим – Параметрический цикл.

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

Допустим у нас в коробочке лежит 5 дискет и нам их надо отформатировать.

Как работает данный алгоритм? В данном алгоритме 5 раз выполняем команды "Взять дискету из коробки", "Отформатировать дискету", "Отложить отформатированную дискету в сторону".При этом с каждым разом выполнения тела цикла, перменная I-с четчик цикла увеличивается на единицу, как только счетчик цикла становиться равный 5, выходим из цикла.

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

Блок схема цикла с постусловием и ее запись на алгоритмическом языке.

нц для i от i1 до i2

   тело цикла (последовательность действий)

 кц

Рассмотрим пример, в котором цикл задается условием. Алгоритм перевода целых десятичных двухзначных чисел в двоичную систему.

1. Записать двузначное число.
2. Разделить исходное число на 2 и записать частное.
3. Разделить частное на 2.
4. Сравнить получившееся новое частное с числом 2.
5. Если частное оказалось больше 2, перейти к шагу 3. Если оно равно 1, то прекратить деление.
6. Записать получившийся двоичный код.

В данном примере в цикл включены три пункта (3,4,5).Их выполнение будет продолжаться до тех пор, пока частное не станет равным 1. 

Контрольные вопросы:

1. Что такое линейный алгоритм ? Приведите свои примеры.
2. Приведите пример математического выражения и составьте алгоритм его вычисления. Какого вида получился данный алгоритм.
3. Что такое разветвляющийся алгоритм ? Приведите примеры.
4. Как записывается полная и не полная форма алгоритма? Чем они отличаются?  Приведите примеры.
5. Напишите циклический алгоритм и укажите в нем тело цикла.
6. Как происходит окончание циклического алгоритма.
7. Какие значения будет принимать переменная х в ходе исполнения следующих команд:

       х:=11

       для к от 1 до 5

           нц 

               х:=⏐ x-11⏐

          кц

Домашние задания:

1. Придумать линейную задачу и написать к  ней алгоритм. .
2. Написать блок схему к задаче: найти среднее арифметическое двух чисел.
3. Какие значения может принимать переменная x после исполнения следующих циклов:

а) пока х>13                   б) пока x<13

      нц                                     нц 

        x:=x-1                                     x:=x+1

      кц                                     кц

4. Какие значения будет принимать переменная х в ходе исполнения следующих команд:

         х:=11

         для к от 1 до 5      

          нц

             х:=-х                                  

          кц                                  

5. Составьте алгоритм  для определения сдачи после покупки в магазине товара: перчаток стоимостью а руб., портфеля стоимостью b руб., галстука стоимостью с руб. Исходная сумма, выделенная на покупку - d руб. В случае нехватки денег сдача получится отрицательной.
6. Привести примеры на все виды циклического алгоритма и составить к каждой из них блок схему.