Что значит циклический алгоритм в информатике

Информатика

Именная карта банка для детей
с крутым дизайном, +200 бонусов

Закажи свою собственную карту банка и получи бонусы

План урока:

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

Циклы, их виды

Многие операции, действия выполняются однотипно много раз. Этот процесс повторения называют циклом, а повторяемая последовательность – телом цикла. Процедуру с повторяющимися этапами называют циклической.

Каждое повторение действий в алгоритмах – итерация.

Выделяют 3 основных вида повторяющихся структур:

Описывать подобные процессы удобно схематично или при помощи команд.

Цикл с предусловием

Описание цикла с условием двумя способами:

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

Циклический алгоритм, примеры:

алг забор

нц пока есть кирпичи и раствор цемента

если высота забора 1 алгоритм

Источник

Что значит циклический алгоритм в информатике

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

Циклические алгоритмы бывают двух типов:
Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз;
Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия.

В общем случае схема циклического алгоритма со счетчиком будет выглядеть так:

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

Например, в субботу вечером вы смотрите телевизор. Время от времени поглядываете на часы и если время меньше полуночи, то продолжаете смотреть телевизор, если это не так, то вы прекращаете просмотр телепередач.

В общем случае схема циклического алгоритма с условием будет выглядеть так:

Источник

Циклический алгоритм

Цикл — разновидность управляющей конструкции в высокоуровневых языках программирования, предназначенная для организации многократного исполнения набора инструкций. Также циклом может называться любая многократно исполняемая последовательность инструкций, организованная любым способом (например, с помощью условного перехода).

Содержание

Определения

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

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

Виды циклов

Безусловные циклы

Иногда в программах используются циклы, выход из которых не предусмотрен логикой программы. Такие циклы называются безусловными, или бесконечными. Специальных синтаксических средств для создания бесконечных циклов, ввиду их нетипичности, языки программирования не предусматривают, поэтому такие циклы создаются с помощью конструкций, предназначенных для создания обычных (или условных) циклов. Для обеспечения бесконечного повторения проверка условия в таком цикле либо отсутствует (если позволяет синтаксис, как, например, в цикле LOOP…END LOOP языка Ада), либо заменяется константным значением (while true do … в Паскале).

Цикл с предусловием

Цикл с предусловием — цикл, который выполняется пока истинно некоторое условие, указанное перед его началом. Это условие проверяется до выполнения тела цикла, поэтому тело может быть не выполнено ни разу (если условие с самого начала ложно). В большинстве процедурных языков программирования реализуется оператором while, отсюда его второе название — while-цикл.

Цикл с постусловием

Цикл с постусловием — цикл, в котором условие проверяется после выполнения тела цикла. Отсюда следует, что тело всегда выполняется хотя бы один раз. В языке Паскаль этот цикл реализует оператор repeat..until; в Си — do…while.

В трактовке условия цикла с постусловием в разных языках есть различия. В Паскале и языках, произошедших от него, условие такого цикла трактуется как условие выхода (цикл завершается, когда условие истинно, в русской терминологии такие циклы называют ещё «цикл до»), а в Си и его потомках — как условие продолжения (цикл завершается, когда условие ложно, такие циклы иногда называют «цикл пока»)…..

Цикл с выходом из середины

Цикл с выходом из середины — наиболее общая форма условного цикла. Синтаксически такой цикл оформляется с помощью трёх конструкций: начала цикла, конца цикла и команды выхода из цикла. Конструкция начала маркирует точку программы, в которой начинается тело цикла, конструкция конца — точку, где тело заканчивается. Внутри тела должна присутствовать команда выхода из цикла, при выполнении которой цикл заканчивается и управление передаётся на оператор, следующий за конструкцией конца цикла. Естественно, чтобы цикл выполнился более одного раза, команда выхода должна вызываться не безусловно, а только при выполнении условия выхода из цикла.

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

Легко видеть, что с помощью цикла с выходом из середины можно легко смоделировать и цикл с предусловием (разместив команду выхода в начале тела цикла), и цикл с постусловием (разместив команду выхода в конце тела цикла).

Часть языков программирования содержат специальные конструкции для организации цикла с выходом из середины. Так, в языке Ада для этого используется конструкция LOOP…END LOOP и команда выхода EXIT или EXIT WHEN:

Здесь внутри цикла может быть любое количество команд выхода обоих типов. Сами команды выхода принципиально не различаются, обычно EXIT WHEN применяют, когда проверяется только условие выхода, а просто EXIT — когда выход из цикла производится в одном из вариантов сложного условного оператора.

В тех языках, где подобных конструкций не предусмотрено, цикл с выходом из середины может быть смоделирован с помощью любого условного цикла и оператора досрочного выхода из цикла (такого, как break в Си), либо оператора безусловного перехода goto.

Цикл cо счётчиком

Цикл со счётчиком — цикл, в котором некоторая переменная изменяет своё значение от заданного начального значения до конечного значения с некоторым шагом, и для каждого значения этой переменной тело цикла выполняется один раз. В большинстве процедурных языков программирования реализуется оператором for, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик. Например, в языке Оберон-2 такой цикл имеет вид:

