Что называется разветвляющимся алгоритмом
Алгоритмизация | Лекция №3
Линейные и разветвляющиеся алгоритмы
Содержание:
Данные. Понятие типа данных
Алгоритм, реализующий решение некоторой конкретной задачи, всегда работает с данными. Данные – это любая информация, представленная в формализованном виде и пригодная для обработки алгоритмом.
Данные делятся на переменные и константы.
Переменные – это такие данные, значения которых могут изменяться в процессе выполнения алгоритма.
Константы – это данные, значения которых не меняются в процессе выполнения алгоритма.
вычислить площадь круга по формуле S=пR 2
В данном алгоритме необходимо объявить две переменные:
Константой является число п.
Любая константа, как и переменная, занимает ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.
Типы констант определяются по контексту, т.е. по форме записи в тексте. А типы переменных устанавливаются в описаниях переменных.
Операции
Внутр.представле ние
Целые положительные и отрицательные числа.
Формат с фиксированной точкой
Любые (целые и дробные) числа.
Формат с плавающей точкой
Логические операции: И(and), ИЛИ(or), НЕ(not).
Любые символы компьютерного алфавита.
Коды таблицы символьной кодировки. 1 символ – 1 байт.
ЭВМ – исполнитель алгоритмов
Независимо от того, на каком языке программирования будет написана программа, алгоритм решения любой задачи на ЭВМ может быть составлен из команд:
Линейные алгоритмы
Тип алгоритма определяется характером решаемой задачи в соответствии с его командами задачи. Различают три типа алгоритмов: линейные, разветвляющиеся, циклические.
Линейными называются алгоритмы, в которых все действия осуществляются последовательно друг за другом, при этом каждая команда выполняется только один раз строго после той команды, которая ей предшествует.
Таким, например, является алгоритм вычисления по простейшим безальтернативны м формулам, не имеющий ограничений на значения входящих в эти формулы переменных. Как правило, линейные процессы являются составной частью более сложного алгоритма.
Линейный алгоритм составляется из команд присваивания, ввода, вывода и обращения к вспомогательным алгоритмам.
Присваивание – это операция, которая значение выражения, стоящее справа от символа «=» запоминает в переменной или элементе массива, стоящем слева. При присваивании происходит преобразование типов данных, если они не совпадают.
Присваивание может осуществляться двумя способами:
Например : вычислить дробь 
Формат команды присваивания следующий:
Переменная := выражение
Знак « :=» нужно читать как «присвоить».
Команда присваивания обозначает следующие действия, выполняемые компьютером:
1. вычисляется выражение ;
2. полученное значение присваивается переменной.
Поскольку присваивание является важнейшей операцией в вычислительных алгоритмах, обсудим ее более подробно.
В приведенной ниже таблице напротив каждой команды присваивания указываются значения переменных, которые устанавливаются после ее выполнения.
Разветвляющиеся алгоритмы
До сих пор Вы использовали линейные алгоритмы, т.е. алгоритмы, в которых все этапы решения задачи выполняются строго последовательно. Сегодня Вы познакомитесь с разветвляющимися алгоритмами.
Определение. Разветвляющимся называется такой алгоритм, в котором выбирается один из нескольких возможных вариантов вычислительного процесса. Каждый подобный путь называется ветвью алгоритма.
Признаком разветвляющегося алгоритма является наличие операций проверки условия. Различают два вида условий – простые и составные.
Простым условием (отношением) называется выражение, составленное из двух арифметических выражений или двух текстовых величин (иначе их еще называют операндами), связанных одним из знаков:
Например, простыми отношениями являются следующие:
x-y>10; k 11; ‘мама’<>‘папа’.
В приведенных примерах первые два отношения включают в себя переменные, поэтому о верности этих отношений можно судить только при подстановке некоторых значений:
если х=25, у=3, то отношение x-y>10 будет верным, т.к. 25-3>10
если х=5, у=30, то отношение x-y>10 будет неверным, т.к. 5-30 t
Задача. Вычислить значение модуля и квадратного корня из выражения (х-у).
В этом случае программа будет иметь вид:
write (‘Введите значения переменных х и у через пробел ‘);
write (‘Значение квадратного корня из выражения (х-у) равно ‘);
write (‘Значение модуля выражения (х-у) равно ‘);
Казалось бы задача решена. Но мы не учли области допустимых значений для нахождения квадратного корня и модуля. Из курса математики Вы должны знать, что можно найти модуль любого числа, а вот значение подкоренного выражения должно быть неотрицательно (больше или равно нулю).
Поэтому наша программа имеет свою допустимую область исходных данных. Найдем эту область. Для этого запишем неравенство х-у>=0 и решив его получим х>=у. Значит, если пользователем нашей программы будут введены такие числа, что при подстановке значение этого неравенства будет равно True, то квадратный корень из выражения (х-у) извлечь можно. А если значение неравенства будет равно False, то выполнение программы закончится аварийно.
Задание. Наберите текст программы. Протестируйте программу со следующими значениями переменных и сделайте вывод.
а) х=23, у=5; б) х=-5, у=15; в) х=8, у=8.
Каждая программа, насколько это возможно, должна осуществлять контроль за допустимостью величин, участвующих в вычислениях. Здесь мы сталкиваемся с разветвлением нашего алгоритма в зависимости от условия. Для реализации таких условных переходов в языке Паскаль используют операторы If и Else, а также оператор безусловного перехода Goto.
Рассмотрим оператор If.
Для нашей задачи нужно выполить следующий алгоритм:
то вычислить значение квадратного корня,
иначе выдать на экран сообщение об ошибочном введении данных.
Запишем его с помощью оператора If. Это будет выглядеть так.
if x>=y
Then
Else
write (‘Введены недопустимые значения переменных‘);
Теперь в зависимости от введенных значений переменных х и у, условия могут выполняться или не выполняться.
В общем случае полная форма конструкции условного оператора имеет вид:
Then
Else
Условный оператор работает по следующему алгоритму.
Управляющая структура if может показаться негибкой, так как выполняемые действия могут быть описаны только одним оператором. Иногда может потребоваться выполнение последовательности операторов. В этом случае хотелось бы заключить всю последовательность в воображаемые скобки. В Паскале предусмотрен этот случай.
Then
Begin
Else
Begin
Определение. Составной оператор —объединение нескольких операторов в одну группу. Группа операторов внутри составного оператора заключается в операторные скобки (begin-end).
С учетом полученных знаний преобразуем нашу программу.
Program Znachenia;
Uses
Begin
write (‘Введите значения переменных х и у через пробел ‘);
if x>=y
Then
Begin
write (‘Значение квадратного корня из выражения (х-у) равно ‘);
write (‘Значение модуля выражения (х-у) равно ‘);
Else
write (‘Введены недопустимые значения переменных‘);
Составным оператором является и такой оператор
Cимвол “;” в данном случае разделяет оператор присваивания S:=0 и пустой оператор.
Пустой оператор не влечет никаких действий и в записи программы никак не обозначается.
Например, составной оператор
включает лишь один пустой оператор.
Если Вы обратили внимание, программа на языке Паскаль всегда содержит один составной оператор – раздел операторов программы.
Внимание! Перед служебным словом Else разделитель (точка с запятой) не ставится.
Отметим, что большинство операторов в программах на языке Паскаль заканчиваются точкой с запятой, но после некоторых операторов точка с запятой не ставится. Сформулируем общие правила употребления точки с запятой:
1. Каждое описание переменной и определение константы заканчиваются точкой с запятой.
2. Каждый оператор в теле программы завершается точкой с запятой, если сразу за ним не следуют зарезервированные слова End, Else, Until.
3. После определенных зарезервированных слов, таких, как Then, Else, Var, Const, Begin, никогда не ставится точка с запятой.
Рассмотрим еще один пример.
Задача. Вывести на экран большее из двух данных чисел.
Program Example1;
Begin
writeln(‘Введите 2 числа ‘);
if x>y
Then
Else
Можно также использовать и сокращенную (неполную) форму записи условного оператора. Эта форма используется тогда, когда в случае невыполнения условия ничего делать не надо.
Неполная форма условного оператора имеет следующий вид.
Then
Тогда если выражение, расположенное за служебным словом IF. в результате дает истину, выполняются действия после слова THEN, в противном случае эти действия пропускаются.
Задача. Составить программу, которая, если введенное число отрицательное меняет его на противоположное.
Что называется разветвляющимся алгоритмом
Понятие алгоритма. Исполнитель алгоритма. Свойства алгоритма. Способы записи алгоритмов.
Основные алгоритмические структуры: следование, ветвление, цикл; изображение
на блок-схемах. Вспомогательные алгоритмы.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач. ). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:
1. Достать ключ из кармана.
2. Вставить ключ в замочную скважину.
3. Повернуть ключ два раза против часовой стрелки.
Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов которые мы с вами постоянно выполняем. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.
Дискретность (от лат. discretus — разделённый, прерывистый, раздельность) (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
Детерминированность (от. лат. determinate – определенность, точность) (любое действие должно быть строго и недвусмысленно определено в каждом случае);
Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).
1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие);
3. Разветвляющийся алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий);
4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
На практике наиболее распространены следующие формы представления алгоритмов:
В письменной форме на естественном языке.
В письменной форме на формальном языке.
Для более наглядного представления алгоритма широко используется графическая форма – блок-схема, которая составляется из стандартных графических объектов.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура.
Стадии создания алгоритма:
1. Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает (определить цель, наметить план действий).
2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия (выбрать среду и объект алгоритма, детализировать алгоритм).
Объект, который будет выполнять алгоритм, обычно называют исполнителем.
Назначение исполнителя точно выполнить предписания алгоритма, подчас не задумываясь о результате и целях, т.е. формально. Идеальными исполнителями являются машины, роботы, компьютеры.
Компьютер – автоматический исполнитель алгоритмов.
Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.
Линейный алгоритм
Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке в котором они следуют.
Блок-схема линейного алгоритма:
Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Перечень повторяющихся действий называют телом цикла.
Циклические алгоритмы бывают двух типов:
Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз;
Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.
Циклы со счетчиком используют когда заранее известно какое число повторений тела цикла необходимо выполнить. Например, на уроке физкультуры вы должны пробежать некоторое количество кругов вокруг стадиона.
Для счетчика от нач. значения до кон. значения выполнить действие.
Часто бывает так, что необходимо повторить тело цикла, но заранее не известно, какое количество раз это надо сделать. В таких случаях количество повторений зависит от некоторого условия. Такие циклы называются циклы с условием. Циклы в которых сначала проверяется условие, а затем, возможно, выполняется тело цикла называют циклы с предусловием. Если условие проверяется после первого выполнения тела цикла, то циклы называются циклы с постусловием.
Например, в субботу вечером вы смотрите телевизор. Время от времени поглядываете на часы и если время меньше полуночи, то продолжаете смотреть телевизор, если это не так, то вы прекращаете просмотр телепередач.
В общем случае схема циклического алгоритма с условием будет выглядеть так:
Пока условие повторять действие.
При составлении циклических алгоритмов важно думать о том, чтобы цикл был конечным. Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием.
Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая.
Если пошел дождь, то надо открыть зонт.
Если прозвенел будильник, то надо вставать.
Если встречу Сашу, то скажу ему …
Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.
Эти предложения начинаются с проверки какого-либо условия: пошел дождь, прозвенел будильник, встретил Сашу… Далее в зависимости мы либо вылиняем какое-либо действие, либо не выполняем его (или выполняем какое-то другое действие).
Компьютер тоже в зависимости от какого-либо условия может выполнять или не выполнять те или иные действия. Алгоритм, в котором используется условие, получил название разветвляющегося, так как в зависимости от значения условия выбираются те или иные действия.
В общем случае схема разветвляющегося алгоритма будет выглядеть так: «если условие, то действие 1, иначе действие 2» (Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.). Так же можно использовать неполную форму: «если условие, то действие» (Если встречу Сашу, то скажу ему ). В этом случае не предусматривается действий на случай невыполнения условия.
Условие – это высказывание которое может быть либо истинно, либо ложно.
Еще раз обратим внимание, что существует две формы ветвления – неполная (когда присутствует только одна ветвь, т.е. в зависимости от истинности условия либо выполняется, либо не выполняется действие) и полная (когда присутствуют две ветви, т.е. в зависимости от истинности условия выполняется либо одно, либо другое действие).
Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя.
Что называется разветвляющимся алгоритмом
Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая.
Если пошел дождь, то надо открыть зонт.
Если прозвенел будильник, то надо вставать.
Если встречу Сашу, то скажу ему …
Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.
Вычислительный процесс называется ветвящимся, если для его реализации предусмотрено несколько направлений (ветвей). Каждое отдельное направление процесса обработки данных является отдельной ветвью вычислений. Ветвление в программе — это выбор одной из нескольких последовательностей команд при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным или конечным результатам. Признак характеризует свойство данных и имеет два или более значений.
Ветвящийся процесс, включающий в себя две ветви, называется простым, более двух ветвей — сложным. Сложный ветвящийся процесс можно представить с помощью простых ветвящихся процессов.
Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа: «да» — условие выполнено и «нет» — условие не выполнено.
Алгоритмические структуры
Линейный алгоритм
Линейный алгоритм– это алгоритм, в котором все операции выполняются только последовательно (рис.1).
Разветвляющийся (ветвящийся) алгоритм
Разветвляющийся или ветвящийся алгоритм – это алгоритм, в котором последовательность выполнения операций зависит от определенных условий.
Если в алгоритме присутствует «действие 1» и «действие 2» (то есть ветвь 1 и ветвь 2), то это разветвляющийся алгоритм с полной альтернативой (рис.2). Если же вместо «действия 2» предусмотрен переход к выполнению операции «n», которая находится в общей (основной) ветви, то такая форма записи называется неполной альтернативой (рис.3). Во втором случае (то есть в случае неполной альтернативы) в одной из ветвей алгоритма предусмотрены некоторые действия (операции), а во второй ветви нет никаких действий.
Циклический алгоритм
Циклический алгоритм – это алгоритм, в котором многократно выполняются одни и те же действия, например с целью многократного выполнения вычислений по одним и тем же зависимостям при различных значениях входящих в них переменных. Использование циклов существенно сокращает объем алгоритма. Можно выделить три основных типа циклических алгоритмов:
По способу определения числа повторений различают циклы с заранее неизвестным количеством повторений и заранее известным количеством повторений (циклы с параметром).
В цикле с параметром определенная последовательность операций выполняется несколько раз в зависимости от заданной величины, которая называется параметром цикла. Цикл выполняется, пока параметр цикла принимает значения в заданном диапазоне с заданным шагом. Оператор цикла включает имя переменной, конечное значение и шаг.
Выделяют два типа циклов с условием: цикл с предусловием и цикл с постусловием.
В циклах с предусловием условие проверяется на входе (до операций, выполняемых в цикле). В циклах с постусловием условие проверяется после выполнения всех операций внутри цикла. В этом случае операторы тела цикла будут реализованы хотя бы один раз или до тех пор, пока не станет возможным условие выхода из цикла.
В циклах с постусловием сначала выполняются все операции, включенные в цикл, и только после этого проверяется заданное условие. В зависимости от результата проверки осуществляется выход из цикла или его повторение.
Цикл с условием называют также итерационным циклом.
Для изображения циклов с предусловием и постусловием можно использовать символ «Граница цикла» (рис. 4):
Начало цикла 1
Начало цикла 2
Начало цикла 3
Тело цикла 3
Конец цикла 3
Конец цикла 2
Конец цикла 1
Рисунок 5 – Структура алгоритма, содержащего несколько вложенных циклов
Для организации и внутреннего, и внешнего циклов могут использоваться разные типы алгоритмических структур (цикл с параметром, цикл с предусловием, цикл с постусловием).
На рис. 6 представлена блок-схема алгоритма с внутренним циклом. В данном случае и внешний и внутренний циклы организованы на базе алгоритмической структуры «цикл с параметром».
На каждом шаге по внешнему циклу внутренний цикл выполняется несколько раз. Количество внутренних циклов на каждом внешнем цикле зависит от параметра внутреннего цикла.
Пусть, например, задано, что параметр внешнего цикла меняется от 1 до 5 с шагом 1, а параметр внутреннего цикла – от 1 до 10 с шагом 1.
Это означает, что на каждом шаге по внешнему циклу внутренний цикл будет выполняться 10 раз. Так как внешний цикл должен выполниться 5 раз, то внутренний цикл выполнится при этом 50 раз.
Примеры алгоритмов различных типовых структур: линейных, ветвящихся, циклических, с комбинацией типовых структур.