Вложенные циклы и ветвления в системе КУМИР
Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850) выдающегося математика средневекового Востока. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком.
В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных.
Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами.
Данное выше определение алгоритма нельзя считать строгим – не вполне ясно, что такое «точное предписание» или «последовательность действий, обеспечивающая получение требуемого результата». Поэтому обычно формулируют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций.
Такими свойствами являются:
Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.
Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Способы записи алгоритмов
Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма.
Выделяют следующие основные способы записи алгоритмов:
- вербальный , когда алгоритм описывается на человеческом (естественном) языке. Естественными являются национальные языки (русский, английский, немецкий и т.д.);
- символьный , когда алгоритм описывается с помощью набора символов и является программой (программы пишутся с помощью языков программирования);
- графический , когда алгоритм описывается с помощью набора графических изображений (блок-схема).
Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка - программа.
При графическом способе записи составляются блок-схемы, на которых с помощью условных обозначений (геометрических фигур) обозначаются различные части алгоритма. Элементы блок-схем представлены на рисунке.
Система программирования КУМИР
При освоении темы алгоритмы воспользуемся системой программирования КУМИР.
КуМир (Комплект Учебных МИРов) - система программирования, предназначенная для поддержки начальных курсов информатики и программирования в средней и высшей школе.
В системе КуМир используется школьный алгоритмический язык с русской лексикой и встроенными исполнителями Робот и Чертёжник и др.
При вводе программы КуМир осуществляет постоянный полный контроль ее правильности, сообщая на полях программы обо всех обнаруженных ошибках.
При выполнении программы в пошаговом режиме КуМир выводит на поля результаты операций присваивания и значения логических выражений. Это позволяет ускорить процесс освоения азов программирования.
Графический исполнитель Робот
Графический исполнитель Робот позволяет освоить азы программирования и понять работу основных алгоритмических конструкций.
Графический исполнитель - это объект управления. А уп равлять им будем мы с вами.
Исполнитель робот находится в некоторой стартовой обстановке – прямоугольном поле, разбитом на клетки, между которыми могут стоять стены.
Робот может перемещаться по полю, обходя стены и закрашивать клетки. Робот не может пройти сквозь стену, но может проверять есть ли рядом с ним стена. Робот не может выйти за пределы прямоугольника, ограничивающего поле.
Р
обот может выполнять команды
: вверх, вниз, вправо, влево, закрасить.
Робот может проверять условия : сверху свободно, снизу свободно, справа свободно, слева свободно, добавление частицы не меняет условие на противоположное. Не сверху свободно, не снизу свободно, не справа свободно, не слева свободно.
Базовые алгоритмические структуры
Выделяют три базовые алгоритмические структуры (конструкции) -линейная (следование), ветвление и цикл, из которых можно построить любой алгоритм. Каждая алгоритмическая структура имеет одну точку входа и одну точку выхода.
Будем записывать алгоритмы на и школьном АЯ и в виде блок-схем.
Линейная структура
Линейная структура является самой простой организацией алгоритмов - команды выполняются последовательно одна за другой
Пример:
Циклическая структура (цикл)
Циклическая структура (цикл) обеспечивает многократное выполнение одних и тех же команд. Существует несколько разновидностей циклических структур.
Любая циклическая структура состоит из двух частей - заголовка и тела цикла.
Набор команд, повторяющихся при выполнении цикла, называют телом цикла.
Заголовок определяет количество повторений тела цикла.
Цикл на число повторений (раз)
нц N раз
<команда>
кц
П
ример:
использовать
Робот
алг
столбик
нач
.
нц
5
раз
. . закрасить
. . вверх
.
кц
кон
Цикл с предусловием (пока)
(запись в алгоритмическом языке)
нц пока <условие>
<команда>
к
ц
Пример:
использовать
Робот
алг
Линия
нач
нц
пока
сверху свободно
закрасить
вверх
кц
кон
Цикл с постусловием (при)
(запись в алгоритмическом языке)
н
ц
<команда>
кц_при <условие>
Пример:
использовать
Робот
алг
Линия
нач
нц
закрасить; вверх
кц_при слева свободно
кон
Структура «ветвление».
Структура «ветвление». Решение некоторых задач требует различных действий в зависимости от выполнения некоторых условий. В таких случаях говорят о ветвлении алгоритма.
Для реализации структуры «ветвление» используются две структурированные команды школьного АЯ - если и выбор, каждая из которых может быть полной и неполной.
В блок-схемах и школьном АЯ <условие> - это логическое выражение, результатом которого может быть одно из двух возможных значений - истина или ложь. В школьном АЯ эти значения записывают как да и нет. В языках программирования часто используются значения True и False . В компьютере эти значения хранятся как 1 и 0.
Полное ветвление
(запись в алгоритмическом языке)
е
сли
<условие>
. .
то
<команда1>
. .
иначе
<команда2>
все
Пример:
использовать
Робот
алг
ветвление_полное
нач
.
если
сверху свободно
. .
то
вверх
. .
иначе
вниз
.
все
кон
Неполное ветвление
(запись в алгоритмическом языке)
е
сли
<условие>
. .
то
<команда1>
все
Пример:
использовать
Робот
алг
ветвление_неполное
нач
.
если
сверху свободно
. .
то
вверх
.
все
кон
Вспомогательный алгоритм (процедура)
Алгоритм по которому решается некоторая подзадача из основной задачи и который, как правило выполняется многократно, называется вспомогательным алгоритмом.
Вспомогательный алгоритм, записанный на языке программирования, называется подпрограммой или процедурой.
Вспомогательный алгоритм вызывается из основной программы через имя. Вспомогательный алгоритм записывается после основного алгоритма. У вспомогательного алгоритма обязательно должно быть имя.
использовать
Робот
алг
нач
вниз
квадрат
вниз
вниз
кон
алг квадрат
нач
закрасить
вправо
закрасить
вниз
закрасить
влево
закрасить
кон
Вложенные циклы и ветвления
При решении некоторых задач с роботом необходимо использовать вложенные циклы или ветвления.
Ц
икл называется вложенным, если он размещается внутри другого цикла.
Рассмотрим вложенный цикл на примере цикла пока.
Мы знаем, что цикл состоит из заголовка цикла, который определяет количество повторений тела цикла.
Тело цикла, это та часть цикла, которая повторяется при выполнении цикла.
Телом цикла может быть команда, несколько команд, а также другой цикл или ветвление.
В том случае, когда телом цикла является другой цикл или ветвление, они называются вложенными.
Вложенный цикл
На первом проходе, внешний цикл вызывает внутренний, который исполняется до своего завершения, после чего управление передается в тело внешнего цикла. На втором проходе внешний цикл опять вызывает внутренний. И так до тех пор, пока не завершится внешний цикл.
Вложенное ветвление
Рассмотрим решение задачи с вложенными ветвлениями и циклами:
Задача 1 Робот находится на стене, в которой есть отверстия, двигаясь вдоль стены вправо, робот должен закрашивать все клеточки, где есть отверстия.
использовать Робот алг нач. нц пока справа с вободно
нц пока снизу свободно
.закрасить; вправо
. . кц
. . вправо
. кц кон С
оставим алгоритм решения задачи с вне6шим циклом пока и вложенным циклом пока.
ешим эту же задачу, используя внешний цикл пока и вложенное ветвление.
Решим эту же задачу с помощью внешнего цикла при и вложенного цикла пока.
Цели : сформировать умение записи, исполнения и отладки алгоритмов с использованием цикла пока ; добиться понимания использования цикла пока ; развивать умение анализировать.
Ученики должны знать : правила записи и исполнения цикла пока ; свойства цикла пока .
Ученики должны уметь : использовать при составлении алгоритмов конструкцию цикла пока и записывать ее на языке Кумир, владеть методами отладки: по шагам, непрерывно.
Метод обучения: объяснительно-иллюстративный и репродуктивный (на этапе объяснения нового материала), репродуктивный с элементами проблемного (этап закрепления материала).
Обеспечение урока:
- система Кумир;
- интерактивная доска;
- мультимедийный проектор;
- карточки-задания.
Ход урока
1. Объяснение нового материала.
В общем случае алгоритм должен быть универсальным, т.е., он не должен зависеть от расстояния между Роботом и стеной. Для этого в алгоритмическом языке есть специальная команда – цикл пока .
Общий вид цикла пока
В общем виде цикл пока записывается так:
При выполнении цикла компьютер повторяет следующие действия:
а) проверяет записанное после служебного слова пока условие;
б) если условие не соблюдается, то выполнение цикла завершается, и компьютер начинает выполнять команды, записанные после кц . Если же условие соблюдается, то компьютер выполняет тело цикла, снова проверяет условие и т.д.
Пример .
Метод отладки : по шагам.
Диалог Компьютера и Робота
Компьютер : снизу свободно?
Робот : да.
Компьютер : вниз.
Робот : смещается вниз в клетку Б.
Компьютер : снизу свободно?
Робот : да.
Компьютер : вниз.
Робот : смещается вниз в клетку В.
Компьютер : снизу свободно?
Робот: нет.
Так как Робот ответил нет, т.о. записанное после пока условие не соблюдается и выполнение цикла заканчивается.
Продемонстрировать в системе Кумир методы отладки: по шагам и непрерывно.
Тело цикла может не выполниться ни разу, если условие в цикле пока не соблюдается с самого начала. Например, если в алгоритме «вниз до стены» Робот на первый же вопрос «снизу свободно » ответит нет , то компьютер не вызовет команду «вниз» ни разу.
Зацикливание. Выполнение цикла пока может и не завершиться, если условие все время будет соблюдаться. Например, если ниже Робота никаких стен нет, то при выполнении предыдущего алгоритма, компьютер «зациклится», т.е. будет бесконечно спрашивать у Робота «снизу свободно», получать в ответ да и командовать «вниз».
Выполнение упражнений.
2. Эксперименты с программой на примере исполнителя Робот.
Необходимо, в системе Кумир, предварительно сделать заготовки расположения Робота (файлы 1. fil -6. fil ).
Упражнения.
Эксперименты с программой.
Задание 1 . (Загрузить файл 1.fil)
Требуется перевести Робота из клетки А в клетку Б. Использовать цикл пока:
использовать Робот
Задание 2 . (Загрузить файл 2.fil)
Дано, что Робот находится у левой стены внутри прямоугольника, огороженного со всех сторон стенами. Внутри прямоугольника стен нет, размеры прямоугольника неизвестны. Требуется закрасить горизонтальный ряд клеток от исходного положения Робота до правой стены и вернуть Робота в исходное положение.
Задание 3 . (Загрузить файл 3.fil)
Робот находится в горизонтальном коридоре. Закрасить все клетки коридора:
Задание 4 . (Загрузить файл 4.fil)
1. Переделайте алгоритм «закрасить ряд вправо и вернуться» используя в нем цикл:
2. Используя вспомогательный алгоритм, составьте алгоритм, при выполнении которого Робот закрашивает прямоугольник.
Задание 5 . (Загрузить файл 5.fil)
Составьте алгоритм для закраски всех клеток вокруг прямоугольной стены:
Задание 6 . (Загрузить файл 6.fil) (Из материалов экзамена 2009г.)
Робот находится в левом верхнем углу огороженного пространства, имеющего форму прямоугольника. Размеры прямоугольника неизвестны. Написать для Робота алгоритм, закрашивающий четыре угловые клетки прямоугольника.
Задание 7 . (Загрузить файл 6.fil) (Из материалов экзамена 2009 г.)
Робот находится в левом верхнем углу огороженного пространства, имеющего форму прямоугольника. Размеры прямоугольника неизвестны. Написать для Робота алгоритм, закрашивающий все клетки, расположенные внутри прямоугольника и прилегающие к нижней стороне прямоугольника.
3. Закрепление. Вопросы:
Какие команды Компьютер будет давать Роботу при выполнении цикла:
а) нц пока клетка не закрашена
б) нц пока клетка закрашена
В ситуации, когда Робот стоит:
- в закрашенной клетке,
- в не закрашенной?
Расположение Робота показано на следующих рисунках:
Как будет выполняться цикл?
Домашнее задание. Определите значение переменной S после выполнения операторов:
Литература : А.Г.Кушниренко «Основы информатики и вычислительной техники».
И сегодня поговорим о циклах. Давайте разберемся, что же такое цикл и как научить выполнять циклические алгоритмы нашего Робота.
Итак, что такое цикл ? Представьте, что мы находимся на уроке физической культуры и перед нами стоит задача сделать 7 приседаний . Это задание можно оформить в виде линейного алгоритма и тогда оно будет выглядеть примерно так:
сделай приседание
сделай приседание
сделай приседание
сделай приседание
сделай приседание
сделай приседание
сделай приседание
Т. е мы повторили команду сделай приседание 7 раз. А есть ли смысл писать 7 одинаковых команд? Может проще дать команду сделай 7 приседаний ? Конечно проще и правильнее. Это и есть цикл . Вы можете сами вспомнить примеры циклов из жизни — их довольно много.
Таким образом линейный алгоритм , где повторяются одни и те же команды мы можем оформить в виде циклического алгоритма — примерно так:
повторяй 7 раз
сделай приседание
конец цикла
Вот так, на придуманном нами языке мы оформили цикл. У исполнителя Робот тоже есть возможность записывать циклы. Причем, циклы бывают разные . Тот вариант, который мы только что рассмотрели называется цикл со счетчиком или цикл с параметром .
Виды циклов.
Цикл со счетчиком.
Цикл со счетчиком применяется когда заранее известно сколько повторений необходимо сделать. В примере выше с приседаниями именно такой случай.
Для того, чтобы написать цикл со счетчиком для исполнителя необходимо знать его синтаксис. А он такой:
нц <количество повторений > раз
<команда 1>
<команда 2>
…
<команда n>
Здесь мы должны указать количество повторений (число) и команды, которые будут повторяться. Команды, которые повторяются в цикле называют телом цикла .
Давайте рассмотрим это на примере.
Изначально Робот находился в левой верхней клетке.
Давайте для начала решим задачу линейно. В этом случае мы будет закрашивать текущую клетку и перемещаться на 1 клетку вправо и программа будет выглядеть так:
использовать Робот
алг
нач
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вправо
Как видим, команды закрасить и вправо повторяются 7 раз. Давайте теперь перепишем программу с использованием цикла. Кстати, чтобы вставить цикл в свою программу можно в меню Вставка выбрать пункт нц-раз-кц или нажать одну из комбинаций клавиш Esc, Р (русская буква Р) или Esc, H (латинская буква H). Причем клавиши надо нажимать последовательно — сначала Esc, отпустить ее и только потом Р или H.
Так вот, наша программа с циклом будет выглядеть так:
использовать Робот
нц 7 раз
закрасить
вправо
Если мы ее запустим, то увидим, что в результате получится тоже самое — 7 закрашенных клеток. Однако программа стала короче и значительно грамотней с алгоритмической точки зрения!
В качестве разминки и закрепления предлагаю самостоятельно написать программу для Робота, которая нарисует квадрат со стороной 7 клеток. Естественно, используя цикл. Жду решения в комментариях.
Цикл с условием.
При решении задачи 19 ГИА по информатике с Роботом использовать цикл со счетчиком не получится. Так как там поле, как правило, бесконечное и стены не имеют конкретной длины. Поэтому мы не сможем определить количество повторений для цикла со счетчиком. Но не беда — нам поможет цикл с условием .
Вернемся к физкультуре и изменим задачу. Ведь кто-то может и не сделать 7 приседаний, а другой способен сделать 27. Можно ли учесть это при создании цикла? Конечно. Только теперь мы будем использовать не счетчик (количество повторений), а условие. К примеру, пока не устал, делай приседания. В этом случае человек будет делать не конкретное число приседаний, а приседать до тех пор, пока не устанет. И наш цикл на абстрактном языке примет такой вид:
пока не устал
сделай приседание
конец цикла
Слова не устал в нашем случае — это условие. Когда оно истинно, цикл выполняется. Если же оно ложно (устал) тело цикла не будет выполнено. У исполнителя Робот есть несколько условий
сверху свободно
снизу свободно
слева свободно
справа свободно
сверху стена
снизу стена
слева стена
справа стена
Но в условии задачи 19 ГИА указаны только первые 4. Так что будем пользоваться только ими.
Теперь давайте решим следующую задачу для Робота — нарисовать вертикальную линию от левой до правой границы поля использую цикл с условием. Изначально Робот находится в левом верхнем углу.
Давайте сначала сформулируем словесный алгоритм — т. е. опишем словами что нужно делать Роботу. Этот алгоритм будет звучать примерно так:
«Пока справа свободно делай шаг вправо и закрашивай клетку »
В результате Робот пробежит по всем клеткам вправо и будет их закрашивать до тех пор, пока справа не окажется стена.
Исходный код нашей программы для Робота будет примерно такой:
использовать Робот
нц пока справа свободно
вправо
закрасить
В результате выполнения этой программы мы увидим вот такую картину:
Карточки-задания
Найдите среди n -целых чисел вводимых с клавиатуры количество отрицательных
Дано два произвольных числа. Пока их произведение меньше 100, увеличивать каждое число на 2 и вывести конечные числа на монитор
Последовательно вводятся n -целых чисел. Найти количество пятерок в последовательности
Последовательно вводятся n -целых чисел. Найти разницу между максимальным и минимальным значениями данных чисел
Найдите среди n -целых чисел вводимых с клавиатуры количество отрицательных
Дано два произвольных числа. Пока их произведение меньше 100, увеличивать каждое число на 2 и вывести конечные числа на монитор
Последовательно вводятся n -целых чисел. Найти количество пятерок в последовательности
Последовательно вводятся n -целых чисел. Найти разницу между максимальным и минимальным значениями данных чисел
Найдите среди n -целых чисел вводимых с клавиатуры количество отрицательных
Дано два произвольных числа. Пока их произведение меньше 100, увеличивать каждое число на 2 и вывести конечные числа на монитор
Последовательно вводятся n -целых чисел. Найти количество пятерок в последовательности
Последовательно вводятся n -целых чисел. Найти разницу между максимальным и минимальным значениями данных чисел
Найдите среди n -целых чисел вводимых с клавиатуры количество отрицательных
Дано два произвольных числа. Пока их произведение меньше 100, увеличивать каждое число на 2 и вывести конечные числа на монитор
Последовательно вводятся n -целых чисел. Найти количество пятерок в последовательности
Последовательно вводятся n -целых чисел. Найти разницу между максимальным и минимальным значениями данных чисел