И сегодня поговорим о циклах. Давайте разберемся, что же такое цикл и как научить выполнять циклические алгоритмы нашего Робота.
Итак, что такое цикл ? Представьте, что мы находимся на уроке физической культуры и перед нами стоит задача сделать 7 приседаний . Это задание можно оформить в виде линейного алгоритма и тогда оно будет выглядеть примерно так:
сделай приседание
сделай приседание
сделай приседание
сделай приседание
сделай приседание
сделай приседание
сделай приседание
Т. е мы повторили команду сделай приседание 7 раз. А есть ли смысл писать 7 одинаковых команд? Может проще дать команду сделай 7 приседаний ? Конечно проще и правильнее. Это и есть цикл . Вы можете сами вспомнить примеры циклов из жизни — их довольно много.
Таким образом линейный алгоритм , где повторяются одни и те же команды мы можем оформить в виде циклического алгоритма — примерно так:
повторяй 7 раз
сделай приседание
конец цикла
Вот так, на придуманном нами языке мы оформили цикл. У исполнителя Робот тоже есть возможность записывать циклы. Причем, циклы бывают разные . Тот вариант, который мы только что рассмотрели называется цикл со счетчиком или цикл с параметром .
Виды циклов.
Цикл со счетчиком.
Цикл со счетчиком применяется когда заранее известно сколько повторений необходимо сделать. В примере выше с приседаниями именно такой случай.
Для того, чтобы написать цикл со счетчиком для исполнителя необходимо знать его синтаксис. А он такой:
нц <количество повторений > раз
<команда 1>
<команда 2>
…
<команда n>
Здесь мы должны указать количество повторений (число) и команды, которые будут повторяться. Команды, которые повторяются в цикле называют телом цикла .
Давайте рассмотрим это на примере.
Изначально Робот находился в левой верхней клетке.
Давайте для начала решим задачу линейно. В этом случае мы будет закрашивать текущую клетку и перемещаться на 1 клетку вправо и программа будет выглядеть так:
использовать Робот
алг
нач
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вправо
закрасить
вправо
Как видим, команды закрасить и вправо повторяются 7 раз. Давайте теперь перепишем программу с использованием цикла. Кстати, чтобы вставить цикл в свою программу можно в меню Вставка выбрать пункт нц-раз-кц или нажать одну из комбинаций клавиш Esc, Р (русская буква Р) или Esc, H (латинская буква H). Причем клавиши надо нажимать последовательно — сначала Esc, отпустить ее и только потом Р или H.
Так вот, наша программа с циклом будет выглядеть так:
использовать Робот
нц 7 раз
закрасить
вправо
Если мы ее запустим, то увидим, что в результате получится тоже самое — 7 закрашенных клеток. Однако программа стала короче и значительно грамотней с алгоритмической точки зрения!
В качестве разминки и закрепления предлагаю самостоятельно написать программу для Робота, которая нарисует квадрат со стороной 7 клеток. Естественно, используя цикл. Жду решения в комментариях.
Цикл с условием.
При решении задачи 19 ГИА по информатике с Роботом использовать цикл со счетчиком не получится. Так как там поле, как правило, бесконечное и стены не имеют конкретной длины. Поэтому мы не сможем определить количество повторений для цикла со счетчиком. Но не беда — нам поможет цикл с условием .
Вернемся к физкультуре и изменим задачу. Ведь кто-то может и не сделать 7 приседаний, а другой способен сделать 27. Можно ли учесть это при создании цикла? Конечно. Только теперь мы будем использовать не счетчик (количество повторений), а условие. К примеру, пока не устал, делай приседания. В этом случае человек будет делать не конкретное число приседаний, а приседать до тех пор, пока не устанет. И наш цикл на абстрактном языке примет такой вид:
пока не устал
сделай приседание
конец цикла
Слова не устал в нашем случае — это условие. Когда оно истинно, цикл выполняется. Если же оно ложно (устал) тело цикла не будет выполнено. У исполнителя Робот есть несколько условий
сверху свободно
снизу свободно
слева свободно
справа свободно
сверху стена
снизу стена
слева стена
справа стена
Но в условии задачи 19 ГИА указаны только первые 4. Так что будем пользоваться только ими.
Теперь давайте решим следующую задачу для Робота — нарисовать вертикальную линию от левой до правой границы поля использую цикл с условием. Изначально Робот находится в левом верхнем углу.
Давайте сначала сформулируем словесный алгоритм — т. е. опишем словами что нужно делать Роботу. Этот алгоритм будет звучать примерно так:
«Пока справа свободно делай шаг вправо и закрашивай клетку »
В результате Робот пробежит по всем клеткам вправо и будет их закрашивать до тех пор, пока справа не окажется стена.
Исходный код нашей программы для Робота будет примерно такой:
использовать Робот
нц пока справа свободно
вправо
закрасить
В результате выполнения этой программы мы увидим вот такую картину:
Знакомство с программой Кумир осваение азов программирования.
В ней учащиеся могут получить практические навыки при создании и отладке алгоритма, работая с такими исполнителями, как Робот, Чертёжник, Водолей, Кузнечик,Черепашка.
При изучении одного из наиболее трудных разделов информатики «алгоритмизация и программирование».
Цель разработки :
Скачать:
Предварительный просмотр:
Методическая разработка по информатике.
Тема: «Исполнитель Робот в программе КуМир на уроках информатики »
учитель технологии «Информатика и ИКТ»
Пояснительная записка
Цель разработки : изучить возможности программирования на примере конкретного исполнителя Робот с использованием среды КУМИР; дать практические навыки работы с исполнителем.
Методическая разработка составлена для проведения уроков информатики Практика на компьютере : работа с учебным исполнителем алгоритмов; составление линейных, ветвящихся и циклических алгоритмов управления исполнителем; составление алгоритмов со сложной структурой; использование вспомогательных алгоритмов (процедур, подпрограмм).
Учащиеся должны знать:
- что такое исполнитель; СКИ Робота, среду исполнителя Робот;
- что такое алгоритм; в чем состоят основные свойства алгоритма;
- способы записи алгоритмов: блок-схемы, учебный алгоритмический язык; основные алгоритмические конструкции: следование, ветвление, цикл; структуры
- алгоритмов; ⇒ назначение вспомогательных алгоритмов; технологии построения сложных алгоритмов:
Учащиеся должны уметь:
- понимать описания алгоритмов на учебном алгоритмическом языке;
- выполнить трассировку алгоритма для известного исполнителя;
- составлять линейные, ветвящиеся и циклические алгоритмы управления исполнителя Робот; выделять подзадачи; определять и использовать вспомогательные алгоритмы.
Занятие 1 (2 часа) Урок 1.
Исполнитель Робот. Система команд исполнителя.
План урока.
- Описание СКИ исполнителя, среды исполнителя.
2.Разбор типичных алгоритмов Робота.
Ход урока.
Рассмотрим описание исполнителя.
Среда исполнителя : Исполнитель Робот умеет перемещаться по лабиринту, начерченному на плоскости, разбитой на клетки.
СКИ Робота : простые команды: вверх, вниз, влево, вправо, закрасить.
Команды логические: (проверки условия)
сверху свободно снизу свободно
слева свободно справа свободно.
Логические связки: И,НЕ, ИЛИ:
Пример:(Не слева свободно) или (не справа свободно)
Команда ветвления : команда цикла:
Если условие то нц пока условие
Серия команд серия команд
всё кц
(В КИМах 2009 года команды Робота отличались от привычных детям, что приводило к путанице :)
Команда ветвления : команда цикла:
Если условие то нц пока условие делать
Серия команд серия команд
конец конец
Общий вид окна программы Кумир. Графическая среда Робота:
В КИМах демонстрационного варианта 2010 года формат команд изменен на привычный
Порядок создания алгоритма:
1.Командами Инструменты -Редактировать стартовую обстановку нарисовать на поле Робота стены и установить Робота в начальное положение.
2.Командами Робот- Сменить стартовую обстановку сохранить новую обстановку.
3.Командами Вставка- Использовать Робот указать исполнителя.
4.В окне документа записать алгоритм, используя меню Вставка.
5.Командами Выполнение –выполнить непрерывно (или по шагам) запустить алгоритм.
6.Рассмотреть результат выполнения алгоритма и при необходимости произвести его отладку.
Занятие 1 (2 часа) Урок 2.
Практическая работа « Составление линейных алгоритмов».
Задания: 1.Робот в произвольной точке поля. Закрасить клетку сверху, снизу и справа от исходного положения.
- Робот в произвольной точке поля. Передвинуть Робот на 4 клетки вправо, закрасив их.
- Создайте новую стартовую обстановку, нарисовав на поле квадрат со стороной 4 клетки. Сохраните обстановку как стартовую.
- Создайте новую стартовую обстановку, нарисовав на поле коридор с проходами в стенах. Сохраните обстановку как obst2.fil. Смените стартовую обстановку на вновь созданную.
Занятие 2 (2 часа) Урок 1.
Тема : Ветвление и последовательная детализация алгоритма.
Разбор задач КИМов с использованием исполнителя Робот.
использовать Робот
алг ким 2009
нач
если не снизу свободно
то вправо
все
если не снизу свободно
то вправо
все
если не снизу свободно
то вправо
все
кон
использовать Робот
алг ким 2010
нач
если не снизу свободно
то вправо
все
если не снизу свободно
то вправо
все
если не снизу свободно
то вправо
все
кон
Пр. раб. №14. Составление и отладка алгоритмов ветвления
Задания. См. Приложение.
Занятие 3. Циклические алгоритмы. Урок 1-2
Цель: раскрыть сущность понятия цикла в алгоритмах, показать формы записи циклов алгоритмах, дать навыки создания и записи циклических алгоритмов.
Пр. раб. №15. Составление и отладка циклических алгоритмов
1.Составьте алгоритм, закрашивающий все внутренние клетки, прилегающие к стене.
использовать Робот
алг
нач
нц пока справа свободно
закрасить; вправо
кц
нц пока снизу свободно
закрасить; вниз
кц
нц пока не снизу свободно
закрасить; влево
кц
кон
2.Составить алгоритм, закрашивающий все клетки между Роботом и стеной. Расстояние до стены неизвестно.
использовать Робот
алг
нач
нц пока справа свободно
вправо; закрасить
кц
кон
3.Составить алгоритм, закрашивающий все клетки, находящиеся между двумя стенами.
использовать Робот
алг уч3
нач
нц пока (не сверху свободно) или (не снизу свободно)
вправо
если (не сверху свободно) и (не снизу свободно)
то
закрасить
все
кц
кон
4.Составить алгоритм, закрашивающий все клетки вокруг прямоугольной стены.
алг уч4
нач
закрасить;вверх
нц пока не справа свободно
закрасить;вверх;
кц
закрасить;вправо
нц пока не снизу свободно
закрасить;вправо;
кц
закрасить;вниз
нц пока не слева свободно
закрасить;вниз;
кц
закрасить;влево
нц пока не сверху свободно
закрасить; влево;
кц
кон
использовать Робот
алг уч5
нач
вправо
нц пока не снизу свободно
закрасить; вправо
кц
закрасить; вниз
нц пока слева свободно
закрасить; влево
кц
нц пока не слева свободно
закрасить; вниз
кц
закрасить;влево;закрасить; вверх;
нц пока сверху свободно
закрасить; вверх
кц
нц пока не сверху свободно
закрасить; влево
кц
кон
Занятие 4 Урок 1
Вспомогательные алгоритмы .
Цель: ввести понятие основного и вспомогательного алгоритма; объяснить правила использования вспомогательного алгоритма; разобрать примеры алгоритмов с использованием вспомогательного.
План урока
1.Ввод новых терминов (основного и вспомогательного алгоритма, вызова) и объяснение новых понятий.
2.Разбор примеров решения задач с применением вспомогательного алгоритма.
При решении некоторых задач удобно разбить их на более мелкие подзадачи, каждую из которых можно оформит как самостоятельный алгоритм. В этом случае сначала составляется так называемый основной алгоритм, в котором для решения подзадач используются вызовы вспомогательных алгоритмов, которые дописываются позднее. Такой способ решения называется методом последовательного уточнения. Он позволяет работать над проектом группе программистов, каждый при этом решает свою подзадачу.
В процессе решения задачи каждый вспомогательный алгоритм может при необходимости быть разбит на более мелкие вспомогательные алгоритмы.
Команда выполнения вспомогательного алгоритма называется вызовом и записывается в теле основного алгоритма.
Один и тот же алгоритм может рассматриваться как основной и вспомогательный по отношению к другим алгоритмам. В алгоритмическом языке сначала записывается основной алгоритм, ниже подряд записываются вспомогательные.
Задача1:
Робот находится в верхнем левом углу поля. Стен и закрашенных клеток нет. Составить алгоритм, с использованием вспомогательного, рисующий четыре крестика на одной горизонтали. Конечное положение Робота может быть произвольным.
Решение
Разбор на доске:
Задача2. Робот находится в верхнем левом углу поля. Стен и закрашенных клеток нет. Составьте алгоритм, который закрашивает в шахматном порядке квадрат 8 х 8. Конечное положение Робота может быть произвольным.
Занятие 4 Урок 2
Практическая работа на ПК «Решение задачи с использованием вспомогательных алгоритмов» .
Цель : привить практические навыки построения алгоритмов методом последовательного уточнения.
План урока
1.Задание полностью проходит за ПК. Учащиеся получают задания и выполняют их в программной среде Кумир. Результаты Работы сохраняются в виде файлов для последующей проверки.
Задача1 . Робот находится в нижнем левом углу поля. Стен и закрашенных клеток нет. Составьте алгоритм, который закрашивает 6 вертикальных полос одинаковой длины в 6 клеток. Конечное положение Робота может быть произвольным.
Задача2 .Используя вспомогательные, составьте алгоритм для закрашивания клеток, образующих число 1212.
Домашнее задание : Придумайте алгоритм, рисующий следующее изображение: Для решения задачи примените два вспомогательных алгоритма.
Занятие 5 Урок 1-2
Контрольная работа
«Составление алгоритма в среде исполнителя Робот».
Цель: проверить полученные знания по созданию и умению анализировать алгоритмы в программной среде Кумир.
Задания для контрольной работы делятся по уровням сложности и включает в себя 3 задачи с исполнителем Робот (1 и 2 задача –на ветвление и циклы, 3 задача с- на использование вспомогательного алгоритма.) Тексты заданий приводятся в приложении.
Исходные и конечные обстановки и созданные алгоритмы записываются в виде файла.
Оценка выставляется соответственно уровню сложности задания. Ученик вправе сам выбрать тип задания.
1. Введение
система "КуМир" (название происходит от слов "Комплект Учебных Миров"), с которой вас познакомит данный электронный вариант учебника.
Разработчики языка "КуМир" преследовали цель создать простой язык для начального курса информатики, отвечающий современной технологии программирования и допускающий производственное использование. За основу был взят школьный алгоритмический язык. Язык был дополнен некоторыми возможностями, превращающими его из учебного в производственный. В языке есть:
типы цел, вещ, лит
; традиционный набор операций над данными этих типов (включая операции над строками и стандартный набор математических функций);
массивы (таб
) указанных типов; структурные управляющие конструкции циклов, ветвление и др.
КуМир открыт - подключение внешних исполнителей обогащает язык новыми возможностями: от управления базами данных и работы с геометрическими объектами до расширения множества допустимых числовых типов (при этом язык позволит смешивать в выражениях новые типы с уже существующими числовыми типами).
Современная технология программирования учит разбивать программу не только на подпрограммы, но и на более крупные единицы: наборы программ, работающих над общими данными. В разных языках программирования такие единицы называются по-разному, в КуМире такая единица называется "Исполнитель". Понятие исполнителя чрезвычайно важно в практической работе , и должно быть введено на возможно более ранних стадиях обучения.
Опыт использования КуМира в преподавании и для разработки учебного программного обеспечения показал, что язык прост в изучении и вместе с тем достаточно мощен для расширения широкого класса производственных задач.
Подобно Е-практикуму, КуМир является интегрированной системой, включающей текстовый редактор, инкрементальный компилятор с нулевым временем ответа, а так же простой и удобный отладчик. Хорошее название для системы такого рода - "Редактор-компилятор": пока вы вводите вашу программу, компилятор ее обрабатывает, и в любой момент программа готова к выполнению без малейшей задержки.
2. Имена и типы величины. Операции КуМира
В записи имен переменных могут быть использованы любые символы русского и латинского алфавита , а так же цифры. Имя не должно начинаться с цифры. На длину имен в системе КуМир строгих ограничений не накладывается, но для удобства редактирования и во избежание переполнения строк переменным и алгоритмам не стоит давать слишком длинные имена. Обычно имя подбирается так, чтобы можно было понять, для чего предназначен алгоритм. При редактировании программ также следует помнить о том, что русские и латинские буквы, сходные по написанию, различаются ЭВМ. Например, если при описании переменной с именем А пользователь набрал "А" на латинском алфавите, а в тексте алгоритма пытается обратиться к этой переменной, набирая ее имя на русском алфавите, то в данной строке на "полях" появится сообщение "имя не определено". |
Постоянная величина (константа) не изменяет своего значения в ходе выполнения алгоритма.
Переменная величина может изменять значение в ходе выполнения алгоритма.
Выражение
- запись, определяющая последовательность действий над величинами. Выражение может содержать константы, переменные, знаки операций, функции.
Для записи выражений в КуМире используются следующие символы:
Для обозначения знаков логических операций используются символы:
= равно;
< > не равно;
< меньше;
> больше;
< = меньше или равно;
> = больше или равно;
Для записи сложных условий используются такие операции как: И
, ИЛИ, НЕ.
И -
одновременное выполнение перечисленных условий (Х > 0 и Х < = 2);
ИЛИ
- выполнение хотя бы одного из условий (Х > 0 или Y > 0);
НЕ
- отрицание.
3. Встроенные функции языка КуМир
Приведем пример встроенных функций:
Обращение | Функция | Типы |
|
Аргумента | Функции |
||
SIN (X) COS (X) TG (X) EXP (X) LN (X) ABS (X) SQRT (X) MOD (A, B) INT (X) ПИ | синус х косинус х тангенс х | вещ | вещ |
Пример записи арифметических выражений на алгоритмическом языке:
4. Команды ВВОДА / ВЫВОДА информации
Часто требуется организовать обмен информацией ("диалог") между человеком и ЭВМ в процессе выполнения алгоритма. Для этого в алгоритмическом языке есть специальные команды ВЫВОДА информации из памяти ЭВМ на экран и ВВОДА информации с клавиатуры (от человека) в память ЭВМ.
Команда ВВОДА -
команда, по которой значения переменных задаются через устройства ввода (клавиатура).
Команда ВЫВОДА
- команда, по которой значение величины отражается на устройстве вывода компьютера (экран монитора).
Поскольку в алгоритмическом языке для запоминания информации используются величины, то в командах ввода / вывода указываются имена величин, значения которых надо вывести (показать на экране) или ввести (запомнить в памяти ЭВМ).
Пример:
Служебное слово НС (новая строка) указывает ЭВМ, что информация должна выводиться на новую строку.
5. Команда присваивания. Создание и редактирование программ линейной структуры
Для того чтобы запомнить или изменить значение величины, в алгоритмическом языке есть специальная команда - команда присваивания , которая записывается в виде:
ИМЯ ВЕЛИЧИНЫ: = ВЫРАЖЕНИЕ
Знак " : = " (двоеточие, а потом равенство) называется знаком присваивания и читается как "присвоить" (например, команда " n: = e" читается " n присвоить е"). При выполнении команды присваивания ЭВМ сначала вычисляет записанное в правой части выражение (заменяя имена величин на их значения), а потом полученное значение выражения записывает в память.
Алгоритмы, представляющие собой простую последовательность действий, называются алгоритмами линейной структуры.
Рассмотрим процесс создания линейного алгоритма на примере вычисления выражения:
1. Вычислить сумму двух чисел
2. Написать программу нахождения гипотенузы прямоугольного треугольника по двум данным катетам
3. Найти объем куба, если известна его сторона
6. Создание и редактирование программ разветвляющейся структуры
Решение задач не всегда можно представить в виде линейного алгоритма. Существуют задачи, в которых требуется организовать выбор выполнения последовательности действий в зависимости от каких-либо условий. Такие алгоритмы называются алгоритмами разветвляющейся структуры. В системе программирования КуМир для создания алгоритма разветвляющейся структуры предусмотрены конструкции "ЕСЛИ - ТО - ИНАЧЕ - ВСЕ" и "ВЫБОР - ПРИ - ВСЕ".
Команда ветвления: ЕСЛИ - ТО - ИНАЧЕ - ВСЕ
Команда ветвления - разделяет алгоритм на два пути в зависимости от некоторого условия; затем исполнение алгоритма выходит на общее продолжение. Ветвление бывает полное и неполное.
Графическая схема выполнения конструкции "если "
|
|
Служебные слова "если
", "то
", "иначе
" имеют обычный смысл. Слово "все
" означает конец конструкции. Между "то
" и "иначе
" - в одной или нескольких строках - записывается последовательность команд алгоритмического языка (серия 1). Между "иначе
" и "все
" записывается другая последовательность команд (серия 2). Серия 2 вместе со служебным словом "иначе
" может отсутствовать. При выполнении конструкции "если
" ЭВМ сначала проверяет условие, записанное между "если
" и "то
". В результате проверки получается либо ДА
, либо НЕТ.
Если получится ДА,
то выполняется СЕРИЯ 1, а если НЕТ, -
то СЕРИЯ 2 (если она есть) .
Если условие не соблюдается (получится НЕТ
), а серия 2 вместе с "иначе
" отсутствует, то ЭВМ сразу переходит к выполнению команд, записанных после слова "все
".
7. Виды циклов в системе программирования КуМир
Алгоритмы, отдельные действия которых многократно повторяются, называются алгоритмами циклической структуры. Совокупность действий алгоритма, связанную с повторением, называют циклом.
Команда цикла
обеспечивает повторное выполнение последовательности команд (тела цикла) по некоторому условию.
Для программирования алгоритмов циклической структуры в системе программирования КуМир предусмотрено два вида циклов: цикл с предусловием (цикл пока) и цикл с параметром (цикл для).
Цикл с предусловием (цикл пока)
Цикл с предусловием (цикл пока) - цикл, выполнение которого повторяется, пока истинно условие цикла. Служебные слова НЦ (начало цикла) и КЦ (конец цикла)пишутся строго одно под другим и соединяются вертикальной чертой. Правее этой черты записывается повторяемая последовательность команд (тело цикла).
|
|
При его выполнении ЭВМ циклически повторяет следующие действия:
а) проверяет записанное после слова пока
условие;
б) если условие не соблюдается (условие ложно), то выполнение цикла завершается и ЭВМ начинает выполнять команды, записанные после КЦ
. Если же условие соблюдается (условие истинно), то ЭВМ выполняет тело цикла, снова проверяет условие и т. д.
Если условие в цикле пока
не соблюдается с самого начала, то тело цикла не выполняется ни разу.
Замечание
. Выполнение цикла пока
может и не завершиться, если условие все время будет истинным (эту ситуацию принято называть зацикливанием). Поэтому во избежание подобных ситуаций в теле цикла должны содержаться команды изменения условия.
Дано целое положительное число N. Вычислить факториал этого числа: N! = 1 * 2 * 3 * ... * N.
Цикл с параметром (цикл для)
Цикл с параметром (цикл для) - повторное выполнение тела цикла, пока целочисленный параметр пробегает множество всех значений от начального (i1) до конечного (in):
|
|
Здесь i - переменная целого типа, называемая параметром цикла: i1, in - начальное и конечное значения параметра цикла, которые могут быть заданы либо произвольными целыми числами, либо выражениями с целыми значениями; h - шаг изменения значения параметра цикла, значением шага может быть любое целое число (как положительное, так и отрицательное). Запись "шаг h" в первой строке может вообще отсутствовать, при этом по умолчанию значение шага принимается равным 1.
При выполнении цикла для,
его тело выполняется для i = i1, i = i1 + h, i = i1 + 2*h, . . . , i = in. Правила алгоритмического языка допускают задание любых целых i1, in, h. В частности, in может быть меньше i1. Если при этом значение h < 0, то цикл выполняется нужное количество раз, а если h имеет положительное значение, то этот случай не считается ошибочным - просто тело цикла не будет выполнено ни разу, а ЭВМ сразу перейдет к выполнению команд, записанных после КЦ
. При h = 0 происходит зацикливание.
Пример: Дано целое положительное число N. Вычислить факториал этого числа: N! = 1 * 2 * 3 * ... * N.
8. Алгоритмы рекуррентных выражений
В математике и информатике часто встречаются последовательности, в которых каждый последующий член вычисляется через предыдущие.
В арифметической прогрессии, например, каждый следующий член равен предыдущему, увеличенному на разность прогрессии:
ai = ai-1 + d
В последовательности 1, 1, 2, 3, 5, 8, 13, ... (она называется последовательностью Фибоначчи ) каждый следующий член равен сумме двух предыдущих. Для этой последовательности
ai = ai-1 + ai-2 , a1 = a2 =1
Формулы, выражающие очередной член последовательности через один или несколько предыдущих членов, называются рекуррентными соотношениями .
9. Табличные величины и работа с ними
Для записи алгоритмов, работающих с большим объемом информации, в алгоритмическом языке существуют специальные табличные величины, называемые таблицами (массивами).
Табличные величины состоят из других величин, как правило, целых или вещественных, называемых элементами. Элементы в таблице могут быть расположены по-разному. В алгоритмическом языке системы программирования КуМир используются 2 наиболее часто встречающихся вида таблиц: линейные и прямоугольные таблицы.
Работа с линейными таблицами (одномерными массивами)
Как и любая величина, линейная таблица занимает место в памяти ЭВМ, имеет имя, значение и тип. В КуМире используются таблицы целого (целтаб) и вещественного (вещтаб) типов. Например:
|
Запись целтаб А [ 1: 5 ] означает, что величина А является таблицей (таб), состоящей из целых (цел) чисел, элементы данной таблицы имеют индексы от1 (нижняя граница) до 5 (верхняя граница). Значение А - это пять целых чисел: 3, 15, 0, -10,101.
Элементы таблицы отдельных имен не имеют. Для обозначения i-го элемента таблицы А используется запись А [ i ]. Например, при выполнении команды А [ 3 ] : = A [ 2 ] + A [ 4 ] ЭВМ подставит вместо А [ 2 ] и А [ 4 ] значения 2-го и 4-го элементов таблицы А, т. е. числа 15 и -10, сложит их и присвоит полученное значение 3-му элементу, таким образом, на месте 3-го элемента в таблице вместо 0 появится значение 5.
В качестве значений границ таблицы могут быть использованы любые (как положительные, так и отрицательные) целые числа, а также 0. Значение нижней границы должно быть меньше значения верхней границы, в случае их равенства таблица считается состоящей из одного элемента. Если в описании таблицы из-за описки нижняя граница окажется больше верхней, например, целтаб [ 3: 1], то это не будет считаться ошибкой, и при вводе алгоритма никаких сообщений на "полях" не появится. В этом случае будет считаться, что в этой таблице нет ни одного элемента, и при первом же обращении к этой таблице появится сообщение "плохой индекс".
Задача.
Работа с прямоугольными таблицами (матрицами)
Как и линейная таблица, матрица занимает место в памяти ЭВМ, имеет имя, значение и тип. В КуМире используются таблицы целого (целтаб) и вещественного (вещтаб) типов.
Запись целтаб А [ 1: 5, 1:2 ] означает, что величина А является таблицей (таб), состоящей из целых (цел) чисел, элементы данной таблицы имеют индексы от (первый столбец, первая строка) до (последний столбец, последняя строка). Значение А - это десять целых чисел: 3, 15, 0, -10, 101, 200, -45, 50, 10, 222.
Элементы таблицы отдельных имен не имеют. Для обозначения i-го элемента таблицы А используется запись А [ i, j ]. Например, при выполнении команды А [ 3, 1 ] : = A [ 2, 1 ] + A [ 4, 1 ] ЭВМ подставит вместо А [ 2, 1 ] и А [ 4, 1 ] значения 2-го и 4-го элементов первого столбца таблицы А, т. е. числа 15 и -10, сложит их и присвоит полученное значение 3-му элементу в первой строке таким образом, на месте 3-го элемента первой строки в таблице вместо 0 появится значение 5.
В качестве значений границ таблицы могут быть использованы любые (как положительные, так и отрицательные) целые числа, а также 0. Значение нижней границы должно быть меньше значения верхней границы, в случае их равенства таблица считается состоящей из одного элемента. Если в описании таблицы из-за описки нижняя граница окажется больше верхней, например, целтаб [ 3: 1, 5: 2], то это не будет считаться ошибкой, и при вводе алгоритма никаких сообщений на "полях" не появится. В этом случае будет считаться, что в этой таблице нет ни одного элемента, и при первом же обращении к этой таблице появится сообщение "плохой индекс".
Задача. В заданной таблице В определить индекс и значение максимального элемента.
Приложение: Задачи
Линейные алгоритмы
Задача №1
Найдите сумму двух чисел - а и b
Решение:
алг
сумма
нач
вещ
a, b, c
вывод
" введите значение 2 чисел"
ввод
a, b
с:= a + b
вывод
нс
, " сумма чисел",a,"и",b,"равна",c
кон
Задача №2
Найдите разность двух чисел
Решение:
алг
разность
нач
вещ
a, b, c
вывод
" введите значения переменных "
ввод
a, b
с:= a - b
вывод нс,
" разность чисел",a,"и",b," равна",c
кон
Задача №3
Найдите произведение двух любых натуральных чисел
Решение:
цел a, b, c
алг
произведение
нач
вывод
"
введите два числа"
ввод
a,
b
c: =
a +
b
вывод нс,
"
произведение чисел",a,"и",b"равно",c
кон
Задача №4
Найдите частное двух натуральных чисел
Решение:
вещ a, b, c
алг
частное
нач
вывод "
введите делимое и делитель"
ввод
a, b
c:= a / b
вывод нс,
" частное чисел",a,"и",b,"равно",c
кон
Задача №5
Найдите среднее арифметическое пяти произвольных чисел
Решение:
вещ a, b, c, d, e, f
алг
арифметическое
нач вещ
a, b, c, d, e, f
вывод
" введите 5 любых чисел"
ввод
a, b, c, d, e
f:=(a + b + c + d + e)/ 5
вывод нс
," среднее арифметическое 5 чисел равно", f
кон
Ветвление
Задача №1
Найдите среди 3 целых чисел наибольшее (числа произвольные)
алг
максимум
нач цел
а, б, в
вывод
" введите три произвольных числа"
ввод
а, б, в
если
а>б>с
то вывод нс
," максимальным числом является", а
все
если
а<б>с
то вывод нс
," максимальным числом является", б
все
если
а<б<с
то вывод нс
," максимальным числом является", с
все
кон
Задача №2
Дано два произвольных числа. Если первое число больше второго, то ему присвоить их сумму, а второму числу их произведение. Если же второе число больше первого, то первому числу присвоить их произведение, а второму их сумму.
алг
условие
нач вещ
а, б
вывод
" введите два числа"
ввод
а, б
если
а > б
то
а:= а + б
б:= а * б
иначе
а:= а * б
б:= а + б
вывод нс
, а, б
кон
Задача №3:
Найдите среди 4 произвольных чисел минимальное
Решение:
алг
минимум
нач вещ
а, б, с, е
вывод
" введите 4 произвольных числа"
ввод
а, б, с. е
если
а>б>с>е
то вывод нс
," максимальное число-",а
все
если
а<б>c>е
то вывод нс
,"максимальное число -",б
все
если
а<б<с>е
то вывод нс
," максимальное число -", с
все
если
а<б<с<е
то вывод нс
, " максимальное число -", е
все
кон
Задача №4
Даны 2 катета (2 см и 2 см) равнобедренного треугольника и его основание (2.82 см). Определить, является ли треугольник прямоугольным.
Решение:
алг
треугольник
нач вещ
я, ч, с
я:= 2
ч:= 2
с:= 2.82
если
с**2= (я**2)+(ч**2)
то вывод
" истина"
иначе вывод
" ложь"
все
кон
Задача №5
Вывести сообщение " истина", если произведение двух отрицательных чисел больше ноля, иначе вывести сообщение " ложь"
Решение:
алг
отриц
нач вещ
я, ч, с, м
вывод
" введите два отрицательных числа"
ввод
я, ч
с:=0
м:= я * ч
если
м>с
то вывод нс
," истина"
иначе вывод нс
,"ложь"
все
кон
Цикл «для»
Задача №1
Найдите Факториал натурального числа n (Факториалом натурального числа n является произведение всех натуральных чисел на промежутке от 1 до n ) Решение:
алг
факториал
нач вещ
а. б
цел
н, и
вывод
ввод
н
а:= 1
нц для
и от
1 до
н
вывод нс
,
" введите число"
ввод
б
а:= а * б
кц
вывод нс
,
" факториал ",н,"целых чисел равен", а
кон
Задача №2
Найдите максимальное значение среди
n - целых чисел
Решение:
алг
максимум
нач вещ
а, б
цел
и, н
вывод
" введите количество целых чисел для сравнения"
ввод
н
а:=0
нц для
и от
1 до
н
вывод нс
,
"введите число"
ввод
б
если
б>а
то
а:=б
все
кц
вывод нс
,
" максимальным числом среди данных является число", а
кон
Задача №3
Найдите среди
n-целых чисел количество отрицательных
Решение:
алг
совпадение
нач вещ
а, б, с
цел
н, и, з
вывод
"
введите количество натуральных чисел"
ввод
н
вывод нс
,
"введите число"
ввод
б
н:= н - 1
з:= 0
нц для
и от
1 до
н
вывод нс
,"
введите число"
ввод
с
если
с = б
то
з:= з + 1
все
кц
вывод нс
,
кон
Задача №4
Последовательно вводятся n-целых чисел. Найти количество совпадений с первым числом
Решение:
нач вещ
а, б, с
цел
н, и, з
вывод
" введите количество натуральных чисел"
ввод
н
вывод нс
,
"введите число"
ввод
б
н:= н - 1
з:= 0
нц для
и от
1 до
н
вывод нс
,
" введите число"
ввод
с
если
с = б
то
з:= з + 1
все
кц
вывод нс
,
" количество совпадений с первым числом равно", з
кон
Задача №5
Последовательно вводятся n-целых чисел. Найти разницу между максимальным и минимальным значениями данных чисел
Решение:
алг
разница
нач вещ
а. б, с, д
цел
н, и
вывод
"Введите количество чисел"
ввод
н
а:= 0
с:= 0
нц для
и от
1 до
н
вывод нс
,
"введите число"
ввод
д
если
д>с
то
с:= д
все
если
д<а
то
а:= д
все
кц
б:= с - а
вывод нс
,
"разница между минимальным и максимальным значениями равна", б
кон
Цикл «пока»
Задача №1
Найти сумму всех чисел на промежутке от 1 до 5
Решение:
алг
числа
нач вещ
а, б
вывод
" введите два таких числа, что второе число больше первого"
ввод
а, б
нц пока
а<б
а:= а + 1
кц
вывод нс
, а
кон
Задача №2
Дано два таких числа, что второе число больше первого. Надо прибавлять к первому числу по 1, пока оно не будет равно второму числе, вывести его на монитор.
Решение:
алг
сумма
нач вещ
а, б, с
вывод
" введите промежуток суммирования"
ввод
а, б
с:= а
нц пока
а < б
а:= а + 1
с:= с + а
кц
вывод нс
," сумма чисел на данном промежутке равна", с
кон
Задача №3
Дано два произвольных числа. Пока их произведение меньше 100, увеличивать каждое число на 2 и вывести конечные числа на монитор
Решение:
алг
произведение
нач вещ
а, б, с
вывод
" введите два произвольных числа "
ввод
а, б
с:= 100
нц пока
а * б < с
а:= а + 2
б:= б + 2
кц
вывод нс
, а, б
кон
Одномерные массивы
Задача №1
Заполните массив случайными числами и выведите его элементы Решение:
алг
массив 2
нач цел
n, i
вещ
b, max
вещтаб
а [ 1:n ]
вывод
" заполните массив "
ввод
n
max:= 0
нц для
i от
1 до
n
вывод нс
,
" введите элемент массива"
ввод
b
если
b > max
то
max:= b
все
кц
вывод нс
,
кон
Задача №2
Найдите максимальный элемент массива и выведите его на монитор Решение:
алг
массив 2
нач
цел
n, i
вещ
b, max
вещтаб
а [ 1:n ]
вывод
" заполните массив "
ввод
n
max:= 0
нц для
i от
1 до
n
вывод нс
,
" введите элемент массива"
ввод
b
если
b > max
то
max:= b
все
кц
вывод нс
,
" максимальный элемент данного массива равен", max
кон
Задача №3
Найдите сумму элементов одномерного массива Решение:
алг
сумма
нач
цел
n, i
вещтаб
а [ 1:n ]
вещ
b, z
вывод
" введите количество элементов массива "
ввод
n
z:= 0
нц для
i от
1 до
n
вывод нс
,
" введите элемент массива"
ввод
b
z:= z + b
кц
вывод нс
,
" сумма",n,"элементов массива равна", z
кон
Задача №4
Найдите произведение элементов одномерного массива Решение:
алг
произведение
нач цел
i, n
вещ
s, d
вещтаб
а [ 1:n ]
вывод
" введите количество элементов массива"
ввод
n
d:= 1
нц для
i от
1 до
n
вывод нс
,
"введите число"
ввод
s
d:= d * s
кц
вывод нс
,"
произведение", n, " элементов равно", d
кон
Массивы
Задача №1
Заполните матрицу случайными числами Решение:
алг
массив двумерный
цел
n, j, h, v
нач вещтаб
а
вывод
" введите количество элементов таблицы"
ввод
n
h:= 0
v:= 0
вывод нс
,
" заполните массив"
ввод
a
нц для
j от
1 до
n
если
а > 0
то
h:= h + 1
иначе
v:= v + 1
кц
вывод нс
,
а
кон
Задача №2
Вычислите количество положительных и отрицательных элементов первой строчки матрицы Решение:
алг
массив 2
нач
вещ
b, x, z
цел
i, n
вывод
ввод
n x:= 0
z:= 0
нц для
i от
1 до
n
вывод
нс
," введите число"
ввод
b
если
b > 0
то
x:= x + 1
иначе
z:= z + 1
все
кц
вывод нс
,
вывод нс
,
кон
Задача №3
Вычислите сумму элементов каждой строки Решение:
алг
массив 3
нач вещ
b, x, z, y
цел
i, n
вещтаб
a[ 1:n, 1:n ]
вывод
" введите количество столбцов"
ввод
n x:= 0
z:= 0
нц для
i от
1 до
n
вывод нс
,
" заполните массив"
ввод
a[ 1:n, 1:n ]
b:= a[ 1,i ]+a[ n, i ]
кц
вывод нс
,
" количество положительных чисел равно",x
вывод нс
,
" количество отрицательных чисел равно", z
кон
Задача №4
Вычислите сумму трех чисел второй строчки матрицы размером три на три Решение:
алг
матрица
нач
цел
i, n
вещтаб
a[ 1:3, 1:3]
вывод
" заполните массив"
ввод
a[ 1:3, 1:3 ]
n:= 0
нц
для
i от
1 до
3
n:= n + a[ 2,i ]
кц
вывод
нс
,
"сумма чисел второй строки массива равна", n
кон
Цели : сформировать умение записи, исполнения и отладки алгоритмов с использованием цикла пока ; добиться понимания использования цикла пока ; развивать умение анализировать.
Ученики должны знать : правила записи и исполнения цикла пока ; свойства цикла пока .
Ученики должны уметь : использовать при составлении алгоритмов конструкцию цикла пока и записывать ее на языке Кумир, владеть методами отладки: по шагам, непрерывно.
Метод обучения: объяснительно-иллюстративный и репродуктивный (на этапе объяснения нового материала), репродуктивный с элементами проблемного (этап закрепления материала).
Обеспечение урока:
- система Кумир;
- интерактивная доска;
- мультимедийный проектор;
- карточки-задания.
Ход урока
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 после выполнения операторов:
Литература : А.Г.Кушниренко «Основы информатики и вычислительной техники».
Алгоритм рисование спирали:
использовать Чертежник
алг
нач
. сместиться в точку
(3,3)
. опустить перо
. виток(1); виток(3); виток(5); виток(7); виток (9)
. поднять перо
кон
алг
виток(арг
вещ
а)
нач
. сместиться на вектор
(а, 0)
. сместиться на вектор
(0, -а)
. сместиться на вектор
(-а-1,0)
. сместиться на вектор
(0, а+1)
кон
Обратите внимание на блок команд:
Виток(1); виток(3); виток(5); виток(7); виток (9)
Вспомогательный алгоритм «виток(арг вещ а) » вызывается 5 раз, но вызывать его в цикле «N раз» нельзя, т. к. каждый раз он вызывается с разными значениями аргумента.
Но можно заметить, что значения аргумента изменяются от 1 до 9, каждый раз увеличиваясь на 2. Значит, нам может помочь цикл со счётчиком . Так же такой цикл называется цикл «для» .
Цикл
со счётчиком
- цикл, в котором некоторая переменная изменяет
своё значение от заданного начального значения до конечного значения с
некоторым шагом, и для каждого значения этой переменной тело цикла
выполняется один раз.
Обычно этот цикл применяется в том случае, если нужно перебрать какие-то значения и для каждого из них выполнить какие-то действия.
Общий вид цикла со счётчиком:
нц для
<счетчик> от
<нач. знач.> до
<кон. знач.> [шаг
<знач.>]
<тело цикла (последовательность команд)>
кц
Указывать шаг необязательно, если он не указан, то считается равным единице.
Теперь алгоритм «спираль» можем переписать таким образом:
использовать
Чертежник
алг
нач
. сместиться в точку
(3,3)
. опустить перо
. цел
размер
. нц для
размер от
1 до
9 шаг
2
. . виток(размер)
. кц
. поднять перо
кон
алг
виток(арг
вещ
а)
нач
. сместиться на вектор
(а, 0)
. сместиться на вектор
(0, -а)
. сместиться на вектор
(-а-1,0)
. сместиться на вектор
(0, а+1)
кон
В этом примере переменная-счетчик «размер» будет получать значения: 1, 3, 5, 7, 9. Т.е. цикл выполниться 5 раз. Для каждого значения переменой «размер» будет один раз выполнено тело цикла, в нашем примере это вызов вспомогательного алгоритма «виток(арг вещ а) ».
До первого использования переменной ее нужно описать, т. е. указать какого она типа. Это делается в нашей программе в строчке «цел размер», т. е. мы указываем что будем использовать переменную «размер» для хранения целых чисел, и следовательно для нее нужно выделить память. Подробнее о переменных мы будет говорить немного позднее.
Блок-схема такого алгоритма выглядит так:
Рассмотрим еще один пример:
Давайте для начала вспомним и напишем вспомогательный алгоритм, который будет рисовать квадрат в точке (x, y). Для разнообразия для рисования будем использовать команду сместиться на вектор (в предыдущих примерах смещались в точку).
Алгоритм может быть таким:
алг
квадрат(арг
вещ
x, y, сторона)
нач
. сместиться в точку
(x, y)
. сместиться на вектор
(-сторона/2,
сторона/2)
. опустить перо
. сместиться на вектор
(сторона,
0)
. сместиться на вектор
(0,
-сторона)
. сместиться на вектор
(-сторона,
0)
. сместиться на вектор
(0,
сторона)
. поднять перо
кон
Используя такой вспомогательный алгоритм, нарисуем такой рисунок:
Для этого воспользуемся циклом «для». Изучите пример программы:
использовать Чертежник
алг
рисунок1
нач
. цел
z
. нц для
z от
2 до
10 шаг
2
. . квадрат(0, 0, z)
. кц
кон
алг
квадрат(арг
вещ
x, y, сторона)
нач
. сместиться в точку
(x, y)
. сместиться на вектор
(-сторона/2,
сторона/2)
. опустить перо
. сместиться на вектор
(сторона,
0)
. сместиться на вектор
(0,
-сторона)
. сместиться на вектор
(-сторона,
0)
. сместиться на вектор
(0,
сторона)
. поднять перо
кон
В этом примере переменная «z» будет получать значения: 2, 4, 6, 8, 10. Т.е. цикл выполниться 5 раз. Для каждого значения «z» будет один раз выполнено тело цикла, в нашем примере это вызов вспомогательного алгоритма квадрат.
До первого использования переменной ее нужно описать, т. е. указать какого она типа. Это делается в нашей программе в строчке «цел z», т. е. мы указываем что будем использовать переменную «z» для хранения целых чисел, и следовательно для нее нужно выделить память. Подробнее о переменных мы будет говорить немного позднее.
Как вы обратили внимание в алгоритме использовались не только числа, но и алгебраические выражения , формулы, например «-сторона/2». В информатике эти выражения называются арифметическими . Правила языка позволяют при записи алгоритмов всюду, где можно написать число, написать и произвольное арифметическое выражение.