(здесь v — счётчик, b — начальное значение счётчика, e — граничное значение счётчика, s — шаг).

Неоднозначен вопрос о значении переменной по завершении цикла, в котором эта переменная использовалась как счётчик. Например, если в программе на языке Паскаль встретится конструкция вида:

возникает вопрос: какое значение будет в итоге присвоено переменной k: 9, 10, 100, может быть, какое-то другое? А если цикл завершится досрочно? Ответы зависят от того, увеличивается ли значение счётчика после последней итерации и не изменяет ли транслятор это значение дополнительно. Ещё один вопрос: что будет, если внутри цикла счётчику будет явно присвоено новое значение? Различные языки программирования решают данные вопросы по-разному. В некоторых поведение счётчика чётко регламентировано. В других, например, в том же Паскале, стандарт языка не определяет ни конечного значения счётчика, ни последствий его явного изменения в цикле, но не рекомендует изменять счётчик явно и использовать его по завершении цикла без повторной инициализации. Программа на Паскале, игнорирующая эту рекомендацию, может давать разные результаты при выполнении на разных системах и использовании разных трансляторов.

Радикально решён вопрос в языке Ада: счётчик считается описанным в заголовке цикла, и вне его просто не существует. Даже если имя счётчика в программе уже используется, внутри цикла в качестве счётчика используется отдельная переменная. Счётчику запрещено явно присваивать какие бы то ни было значения, он может меняться только внутренним механизмом оператора цикла. В результате конструкция

внешне аналогичная вышеприведённому циклу на Паскале, трактуется однозначно: переменной k будет присвоено значение 100, поскольку переменная i, используемая вне данного цикла, не имеет никакого отношения к счётчику i, который создаётся и изменяется внутри цикла. Считается, что подобное обособление счётчика наиболее удобно и безопасно: не требуется отдельное описание для него и минимальна вероятность случайных ошибок, связанных со случайным разрушением внешних по отношению к циклу переменных. Если программисту требуется включить в готовый код цикл со счётчиком, то он может не проверять, существует ли переменная с именем, которое он выбрал в качестве счётчика, не добавлять описание нового счётчика в заголовок соответствующей процедуры, не пытаться использовать один из имеющихся, но в данный момент «свободных» счётчиков. Он просто пишет цикл с переменной-счётчиком, имя которой ему удобно, и может быть уверен, что никакой коллизии имён не произойдёт.

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

В некоторых языках, например, Си и других, произошедших от него, цикл for, несмотря на синтаксическую форму цикла со счётчиком, в действительности является циклом с предусловием. То есть в Си конструкция цикла:

фактически представляет собой другую форму записи конструкции:

То есть в конструкции for сначала пишется произвольное предложение инициализации цикла, затем — условие продолжения и, наконец, выполняемая после каждого тела цикла некоторая операция (это не обязательно должно быть изменение счётчика; это может быть правка указателя или какая-нибудь совершенно посторонняя операция). Для языков такого вида вышеописанная проблема решается очень просто: переменная-счётчик ведёт себя совершенно предсказуемо и по завершении цикла сохраняет своё последнее значение.

Вложенные циклы

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

Полное число исполнений тела внутреннего цикла не превышает произведения числа итераций внутреннего и всех внешних циклов. Например взяв три вложенных друг в друга цикла, каждый по 10 итераций, получим 10 исполнений тела для внешнего цикла, 100 для цикла второго уровня и 1000 в самом внутреннем цикле.

Одна из проблем, связанных с вложенными циклами — организация досрочного выхода из них. Во многих языках программирования есть оператор досрочного завершения цикла (break в Си, exit в Турбо Паскале, last в Perl и т. п.), но он, как правило, обеспечивает выход только из цикла того уровня, откуда вызван. Вызов его из вложенного цикла приведёт к завершению только этого внутреннего цикла, объемлющий же цикл продолжит выполняться. Проблема может показаться надуманной, но она действительно иногда возникает при программировании сложной обработки данных, когда алгоритм требует немедленного прерывания в определённых условиях, наличие которых можно проверить только в глубоко вложенном цикле.

Решений проблемы выхода из вложенных циклов несколько.

Совместный цикл

Ещё одним вариантом цикла является цикл, задающий выполнение некоторой операции для объектов из заданного множества, без явного указания порядка перечисления этих объектов. Такие циклы называются совместными (а также циклами по коллекции, циклами просмотра) и представляют собой формальную запись инструкции вида: «Выполнить операцию X для всех элементов, входящих в множество M». Совместный цикл, теоретически, никак не определяет, в каком порядке операция будет применяться к элементам множества, хотя конкретные языки программирования, разумеется, могут задавать конкретный порядок перебора элементов. Произвольность даёт возможность оптимизации исполнения цикла за счёт организации доступа не в заданном программистом, а в наиболее выгодном порядке. При наличии возможности параллельного выполнения нескольких операций возможно даже распараллеливание выполнения совместного цикла, когда одна и та же операция одновременно выполняется на разных вычислительных модулях для разных объектов, при том что логически программа остаётся последовательной.

