Информатика

Урок 8: Алгоритм

Алгоритм

Чтобы решить сложную задачу, ее нужно разбить на несколько более простых. Такой детальный, пошаговый план очень удобен и облегчает понимание. А если способ записи и подход сделать единым, можно создать язык, который будет понятен пользователям/исполнителям со всего мира, включая компьютеры.

Обложка урока взята с источника.

План урока:

Алгоритмы, которыми мы пользуемся

Исполнители, система команд исполнителя (СКИ)

Свойства алгоритмов

Классификация алгоритмов

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

Пример алгоритма на Turbo Pascal

 

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

Один человек сразу включает чайник, потом начинает искать чашки, заварку, сахар.

Второй действует согласно плану:

  1. Проверить наличие заварки и сахара.
  2. Если их нет, купить.
  3. Если все есть, найти чашку, проверить ее чистоту.
  4. Поставить чайник греться.
  5. Ополоснуть чашку кипятком.
  6. Насыпать заварку, залить кипятком.
  7. Добавить сахар.

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

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

 

Алгоритмы, которыми мы пользуемся

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

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

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

  • пошаговые кулинарные рецепты;
  • мастер-классы по рукоделию;
  • инструкции к оборудованию;
  • план действия при ЧП.

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

Пример в виде красочной инструкции и сухой пошаговой рекомендации:

1 algoritm
Работа за компьюетром Источник          Инструкция по настройке Источник

А в информатике без них не обойтись – именно на алгоритмах основано программирование.

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

Если действия однотипные, например, «набрать ковш воды и вылить» или «взять яблоко и проверить, есть ли червоточина», то его записывают 1 раз и повторяют конечное число раз.

Когда все задания/этапы будут выполнены, они должны привести к желаемому результату.

 

Исполнители, система команд исполнителя (СКИ)

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

Исполнитель – субъект/объект, который может выполнить команды данного алгоритма.

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

Компьютер (ПК) – автоматизированный исполнитель команд. Алгоритмы программ для ПК пишут на языках программирования (С++, Basic, Pascal, Delphi, Ассемблер, Фортран).

Для каждого типа и уровня исполнителей существует своя система команд исполнителя (СКИ).

 

Свойства алгоритмов

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

  1. Детерминированность – все описания должны быть однозначными, понятными.

Понятность – процедура должна быть на языке, который понятен той категории исполнителей, для которых она пишется.

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

  1. Дискретность – строгие команды, идущие в определенной последовательности.

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

Пример непонятного и неточного задания мы помним из сказки: “Пойди туда, не знаю куда. Принеси то, не знаю что”.

  1. Массовость – план действия подходит под аналогичные ситуации с разными исходными данными. То есть инструкция по приготовлению бутерброда с колбасой позволяет брать разный хлеб и мясопродукт или заменить его сыром.
  2. Результативность – выполнение команд должно приводить к результату. Не должно быть ошибок. При использовании допустимых исходных параметров алгоритм должен давать правильный результат всегда.
  3. Конечность – каждая команда и процедура в целом должны выполняться за конечное число шагов, то есть он не должен быть бесконечным, зацикленным.

Пример бесконечного алгоритма

Мытье рук:

  • включить воду;
  • намочить руки и мыло;
  • выключить воду;
  • намылить руки;
  • включить воду.

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

 

Классификация алгоритмов

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

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

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

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

2 algoritm
Источник

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

Запишем схему линейного алгоритма (покупки чая):

  1. Взять пакет и кошелек с деньгами.
  2. Зайти в любой продуктовый маркет.
  3. Выбрать нужный сорт чая.
  4. Заплатить за товар.
  5. Чай положить в пакет, пойти домой.

Для многих задач важно выполнение определенного условия.

Пример алгоритма ветвления – если нужного сорта нет, то процесс покупки чая усложняется:

  1. Взять пакет и кошелек с деньгами.
  2. Зайти в любой продуктовый маркет.
  3. Посмотреть, есть ли чай «Элитный».
  4. Если да, то узнать цену, отдать деньги.
  5. Покупку положить в пакет, пойти домой.
  6. Если нет, найти сорт «Белый, китайский», узнать цену, отдать деньги.
  7. Упаковку положить в пакет, вернуться домой.
  8. Если нет ни «Элитного», ни «Белого, китайского», то пойти в другой магазин и повторить все с пункта №3.

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

Данный пример включает в себя ветвление «если» и повторение команд:

  1. Взять пакет и кошелек с деньгами.
  2. Зайти в любой продуктовый маркет.
  3. Взять коробку с чаем в руки, посмотреть, это сорт «Элитный».
  4. Если да, то узнать цену, заплатить.
  5. Забрать покупку, вернуться домой.
  6. Если нет, взять следующую упаковку и повторить пункты 3-6.
  7. Если весь чай перебран, но «Элитного» нет, то пойти в другой магазин и повторить все с пункта №3.

Цикличные инструкции следует писать так, чтобы не было вечного цикла или зацикливания – бесконечного повторения операции без достижения результата.

 

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

