Занятие №16

Тема: Алгоритмизация, типы алгоритмов, способы записи

Теория

Понятие алгоритма

Алгоритм— последовательность действий, приводящая исполнителя к решению поставленной задачи. Существует несколько форм представления алгоритмов:

• словесная,

• табличная,

• графическая (блок-схемы),

• на алгоритмическом языке.

Составление алгоритма: важный этап в цепочке: Задача–Алгоритм–Программа.

С алгоритмическим языком познакомимся позднее, а на этом занятии рассмотрим графическое представление алгоритма (в виде блок-схемы).

Программистами используется как этап составления программ графический способ (с помощью блок-схемы).

Блок-схема состоит из блоков, соединенных линиями. Чаще всего используются блоки следующих типов:

- выполнение операции;

- выбор направления выполнения алгоритма в зависимости от выполнения условия;

- ввод/вывод данных;

- начало и конец алгоритма.

Алгоритмические конструкции

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

Ветвление представляет собой алгоритмическую конструкцию, в которой выполнение того или иного действия зависит от истинности условия. Говорят, что конструкция «ветвление» записана в полной форме, если в ней присутствуют команды как для случая истинного условия, так и для его ложного. На рис.2 приведена блок-схема ветвления в полной форме.

Конструкция ветвления в полной форме реализуется следующим образом. Если условие истинно, то выполняется действие 1, если условие ложно, то выполняется действие 2.

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

Конструкция ветвления в сокращенной форме реализуется следующим образом. Если выбрано направление, в котором отсутствует действие, то конструкция ветвления не выполняется и управление получает конструкция, следующая за ветвлением.

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

Различают два вида циклов: циклы с заранее известным числом повторений и циклы с заранее неизвестным числом повторений.

Цикл с заранее известным числом повторений называют циклом с параметром. Блок-схема цикла с параметром помещена на рис.4.

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

Если при истинности условия цикл завершается, то такое условие называется условием завершения цикла. В этом случае цикл продолжается до тех пор, пока условие не станет истинным.

Различают циклы с проверкой условия перед выполнением очередной итерации и циклы с проверкой условия после выполнения очередной итерации. Первые называются циклами с предусловием (рис. 5), вторые – с постусловием (рис. 6).

Тема: Алгоритмизация, типы алгоритмов, способы записи (исполнители Робот, Черепашка) Теория. Исполнители алгоритмов

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

• Исполнитель – это тот, кто умеет понимать и выполнять некоторые команды.

• Среда исполнителя – это предметы, которые окружают исполнителя и с которыми он работает.

• Список (или система) Команд Исполнителя (СКИ) – набор команд, понятных исполнителю. Исполнитель может выполнить только те команды, которые входят в его СКИ.

Исполнителями могут быть:

• люди: ученик, рабочий, учитель, бригада;

• животные: дрессированная собака (санитар, розыскная, охотничья), кошка;

• машины: станки, роботы, компьютеры;

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

Человек как исполнитель отличается от всех остальных исполнителей несколькими признаками, например:

• Понимает команды в различных вариантах (например “Сядь!”, “Садись!”, “Присядь!”).

• Выполняя команды, «додумывает» их с учетом своего опыта.

• Может отказаться исполнять команду, если она ему не нравится (“Ешь манную кашу!”, “Выстрели в окно из рогатки!”). То есть человек обладает волей и отвечает за свои действия.

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

• Алгоритм – это точно определенный план действий исполнителя, направленный на решение какой-то задачи. В алгоритм можно включать только те команды, которые есть в СКИ исполнителя.

Ошибки при работе исполнителей

Работа исполнителя не всегда проходит гладко – иногда встречаются ошибки. Существует три вида ошибок исполнителей.

«НЕ ПОНИМАЮ»	Заданной команды нет в списке команд исполнителя, и он ее не понял. Вероятно, мы ошиблись в записи текста команды.
«НЕ МОГУ»	Исполнитель понял команду, но не может ее выполнить. Например, роботу дана команда “вперед”, а впереди стоит стенка, и он не может идти. Или собаке скомандовали “Сидеть!”, а она уже сидит.
ЛОГИЧЕСКИЕ ОШИБКИ	Исполнитель понял команду и выполнил ее, но сделал не то, что мы от него хотели. Причина этого – наша ошибка в составлении задания (алгоритма).

Пример 1

Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: “Вперед N” (Кузнечик прыгает вперед на N единиц); “Назад M” (Кузнечик прыгает назад на M единиц). Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?

Решение

Обозначая за x количество «Вперед 3» получаем уравнение x+x+12=50, отсюда x=19. Тогда 19“Вперед 3”+31“Назад 2”=19*3-31*2=-5, т.е “Назад 5”

Ответ: “Назад 5”