Что называется разветвляющимся алгоритмом

Что называется разветвляющимся алгоритмом

Понятие алгоритма. Исполнитель алгоритма. Свойства алгоритма. Способы записи алгоритмов.

Основные алгоритмические структуры: следование, ветвление, цикл; изображение

на блок-схемах. Вспомогательные алгоритмы.

Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач. ). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:

1. Достать ключ из кармана.

2. Вставить ключ в замочную скважину.

3. Повернуть ключ два раза против часовой стрелки.

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

Дискретность (от лат. discretus — разделённый, прерывистый, раздельность) (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);

Детерминированность (от. лат. determinate – определенность, точность) (любое действие должно быть строго и недвусмысленно определено в каждом случае);

Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);

Массовость (один и тот же алгоритм можно использовать с разными исходными данными);

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

1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);

2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие);

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

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

На практике наиболее распространены следующие формы представления алгоритмов:

В письменной форме на естественном языке.

В письменной форме на формальном языке.

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

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

Стадии создания алгоритма:

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

2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия (выбрать среду и объект алгоритма, детализировать алгоритм).

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

Исполнитель — объект, который выполняет алгоритм.

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

Компьютер – автоматический исполнитель алгоритмов.

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

Линейный алгоритм

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

Блок-схема линейного алгоритма:

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

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

Циклические алгоритмы бывают двух типов:

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

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

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

Для счетчика от нач. значения до кон. значения выполнить действие.

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

Читайте также:  Открытые стенды для пк

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

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

Пока условие повторять действие.

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

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

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

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

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

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

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

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

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

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

Условие – это высказывание которое может быть либо истинно, либо ложно.

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

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

До сих пор Вы использовали линейные алгоритмы, т.е. алгоритмы, в которых все этапы решения задачи выполняются строго последовательно. Сегодня Вы познакомитесь с разветвляющимися алгоритмами.

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

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

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

= — больше, чем. или равно

Например, простыми отношениями являются следующие:

x-y>10; k 11; ‘мама’<>‘папа’.

В приведенных примерах первые два отношения включают в себя переменные, поэтому о верности этих отношений можно судить только при подстановке некоторых значений:

если х=25, у=3, то отношение x-y>10 будет верным, т.к. 25-3>10

если х=5, у=30, то отношение x-y>10 будет неверным, т.к. 5-30 t

Задача. Вычислить значение модуля и квадратного корня из выражения (х-у).

Для решения этой задачи нужны уже знакомые нам стандартные функции нахождения квадратного корня — Sqr и модуля — Abs. Поэтому Вы уже можете записать следующие операторы присваивания:

В этом случае программа будет иметь вид:

Koren, Modul : real;

write (‘Введите значения переменных х и у через пробел ‘);

write (‘Значение квадратного корня из выражения (х-у) равно ‘);

write (‘Значение модуля выражения (х-у) равно ‘);

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

Читайте также:  Как записать телефонный разговор на андроиде самсунг

Поэтому наша программа имеет свою допустимую область исходных данных. Найдем эту область. Для этого запишем неравенство х-у>=0 и решив его получим х>=у. Значит, если пользователем нашей программы будут введены такие числа, что при подстановке значение этого неравенства будет равно True, то квадратный корень из выражения (х-у) извлечь можно. А если значение неравенства будет равно False, то выполнение программы закончится аварийно.

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

а) х=23, у=5; б) х=-5, у=15; в) х=8, у=8.

Каждая программа, насколько это возможно, должна осуществлять контроль за допустимостью величин, участвующих в вычислениях. Здесь мы сталкиваемся с разветвлением нашего алгоритма в зависимости от условия. Для реализации таких условных переходов в языке Паскаль используют операторы If и Else, а также оператор безусловного перехода Goto.

Рассмотрим оператор If.

Для нашей задачи нужно выполить следующий алгоритм:

то вычислить значение квадратного корня,

иначе выдать на экран сообщение об ошибочном введении данных.

Запишем его с помощью оператора If. Это будет выглядеть так.

if x>=y

Then

Else

write (‘Введены недопустимые значения переменных‘);

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

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

if

Then

Else

Условный оператор работает по следующему алгоритму.

Сначала вычисляется значение логического выражения, расположенного за служебным словом IF. Если его результат истина, выполняется , расположенный после слова THEN, а действия после ELSE пропускаются; если результат ложь, то, наоборот, действия после слова THEN пропускаются, а после ELSE выполняется .

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

Если в качестве оператора должна выполниться серия операторов, то они заключаются в операторные скобки begin-end. Конструкция Begin . End называется составным оператором.

if

Then

Begin

End

Else

Begin

end;

Определение. Составной оператор объединение нескольких операторов в одну группу. Группа операторов внутри составного оператора заключается в операторные скобки (begin-end).

С учетом полученных знаний преобразуем нашу программу.

Program Znachenia;

Uses

Var

Koren, Modul : real;

Begin

write (‘Введите значения переменных х и у через пробел ‘);

if x>=y

Then

Begin

write (‘Значение квадратного корня из выражения (х-у) равно ‘);

write (‘Значение модуля выражения (х-у) равно ‘);

End

Else