Самый простой способ записать алгоритм построчно – словесно. Но текстовая форма оформления подобных детальных инструкций не всегда наглядна и удобна из-за большого количества вспомогательных слов.

Легче воспринимается такой план, если его дополнять картинками.

3 algoritm
Источник

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

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

Блок-схема – графическая форма представления алгоритмов при помощи геометрических объектов и стрелок.

4 algoritm

Блок схема линейного алгоритма вычисления площади прямоугольника:

5 algoritm

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

6 algoritm

 

Пример алгоритма на Turbo Pascal

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

Для примера попробуем программирование линейных алгоритмов при помощи языка Turbo Pascal.

Запустить среду программирования следующими шагами:

Меню Пуск → Все программы → Turbo Pascal

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

Оболочка разработана под DOS, что объясняет необычную реализацию интерфейса.

7 algoritm

Пишем самый простой алгоритм программы для выведения на экран слов приветствия.

На латинской раскладке набираем в синем окне такие команды:

program Test;

begin

write('Доброе утро!');

end.

Учитываем важные моменты при использовании языка Турбо Паскаль:

  • все пишется латинскими буквами;
  • регистр неважен;
  • каждая строка – команда, в конце строки ставится Enter и «;»;
  • после «end» должна быть «.».

Как видим, в программе есть свои слова-команды, как в письменных алгоритмах. Слово program – как заголовок, название объекта, а тest – непосредственно название программы.

Началом является команда begin, end – окончанием, а между ними стоят операторы или команды-действия («write» – напиши на экране). А текст, который нужно выводить на экране берется в скобки и ’….’.

Чтобы запустить программу, следует нажать Ctrl+F9 или набор команд Run Run.

Если нет ошибок в командах, появится такой результат:

8 algoritm

Чтобы выйти обратно, можно нажать любую кнопку клавиатуры.

При каждом запуске будет новая запись, на той же строке. Если заменить write на writeln, то текст будет выводиться в новой строчке:

9 algoritm

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

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

 

ВОПРОСЫ И ЗАДАНИЯ

Вопрос: 1
Выбери инструкции, которые может выполнять дрессированная собака:
1Команды «Сидеть», «Лежать», «Голос»
2Просьба «Сходи в магазин за хлебом»
3Пожелание «Давай ты сядешь, потом полежишь и можешь полаять»
Ответить
1
Вопрос: 2
Выберите корректное окончание определения «Блок-схема – это способ...
1Записи алгоритмов при помощи геометрических фигур-блоков и направляющих стрелок
2Оформления текста в табличной форме
3Создания головоломок
Ответить
1
Вопрос: 3
Закончите предложение «Для записи блок-схемы используются…:
1Формулы
2Списки
3Геометрические фигуры (ромбы, квадраты, овалы)
Ответить
3
Вопрос: 4
Преимущества графического способа записи алгоритмов:
1Красочно, занимает мало места, меньше текста
2Компактно, нет лишней информации, универсально, легко программировать
3Быстро писать, связь с другими дисциплинами
Ответить
2
Вопрос: 5
Чем опасны алгоритмы, в которых количество циклов не конечно:
1Исполнителю надоест выполнять и он не закончит алгоритм
2Алгоритм будет выполняться слишком долго
3Произойдет зацикливание – исполнителю придется выполнять алгоритм бесконечно, то есть результата не достичь
Ответить
3
Допущено ошибок:
Оценка:
Подробнее
Ваши ответы:
1 вопрос:

Выбери инструкции, которые может выполнять дрессированная собака:
1) Команды «Сидеть», «Лежать», «Голос» 2) Просьба «Сходи в магазин за хлебом» 3) Пожелание «Давай ты сядешь, потом полежишь и можешь полаять»
2 вопрос:

Выберите корректное окончание определения «Блок-схема – это способ...
1) Записи алгоритмов при помощи геометрических фигур-блоков и направляющих стрелок 2) Оформления текста в табличной форме 3) Создания головоломок
3 вопрос:

Закончите предложение «Для записи блок-схемы используются…:
1) Формулы 2) Списки 3) Геометрические фигуры (ромбы, квадраты, овалы)
4 вопрос:

Преимущества графического способа записи алгоритмов:
1) Красочно, занимает мало места, меньше текста 2) Компактно, нет лишней информации, универсально, легко программировать 3) Быстро писать, связь с другими дисциплинами
5 вопрос:

Чем опасны алгоритмы, в которых количество циклов не конечно:
1) Исполнителю надоест выполнять и он не закончит алгоритм 2) Алгоритм будет выполняться слишком долго 3) Произойдет зацикливание – исполнителю придется выполнять алгоритм бесконечно, то есть результата не достичь
Посмотреть ответы
Правильные ответы:
1 вопрос: Команды «Сидеть», «Лежать», «Голос»
2 вопрос: Записи алгоритмов при помощи геометрических фигур-блоков и направляющих стрелок
3 вопрос: Геометрические фигуры (ромбы, квадраты, овалы)
4 вопрос: Компактно, нет лишней информации, универсально, легко программировать
5 вопрос: Произойдет зацикливание – исполнителю придется выполнять алгоритм бесконечно, то есть результата не достичь