Алгоритмы и программирование Урок 1 Понятие алгоритма. Линейные алгоритмы - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
4. Перечень экзаменационных тем Дисциплина «Алгоритмы и их сложность» 1 69.64kb.
Лекция 13 Фрактальные алгоритмы 1 133.02kb.
Вопросы к зачету «Теория алгоритмов» 1 7.27kb.
Алгоритмы и способы их описания Понятие алгоритма 9 1470.74kb.
Критическая секция 5 604.63kb.
Современные симметричные и ассиметричные криптосистемы 1 89.57kb.
Современные симметричные и ассиметричные криптосистемы 1 221.41kb.
Кгг. Вопросы к контрольной работе № Базовые растровые алгоритмы 1 17.62kb.
Быстрые алгоритмы и метод бве 3 264.79kb.
Контрольная работа " линейные алгоритмы" 1 86.32kb.
Бионические алгоритмы комбинатрной оптимизации 1 89.98kb.
Заместитель атамана по общим вопросам спб око «Казачья стража» 1 47.32kb.
Направления изучения представлений о справедливости 1 202.17kb.

Алгоритмы и программирование Урок 1 Понятие алгоритма. Линейные алгоритмы - страница №1/1

Алгоритмы и программирование
Урок 1-3. Понятие алгоритма. Линейные алгоритмы

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



Основные свойства алгоритма:

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

Результативность – алгоритм обязательно должен привести к результату

Конечность – результат будет получен за конечное количество шагов

Массовость – один и тот же алгоритм может быть применен для решения однотипных задач

Понятность – все команды, составляющие алгоритм, должны быть понятны исполнителю

Отказы

Существуют два типа отказов:



Не понимаю – команда алгоритма не входит в набор команд исполнителя

Не могу – команда понятна, но не может быть выполнена в данной ситуации

Формальный исполнитель алгоритма

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

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

Основные алгоритмические конструкции

Существует три основные алгоритмические конструкции:



  1. Следование или линейный алгоритм

  2. Ветвление или ветвящийся алгоритм

  3. Цикл (повторение) или циклический алгоритм

Линейный алгоритм – такая последовательность команд, где все команды выполняются друг за другом, ни одна не повторяется и ни одна не пропускается.

Система исполнителей КУМИР.

В систему исполнителей КУМИР входят алгоритмический язык, исполнитель Робот и исполнитель Чертежник.

Алгоритм на языке КуМир записывается так:

алг


нач

· последовательность команд

Кон

После служебного слова АЛГ можно записать тип алгоритма и его имя.



Можно использовать два исполнителя – Робот и Чертежник.

Робот

Исполнитель Робот живет в клетчатом поле, клетки могут отделяться друг от друга стенами. Поле Робота можно редактировать (Инструменты – Редактировать стартовую обстановку). При этом, если вы щелкаете мышью в клетке – она закрашивается, а если между клетками – ставится стена. Изначально стен нет, а Робот стоит в правом верхнем углу.

Команды Робота: ВПРАВО, ВЛЕВО, ВПЕРЕД, НАЗАД, ЗАКРАСЬ.

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

Для вызова Робота дается команда Использовать Робот. (как, впрочем, и любая другая команда)

Пример программы Робота:



использовать Робот
алг
нач
. вправо;вправо;вправо;вправо;вправо;вправо;вправо
. вниз;вниз;вниз;вниз;вниз;
кон



По этой программе робот перейдет в середину поля.

Задание:





Вызвать Инструменты – Редактировать стартовую обстановку Робота создать такую обстановку и перевести робота из начального положения (ромбик) в конечное (звездочка)



  1. Допишите программу так, чтобы робот, закрасив клетки, получил буквы ваших инициалов.

Чертежник

предназначен для построения рисунков, чертежей, графиков на листе (поле исполнителя);

Исполнитель Чертежник может выполнять следующие шесть команд

поднять перо Переводит чертежника в режим перемещения без рисования.

опустить перо Переводит чертежника в режим перемещения с рисованием.

сместиться на вектор (dX, dY) - перемещает перо на dX вправо и dY вверх.

