Что такое разветвленный алгоритм

Что такое разветвленный алгоритм

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

Если пошел дождь, то надо открыть зонт.

Если прозвенел будильник, то надо вставать.

Если встречу Сашу, то скажу ему …

Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.

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

Источник

Что такое разветвленный алгоритм

Существует несколько типов алгоритмов: линейные, разветвляющие, циклические.

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

ЕСЛИ условие справедливо, ТО выполнить действия 1, ИНАЧЕ выполнить действия 2.

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

Если есть «действия 1» и «действия 2», то говорят о полной альтернативе(рис.1.2).

Рис. 1.2. Полная альтернатива

Если же в качестве «действия 2» имеет место формулировка «перейти к п. N», то такая форма записи называется неполной альтернативой (рис. 1.3).

Рис. 1.3. Неполная альтернатива

Например, составить алгоритм для вычисления функции:

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

Для организации любого цикла необходимо следующее:
1. Задать перед началом цикла начальные значения параметров цикла.
2. Изменять параметры цикла перед каждым новым повторением цикла.
3. Проверять условие повторения или окончания цикла.
4. Переходить к началу цикла, если он не закончен, или выходить из цикла.

Источник

Разветвляющиеся алгоритмы. Сложные условия. Каскадные ветвления

Урок 7. Основы алгоритмизации и программирования на языке Python

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

Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.

Получите невероятные возможности

Конспект урока «Разветвляющиеся алгоритмы. Сложные условия. Каскадные ветвления»

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

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

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

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

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

Есть 3 основные логические операции, 2 из которых – бинарные, то есть соединяют 2 выражения логического типа. Первая логическая операция – конъюнкция или логическое умножение. В русском языке для её обозначения используют союз «И». В языке Python она обозначается словом and. Конъюнкция возвращает значение «истина» тогда и только тогда, когда истинны оба соединяемых высказывания.

Вторая логическая операция – дизъюнкция или логическое сложение. В русском языке она обозначается союзом «или», а в языке Python – служебным словом or. Дизъюнкция возвращает значение «истина» тогда, когда истинно хотя бы одно или оба соединяемых высказывания.

И последняя из основных логических операций – инверсия или логическое отрицание. Эта операция является унарной, то есть применяется к одному логическому выражению. Инверсия изменяет значение выражения, к которому применяется, на противоположное. В русском языке она обозначается частицей «не», а в языке Python – служебным словом not.

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

Вернёмся к решению задачи о принадлежности точки прямоугольнику. Некоторые из вас уже наверняка догадались, что решение этой задачи можно сильно упростить, если записать сложное условие принадлежности точки прямоугольнику. Обратим внимание на то, что первое и третье неравенства можно объединить так же, как второе и четвёртое. Объединённые неравенства будут работать и в языке Python так же, как и одиночные, соединённые операцией конъюнкции. То есть сложную конструкцию, состоящую из четырёх ветвлений, можно заменить всего одним ветвлением, условием которого будут два неравенства. То есть точка принадлежит прямоугольнику, если её координата x больше либо равна координате x левой верхней вершины треугольника, а также меньше либо равна координате x правой нижней вершины прямоугольника И координата точки y меньше или равна координате y левой верхней вершины прямоугольника, а также больше либо равна координате y правой нижней вершины прямоугольника. Если это условие выполняется, тогда точка принадлежит прямоугольнику, в противном случае – точка не принадлежит прямоугольнику. Таким образом, для решения задачи нам достаточно всего одного ветвления.

Напишем программу для решения задачи. Вначале выведем на экран сообщение о том, что это программа, определяющая принадлежность точки прямоугольнику. С помощью второй инструкции print выведем на экран запрос на ввод координат верхней левой вершины прямоугольника. Дальше запишем инструкцию для считывания этих координат в переменные x1 и y1. Так как по условию задачи координаты – целые числа, то при считывании мы будем преобразовывать их значения в целочисленный тип int. Теперь дважды скопируем последние две инструкции и изменим их соответственно для считывания координат нижней правой вершины в переменные x2 и y2, а также для считывания координат точки в переменные x и y. Теперь запишем инструкцию ветвления с условием, состоящим из двух полученных ранее неравенств, соединённых служебным словом and. Если это условие выполняется, то выведем на экран сообщение о том, что точка принадлежит прямоугольнику. В противном случае, выведем сообщение о том, что точка не принадлежит прямоугольнику.

