Алгоритмы и исполнители. Способы записи алгоритмов. Объекты алгоритмов.

План урока

ТЕМА: Алгоритмы и исполнители. Способы записи алгоритмов. Объекты алгоритмов.

ЦЕЛИ: 1. Повторить понятие алгоритма.

2. Повторить понятие исполнителя алгоритма.

3. Разобрать свойства алгоритмов и способы их записи.

4. Дать понятие величин и их типов.

5. Закрепить знания решением задач.

Организационный момент

1. Беседа с учащимися по вопросам (5 минут).

- что называют алгоритмом?

- кого называют исполнителем алгоритма?

- какие бывают исполнители алгоритмов?

- что называется СКИ исполнителя алгоритма?

- в каких режимах работы может работать исполнитель алгорима?

- что называется средой исполнителя?

- что называется кругом решаемых задач исполнителя?

Р.Т., стр.60, упр.102

В систему команд исполнителя Водолей входит 6 команд:

1. Наполнить сосуд А

2. Наполнить сосуд В

3. Перелить из А в В

4. Перелить из В в А

5. Вылить из А

6. Вылить из В

Объём сосуда А равен 4 литра, а сосуда В – 3 литра. Как получить 2 литра в одной из емкостей, используя не более 4 команд?

Ответ: 2424

Р.Т., стр.61, упр.103 (а)

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

1. Разбор нового материала

Свойства алгорима

Не любая инструкция, последовательность предписаний или план действий может считаться алгоритмом. Каждый алгоритм обяза­тельно обладает следующими свойствами: дискретность, понятность, определённость, результативность и массовость.

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

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

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

Свойство результативности означает, что алгоритм должен обес­печивать возможность получения результата после конечного, воз­можно, очень большого, числа шагов. При этом результатом считает­ся не только обусловленный постановкой задачи ответ, но и вывод о невозможности продолжения по какой-либо причине решения дан­ной задачи.

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

Способы записи алгоритмов

Самой простой является запись алгоритма в виде набора высказываний на обычном разговорном языке. Словесное описание имеет минимум ляется наименее формализованным. Однако алгоритм в словесной форме может оказаться очень объёмным и трудным для восприятия.

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

Школьный алгоритмический язык. Для записи алгоритмов на школьном алгоритмическом языке используется некоторое ограниченное число слов, смысл и способ употребления которых заданы раз и навсегда. Это так называемые служебные слова, которые выделяются при написании (подчёркиванием или ширным шрифтом)

Р.Т., стр.61, упр.104(а, в)

Исполнитель чертёжник действует на координатной плоскости. У него есть перо, которое может быть поднято или опущено. Определите, что будет нарисовано после выполнения Чертёжником программы:

Поднять перо

Сместиться в точку (3,1)

Опустить перо

Сместиться на вектор (2,0)

Сместиться на вектор (1,1)

Сместиться на вектор (-4,0)

Сместиться в точку (3,1)

Поднять перо

Сместиться на вектор (1,1)

Опустить перо

Сместиться на вектор (0,3)

Сместиться на вектор (1,-2)

Сместиться на вектор (-1,-1)

В) Чертёжнику был дан для исполнения следующий алгоритм:

Нц 3 раз

Сместить на вектор (0,-1)

Сместиться на вектор (-2,0)

Сместиться на вектор (2,-1)

Кц

Какую команду надо выполнить Чертёжнику, чтобы вернуться в исходную точку, из которой он начал движение?

Блок-схема представляет собой графический документ, который даёт представление о порядке работы алгоритма. Здесь шаги изображаются в виде геометрических фигур. Направления линий связи слева направо и сверху вниз считаются стандартными, и линии связи изображаются без стрелок, в противном случае – со стрелками.

Обозначения в блок схемах:

Р.Т., стр.68, упр.112

Представьте с помощью блок-схемы алгоритм решения следующей задачи: «Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?»

Алгоритмы описывают последовательность действий, производи­мых над некоторыми объектами, определёнными условием задачи. Например, при решении задачи о начислении зарплаты сотрудникам предприятия такими объектами могут быть табельный номер сотруд­ника, его фамилия, имя, отчество, оклад, отработанное время и т. д.