сместиться в точку (x, y) - перемещает перо в точку с координатами (x,y).

установить цвет -Устанавливает цвет чернил.

Допускается 9 цветов: ”черный”, ”белый”, ”красный”, ”оранжевый”, ”желтый”, ”зеленый”, ”голубой”, ”синий”, ”фиолетовый”.

надпись (ширина_знакоместа, текст)

Каждый символ рисуется шрифтом Courier New. Позиция пера в момент начала рисования рассматривается как начальная точка базовой линии рисования.



использовать Чертежник
алг
нач
. установить цвет("красный")
. сместиться в точку(2,1)
. опустить перо
. сместиться в точку(1,2)
. сместиться в точку(10,2)
. сместиться в точку(9,1)
. сместиться в точку(2,1)
. поднять перо
. установить цвет("синий")
. сместиться в точку(3,-1)
. надпись(0.8,"Лодка")
кон

Пример использования команды СМЕСТИТЬСЯ НА ВЕКТОР. Рисуем домик:



использовать Чертежник
алг
нач
. установить цвет ("желтый")
. сместиться в точку(2,2)
. опустить перо
. сместиться на вектор (0,2)
. сместиться на вектор (1,1)
. сместиться на вектор (1,-1)
. сместиться на вектор (-2,0)
. сместиться на вектор (2,0)
. сместиться на вектор (0,-2)
. сместиться на вектор (-2,0)
. поднять перо
кон










Введите и выполните данные программы.

Задания:


  1. Дорисуйте лодке парус. Под надписью поставьте еще одну – вашу фамилию.

  2. Нарисуйте ту же лодку, но командами СМЕСТИТЬСЯ НА ВЕКТОР

Уроки 4-5. Константы и переменные. Программы, предназначенные для вычислений

Переменные, с которыми работает КуМир-программа, подразделяются на несколько типов.

Величина каждого из типов может принимать свой набор значений. В языке КуМир

предусмотрены следующие типы величин:

∙ цел — принимает целые значения от -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)

знак числа (-1, 0 или 1) sign(x)

синус sin(x)

косинус cos(x)

тангенс tg(x)

минимум из чисел x и y min(x,y)

максимум из чисел x и y max(x,y)

остаток от деления x на y (x, y — целые) mod(x,y)

частное от деления x на y (x, y — целые) div(x,y)

целая часть числа x int(x)

случайное число в диапазоне от 0 до x RND(x)

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



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

вывод – для вывода текста в кавычках, значения переменной или нескольких переменных. Для перевода строки используется служебное слово (команда) нс через запятую!!!

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

Пример программы на этом языке: вычисление периметра прямоугольного треугольника по известным катетам


алг треугольник
нач
. вещ катет1,катет2,гипотенуза, периметр
. вывод "введи размеры двух катетов"
. ввод катет1,катет2
. гипотенуза:=sqrt(катет1**2+катет2**2)
. периметр:=катет1+катет2+гипотенуза
. вывод "периметр прямоугольного треугольника равен ",периметр
кон


Задания:

  1. Ввести два числа и найти:

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

  1. Ввести два радиуса окружностей (первый больше второго) и найти площадь кольца, образованного этими окружностями. Площадь круга вычисляется по формуле S=3.14*r2

  2. Заданы сопротивления трех резисторов. Найти их общее сопротивление при последовательном и параллельном соединении. При последовательном соединении общее сопротивление равно сумме сопротивлений, а при параллельном надо сначала найти проводимость (сумма величин, обратных сопротивлениям, то есть равных 1/r), а уже затем общее сопротивление, которое обратно проводимости.

Урок 6. Самостоятельная работа по карточкам
Урок 7-9. Вспомогательные алгоритмы

Урок 7. Алгоритмы-процедуры

Рассмотрим простейшую задачу, которую надо решить с использованием исполнителя Чертежник. Нам надо нарисовать три треугольника:


Вообще-то, задача не представляется трудной, но на ней мы разберем еще один способ организации действий – вспомогательный алгоритм или алгоритм-процедуру. Напишем алгоритм, в котором производится рисование треугольника в произвольном месте поля Чертежника. Он будет являться ВСПОМОГАТЕЛЬНЫМ, то есть процедурой. Первым должен быть написан алгоритм основной, а под ним – любое количество алгоритмов-процедур. Они, фактически, являются описанием новых команд исполнителя (в нашем случае – Чертежника). Таким образом,



использовать Чертежник
алг
нач
. сместиться в точку(1,1)
. треугольник
. сместиться в точку(4,1)
. треугольник
. сместиться в точку(2,-1)
. треугольник
кон
алг треугольник
нач
. опустить перо
. сместиться на вектор(2,0)
. сместиться на вектор(-1,1)
. сместиться на вектор(-1,-1)
. поднять перо
кон



Напишите алгоритмы получения слов «ПАПА» с использованием Робота и «МАМА» с использованием Чертежника и вспомогательных алгоритмов.

Урок 8. Алгоритмы-процедуры с параметрами

А теперь напишем процедуру, в которую можно передавать значения переменных. Повторим задачу предыдущего урока, но теперь вызов вспомогательного алгоритма Треугольник будет производиться с использованием координат Х и У. Тогда процедура будет выглядеть так:



алг треугольник (арг вещ x,y)
нач
. сместиться в точку(x,y)
. опустить перо
. сместиться на вектор(2,0)
. сместиться на вектор(-1,1)
. сместиться на вектор(-1,-1)
. поднять перо
кон

А основной алгоритм –

использовать Чертежник
алг
нач
. треугольник(1,1)
. треугольник(4,1)
. треугольник(2,-1)
кон








Как видите, мы получили полноценную команду Чертежника.

Задание: нарисовать с использованием процедур с параметрами:

РОТОР или ТОПОТ

Три лодочки с парусом или три домика с крышей.



Урок 9. Самостоятельная работа

Урок 10. Циклы. Цикл повторить N раз.

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

Существует три способа организации цикла: повторение N раз, цикл ПОКА и цикл ДЛЯ (обычно применяется для обработки массивов).

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



Сегодня рассмотрим несколько примеров циклических алгоритмов.

Нарисуем 10 квадратиков друг за другом по горизонтали

использовать Чертежник
алг
нач
. сместиться в точку(-5,0)
. установить цвет ("желтый")
. нц 10 раз
. . опустить перо
. . сместиться на вектор (1,0)
. . сместиться на вектор (0,1)
. . сместиться на вектор (-1,0)
. . сместиться на вектор (0,-1)
. . поднять перо
. . сместиться на вектор (2,0)
. кц
кон







Напишем алгоритм для робота, который должен пройти такое поле, закрасив клетки напротив положения робота за каждой стеной:









































































































использовать Робот
алг
нач
. нц 6 раз
. . вверх
. . вверх
. . вправо
. . вниз
. . вниз
. . закрасить
. кц
кон







Напишите программы, которые:

Нарисуют 6 домиков друг под другом. Желательно с крышей и дверью.

В том же поле робота закрасят все клетки за стенами.

Урок 11-12 Цикл ПОКА

Цикл с предусловием (цикл пока) - цикл, выполнение которого повторяется, пока истинно условие цикла. Служебные слова НЦ (начало цикла) и КЦ (конец цикла)пишутся строго одно под другим и соединяются вертикальной чертой. Правее этой черты записывается повторяемая последовательность команд (тело цикла).



ris-7_1-poka_1

ris-7_1-poka_2

         При его выполнении ЭВМ циклически повторяет следующие действия:
                 а) проверяет записанное после слова пока условие;
                б) если условие не соблюдается (условие ложно), то выполнение цикла завершается и ЭВМ начинает выполнять команды, записанные после КЦ. Если же условие соблюдается (условие истинно), то ЭВМ выполняет тело цикла, снова проверяет условие и т.д.
         Если условие в цикле пока не соблюдается с самого начала, то тело цикла не выполняется ни разу.
         Замечание. Выполнение цикла пока может и не завершиться, если условие все время будет истинным (эту ситуацию принято называть зацикливанием). Поэтому во избежание подобных ситуаций в теле цикла должны содержаться команды изменения условия.