Совместные циклы имеются в некоторых языках программирования (C#, JavaScript, Python, LISP, коллекции объектов. В определении такого цикла требуется указать только коллекцию объектов и переменную, которой в теле цикла будет присвоено значение обрабатываемого в данный момент объекта (или ссылка на него). Синтаксис в различных языках программирования синтаксис оператора различен:

Источник

Алгоритм, содержащий цикл и ветвление

Теория к заданию 20 из ЕГЭ по информатике

Алгоритмизация и программирование

Алгоритмы, виды алгоритмов, описание алгоритмов. Формальное исполнение алгоритмов

Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.

Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.

Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.

Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.

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

Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.

Во-вторых, алгоритмы в информатике предназначены для реализации в виде компьютерных программ или для создания некоторой компьютерной технологии. Для выполнения алгоритма требуется конечный объем оперативной памяти и конечное время.

Основные требования, предъявляемые к алгоритмам:

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

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

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

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

Конечность: количество шагов алгоритма должно быть конечным.

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

Для оценки и сравнения алгоритмов существует много критериев. Чаще всего анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объема исходных данных. Используются также термины «временная сложность», «трудоемкость» алгоритма. Фактически эта оценка сводится к подсчету количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также емкостная сложность, т. е. увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности дает количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и емкостных затрат.

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

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

Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:

Для описания алгоритмов наиболее распространены следующие методы (языки):

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

Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.

Формальные алгоритмические языки (языки программирования). При записи алгоритмов используют строго определенный набор символов и составленных из них специальных зарезервированных слов. Имеют строгие правила построения языковых конструкций.

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

Словесный способ (запись на обычном языке) не имеет широкого распространения, т. к. таких описаний есть ряд недостатков:

Графический способ представления информации является более наглядным и компактным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление алгоритма называется блок-схемой. Определенному типу действия (ввод/вывод данных, проверка условия, вычисление выражения, начало и конец алгоритма и т. п.) соответствует определенная геометрическая фигура — блочный символ. Блоки соединяются между собой линиями переходов, которые определяют очередность выполнения действий.

Название символа	Графическое изображение	Комментарии
Пуск/Останов (блоки начала и конца алгоритма)		Указание на начало или конец алгоритма
Ввод/Вывод данных (блоки ввода, вывода		Организация ввода/вывода в общем виде
Процесс (операторные блоки)		Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных
Условие (условный блок)		Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия
Начало цикла с параметром		Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков
Предопределенный процесс		Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам
Печать сообщений (документ)		Вывод результатов на печать

При составлении блок-схемы необходимо проверять выполнение следующих условий:

Псевдокод занимает промежуточное положение между естественным языком и языками программирования. В псевдокоде не приняты строгие синтаксические правила для записи команд, что отличает формальные языки программирования. Однако в псевдокоде есть некоторые конструкции, которые присущи формальным языкам, что облегчает переход от записи алгоритма на псевдокоде к записи алгоритма на языке программирования. Псевдокоды бывают разные. Рассмотрим учебный (школьный) алгоритмический язык АЯ.

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

Общий вид записи алгоритма на псевдокоде:

алг — название алгоритма (аргументы и результаты)

дано — условие применимости алгоритма

надо — цель выполнения алгоритма

нач — описание промежуточных величин

последовательность команд (тело алгоритма)

Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон, — телом алгоритма (исполняемой частью алгоритма).

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

Команды учебного языка:

1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.

2. Операторы ввода/вывода:

ввод (список имен переменных)

вывод (список вывода)

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

3. Оператор ветвления (с использованием команды если. то… иначе…всё; выбор);

4. Операторы цикла (с использованием команд для, пока, до).

Запись алгоритма на псевдокоде:

Здесь в предложениях дано и надо после знака «|» записаны комментарии. Комментарии можно помещать в конце любой строки, они существенно облегчают понимание алгоритма.

При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается произвольное изображение команд. Вместе с тем такая запись позволяет понять человеку суть дела и исполнить алгоритм. Однако алгоритм, предназначенный для исполнения на компьютере, должен быть записан на строго формализованном языке. Такой язык называется языком программирования, а запись алгоритма на этом языке — компьютерной программой.

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

Примеры решения задач

Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:

Первая команда уменьшает число на 1, вторая — увеличивает его втрое.

Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.

Пример 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. У второго игрока в этом случае все ходы проигрышные.

Пример 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. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:

нц для i от 7 до n – 1

Здесь переменные а, 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 ряду Фибоначчи.

Решение. Словесный алгоритм:

Приведенный словесный алгоритм в пункте 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, иначе ничего не происходит.

Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А C) (возможна запись (Х C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).

Структура ВЕТВЛЕНИЕ существует в четырех основных вариантах:

если — то (неполная структура);

если — то — иначе (полная структура);

Источник