write (‘Введены недопустимые значения переменных‘);

End.

Составным оператором является и такой оператор

Cимвол “;” в данном случае разделяет оператор присваивания S:=0 и пустой оператор.

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

Например, составной оператор

включает лишь один пустой оператор.

Если Вы обратили внимание, программа на языке Паскаль всегда содержит один составной оператор – раздел операторов программы.

Внимание! Перед служебным словом Else разделитель (точка с запятой) не ставится.

Отметим, что большинство операторов в программах на языке Паскаль заканчиваются точкой с запятой, но после некоторых операторов точка с запятой не ставится. Сформулируем общие правила употребления точки с запятой:

1. Каждое описание переменной и определение константы заканчиваются точкой с запятой.

2. Каждый оператор в теле программы завершается точкой с запятой, если сразу за ним не следуют зарезервированные слова End, Else, Until.

3. После определенных зарезервированных слов, таких, как Then, Else, Var, Const, Begin, никогда не ставится точка с запятой.

Рассмотрим еще один пример.

Задача. Вывести на экран большее из двух данных чисел.

Program Example1;

Var

Begin

writeln(‘Введите 2 числа ‘);

if x>y

Then

Else

End.

Можно также использовать и сокращенную (неполную) форму записи условного оператора. Эта форма используется тогда, когда в случае невыполнения условия ничего делать не надо.

Неполная форма условного оператора имеет следующий вид.

if

Then

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

Читайте также:  Сталкер золотой шар консольные команды

Задача. Составить программу, которая, если введенное число отрицательное меняет его на противоположное.

Program Chisla;

Var

Begin

if x

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Учись учиться, не учась! 11155 — | 8287 — или читать все.

АЛГОРИТМЫ. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

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

— Дискретность — алгоритм должен быть представлен как последовательноcть отдельных законченных действий — команд.

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

Результативность — алгоритм должен приводить к решению задачи за определенное число шагов.

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

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

Словесно-формульный – запись алгоритма осуществляется словами естественного языка или с использованием математических формул.

— Измерить ширину комнаты a

— Измерить длину комнаты b

— Умножить длину на ширину a*b

— Результат есть площадь комнаты S

Схематический (графический) – запись алгоритма осуществляется в виде блок-схемы.

Пример

Обозначение блоков

— Ввод, вывод
— Командный блок (выполняются команды)

— Логический блок (проверяется условие)

Исполнители алгоритмов

словесно-формульный блок-схема

Программа

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

Программа – это алгоритм, записанный на каком-либо языке программирования.

ЛИНЕЙНЫЕ АЛГОРИТМЫ

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

Пример линейного алгоритма в словесной форме

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

1. взять 200 г маргарина, пол стакана воды, 3 стакана муки

2. растопить маргарин

5. перемешать, чтобы не было комков

6. положить в холод на 30 минут

Исходные данные: 200 г маргарина, пол стакана воды, 3 стакана муки

Пример линейного алгоритма в форме блок-схемы

Зная длины трех сторон треугольника, вычислить площадь и периметр треугольника.

Пусть a, b, c — длины сторон треугольника. Необходимо найти S — площадь треугольника, P — периметр.

Для нахождения площади можно воспользоваться формулой Герона: , где r — полупериметр.

РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ

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

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

Примеры разветвляющихся алгоритмов

Алгоритм покупки билетов

Пример: Известны коэффициенты и с квадратного уравнения. Составить алгоритм вычисления корней квадратного уравнения.

Входные данные:a, b, c.

Алгоритм вычисления корней

ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ

Если в алгоритме действие, команда или серия команд выполняется несколько раз, то такой алгоритм называется циклическим.

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

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

Проверить условие выхода из цикла

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

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

Пример: Вычислить если x изменяется от до 2 с шагом 0,1.

Решение:Схема алгоритма имеет вид:

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

Пример: Составить блок-схему вычисления функции y = (x 2 -a 3 )/a 2 при x, изменяющимся от x = 0 до x = 3 с шагом 0,1

Пример: Составить блок-схему вычисления функции

Пример: Дана блок-схема алгоритма

Определить результат выполнения алгоритма при определённых значениях исходных данных

Например, при n=15 или n=0 или n=-7

Проверка условия n>0 Þ «Да» Þ Вывод «n-положительное»

Проверка условия n>0 Þ «Нет» Þ Проверка условия n 0 Þ «Нет» Þ Проверка условия n

Ссылка на основную публикацию
Что значит включена переадресация вызова когда звонишь
Что такое переадресация звонков? Что значит «Переадресация звонков»? Данная услуга позволяет всегда оставаться на связи, за счёт перенаправления исходящих звонков....
Чернила для заправки маркеров
Чернила перманентные E-MTK25 Перманентные чернила edding МTК 25. Чернила на спиртовой основе. В бутылочках с капиллярной пипеткой для заправки перманентных...
Чернила для принтера пушкин
Основные характеристики: - стабильны при потоковой печати, в том числе при печати больших тиражей на термоструйных принтерах; - совместимы с...
Что значит восьмиядерный процессор
Дизайн и эргономика важны для гаджетов, но в то же время каждый пользователь понимает, что сердцем любого электронного устройства являются...
Adblock detector