На поле Робота стоит стена неизвестного размера. Робот находится над ней в какой-то клетке. Дойти до стены и закрасить все клетки над стеной.

использовать Робот
алг
нач
. нц пока снизу не стена
. . вниз
. кц
. нц пока снизу стена
. . закрасить
. . влево
. кц
. вправо
. нц пока снизу стена
. . закрасить
. . вправо
. кц
кон



Измените программу так, чтобы были закрашены все клетки вокруг стены




Дополнительные задания:

1.Надо использовать команду Пока

p2-1p2-2p2-3

2 Здесь надо использовать команды цикла Пока и N раз



p5-1 p5-7
p9-1 p9-3
Урок 13-15. Ветвления

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

В системе программирования КуМир для создания алгоритма разветвляющейся структуры предусмотрены конструкции "ЕСЛИ - ТО - ИНАЧЕ - ВСЕ" и "ВЫБОР - ПРИ - ВСЕ".

         Команда ветвления - разделяет алгоритм на два пути в зависимости от некоторого условия; затем исполнение алгоритма выходит на общее продолжение. Ветвление бывает полное и неполное.

         Служебные слова "если", "то", "иначе" имеют обычный смысл. Слово "все" означает конец конструкции. Между "то" и "иначе" - в одной или нескольких строках - записывается последовательность команд алгоритмического языка (серия 1). Между "иначе" и "все" записывается другая последовательность команд (серия 2). Серия 2 вместе со служебным словом "иначе" может отсутствовать. При выполнении конструкции "если" Кумир сначала проверяет условие, записанное между "если" и "то". В результате проверки получается либо ДА , либо НЕТ. Если получится ДА, то выполняется СЕРИЯ 1, а если НЕТ, - то СЕРИЯ 2 (если она есть) .
          Если условие не соблюдается (получится НЕТ), а серия 2 вместе с "иначе" отсутствует, то Кумир сразу переходит к выполнению команд, записанных после слова "все".

Пример использования полной формы ветвления:



алг четнечет
нач
. цел а
. вывод "введите число"
. ввод а
. если mod(а,2)=0
. . то
. . . вывод "число четное"
. . иначе
. . . вывод "число нечетное"
. все
кон


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



алг название оценки
нач
. цел оценка
. вывод "введите оценку цифрой"
. если оценка=1
. . то
. . . вывод "КОЛ!!!"
. все
. если оценка=2
. . то
. . . вывод "ПАРА!!!"
. все
. если оценка=3
. . то
. . . вывод "ТРОЯЧОЧЕК..."
. все
. если оценка=4
. . то
. . . вывод "ХОРОШО!!!"
. все
. если оценка =5
. . то
. . . вывод "ОТЛИЧНО!ПОТРЯСАЮЩЕ!"
. все
кон






алг название оценки
нач
. цел оценка
. вывод "введи оценку цифрой"
. ввод оценка
. выбор
. . при оценка=1:вывод "кол"
. . при оценка=2: вывод "ПАРА!!"
. . при оценка=3: вывод "ТРОЯЧОК..."
. . при оценка=4: вывод "четыре!!! ХОРОШО!!!"
. . при оценка=5: вывод "ОТЛИЧНО! ПОТРЯСАЮЩЕ!"
. . иначе вывод "вы погорячились при вводе данных"
. все
.




Обратите внимание на ветвь иначе в форме ветвления с множественным выбором. Здесь очень удобно организуется так называемая «защита от дурака»



Вводим и выполняем все три примера. Для первого варианта предусматриваем защиту от дурака.

Дополнительные задания:



  1. Заданы два числа. Найти число, квадрат которого больше.

  2. Ввести два числа и определить, является ли их сумма четной.

  3. Написать программу, по которой запрашивается номер дня недели и выводится его название на английском языке

  4. размеры стен и положение отверстий неизвестно. Закрасить все клетки над отверстиями. (цикл Пока и Если)

  5. Весьма сложное задание!!! Подсчитать и вывести количество закрашенных клеток в коридоре



Самое сложное задание!!!!!!!

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




Ревность — это боязнь превосходства другого лица. Александр Дюма-сын
ещё >>