Алгоритмы и программирование
Урок 1-3. Понятие алгоритма. Линейные алгоритмы
Алгоритмом называется последовательность команд, понятных исполнителю, приводящая к результату за конечное количество шагов.
Основные свойства алгоритма:
Дискретность – предполагает, что алгоритм состоит из отдельных команд, к выполнению каждой из которых можно приступать только по окончании выполнения предыдущей
Результативность – алгоритм обязательно должен привести к результату
Конечность – результат будет получен за конечное количество шагов
Массовость – один и тот же алгоритм может быть применен для решения однотипных задач
Понятность – все команды, составляющие алгоритм, должны быть понятны исполнителю
Отказы
Существуют два типа отказов:
Не понимаю – команда алгоритма не входит в набор команд исполнителя
Не могу – команда понятна, но не может быть выполнена в данной ситуации
Формальный исполнитель алгоритма
Исполнитель алгоритма - человек, животное, техническое устройство или язык программирования, исполняющий алгоритм.
Формальное исполнение алгоритма – это буквальное исполнение команд, не задумываясь над их содержанием. Любой компьютер или язык программирования – формальный исполнитель.
Основные алгоритмические конструкции
Существует три основные алгоритмические конструкции:
Следование или линейный алгоритм Ветвление или ветвящийся алгоритм Цикл (повторение) или циклический алгоритмЛинейный алгоритм – такая последовательность команд, где все команды выполняются друг за другом, ни одна не повторяется и ни одна не пропускается.
Система исполнителей КУМИР.
В систему исполнителей КУМИР входят алгоритмический язык, исполнитель Робот и исполнитель Чертежник.
Алгоритм на языке КуМир записывается так:
алг
нач
· последовательность команд
Кон
После служебного слова АЛГ можно записать тип алгоритма и его имя.
Можно использовать два исполнителя – Робот и Чертежник.
Робот
Исполнитель Робот живет в клетчатом поле, клетки могут отделяться друг от друга стенами. Поле Робота можно редактировать (Инструменты – Редактировать стартовую обстановку). При этом, если вы щелкаете мышью в клетке – она закрашивается, а если между клетками – ставится стена. Изначально стен нет, а Робот стоит в правом верхнем углу.
Команды Робота: ВПРАВО, ВЛЕВО, ВПЕРЕД, НАЗАД, ЗАКРАСЬ.
Команды в алгоритме можно писать друг под другом, или в строку, но в этом случае они отделяются знаком ;
Для вызова Робота дается команда Использовать Робот. (как, впрочем, и любая другая команда)
Пример программы Робота:
использовать Робот |
По этой программе робот перейдет в середину поля.
Задание:
Вызвать Инструменты – Редактировать стартовую обстановку Робота создать такую обстановку и перевести робота из начального положения (ромбик) в конечное (звездочка)
Допишите программу так, чтобы робот, закрасив клетки, получил буквы ваших инициалов.Чертежник
предназначен для построения рисунков, чертежей, графиков на листе (поле исполнителя);
Исполнитель Чертежник может выполнять следующие шесть команд
поднять перо Переводит чертежника в режим перемещения без рисования.
опустить перо Переводит чертежника в режим перемещения с рисованием.
сместиться на вектор (dX, dY) - перемещает перо на dX вправо и dY вверх.
сместиться в точку (x, y) - перемещает перо в точку с координатами (x, y).
установить цвет - Устанавливает цвет чернил.
Допускается 9 цветов: ”черный”, ”белый”, ”красный”, ”оранжевый”, ”желтый”, ”зеленый”, ”голубой”, ”синий”, ”фиолетовый”.
надпись (ширина_знакоместа, текст)
Каждый символ рисуется шрифтом Courier New. Позиция пера в момент начала рисования рассматривается как начальная точка базовой линии рисования.
использовать Чертежник Пример использования команды СМЕСТИТЬСЯ НА ВЕКТОР. Рисуем домик:
|
Введите и выполните данные программы.
Задания:
Дорисуйте лодке парус. Под надписью поставьте еще одну – вашу фамилию. Нарисуйте ту же лодку, но командами СМЕСТИТЬСЯ НА ВЕКТОРУроки 4-6. Константы и переменные. Программы, предназначенные для вычислений
Переменные, с которыми работает КуМир-программа, подразделяются на несколько типов.
Величина каждого из типов может принимать свой набор значений. В языке КуМир
предусмотрены следующие типы величин:
∙ цел — принимает целые значения от -2 147 483 647 до 2 147 483 647 (соответстует двойному целому в языках Бейсик и Паскаль)
∙ вещ — принимает вещественные значения между −21023 и 21023
∙ лог — принимает значения да или нет (внутреннее представление – да=1, нет=0)
∙ сим — значением может быть любой символ (буква, цифра, знак)
∙ лит — значением может быть строка символов
Типы цел и вещ называются числовыми; типы сим и лит — текстовыми
Операции и функции:
Все арифметические операции соответствуют операциям на Бейсике, Паскале или ЭТ Excel: + - / *, а возведение в степень обозначается ** (например, а2 запишется а**2) корни могут быть вычислены с применением той же операции, то есть а**(1/2) – это квадратный корень, а а**(1/3) – это уже кубический корень.
Название функции Форма записи
корень квадратный sqrt(x)
абсолютная величина abs(x) и iabs(x)
синус sin(x)
косинус cos(x)
тангенс tg(x)
остаток от деления x на y (x, y — целые) mod(x, y)
частное от деления x на y (x, y — целые) div(x, y)
целая часть числа x int(x)
случайное число в диапазоне от 0 до x RND(x)
Те команды, которые мы сегодня будем использовать, интуитивно понятны. Они практически соответствуют командам, используемым в языке Паскаль.
ввод – для ввода данных в переменные, перечисленные списком через запятую. Может присутствовать только одна переменная.
вывод – для вывода текста в кавычках, значения переменной или нескольких переменных. Для перевода строки используется служебное слово (команда) нс через запятую!!!
Перед телом программы описываются переменные, которые будут использованы в программе и указывается их тип.
Пример программы на этом языке: вычисление периметра прямоугольного треугольника по известным катетам
алг треугольник |
Задания:
Ввести два числа и найти:Сумму чисел, разность чисел, результат целочисленного деления первого числа на второе, остаток от деления первого числа на второе. Обратите внимание на то, что две последние операции возможны только с целыми числами, поэтому переменные должны задаваться целочисленными
Ввести два радиуса окружностей (первый больше второго) и найти площадь кольца, образованного этими окружностями. Площадь круга вычисляется по формуле S=3.14*r2 Заданы сопротивления трех резисторов. Найти их общее сопротивление при последовательном и параллельном соединении. При последовательном соединении общее сопротивление равно сумме сопротивлений, а при параллельном надо сначала найти проводимость (сумма величин, обратных сопротивлениям, то есть равных 1/r), а уже затем общее сопротивление, которое обратно проводимости.Литерные переменные и их обработка
В литерную переменную можно поместить строку символов размером от 0 до 255 знаков. Поместить в переменную их можно присвоением значения или при помощи команды ВВОД. Далее текст, помещенный в переменную может обрабатываться. Например, тесты можно сравнивать между собой (большим считается текст, который в алфавитном порядке стоит дальше). Например, СЛОН больше, чем КИТ, а Я больше, чем СЛОН. Можно определить длину текста, то есть количество символов в нем. При этом символом является в том числе и пробел. Каждый символ в памяти занимает или 1 байт (8 бит), или 2 байта (16 бит в кодировке UNICODE). Кроме того, можно копировать из текста любые знаки, а потом записывать их в другую переменную или приписывать их к любой переменной.
- Сколько знаков содержит фраза «Если на клетке со слоном написано – ЭТО ЛЕВ – не верь глазам своим!» Сколько бит требуется для кодирования слова «Информатика» в Unicode? Придумайте 5 слов, которые больше, чем ПАР, но меньше, чем ПАРОХОД
Пример программы получения новых слов из заданного:
алг слова |
Какие слова будут получены? Напишите программу, которая из слов ГАСТРОНОМ, ВЕЗДЕХОД, ПАРАНОРМАЛЬНЫЙ создаст как можно больше слов (существительных), но не менее 5 (в словах не менее 3 букв). Любую букву можно использовать любое количество раз. Разрешено создавать имена собственные.
Урок 7-9. Вспомогательные алгоритмы
Урок 7. Алгоритмы-процедуры
Рассмотрим простейшую задачу, которую надо решить с использованием исполнителя Чертежник. Нам надо нарисовать три треугольника:
Вообще-то, задача не представляется трудной, но на ней мы разберем еще один способ организации действий – вспомогательный алгоритм или алгоритм-процедуру. Напишем алгоритм, в котором производится рисование треугольника в произвольном месте поля Чертежника. Он будет являться ВСПОМОГАТЕЛЬНЫМ, то есть процедурой. Первым должен быть написан алгоритм основной, а под ним – любое количество алгоритмов-процедур. Они, фактически, являются описанием новых команд исполнителя (в нашем случае – Чертежника). Таким образом,
использовать Чертежник |
Напишите алгоритмы получения слов «ПАПА» с использованием Робота и «МАМА» с использованием Чертежника и вспомогательных алгоритмов.
Урок 8. Алгоритмы-процедуры с параметрами
А теперь напишем процедуру, в которую можно передавать значения переменных. Повторим задачу предыдущего урока, но теперь вызов вспомогательного алгоритма Треугольник будет производиться с использованием координат Х и У. Тогда процедура будет выглядеть так:
алг треугольник (арг вещ x, y) А основной алгоритм –
|
Как видите, мы получили полноценную команду Чертежника.
Задание: нарисовать с использованием процедур с параметрами:
РОТОР или ТОПОТ
Три лодочки с парусом или три домика с крышей.
Урок 9. Самостоятельная работа
Уроки 10-12
Урок 10. Циклы. Цикл повторить N раз.
Циклом называется такая организация действий, когда часть алгоритма может быть выполнена несколько раз.
Существует три способа организации цикла: повторение N раз, цикл ПОКА и цикл ДЛЯ (обычно применяется для обработки массивов).
Во всех этих составных командах используются служебные слова НЦ – начало цикла, то есть начало той части алгоритма, которая должна повторяться, и КЦ – конец цикла. Команды, стоящие между НЦ и КЦ называются тело цикла.
Сегодня рассмотрим несколько примеров циклических алгоритмов.
Нарисуем 10 квадратиков друг за другом по горизонтали
| Напишем алгоритм для робота, который должен пройти такое поле, закрасив клетки напротив положения робота за каждой стеной:
|
Напишите программы, которые:
Нарисуют 6 домиков друг под другом. Желательно с крышей и дверью.
В том же поле робота закрасят все клетки за стенами.
Урок 11-12 Цикл ПОКА
Цикл с предусловием (цикл пока) - цикл, выполнение которого повторяется, пока истинно условие цикла. Служебные слова НЦ (начало цикла) и КЦ (конец цикла)пишутся строго одно под другим и соединяются вертикальной чертой. Правее этой черты записывается повторяемая последовательность команд (тело цикла).
|
|
При его выполнении ЭВМ циклически повторяет следующие действия:
а) проверяет записанное после слова пока условие;
б) если условие не соблюдается (условие ложно), то выполнение цикла завершается и ЭВМ начинает выполнять команды, записанные после КЦ. Если же условие соблюдается (условие истинно), то ЭВМ выполняет тело цикла, снова проверяет условие и т. д.
Если условие в цикле пока не соблюдается с самого начала, то тело цикла не выполняется ни разу.
Замечание. Выполнение цикла пока может и не завершиться, если условие все время будет истинным (эту ситуацию принято называть зацикливанием). Поэтому во избежание подобных ситуаций в теле цикла должны содержаться команды изменения условия.
На поле Робота стоит стена неизвестного размера. Робот находится над ней в какой-то клетке. Дойти до стены и закрасить все клетки над стеной.
Измените программу так, чтобы были закрашены все клетки вокруг стены |
Дополнительные задания:
1.Надо использовать команду Пока
2 Здесь надо использовать команды цикла Пока и N раз
Урок 13-15. Ветвления
Ветвлением называется такая организация действий, когда часть команд алгоритма может выполняться или не выполняться в зависимости от выполнения или невыполнения условий.
В системе программирования КуМир для создания алгоритма разветвляющейся структуры предусмотрены конструкции "ЕСЛИ - ТО - ИНАЧЕ - ВСЕ" и "ВЫБОР - ПРИ - ВСЕ".
Команда ветвления - разделяет алгоритм на два пути в зависимости от некоторого условия; затем исполнение алгоритма выходит на общее продолжение. Ветвление бывает полное и неполное.
Служебные слова "если", "то", "иначе" имеют обычный смысл. Слово "все" означает конец конструкции. Между "то" и "иначе" - в одной или нескольких строках - записывается последовательность команд алгоритмического языка (серия 1). Между "иначе" и "все" записывается другая последовательность команд (серия 2). Серия 2 вместе со служебным словом "иначе" может отсутствовать. При выполнении конструкции "если" Кумир сначала проверяет условие, записанное между "если" и "то". В результате проверки получается либо ДА, либо НЕТ. Если получится ДА, то выполняется СЕРИЯ 1, а если НЕТ, - то СЕРИЯ 2 (если она есть) .
Если условие не соблюдается (получится НЕТ), а серия 2 вместе с "иначе" отсутствует, то Кумир сразу переходит к выполнению команд, записанных после слова "все".
Пример использования полной формы ветвления:
алг четнечет |
Следующий пример показывает применение неполной формы ветвления. Она чаще всего применяется тогда, когда в случае выполнения условия нужно делать некие действия, а в случае невыполнения – никаких действий, или когда вариантов действий больше двух.
|
Обратите внимание на ветвь иначе в форме ветвления с множественным выбором. Здесь очень удобно организуется так называемая «защита от дурака» |
Вводим и выполняем все три примера. Для первого варианта предусматриваем защиту от дурака.
Дополнительные задания:
Заданы два числа. Найти число, квадрат которого больше. Ввести два числа и определить, является ли их сумма четной. Написать программу, по которой запрашивается номер дня недели и выводится его название на английском языкеУроки 16-18.
размеры стен и положение отверстий неизвестно. Закрасить все клетки над отверстиями. (цикл Пока и Если) Весьма сложное задание!!! Подсчитать и вывести количество закрашенных клеток в коридоре 
3.Самое сложное задание
Самое сложное задание!!!!!!!
В каждой клетке поля задана радиация. Пройти все поле и закрасить все клетки, в которых радиация больше 20. Вывести количество таких клеток. Если их количество превышает 10, то вывести сообщение о том, что территория непригодна для проживания. По возможности найти самую высокую радиацию в поле и вывести ее.
Самостоятельная работа по карточкам.