print (‘Программа, определяющая принадлежность точки \nпрямоугольнику.’)

print (‘Введите координаты левой верхней вершины \nпрямоугольника.’)

x1, y1 = int (input ()), int (input ())

print (‘Введите координаты правой нижней вершины \nпрямоугольника.’)

x2, y2 = int (input ()), int (input ())

print (‘Введите координаты точки.’)

x, y = int (input ()), int (input ())

if x2 >= x >= x1 and y2 2 + bx + c = 0. При этом a ≠ 0. Таким образом, квадратное уравнение можно задать значениями его коэффициентов: a, b и c.

Составим блок-схему алгоритма решения задачи. Вначале программа будет принимать на ввод коэффициенты уравнения: a, b и c. Далее мы должны вычислить значение дискриминанта уравнения. Для этого переменной D мы присвоим значение b 2 – 4ac. Далее, как мы помним, нам нужно проверить значение дискриминанта. Если оно отрицательное, то уравнение не имеет решений. Если дискриминант равен нулю, то уравнение имеет единственное решение, которое вычисляется, как b – 2a. Если же дискриминант положительный, то уравнение имеет два решения, которые вычисляются по формуле:

Чтобы это реализовать, сначала мы запишем ветвление с условием, что дискриминант отрицательный. Если это условие выполняется – уравнение не имеет решений, и мы выведем сообщение об этом. Если же условие не выполняется, то мы запишем второе ветвление с условием, что дискриминант равен нулю. Если это условие выполняется, то уравнение имеет одно решение. Мы вичислим его значение в переменной x, после чего выведем результат на экран. Если же и это условие не выполняется, значит дискриминант положительный и уравнение имеет два решения. Мы вычислим эти решения в переменных x1 и x2, после чего выведем их на экран. На этом работа программы будет завершена.

Как видим, наличие вложенного ветвления в одной из ветвей внешнего реализует разделение кода на три ветви. В языке Python разделение кода более чем на две ветви реализуется с помощью каскадного ветвления. Рассмотрим его запись. Как мы помним, обычное ветвление записывается так… Однако между блоками if и else можно добавить ещё один блок – elif с некоторым условием и инструкциями. Это ветвление работает таким образом, что сначала будет проверено условие в блоке if. Если это условие выполняется, то будут выполнены инструкции, записанные в этом блоке. Если же условие в блоке if не выполняется, то будет проверено условие в блоке elif. Если оно выполняется, то будут выполнены инструкции, записанные в этом блоке, если же и это условие не будет выполняться, то будут выполнены инструкции из блока else. Блоков elif может быть несколько, их условия будут проверяться сверху вниз, при этом будут выполнены инструкции, записанные в каком-то одном из блоков.

Используя каскадное ветвление, напишем программу для решения задачи. Вначале с помощью инструкции print выведем сообщение о том, что это программа для решения квадратных уравнений и запрос на ввод его коэффициентов. Дальше запишем инструкцию для считывания коэффициентов квадратного уравнения. В условии не сказано, что это целые числа, поэтому при считывании их значения мы будем преобразовывать в вещественный тип float. Далее вычислим значение дискриминанта в переменной D. Так как в дальнейшем нам понадобится функция извлечения квадратного корня, загрузим её в наш модуль из модуля math. Далее запишем инструкцию ветвления с условием, что дискриминант меньше нуля. Если это условие выполняется, то выведем на экран сообщение о том, что уравнение не имеет решений. Дальше запишем блок elif с условием, что D = 0. В случае выполнения этого условия мы вычислим решение уравнения в переменной x. Далее выведем на экран с соответствующим поясняющим сообщением значение переменной x. В блоке else мы вычислим два решения уравнения в переменных x1 и x2, после чего с соответствующим поясняющим сообщением выведем на экран их значения.

print (‘Программа для решения квадратных уравнений.\nВведите коэффициенты уравнения.’)

a, b, c = float (input ()), float (input ()), float (input ())

from math import sqrt

· Вложенным называется ветвление, которое находится в одной из ветвей другого ветвления.

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

· Основные логические операции: конъюнкцию, дизъюнкцию и инверсию.

· Каскадные ветвления используются для разделения кода более чем на две ветви.

Источник

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

Теория к заданию 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 (исключающее ИЛИ).

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

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

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

Источник