Решение
подобного рода задач основано на
пошаговом исполнении алгоритма, в
итоге делается вывод о том, какую задачу
выполняет этот алгоритм и что является
конечным результатом.
Предлагается
задача: в приведенном алгоритме при к
= 4
каким будет выведенное значение Р?
Это
задание можно сформулировать как
тестовое, где нужно выбрать правильный
ответ из нескольких предложенных и
обосновать его.
В
нашем случае варианты ответов (правильный
выделен жирным шрифтом).
1)
1; 3) 12;
5) 1944.
2)4;
4)81;
Кроме
того, можно предложить просто определить
ответ и сформулировать условие задачи,
решение которой приведено.
В
нашем примере задача формулируется
так:
найти произведение первых k
натуральных чисел, кратных 3; Р = 1944.
Этот
же алгоритм, в зависимости от того, как
преподавался курс алгоритмизации и
программирования, можно предложить
для исследования, записав его на одном
из алгоритмически
Язык
Бейсик
input
“Введите натуральное число: “, k
р
=: 1 t=: О
fог
i = 1 tо
k
t=t+3:
p=p*t
пехt
i
print
“Результат: “, р
епd.
Ввод
k
P
:=1
T:=0
начало
T:=T+3
I:=1,
k, 1
P:=P*T
Вывод
Р
Конец Билет №5
1. Операционная система компьютера (назначение, состав, способ организации диалога с пользователем). Загрузка компьютера.
2. Создание, преобразование, сохранение, распечатка рисунка в среде графического редактора.
1.
Операционная система компьютера
(назначение, состав, способ организации
диалога с пользователем). Загрузка
компьютера.
Операционная
система
— это важнейшая часть системного
программного обеспечения, которая
организует процесс выполнения задач
на ЭВМ, распределяя для этого ресурсы
машины, управляя работой всех ее
устройств и взаимодействием с
пользователем. Иными словами, это
своеобразный администратор компьютера,
распределяющий его ресурсы так, чтобы
пользователь мог решать свои задачи
максимально удобно.
Примечание.
Ресурсами компьютера являются
процессорное время, память всех
видов, устройства ввода/вывода, программы
и данные.
Роль
операционной системы можно наглядно
представить себе с помощью следующего
рисунка. В центре его изображен собственно
компьютер, т.е. все то оборудование,
которое стоит на вашем столе и которое
можно непосредственно “потрогать
руками” (в информатике эта часть
часто называется hardware).
Внешней оболочкой является разнообразное
программное обеспечение (software),
позволяющее многочисленным пользователям
решать свои прикладные задачи из всех
областей человеческой деятельности.
ОС организует их совместную работу
и служит своеобразным программным
расширением управляющего устройства
компьютера. Вы можете спросить: а так
ли нужен еще один дополнительный
слой? Очень
нужен,
учитывая тот факт, что невозможно
заложить в центральный блок информацию
обо всех устройствах, которые к нему
могут быть подсоединены. И, кроме
того, новое устройство может быть
изобретено уже после изготовления
компьютера! Отсюда очевидно, что
загружаемая (а следовательно, изменяемая)
программная часть, обеспечивающая
работу компьютерное аппаратуры,
совершенно необходима.
С
другой стороны, наличие операционной
системы очень существенно облегчает
разработку нового программного
обеспечения. Все наиболее часто
встречающиеся при работе компьютера
задачи сконцентрированы в ОС. Поэтому
программисту уже не требуется заботиться
о размещении своей программы в объеме
памяти каждого конкретного компьютера
или описывать отдельные технические
детали взаимодействия со всевозможными
внешними устройствами разнообразных
фирм-изготовителей — для этого достаточно
просто обратиться к соответствующей
функции операционной системы. Приведем
простой частный пример. Если бы об этом
не заботилась ОС, каждая программа
должна была бы самостоятельно проверять
наличие дискеты в дисководе при записи
информации или факт подключения
принтера перед печатью на бумагу. И
таких ситуаций существует великое
множество.
Но
наличие операционной системы удобно и
пользователю. Поскольку на современных
компьютерах диалог с ним ведется
именно средствами ОС, то интерфейс
(проще говоря, способы взаимодействия
с человеком) во
всех программах получается примерно
одинаковым. Так, освоив 2—3 программы в
системе Windows, пользователь может
довольно быстро научиться работать с
еще одной, даже совершенно новой для
него,
Таким
образом, мы видим, что операционная
система решает целый комплекс важных
задач управления компьютером. Сформулируем
их по возможности более полно. Итак, ОС
современного компьютера выполняет
следующие функции.
• Организация
согласованного выполнения всех процессов
в компьютере. Планирование работ,
распределение ресурсов.
• Организация
обмена с внешними устройствами. Хранение
информации и обеспечение доступа к ней,
предоставление справок.
• Запуск
и контроль прохождения задач пользователя.
• Реакция
на ошибки и аварийные ситуации. Контроль
за нормальным функционированием
оборудования.
• Обеспечение
возможности доступа к стандартным
системным средствам (программам,
драйверам, информации о конфигурации
и т.п.).
• Обеспечение
общения с пользователем.
• Сохранение
конфиденциальности информации в
многопользовательских системах.
Первые
операционные системы (СР/М, МS-DOS,Unix
) вели диалог с пользователем на экране
текстового дисплея. Это был в полном
смысле слова диалог, в ходе которого
человек и компьютер по очереди
обменивались сообщениями: человек
вводил очередную команду, а компьютер,
проверив ее, либо выполнял, либо отвергал
по причине ошибки. Такие системы в
литературе принято называть ОС
с интерфейсом командной строки.
Пользователь
последовательно набрал две команды
вывода каталога дисков, причем первую
компьютер выполнил нормально, и на
экране появился требуемый список
файлов, а вторую “отказался” делать,
поскольку оператор ошибочно указал
имя несуществующего диска. Очевидно,
что подобный способ общения не очень
удобен для человека, поскольку требует
постоянно держать в голове жесткий
синтаксис всех допустимых команд и
очень внимательно их вводить. Поэтому
почти сразу же стали появляться сервисные
системные программы, тем или иным
способом облегчающие работу с ОС.
Наиболее ярким примером таких
программ-оболочек может служить широко
известный Norton Commander,
который был настолько распространен,
что многие пользователи искренне
считали его частью операционной системы.
Развитие
графических возможностей дисплеев
привело к коренному изменению принципов
взаимодействия человека и компьютера.
Командная строка была безвозвратно
вытеснена
графическим интерфейсом,
когда объекты манипуляций в ОС изображаются
в виде небольших рисунков, а необходимые
действия тем или иным образом выбираются
из предлагаемого машиной списка — так
называемого меню. При подобном методе
диалога набор текста полностью отсутствует
и вполне достаточно всего нескольких
клавиш. Существенным дополнением к
графическому способу ведения диалога
явилось появление нового устройства
ввода информации в компьютер —
манипулятора “мышь”, без которого
сейчас просто невозможно представить
современный компьютер. Примерами
операционной системы с графическим
интерфейсом служат довольно похожие
ОС для компьютеров “Масintosh” (не
имеет специального названия и
обозначается просто System с номером
версии) и “IВМ РС” — 0S/2 и Windows.
Последняя система в нашей стране
распространена необычайно широко.
Перейдем
теперь к описанию состава операционных
систем. Он, конечно, может быть довольно
разным для различных систем. Так, для
“классических” ОС с командной
строкой довольно четко выделяются три
основные части:
• машинно-зависимая
часть для работы с конкретными видами
оборудования;
• базовая
часть (ядро), не зависящая от конкретных
деталей устройств: она работает с
абстрактными логическими устройствами
и при необходимости вызывает функции
из предыдущей части; отвечает за наиболее
общие принципы устройства ОС;
• программа
ведения диалога с пользователем (ее
часто называют
командным процессором).
Значительная
часть операционной системы находится
в памяти постоянно, что обеспечивает
ее эффективную работу. Программы для
некоторых редко используемых операций
типа форматирования дискет чаще всего
оформляются в виде самостоятельных
служебных программ и хранятся на внешних
носителях. Такие программы обычно
называют
утилитами.
Кроме того, в ОС, как правило, включают
небольшой стандартный набор самого
необходимого программного обеспечения,
например, простейший текстовый редактор.
Состав
операционных систем с графическим
интерфейсом типа Windows заметно шире,
но в целом имеет похожее строение.
В
момент включения компьютера в ОЗУ нет
осмысленной информации. Поэтому
особый интерес представляет вопрос о
том, как операционная система загружается.
Процесс этот в заметно упрощенном виде
выглядит так. При включении компьютера
(или при нажатии кнопки сброса) счетчик
процессора аппарате устанавливается
на начальный адрес ПЗУ, и стартует
выполнение программы начальной загрузки.
Прежде всею ищется и тестируется
установленное оборудование. Современные
компьютеры в основном используют внешние
устройства “plug
and р1ау” (переводится
— “включил и работай”), поэтому они
способны сообщить процессору свои
основные характеристики и условия
работы. Опрос внешних устройств и
проверка их работоспособности
занимают достаточно длительное время,
несмотря на высокое быстродействие
компьютера. В случае если все оборудование
функционирует нормально, происходит
переход к следующему этапу — поиску
начального загрузчика операционной
системы. Он может находиться на жестком
диске, на дискете, на СD-RОМ
и даже быть получен с помощью сетевой
платы. Поэтому компьютер опрашивает
перечисленные устройства по очереди,
в определенном порядке, до тех пор, пока
не обнаружит требуемую информацию (в
скобках заметим, что порядок поиска при
наличии достаточных навыков и знаний
может быть легко изменен). Итак, загрузчик,
представляющий собой не что иное,
как программу
дальнейшей загрузки,
обнаружен и прочитан в память. Дальнейшие
действия машины уже определяются тем,
что введено извне. Поскольку начальный
загрузчик очень мал, то он умеет очень
немного — найти и прочесть первый файл
ОС с фиксированным именем и передать
ему управление. И только после этого
будет загружена в ОЗУ остальная часть
операционной системы и машина сможет,
наконец, нормально общаться с
пользователем.
Примечание.
Несколько слов для тех, кого удивила
сложность описанного процесса. Почему
загрузка ОС такая многоступенчатая
• и почему, например, нельзя просто
записать начальный
загрузчик в то же самое ПЗУ? Технически
это не представляет никакого труда, но
все дело в том, что тогда мы сможем
пользоваться только
одной(!)
операционной системой, а именно той,
загрузчик для которой жестко “зашили”
в ПЗУ.
И
в заключение еще одно дополнительное
замечание. Может быть, не стоит
требовать этот материал с учеников, но
рассказать об этом, по-моему, стоит.
Всегда ли существовала ОС и может ли
компьютер работать без нее? Как ни
странно, ответ на оба вопроса отрицательный.
Операционная система существовала не
всегда,
а возникла на стыке второго и третьего
поколений.
Cсущественными
причинами возникновения ОС являются
появление сложных внешних устройств —
в первую очередь магнитных дисков, и
необходимость разделения ресурсов
между задачами и пользователями. Что
касается работы без ОС, то теоретически
можно написать такую программу, которая
будет сама загружаться и работать с
внешними устройствами без всякого
участия ОС. На практике это чересчур
сложно и никогда не делается. Даже если
компьютер целыми днями работает по
единственной программе (кассовый аппарат
в магазине или учет переводов в сберкассе),
в нем все равно обычно используется
операционная система.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Алгоритм. Свойства алгоритмов.
Блок-схемы. Алгоритмические языки
Код ОГЭ: 1.3.1. Алгоритм, свойства алгоритмов, способы записи алгоритмов.
Блок-схемы. Представление о программировании
Понятие алгоритма является одним из основных понятий вычислительной математики и информатики.
■ Алгоритм
— строго определенная последовательность действий для некоторого исполнителя, приводящая к поставленной цели или заданному результату за конечное число шагов.
Любой алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Исполнитель — субъект, способный исполнять некоторый набор команд. Совокупность команд, которые исполнитель может понять и выполнить, называется системой команд исполнителя.
Для выполнения алгоритма исполнителю недостаточно только самого алгоритма. Выполнить алгоритм — значит применить его к решению конкретной задачи, т. е. выполнить запланированные действия по отношению к определенным входным данным. Поэтому исполнителю необходимо иметь исходные (входные) данные — те, что задаются до начала алгоритма.
В результате выполнения алгоритма исполнитель должен получить искомый результат — выходные данные, которые исполнитель выдает как результат выполненной работы. В процессе работы исполнитель может создавать и использовать данные, не являющиеся выходными, — промежуточные данные.
Свойства алгоритмов
Алгоритм должен обладать определенными свойствами. Наиболее важные свойства алгоритмов:
- Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.
- Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.
- Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя.
- Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд.
- Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.
Способы представления алгоритмов:
- словесная запись (на естественном языке). Алгоритм записывается в виде последовательности пронумерованных команд, каждая из которых представляет собой произвольное изложение действия;
- блок–схема (графическое изображение). Алгоритм представляется с помощью специальных значков (геометрических фигур) — блоков;
- формальные алгоритмические языки. Для записи алгоритма используется специальная система обозначений (искусственный язык, называемый алгоритмическим);
- псевдокод. Запись алгоритма на основе синтеза алгоритмического и обычного языков. Базовые структуры алгоритма записываются строго с помощью элементов некоторого базового алгоритмического языка.
Словесная запись алгоритма
Произвольное изложение этапов алгоритма на естественном языке имеет свои недостатки. Словесные описания строго не формализуемы, поэтому может быть нарушено свойство определенности алгоритма: исполнитель может неточно понять описание этапа алгоритма. Словесная запись достаточно многословна. Сложные задачи трудно представить в словесной форме.
■ Пример 1. Записать в словесной форме правило деления обыкновенных дробей.
Решение.
Шаг 1. Числитель первой дроби умножить на знаменатель второй дроби.
Шаг 2. Знаменатель первой дроби умножить на числитель второй дроби.
Шаг 3. Записать дробь, числителем которой являет результат выполнения шага 1, знаменателем — результат выполнения шага 2.
Описанный алгоритм применим к любым двум обыкновенным дробям. В результате его выполнения будут получены выходные данные — результат деления двух дробей (исходных данных).
Формальные исполнители алгоритма
Формальный исполнитель — это исполнитель, который выполняет все команды алгоритма строго в предписанной последовательности, не вникая в его смысл, не внося ничего в алгоритм и ничего не отбрасывая. Обычно под формальным исполнителем понимают технические устройства, автоматы, роботов и т. п. Компьютер можно считать формальным исполнителем.
Программы на языке произвольного формального исполнителя могут состоять только из элементарных команд, которые входят в его систему (которые исполнитель «понимает»).
Исполнитель может иметь свою среду (например, систему координат, клеточное поле и др.). Среда исполнителя — это совокупность объектов, над которыми он может выполнять определенные действия (команды), и связей между этими объектами. Алгоритмы в этой среде выполняются исполнителем по шагам.
■ Пример 2. Исполнитель Крот имеет следующую систему команд:
- вперед k — продвижение на указанное число шагов вперед;
- поворот s — поворот на s градусов по часовой стрелке;
- повторить m [команда1 … командаN] — повторить m раз серию указанных команд.
Какой след оставит за собой исполнитель после выполнения следующей последовательности команд?
Повторить 5 [вперед 10 поворот 72]
Решение. Команда вынуждает исполнителя 5 раз повторить набор действий: пройти 10 шагов вперед и повернуть на 72° по часовой стрелке. Так как поворот происходит на один и тот же угол, то за весь путь исполнитель повернет на 5 х 72° = 360°. Поскольку все отрезки пути одинаковой длины и сумма внешних углов любого многоугольника составляет 360°, то в результате будет оставлен след в форме правильного пятиугольника со стороной в 10 шагов исполнителя.
Заметим, что если увеличить количество повторов серии команд, то исполнитель будет повторно передвигаться по тем же отрезкам (произойдет повторное движение по тому же пятиугольнику).
■ Пример 3. В системе команд предыдущего исполнителя Крот сформировать алгоритм вычерчивания пятиступенчатой лестницы (длина ступеньки — 10 шагов исполнителя).
Решение. За каждый шаг цикла должно происходить 4 действия: движение вперед на 10 шагов исполнителя, поворот на 90° по часовой стрелке, еще 10 шагов вперед и поворот на 90° против часовой стрелки (= 270° по часовой). В результате за один шаг цикла формируется ломаная из двух отрезков длиной 10 под прямым углом. За пять таких шагов сформируется 5–ступенчатая лестница (ломаная будет содержать 10 звеньев).
Повторить 5 [вперед 10 поворот 90 вперед 10 поворот 270]
Блок–схема
Блок–схема — наглядный способ представления алгоритма. Блок–схема отображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Определенному типу действия соответствует определенная геометрическая фигура блока. Линии, соединяющие блоки, определяют очередность выполнения действий. По умолчанию блоки соединяются сверху вниз и слева направо. Если последовательность выполнения блоков должна быть иной, используются направленные линии (стрелки).
Основные элементы блок–схемы алгоритма:
Общий вид блок–схемы алгоритма:
■ Пример 4. Алгоритм целочисленных преобразований представлен в виде фрагмента блок–схемы. Знаком := в нем обозначен оператор присваивания некоторого значения указанной переменной. Запись X := 1 означает, что переменная Х принимает значение 1.
Определить результат работы алгоритма для исходных данных Х = 7, Y = 12.
Решение.
- Блок ввода данных определит исходные значения переменных Х и Y (7 и 12 соответственно).
- В первом условном блоке осуществляется сравнение значений Х и Y. Поскольку условие, записанное в блоке, неверно (7 < 12), происходит переход по линии «нет».
- Во втором условном блоке выполняется второе сравнение, которое для исходных данных оказывается верным. Происходит переход по линии «да».
- Вычисляется результат выполнения алгоритма: X := 0, Y := 1.
Ответ: X := 0, Y := 1.
Алгоритмические языки
Алгоритмический язык — это искусственный язык (система обозначений), предназначенный для записи алгоритмов. Он позволяет представить алгоритм в виде текста, составленного по определенным правилам с использованием специальных служебных слов. Количество таких слов ограничено. Каждое служебное слово имеет точно определенный смысл, назначение и способ применения. При записи алгоритма служебные слова выделяют полужирным шрифтом или подчеркиванием.
В алгоритмическом языке используются формальные конструкции, но нет строгих синтаксических правил для записи команд. Различные алгоритмические языки различаются набором служебных слов и формой записи основных конструкций.
Алгоритмический язык, конструкции которого однозначно преобразуются в команды для компьютера, называется языком программирования. Текст алгоритма, записанный на языке программирования, называется программой.
Псевдокод
Псевдокод занимает промежуточное положение между естественным языком и языками программирования. Пример псевдокода — учебный алгоритмический язык. Алфавит учебного алгоритмического языка является открытым. Существенным достоинством этого языка является то, что его служебные слова, конструкции и правила записи алгоритма весьма схожи с теми, что применяются в распространенных языках программирования. Благодаря этому учебный алгоритмический язык позволяет легче освоить основы программирования.
Служебные слова учебного алгоритмического языка:
Стандартная структура алгоритма
Представление алгоритма на алгоритмическом языке (в том числе и языке программирования) состоит из двух частей. Первая часть — заголовок — задает название алгоритма и включает описание переменных, которые используются в нем. Вторая часть — тело алгоритма — содержит последовательность команд алгоритма.
Общий вид записи алгоритма на учебном алгоритмическом языке:
В начале заголовка записывается служебное слово алг, после чего указывается имя алгоритма. Описание переменных, являющихся аргументами алгоритма и его результатами, приводится после названия в круглых скобках.
В следующих строках конкретизируют, какие именно переменные являются аргументами алгоритма (входными данными), а какие — его результатами (выходными данными). Для этого после служебного слова арг приводится список имен переменных–аргументов; в следующей строке после служебного слова рез приводится список имен переменных–результатов.
Между служебными словами нач и кон размещается тело алгоритма — конечная последовательность команд, выполнение которых предписывает алгоритм. Команды алгоритма записывают одну за одной в отдельных строках. В случае необходимости можно записать две или более команд в одной строке, тогда соседние команды разделяют точкой с запятой. Если в алгоритме применяются промежуточные переменные, их описание приводят в начальной строке тела алгоритма рядом со словом нач.
Примеры заголовков алгоритмов:
В первом примере алгоритм имеет название Объем_шара, один вещественный аргумент Радиус и один вещественный результат Объем. Во втором примере алгоритм под названием Choice имеет три аргумента — целые M и N и логический b, а также два результата — вещественные Var1 и Var2.
Пример алгоритма вычисления гипотенузы прямоугольного треугольника:
На вход алгоритму даются два вещественных аргумента a и b (величины катетов), результатом является вещественная переменная с (гипотенуза). Для ее расчета используется функция вычисления квадратного корня sqrt.
Описание величин и действия над ними
При описании алгоритма необходимо указать названия (обозначения) всех величин, которые будут в нем найдены или использованы.
При представлении алгоритма решения в виде блок–схемы выбранные обозначения величин приводятся отдельно от блок–схемы (как объяснение к ней). Если алгоритм представлен на языке программирования, то характеристика обрабатываемых величин включается в программу. Учебный алгоритмический язык также предусматривает описание величин, используемых в алгоритме.
Все величины в алгоритме разделяют на постоянные (константы) и переменные. Константа не может изменять свои значения в процессе работы алгоритма. Переменная может приобретать различные значения, которые сохраняются до тех пор, пока она не получит новое значение. Переменным величинам назначают имена. Таким образом, переменная — это именуемая величина, которая в процессе выполнения алгоритма может приобретать и хранить различные значения.
В алгоритмическом языке не существует специальных правил именования переменных. Однако их названия не должны совпадать со служебными словами алгоритмического языка. Во многих языках программирования для имен можно использовать только латинские буквы, цифры, знак подчеркивания. Имена обязательно должны начинаться с буквы, при этом строчные и прописные буквы в именах не различаются. В одном алгоритме не могут существовать разные объекты с одинаковыми именами. Все имена являются уникальными. Имена переменных и констант стараются выбирать так, чтобы они напоминали их смысл. Например, имена переменных и констант: S, p12, result, итог.
При представлении алгоритма на алгоритмическом языке именуются не только величины, но и сам алгоритм, и другие объекты. Имя алгоритма выбирают так же, как и имена переменных.
Величина — переменная, с которой связывается определенное множество значений. Этой величине присваивается имя (в языках программирования его называют идентификатор).
Значение — то, чему равна переменная в конкретный момент. Значение переменной можно задать двумя способами: присваиванием и с помощью процедуры ввода.
Тип переменной определяет диапазон всех значений, которые может принимать данная переменная, и допустимые для нее операции. Существует несколько предопределенных типов переменных. К стандартным типам относятся числовые, литерные и логические типы.
Числовой тип предназначен для обработки числовых данных. Различают целый и вещественный числовые типы. Целый тип в учебном алгоритмическом языке обозначается служебным словом цел, к нему относятся целые числа некоторого определенного диапазона. Они не могут иметь дробной части, даже нулевой. Число 123,0 является не целым, а вещественным числом. Вещественные величины относятся к вещественному типу данных и обозначаются в учебном алгоритмическом языке служебным словом вещ. Такие величины могут отображаться двумя способами: в форме с фиксированной запятой (например, 0,0511 или –712,3456) и с плавающей запятой (те же примеры: 5,11*10-2 и –7,123456*102).
Над числовыми данными можно выполнять арифметические операции и операции сравнения.
Над целыми числами можно также выполнять две операции целочисленного деления div и mod. Операция div обозначает деление с точностью до целых чисел (остаток от деления игнорируется). Операция mod позволяет узнать остаток при делении с точностью до целых чисел. Например, результатом операции 100 div 9 будет число 11, а результатом 100 mod 9 — число 1.
Литерный тип представляет собой символы и строки, он дает возможность работать с текстом. Литерные величины — это произвольные последовательности символов. Эти последовательности заключаются в двойные кавычки: «результат», «sum_price». В качестве символов могут быть использованы буквы, цифры, знаки препинания, пробел и некоторые другие специальные знаки (возможными символами могут быть символы таблицы ASCII). В учебном алгоритмическом языке литерные величины обозначаются лит.
Над литерными величинами возможны операции сравнения и слияния. Сравнение литерных величин производится в соответствии с их упорядочением: «a» < «b», «b» < «с» и т. д. Слияние (конкатенация) литерных величин приводит к образованию новой величины: «пол» + «е» образует «поле».
Логический тип определяет логические переменные, которые могут принимать только два значения — истина (True) или ложь (False). Над логическими величинами можно выполнять все стандартные логические операции.
Команды учебного алгоритмического языка
Учебный алгоритмический язык использует следующие команды для реализации алгоритма:
ОПЕРАЦИЯ ПРИСВАИВАНИЯ
Ко всем типам величин может быть применена операция присваивания, которая обозначается знаком «:=» и служит для вычисления выражения, стоящего справа, и присваивания его значения переменной, указанной слева. Например, если переменная H имела значение 12, а переменная М — значение 3, то после выполнения оператора присваивания H := М + 10 значение переменной H изменится и станет равным 13.
Вычисления в операторе присваивания выполняются справа налево: сначала необходимо вычислить значение выражения справа от знака присваивания. Поэтому допустимы конструкции вида H := Н + 10. В этом случае сначала будет вычислено выражение в правой части (12 + 10), а его результат будет присвоен в качестве нового значения переменной Н (значение 22).
Для оператора присваивания обязательно должны быть определены значения всех переменных в его правой части. Кроме того, типы данных в левой и правой части должны соответствовать друг другу.
ВВОД И ВЫВОД ДАННЫХ
В процессе работы алгоритма происходит обработка исходных данных для получения выходных (результирующих) данных. В процессе этого преобразования могут быть найдены некоторые промежуточные результаты. Входные данные должны быть переданы алгоритму («введены»), а по окончании работы алгоритм должен вывести результат.
При записи алгоритма с помощью блок–схемы ввод и вывод данных отображаются с помощью блоков ввода/вывода (параллелограммов). При этом только указывается перечень данных для ввода или вывода, а сам процесс не детализируется.
Описание алгоритма средствами псевдокода может вовсе не предусматривать команды ввода или вывода данных. В заголовке алгоритма указывается, какие данные являются аргументами, какие — результатами работы алгоритма. Считается, что аргументы будут предоставлены до выполнения алгоритма, результаты будут выведены после его выполнения, и описывается лишь процесс превращения аргументов в результаты.
В записи алгоритма с помощью учебного алгоритмического языка для операций ввода/вывода используются команды ввод и вывод. После этих служебных слов указывается список ввода или вывода. Элементы этих списков перечисляются через запятую.
Список ввода может содержать только имена переменных. После выполнения команды ввод алгоритм получит значения перечисленных в списке переменных.
Список вывода может содержать имена переменных, константы и выражения. Если в списке вывода указано имя переменной, будет выведено ее значение. Если список вывода содержит выражение, будет выведен результат его вычисления. Текстовые константы следует записывать в списке вывода в кавычках (выводиться они будут без кавычек).
Если при выполнении алгоритма ввести значения 20 и 10, то переменная v примет значение 20, а переменная t — значение 10. По окончании работы алгоритма будет выведен результат:
Путь 200 м
Тот же результат был бы получен, если бы изменить строку вывода на
вывод «Путь «, v * t, » м»
Конспект по информатике «Алгоритм. Свойства алгоритмов. Блок-схемы. Алгоритмические языки».
Вернуться к Списку конспектов по информатике.
Задачи на
составление блок-схем алгоритмов
Основные
блоки
Примеры
определения результата выполнения алгоритма по заданной блок-схеме.
Пример 1.
Дана
блок-схема алгоритма
Определить
результат выполнения алгоритма при определённых значенияхисходных
данных
Например, при
x=16
и y=2
Ввод: х=16
y=2
x=ж16=4
y=y2=4
x=4+1=5
y=4+5=9
Вывод:
y=9
Пример
2.
Дана
блок-схема алгоритма
Определить
результат выполнения алгоритма при определённых значениях
исходных данных
Например, при
x=-6
или x=0 или x=7
1)
Ввод: х=–6
Проверка
условия
x>0
о
ЋНетЛ оy=-2*(-6)=12
Вывод:
y=12
2)
Ввод: х=0
Проверка
условия
x>0
о
ЋНетЛ оy=-2*0=0
Вывод:
y=0
3)
Ввод: х=7
Проверка
условия
x>0
о
ЋДаЛ оy=2*7=14
Вывод:
y=14
Пример 3.
Дана
блок-схема алгоритма
Определить
результат выполнения алгоритма при определённых значениях
исходных данных
Например, при
n=15
или n=0 или n=-7
1)
Ввод: n=15
Проверка
условия
n>0
о
ЋДаЛ
о
Вывод Ћn-положительноеЛ
2)
Ввод: n=0
Проверка
условия
n>0
о
ЋНетЛ о
Проверка условия
n<0о
ЋНетЛ о
Вывод Ћn=0Л
3)
Ввод: n=-7
Проверка
условия
n>0
о
ЋНетЛ о
Проверка условия
n<0о
ЋДаЛ о
Вывод Ћn-отрицательноеЛ
Пример 4.
Дана
блок-схема алгоритма
Определить
результат выполнения алгоритма при определённых значениях
исходных данных
Например, при
A=7; B=8;
C=9 или A=6; B=6; C=-10 или A=6;
B=10; C=-10
1)
Ввод: A=7;
B=8;
C=9
Проверка
условия
A=B
о
ЋНетЛ о
Проверка условия
B>C
о
ЋНетЛ о
B=9+8=17;
F=7+17=24
о
Вывод
F=24
2)
Ввод: A=6;
B=6;
C=-10
Проверка
условия
A=B
о
ЋДаЛ о
С=6+6=12;
F=6+12=18
о
Вывод
F=18
3)
Ввод: A=6;
B=10;
C=-10
Проверка
условия
A=B
о
ЋНетЛ о
Проверка условия
B>C
о
ЋДаЛ о
A=6+10=16;
F=16+(-10)=6
о
Вывод
F=6
Пример
5.
Дана
блок-схема алгоритма
Определить
результат выполнения алгоритма при определённых значениях
исходных данных
Например, при
n=4
или n=1
1)
Ввод: n=4
S=0
k=4
Проверка
условия
k>2
о
ЋДаЛ о
S=0+4=4;
n=4-1=3
Проверка
условия
k>2
о
ЋДаЛ о
S=4+3=7;
n=3-1=2
Проверка
условия
k>2
о
ЋНетЛ о
Вывод
S=7
2)
Ввод: n=1
S=0
k=1
Проверка
условия
k>2
о
ЋНетЛ о
Вывод
S=0
Решение задач на выполнение алгоритма
Задача №1 Определите значение переменной а после выполнения фрагмента алгоритма:
Примечание: знаком * обозначено умножение,
знаком := обозначена операция присваивания.
Решение задачи №1 Последовательно выпишем значения переменных в ходе цикла, пока переменная b не станет равной 1 .
| Шаг 1. | b=b-1=3-1=2 a=a*9=1*9=9 |
| Шаг 2. | b=b-1=2-1=1 a=a*9=9*9=81 |
Так как после второго шага переменная b равна 1, то по условию «b=1», цикл завершён.
Ответ: Переменная а равна 81.
Задача №2
Примечание: знаком * обозначено умножение,
знаком := обозначена операция присваивания.
Решение задачи №2 Последовательно выпишем значения переменных в ходе цикла, пока переменная b не станет равной 1 .
| Шаг 1. | b=b-2=7-2=5 a=a*8=1*8=8 |
| Шаг 2. | b=b-2=5-2=3 a=a*8=8*8=64 |
| Шаг 3. | b=b-2=3-2=1 а=a*8=64*8=512 |
Так как после второго шага переменная b равна 1, то по условию «b=1», цикл завершён.
Ответ: Переменная а равна 512.
Задача №3
Решение задачи №3 Последовательно выпишем значения переменных в ходе цикла, пока не выполнится следующее условие «а<9» .
| Шаг 1. | Проверяем условие «а<b», условия не выполняется (идем по стрелки «нет»). b=b+2=1+2=3 a=a+1=1+1=2 |
| Шаг 2. | Проверяем условие «а<b», условия выполняется (идем по стрелки «да»). b=b+2=3+2=5 a=a+3=2+3=5 |
| Шаг 3. | Проверяем условие «а<b», условия не выполняется (идем по стрелки «нет»). b=b+2=5+2=7 a=a+1=5+1=6 |
| Шаг 4. | Проверяем условие «а<b», условия выполняется (идем по стрелки «да»). b=b+2=7+2=9 a=a+3=6+3=9 |
Так как после четвертого шага переменная а равна 9, то по условию «а<9» , цикл завершён.
Ответ: Переменная b равна 9.
Задача №4 Определите значение переменной b после выполнения фрагмента алгоритма:
Решение задачи №4 Последовательно выпишем значения переменных в ходе цикла, пока не выполнится следующее условие «а<9» .
| Шаг 1. | Проверяем условие «а<b», условия не выполняется (идем по стрелки «нет»). b=b*2=1*2=2 a=a+2=1+2=3 |
| Шаг 2. | Проверяем условие «а<b», условия не выполняется (идем по стрелки «нет»). b=b*2=2*2=4 a=a+2=3+2=5 |
| Шаг 3. | Проверяем условие «а<b», условия не выполняется (идем по стрелки «нет»). b=b*2=4*2=8 a=a+2=5+2=7 |
| Шаг 4. | Проверяем условие «а<b», условия выполняется (идем по стрелки «да»). b=b+2=8+2=10 a=a+2=7+2=9 |
Так как после четвертого шага переменная а равна 9, то по условию «а<9» , цикл завершён.
Ответ: Переменная b равна 10.
Задача №5 Определите значение переменной b после выполнения фрагмента алгоритма: 
Решение задачи №5 Последовательно выпишем значения переменных в ходе цикла, пока не выполнится следующее условие «а=1» .
| Шаг 1. | a=a/2=256/2=128 b=b+a=0+128=128 |
| Шаг 2. | a=a/2=128/2=64 b=b+a=128+64=192 |
| Шаг 3. | a=a/2=64/2=32 b=b+a=192+32=224 |
| Шаг 4. | a=a/2=32/2=16 b=b+a=224+16=240 |
| Шаг 5. | a=a/2=16/2=8 b=b+a=240+8=248 |
| Шаг 6. | a=a/2=8/2=4 b=b+a=248+4=252 |
| Шаг 7. | a=a/2=4/2=2 b=b+a=252+2=254 |
| Шаг 8. | a=a/2=2/2=1 b=b+a=254+1=255 |
Так как после восьмого шага переменная а равна 1, то по условию «а=1» , цикл завершён.
Ответ: Переменная b равна 255.
Задачи для самостоятельного решения
Задача №6 Определите значение переменной b после выполнения фрагмента алгоритма: 
Задача №7 Определите значение переменной a после выполнения фрагмента алгоритма:
Анализ результата исполнения алгоритма
Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.
Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.
Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.
Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.
Область математики, известная как теория алгоритмов, посвящена исследованию свойств, способов записи, области применения различных алгоритмов, а также созданию новых алгоритмов. Теория алгоритмов находит широкое применение в различных областях деятельности человека — в технике, производстве, медицине, образовании и т. д. Появление компьютера позволило решать чрезвычайно сложные, трудоемкие задачи.
Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.
Во-вторых, алгоритмы в информатике предназначены для реализации в виде компьютерных программ или для создания некоторой компьютерной технологии. Для выполнения алгоритма требуется конечный объем оперативной памяти и конечное время.
Основные требования, предъявляемые к алгоритмам:
Дискретность (прерывность): алгоритм должен представлять решение задачи в виде последовательности простых (или ранее определенных) этапов (шагов). Каждый шаг алгоритма формулируется в виде инструкций (команд).
Определенность (детерминированность; лат. determinate — определенность, точность): шаги (операции) алгоритма должны допускать однозначную трактовку и быть понятными для исполнителя алгоритма. Это свойство указывает на то, что любое действие в алгоритме должно быть строго определено и описано для каждого случая.
Массовость: алгоритм должен давать решение не только для конкретного набора значений, а для целого класса задач, который определяется диапазоном возможных исходных данных (область применимости алгоритма). Свойство массовости подразумевает использование переменных в качестве исходных данных алгоритма.
Результативность: алгоритм должен давать конкретный результат, т. е. должны быть рассмотрены все возможные ситуации и для каждой из них получен результат. Под результатом может пониматься и сообщение о том, что задача решения не имеет.
Конечность: количество шагов алгоритма должно быть конечным.
Эффективность: количество шагов и сами шаги алгоритма должны быть такими, чтобы решение могло быть найдено за конечное и, более того, приемлемое время.
Для оценки и сравнения алгоритмов существует много критериев. Чаще всего анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объема исходных данных. Используются также термины «временная сложность», «трудоемкость» алгоритма. Фактически эта оценка сводится к подсчету количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также емкостная сложность, т. е. увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности дает количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и емкостных затрат.
Анализом сложности алгоритмов, исследованием классов задач, решаемых с помощью алгоритмов той или иной сложности, и многими другими теоретическими вопросами занимается специальная область информатики.
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых элементов.
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:
- следование — образуется из последовательности действий, следующих одно за другим;
- ветвление (развилка) — обеспечивает в зависимости от результатов проверки условия (ДА или НЕТ) выбор одного из альтернативных путей алгоритма;
- цикл — обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Для описания алгоритмов наиболее распространены следующие методы (языки):
Обычный язык. Изложение алгоритма ведется на обычном языке с разделением на последовательные шаги.
Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.
Формальные алгоритмические языки (языки программирования). При записи алгоритмов используют строго определенный набор символов и составленных из них специальных зарезервированных слов. Имеют строгие правила построения языковых конструкций.
Псевдокод. Синтез алгоритмического и обычного языков. Элементы некоторого базового алгоритмического языка используются для строгой записи базовых структур алгоритма.
Словесный способ (запись на обычном языке) не имеет широкого распространения, т. к. таких описаний есть ряд недостатков:
- строго не формализуемы;
- достаточно многословны;
- могут допускать неоднозначность толкования отдельных предписаний;
- сложные задачи с анализом условий, с повторяющимися действиями трудно представляются в словесной или словесно-формульной форме.
Графический способ представления информации является более наглядным и компактным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление алгоритма называется блок-схемой. Определенному типу действия (ввод/вывод данных, проверка условия, вычисление выражения, начало и конец алгоритма и т. п.) соответствует определенная геометрическая фигура — блочный символ. Блоки соединяются между собой линиями переходов, которые определяют очередность выполнения действий.
| Название символа | Графическое изображение | Комментарии |
| Пуск/Останов (блоки начала и конца алгоритма) |  |
Указание на начало или конец алгоритма |
| Ввод/Вывод данных (блоки ввода, вывода |  |
Организация ввода/вывода в общем виде |
| Процесс (операторные блоки) |  |
Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных |
| Условие (условный блок) |  |
Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия |
| Начало цикла с параметром |  |
Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков |
| Предопределенный процесс |  |
Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам |
| Печать сообщений (документ) |  |
Вывод результатов на печать |
При составлении блок-схемы необходимо проверять выполнение следующих условий:
- из каждого прямоугольника и параллелограмма (кроме конца алгоритма) должна выходить только одна стрелка;
- в каждый прямоугольник и параллелограмм (кроме начала алгоритма) должна входить хотя бы одна стрелка;
- в каждый ромб должна входить хотя бы одна стрелка, а выходить из него — две стрелки, помеченные словами «ДА» и «НЕТ».
Псевдокод занимает промежуточное положение между естественным языком и языками программирования. В псевдокоде не приняты строгие синтаксические правила для записи команд, что отличает формальные языки программирования. Однако в псевдокоде есть некоторые конструкции, которые присущи формальным языкам, что облегчает переход от записи алгоритма на псевдокоде к записи алгоритма на языке программирования. Псевдокоды бывают разные. Рассмотрим учебный (школьный) алгоритмический язык АЯ.
Алфавит учебного алгоритмического языка является открытым. В него могут быть введены любые понятные всем символы: русские и латинские буквы, знаки математических операций, знаки отношений, специальные знаки и т. д. Кроме алфавита, в алгоритмической нотации определяются служебные слова, которые являются неделимыми. Служебные слова обычно выделяются жирным шрифтом или подчеркиванием. К служебным словам относятся:
| алг — заголовок алгоритма | нц — начало цикла | знач |
| нач — начало алгоритма | кц — конец цикла | и |
| кон — конец алгоритма | дано | или |
| арг — аргумент | надо | не |
| рез — результат | если | да |
| цел — целый | то | нет |
| сим — символьный | иначе | при |
| лит — литерный | всё | выбор |
| лог — логический | пока | утв |
| вещ — вещественный | для | ввод |
| таб — таблица | от | вывод |
| длин — длина | до |
Общий вид записи алгоритма на псевдокоде:
алг — название алгоритма (аргументы и результаты)
дано — условие применимости алгоритма
надо — цель выполнения алгоритма
нач — описание промежуточных величин
последовательность команд (тело алгоритма)
Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон, — телом алгоритма (исполняемой частью алгоритма).
В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное именем массива и граничными парами по каждому индексу элементов массива.
Команды учебного языка:
1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.
2. Операторы ввода/вывода:
ввод (список имен переменных)
вывод (список вывода)
Список вывода может содержать комментарии, которые заключаются в кавычки.
3. Оператор ветвления (с использованием команды если. то… иначе…всё; выбор);
4. Операторы цикла (с использованием команд для, пока, до).
Запись алгоритма на псевдокоде:
Здесь в предложениях дано и надо после знака «|» записаны комментарии. Комментарии можно помещать в конце любой строки, они существенно облегчают понимание алгоритма.
При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается произвольное изображение команд. Вместе с тем такая запись позволяет понять человеку суть дела и исполнить алгоритм. Однако алгоритм, предназначенный для исполнения на компьютере, должен быть записан на строго формализованном языке. Такой язык называется языком программирования, а запись алгоритма на этом языке — компьютерной программой.
Для решения одной и той же задачи можно предложить несколько алгоритмов. Алгоритмы составляются с ориентацией на определенного исполнителя алгоритма. У каждого исполнителя имеется свой конечный набор команд, которые для него понятны и исполняемы. Этот набор называется системой команд исполнителя. Пользуясь системой команд, исполнитель может выполнить алгоритм формально, не вникая в содержание поставленной задачи. От исполнителя требуется только строгое выполнение последовательности действий, предусмотренной алгоритмом. Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:
- первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
- вторая стадия — алгоритм должен быть представлен в форме, понятной исполнителю алгоритма (вторая стадия может отсутствовать, если исполнять алгоритм будет сам разработчик).
Примеры решения задач
Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:
Первая команда уменьшает число на 1, вторая — увеличивает его втрое.
Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.
Ответ: 13311
Пример 2. Имеется Исполнитель алгоритма, который может передвигаться по числовой оси.
Система команд Исполнителя алгоритма:
1. «Вперед N» (Исполнитель алгоритма делает шаг вперед на N единиц).
2. «Назад M» (Исполнитель алгоритма делает шаг назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было. Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?
1. Найдем, сколько было команд «Вперед», а сколько «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение: x + (x + 12) = 50, где x — количество команд «Вперед». Тогда общее количество команд «Вперед»: x = 19, а количество команд «Назад»: 19 + 12 = 31.
2. Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед 3», Исполнитель алгоритма оказался бы на отметке числовой оси 57 (19 * 3 = 57). После выполнения 31 раз команды «Назад 2» (31 * 2 = 62) он оказался бы на отметке –5 (57 – 62 = –5).
3. Все эти команды можно заменить одной — «Назад 5».
Ответ: команда«Назад 5».
Пример 3. Черепашка является исполнителем для создания графических объектов на рабочем поле. При движении Черепашка оставляет след в виде линии. Черепашка может исполнять следующие команды:
| Название команды | Параметр | Действия исполнителя |
| вп | Число шагов | Продвигается в направлении головы на указанное число шагов |
| нд | Число шагов | Продвигается в направлении, противоположном направлению головы на указанное число шагов |
| пр | Число градусов | Поворачивается направо относительно направления, заданного головой черепашки |
| лв | Число градусов | Поворачивается налево относительно направления, заданного головой черепашки |
Для записи повторяющихся действий (цикла) используется команда Повтори. В этой команде два параметра: первый задает количество повторений (итераций), а второй — список команд которые должны повторяться (тело цикла); список заключается в квадратные скобки.
Записать для исполнителя Черепашка алгоритмы:
а) построения квадрата со стороной 100;
б) построения правильного шестиугольника со стороной 50.
в) построения изображения цифры 4, если голова Черепашки смотрит на север.
Ответ: а) Повтори 4 [вп 100 пр 90]; б) Повтори 6 [вп 50 пр 360/6]; в) вп 100; повтори [лв 135 вп 50].
Пример 4. Два игрока играют в следующую игру (это вариант восточной игры). Перед ними лежат три кучки камней, в первой из которых 2, во второй — 3, в третьей — 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в одной из кучек, или добавляет по два камня в каждую из них. Выигрывает игрок, после хода которого либо в одной из кучек становится не менее 15 камней, либо общее число камней в трех кучках становится не менее 25. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ следует обосновать.
Решение. Удобнее всего составить таблицу возможных ходов обоих игроков. Заметим, что в каждом случае возможны всего четыре варианта хода. В таблице курсивом выделены случаи, которые сразу же приносят поражение игроку, делающему этот ход (например, когда камней в какой-либо кучке становится больше или равно 8, другой игрок непременно выигрывает следующим ходом, удваивая количество камней в этой кучке). Из таблицы видно, что при безошибочной игре обоих игроков первый всегда выиграет, если первым ходом сделает 4, 5, 6. У второго игрока в этом случае все ходы проигрышные.
| 1-й ход | 2-й ход | |||
| Начало | 1-й игрок | 2-й игрок | 1-й игрок | 2-й игрок |
| 2,3,4 | 4,3,4 | 8,3,4 | выигрыш | |
| 4,6,4 | 8,6,4 | выигрыш | ||
| 4,12,4 | выигрыш | |||
| 4,6,8 | выигрыш | |||
| 6,8,6 | выигрыш | |||
| 4,3,8 | выигрыш | |||
| 6,5,6 | 12,5,6 | выигрыш | ||
| 6,10,6 | выигрыш | |||
| 6,5,12 | выигрыш | |||
| 8,7,8 | выигрыш | |||
| 2,6,4 | 4,6,4 | 8,6,4 | выигрыш | |
| 4,12,4 | выигрыш | |||
| 4,6,8 | выигрыш | |||
| 6,8,6 | выигрыш | |||
| 2,12,4 | выигрыш | |||
| 2,6,8 | выигрыш | |||
| 4,8,6 | выигрыш | |||
| 2,3,8 | выигрыш | |||
| 4,5,6 | 8,5,6 | выигрыш | ||
| 4,10,6 | выигрыш | |||
| 4,5,12 | выигрыш | |||
| 6,7,8 | выигрыш |
Пример 5. Записано 7 строк, каждая из которых имеет свой номер. В нулевой строке после номера записана цифра 001. Каждая последующая строка содержит два повторения предыдущей строки и добавленной в конец большой буквы латинского алфавита (первая строка — A, вторая строка — B и т. д.). Ниже приведены первые три строкиєтой записи (в скобках указан номер строки):
Какой символ находится в последней строке на 250-м месте (считая слева направо)?
Примечание. Первые семь букв латинского алфавита: A, B, C, D, E, F, G.
Решение. Найдем длину каждой строки. Длина каждой следующей строки в два раза больше длины предыдущей плюс один символ, длина строк составит:
(6) 127*2+1=255 символов.
Так как задано 7 строк, а нумерация начинается с нулевой строки, последняя строка имеет номер 6 и содержит 255 символов. Последний символ в строке — F. Предпоследний элемент — E, далее идут символы D, C, B, A, 1 (по правилу формирования строк). Таким образом, 250-й символ — это 1.
Пример 6. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:
n := Длина(а)
b := Извлечь(а, k)
нц для i от 7 до n – 1
с := Извлечь(а, i)
b := Склеить(b, с)
Здесь переменные а, b, с — строкового типа; переменные n, i — целые.
В алгоритме используются следующие функции:
Длина(х) — возвращает количество символов в строке х. Имеет тип «целое».
Извлечь(х, i) — возвращает i-й символ слева в строке х. Имеет строковый тип.
Склеить(х, у) — возвращает строку, в которой находятся все символы строки х, а затем все символы строки у. Имеет строковый тип.
Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение «ВОСКРЕСЕНЬЕ»?
Решение. Находим общее число символов в строке а, получим, что n = 11.
Выполняя команду b := Извлечь(а, k) при k = 2, получим, что b примет значение “О“.
В цикле последовательно, начиная с 7-го символа строки а и заканчивая предпоследним (n – 1), извлекаем символ из строки а и присоединяем к строке b.
В результате получим слово “ОСЕНЬ” (символы с номерами 2 + 7 + 8 + 9 + 10).
Пример 7. Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который называется его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.
В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Составить словесный алгоритм и блок-схему проверки принадлежности введенного числа n ряду Фибоначчи.
Решение. Словесный алгоритм:
- Ввести число n.
- Установить значение первых трех чисел Фибоначчи: 1, 1, 2 (сумма двух предыдущих чисел).
- Пока введенное число n больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
- Если число Фибоначчи равно введенному n или было введено число n = 1, значит, что было введено число Фибоначчи, в противном случае — введенное число не является числом Фибоначчи.
Приведенный словесный алгоритм в пункте 1, 2 содержит начальные установки, в пункте 3 — цикл с условием, а пункт 4 — это вывод результата работы алгоритма.
F — текущее число ряда Фибоначчи;
F1 и F2 — два предыдущих числа ряда Фибоначчи для числа F;
n — число, для которого требуется определить, является ли оно числом из ряда Фибоначчи.
Использование основных алгоритмических конструкций: следование, ветвление, цикл
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл.
Базовая структура СЛЕДОВАНИЕ указывает на то, что управление передается последовательно от одного действия к другому.
| Учебный алгоритмический язык | Язык блок-схем |
| действие 1 действие 2 … действие n |
 |
