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

Колтышева Елена Амировна

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

 

Скачать:

ВложениеРазмер
Файл algoritmizatsiya.vidy_.docx208.22 КБ

Предварительный просмотр:

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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




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

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

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

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

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

Решение:

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

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

               

 

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

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

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

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

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

  1. Конец.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     

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

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

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

                                                                  Если     условие

То         действия 1

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

 

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

  Если  условие

То  действия

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. Отформатировать дискетку.
  1. Перейти к действию 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

      кц                                     кц

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

         х:=11

         для к от 1 до 5      

          нц

             х:=-х                                  

          кц                                  

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


По теме: методические разработки, презентации и конспекты

Презентация по теме "Алгоритмы. Свойства. Способы записи алгоритмов. Линейные алгоритмы"

В данной презентации представлен материал к разделу "Алгоритмизация". В презентации рассмотрены понятия: алгоритм, свойства алгоритма, способы записи алгоритмов, линейные алгоритмы. Представлены задач...

Алгоритм. Понятие, свойства, формы записи

Из истории…Алгоритм – это описание последовательности действий, исполнение которых приводит к решению поставленной задачи за конечное число шагов.Алгоритмизация – это процесс разработки алгоритм...

Конспект урока на тему: "«Основные виды алгоритмических структур. Линейные алгоритмы»."

Цели  урока:Образовательная.Организовать работу учащихся по изучению и первичному закреплению знаний путем  коллективной и самостоятельной практической деятельности.Развивающая. О...

Алгоритм, его формы записи записи, виды алгоритмов

Рекомендуется использовать презентацию на начальном уровне знакомства с алгоритмами 5-6 класс...

3.11.21 и 5.11.21 для МСТ1 и 2.11.21 ПКД1 Тема: "Понятие алгоритма. Свойства алгоритма. Виды алгоритмов. Способы описания алгоритмов".

Задание:1) Приготовить сообщение по данной теме.2) Создать кроссворд со словами описывающие способы записи алгоритмов и виды  вычислительных процессов при решении задач....

Конспект к уроку "Формы записи алгоритмов. Виды алгоритмов."

Формы записи алгоритмов. Виды алгоритмов....

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

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