В информатике отдельный информационный объект (число, символ, строка, таблица и др.) называется величиной.

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

В алгоритмах над величинами выполняются некоторые операции. Например:

• арифметические операции +, -, * (умножение), / (деление);

• операции отношения , =, =, ;

• логические операции И, ИЛИ, НЕ.

Объекты, над которыми выполняются операции, называются опе­рандами. Не всякий объект может быть операндом для выполнения любой операции. Например, текст не может быть объектом для вы­полнения арифметических операций; отрицательное число не может быть операндом для извлечения квадратного корня и т.д.

Множество величин, объединённых определённой совокупностью допустимых операций, называют величинами определённого типа. При составлении алгоритмов используют величины числового (цело­го и вещественного), символьного, литерного и логического типов.

В математике и физике оперируют числовыми величинами — на­туральными, целыми, действительными числами. При составлении алгоритмов чаще всего используют числовые величины целого и ве­щественного типов, которые в алгоритмическом языке обозначают­ся цел и вещ соответственно.

В задачах, возникающих в повседневной жизни, встречаются и нечисловые величины, значениями которых являются символы, сло­ва, тексты и др. При составлении алгоритмов обработки текстовой информации используют величины символьного (сим) и литерного (лит) типов. Значением символьной величины является один символ: русская или латинская буква, цифра, знак препинания или другой символ. Значением литерной величины является последовательность символов. Иногда эту последовательность называют строкой или це­почкой. Литерные значения в алгоритме записывают в кавычках, например: 'алгоритм', 'литерная величина', '2011'.

Величины логического (лог) типа могут принимать всего два зна­чения:

ДА (ИСТИНА, TRUE, 1); НЕТ (ЛОЖЬ, FALSE, 0).

Для ссылок на величины используют их имена (идентификато­ры). Имя величины может состоять из одной или нескольких латин­ских букв, из латинских букв и цифр: Al, М, АР.

Рекомендуется выбирать мнемонические имена, т. е. имена, отражающие суть объектов решаемой задачи, например SUMMA, PLAN, CENA и т. д.

Если величину представить как ящик, содержи­мым которого является некоторое значение, то имя величины — это ярлык, повешенный на ящик.

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

Выражения состоят из операндов (констант, переменных, функ­ций), объединённых знаками операций. Выражения записываются в виде линейных последовательностей символов (без подстрочных и надстрочных символов, обыкновенных дробей и т. д.); знаки опера­ций пропускать нельзя. Порядок выполнения операций определяет­ся скобками и приоритетом (старшинством) операций; операции оди­накового приоритета выполняются слева направо.

Различают арифметические, логические и строковые выражения.

Арифметические выражения служат для определения числового значения. Например, 2*х+3 — арифметическое выражение, значе­ние которого при х = 1 равно пяти, а при х = -1 единице. Выраже­ние sqrt(x) служит для обозначения операции извлечения квадратно­го корня из х.

Логические выражения описывают некоторые условия, которые могут удовлетворяться или не удовлетворяться. Логическое выраже­ние может принимать одно из двух значений — ИСТИНА или ЛОЖЬ.

Строковые выражения состоят из величин (констант, перемен­ных) символьного и литерного типов, соответствующих функций и операций сцепления (присоединения). Операция сцепления обозна­чается знаком « + » и позволяет соединить в одну последовательность несколько последовательностей символов. Значениями строковых выражений являются последовательности символов.

Р.Т., стр.69, упр.114

Установите соответствие между типами величин и их значениями:

Р.Т., стр.70, упр.115

Р.Т., стр.70, упр.116

Переведите выражения из линейной записи в общепринятую:

A * B / C + D

A * B / C * D

A+ B / C

(A + B) / C

A + B / C + D

(A + B) / (C + D)

Р.Т., стр.70, упр. 117

Запишите на алгоритмическом языке:

Р.Т., стр.71, упр.119

Домашнее задание: учебник, параграфы 3.1, 3.2, 3.3 (до пункта 3.3.3.) читать, Р.Т. до стр. 72, упр. 120 (включительно).

8