Использование исключительно этой структуры возможно лишь для достаточно простых задач, ход решения которых не меняется в зависимости от конкретных исходных данных и состоит в последовательном выполнении определенных операций.
В качестве примера рассмотрим решение простой задачи.
Пример. Найти y(x) = x2 + 3x + 5, используя только операции умножения и сложения.
Решение. На рис. приводятся два алгоритма, реализующие решение поставленной задачи.
Порядок вычисления y(x) в первом случае — обычный, а во втором — (x + 3) x + 5. Обе формулы эквивалентны, но в первом случае для вычисления необходимо 2 умножения, 2 сложения и 3 переменных (x, y, z), а во втором используются 1 умножение, 2 сложения и 2 переменные (x, y).
Приведенный пример показывает, что даже простые задачи могут решаться с помощью различных вариантов алгоритмов.
Обратите внимание, как в блоке следования используется оператор присваивания.
Операция присваивания — важнейшая операция во всех языках программирования. С помощью присваивания переменные получают новые значения: в левой части инструкции ставится идентификатор величины, а в правой части — выражение, значение которого можно определить.
В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных правой части уже определены.
Базовая структура ВЕТВЛЕНИЕ (РАЗВИЛКА) используется в случае, когда выполнение программы может измениться в зависимости от результата проверки условия и пойти двумя разными (альтернативными) путями. Другими словами, условие является некоторым высказыванием (предикатом) и может быть истинным или ложным (принимать значение TRUE или FALSE). Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Различают две структуры этого типа — полную и неполную. В случае полной структуры, если условие выполняется (является истинным), вслед за ним выполняется действие 1, иначе — действие 2. В случае неполной структуры, если условие выполняется (является истинным), то вслед за ним выполняется действие 1, иначе ничего не происходит.
Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А < X < С, т. е. Х < А и (Х > C) (возможна запись (Х < А) and (Х > C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).
Как определить значение переменной после выполнения алгоритма
Задания Д7 № 369 
В алгоритме, записанном ниже, используются переменные a и b. Символ «:=» обозначает оператор присваивания, знаки «+», «-», «*» и «/» — соответственно операции сложения, вычитания, умножения и деления. Правила выполнения операций и порядок действий соответствуют правилам арифметики. Определите значение переменной a после выполнения алгоритма:
В ответе укажите одно целое число — значение переменной a.
b := 100 + a/b = 102
a := b/6*a = 17 · 10 = 170.
Задания Д7 № 389
В алгоритме, записанном ниже, используются переменные a и b. Символ «:=» обозначает оператор присваивания, знаки «+», «-», «*» и «/» — соответственно операции сложения, вычитания, умножения и деления. Правила выполнения операций и порядок действий соответствуют правилам арифметики. Определите значение переменной a после выполнения алгоритма:
Результат – выполнение – алгоритм
Cтраница 1
Результат выполнения алгоритма предсказуем, выполняется за конечное, желательно минимальное число шагов и представляет, в определенном смысле, практическое значение.
[1]
Результатом выполнения алгоритма должна быть одна или несколько выходных величин, зависящих от исходных данных. Для алгоритма Евклида таким результатом является наибольший общий делитель.
[2]
В результате выполнения алгоритма для k 3 при исходном А – 15 были найдены три подмножества, очерченные пунктирной линией.
[3]
В результате выполнения алгоритма для каждой подсети формируется адекватная ей модель субавтомата, характеризуемая минимальным размером логических последовательностей.
[4]
В результате выполнения алгоритма обратного распространения ошибки вырабатываются ( аналогично тому, как показано в разд.
[5]
В качестве результата выполнения алгоритма в случае отсутствия действительных положительных корней в его схеме ( рис. 10.1) предусматривается печать некоторого целого числа г, служащего в данном случае признаком отсутствия искомого корня.
[7]
Полученное в результате выполнения алгоритма расписание sa изображено на рпс.
[8]
Что получается в результате выполнения алгоритма построения ТСП. Как производится выбор конкретной технологической сети проектирования.
[9]
Таким образом, в результате выполнения алгоритма расчета оптимальных режимов КС запоминается т оптимальных режимов, которые соответствуют управляющим воздействиям для перехода от узлового множества Ri ( VII – 1) к множеству RJ.
[10]
Осредпепные сплайны, получаемые в результате выполнения алгоритма СР, имеют существенные преимущества перед алгебраическими полиномами, получаемыми с помощью алгоритма ПР.
[11]
В результате выполнения алгоритма должно быть получено структурное описание множества рациональных вариантов объекта проектирования.
[12]
На рис. 6.3 представлен алгоритм процесса одномерной оптимизации методом золотого сечения. В результате выполнения алгоритма выдается оптимальное значение проектного параметра х, в качестве которого принимается середина последнего интервала неопределенности.
[13]
ЦВМ может иметь продолжением автоматич. В этом случае результаты выполнения алгоритма удобно представлять в форме, пригодной для управления технологич. ЦВМ эффективно используются для синтеза релейно-контактных схем, различного рода монтажных схем радиоэлектроники, выбора оптим.
[15]
Страницы:
1
2
