Что такое полное ветвление

Алгоритм разветвляющейся структуры. Полная, неполная форма организации ветвления

Учебная – углубление, обобщение и систематизация знаний по программированию.

Развивающая – развитие алгоритмического мышления, памяти, внимательности.

Воспитательная – развитие познавательного интереса, логического мышления.

1. Организационный момент.

Задание 2.1. Найти ошибку в записи программы:

Write ln (ввести значение R)
Readln (R);
L = 2*Pi*R;
S = Pi * Sqrt (R);
Writeln (‘S=’, S:7);
Writeln (‘l=’, l:7);

End.Program Zadacha;

Writeln (‘ввести значение R’);
Readln (R);
L := 2*Pi*R;
S := Pi * Sqr (R);
Writeln (‘S=’, S:7:2);
Writeln (‘l=’, l:7:2);

3. Введение нового материала

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

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

Общий вид блок-схем алгоритмической структуры “ветвление”

Задание 3.2. Составим блок схему сказочного алгоритма: “Поехал Иван – Царевич на сером волке за Жар – Птицей. Ехал он, ехал, глядь – перед ним лежит огромный камень. На камне надпись: “Направо пойдешь – коня потеряешь, налево пойдешь – голову сложишь…”

Задание 3.3. По условию в блок-схеме определить результат:

Ответ: 1 – кислая среда; 2 – щелочная среда; 3- нейтральная среда.

Синтаксис на языке программирования TurboPascal:

Полное ветвление: if then else ;

Неполное ветвление: if then ;

— логическое выражение типа Boolean;

Если несколько, то они заключаются в скобки и объединяются ключевыми словами: and, or, not.

В TurboPascal, если в качестве оператора должны выполняться серия операторов, то они объединяются в операторные скобки Begin – end;

Задание 4.1. Даны два числа А и В. Найти наибольшее из них.

(Задача решается на основе этапов решения задач на ПК)

Найти: наибольшее из А или В2. Математическая постановка задачиЕсли А>B, то А – наибольшее число, иначе В – наибольшее.3. Разработка алгоритма

рис. 5.4. Разработка программы на изучаемом языке программированияЯзык программирования TurboPascal:

Задание 4.2. Дополним “Задание 4.1.”: найти наибольшее из трех заданных чисел А, В, и С.

Обратим внимание на отличие в записи блок-схемы и программы.

Найти: наибольшее из трех чисел2. Математическая постановка задачиЕсли А>B и А>C, то А – наибольшее число.

Далее можно сравнить только два числа: если В>C, то В – наибольшее, иначе С – наибольшее.3. Разработка алгоритма

рис. 6.4. Разработка программы на изучаемом языке программированияЯзык программирования TurboPascal:

5. Подведение итогов.

Источник

Информатика. 7 класс

Электронное приложение к учебному пособию

Напишите нам

белый — основные материалы, обязательные для изучения;

голубой — примеры, иллюстрирующие основные материалы;

желтый — определения основных понятий;

светло-зеленый — исторические сведения, информация об ученых, внесших вклад в развитие информатики, и другие интересные факты.

В учебном пособии используются следующие условные обозначения:

— вопросы и задания для проверки знаний;

— раздел «Упражнения» содержит задания, при выполнении которых используется компьютер;

— раздел «Упражнения» содержит задания для выполнения в тетради;

— раздел «Упражнения» содержит задания, при выполнении которых может быть использована информация, размещенная на Национальном образовательном портале;

* — задание или пример для любознательных.

§ 12. Алгоритмическая конструкция ветвление

12.1. Команда ветвления

Довольно часто на поставленный вопрос человек получает ответ «да» или «нет». В зависимости от ответа он определяет свои действия и выполняет одну или другую команду (группу команд).

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

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

Ветвление может изображаться на блок-схеме следующим образом:

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

Строка if условие > then является заголовком ветвления. Эту строку можно прочитать следующим образом: «Если условие верно, то». После слова then записывается последовательность команд 1, которая выполнится, если условие истинно. После слова else записывается последовательность команд 2, которая выполнится, если условие ложно. Слова begin и end; в данном случае играют роль операторных скобок. Обратите внимание, что перед словом else точка с запятой не ставится.

Ветвление может быть записано в полной или сокращенной форме.

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

На блок-схеме сокращенная форма ветвления изображается следующим образом:

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

Алгоритм может содержать более одной конструкции ветвления (пример 12.3).

Пример 12.4. Решим задачу if 1 из встроенного задачника.

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

Вначале Робот должен сдвинуться вправо. Если стена снизу, то сверху свободно и можно обойти стену сверху, в противном случае Робот обходит стену снизу.

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

Если сверху свободно, то

Пример 12.5. Робот находится на неизвестной клетке поля без линий. Он должен закрасить клетку слева от себя.

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

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

12.2. Составные условия

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

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

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

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

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

Источник

Основные алгоритмические конструкции. Ветвление

Урок 19. Информатика 8 класс (ФГОС)

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

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

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

Конспект урока «Основные алгоритмические конструкции. Ветвление»

· Составление разветвляющихся алгоритмов.

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

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

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

Рассмотрим пример. На уроке русского языка для того чтобы применить правило правописания приставок на «з-» и «с-» вы будете действовать по алгоритму:

Для принятия решения ход рассуждений может быть таким:

Полная форма ветвления:

Графически, полная форма структуры ветвление представляется следующим образом:

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

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

Иногда, встречаются ситуации, когда вторая последовательность команд отсутствует, то есть сокращённая форма записи.

Графически, неполная форма структуры ветвление представляется следующим образом:

Изображаем блок «Принятие решения», который условно обозначается ромбом, внутри его записывается условие.

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

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

С помощью этих знаков можно сравнивать любые переменные, числа и арифметические выражения, символьные переменные.

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

Обратите внимание на второй блок данной блок-схемы. Здесь записаны имена и типы величин (данных), которые обрабатываются в алгоритме.

В данном примере, в условии, используется одна операция сравнения. Такие условия называются простыми.

То есть простыми называются условия, состоящие из одной операции сравнения.

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

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

Рассмотрим следующее задание: Из ряда чисел 15, 16, 17 и 18 выписать значения х, удовлетворяющие условию из блок-схемы.

Перед нами блок схема. Для определения результата построим таблицу.

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

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

Источник

Информационные технологии копия 2

Основы алгоритмизации и технологии программирования

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

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

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

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

Дискретность (разрывность – противоположно непрерывности) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги».

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

Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Прямо пойдешь – голову потеряешь, направо пойдешь – жену найдешь, налево пойдешь – разбогатеешь. Стоит Иван и думает, что дальше делать». Таких инструкций алгоритм содержать не может.

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

Формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.

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

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

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

Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.

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

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

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

Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем (рис. 1).

(1) Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат);

(8) Блок – решение (проверка условия или условный блок);

(9) Блок, описывающий блок с параметром;

(10) Блок – границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»;

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

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

Основные алгоритмические конструкции

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

Линейная алгоритмическая конструкция

Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i- гo действия (шага) выполняется (i+ 1)-е действие (шаг), если i-e действие – не конец алгоритма.

Опишем алгоритм сложения двух чисел на псевдокоде в виде блок-схемы (рис. 2).

Разветвляющаяся алгоритмическая конструкция

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

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

Заданы три числа. Найти значение наименьшего из них Заданные числа обозначим: а, b, с; результирующее наименьшее – min. На рис. 5 представлена блок-схема алгоритма решения данной задачи.

Алгоритмическая конструкция «Цикл»

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

Арифметический цикл

В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение параметра равно N, на втором – N + h, на третьем – N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но такое, что дальнейшее его изменение приведет к значению, большему, чем К.

Вывести 10 раз слово «Привет!».

Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i=1 будет выведено первое слово, при i=2 будет выведено второе слова и т. д. Так как требуется вывести 10 слов, то последнее значение параметра i=10. В заданном примере требуется 10 раз повторить одно и то же действие: вывести слово «Привет!». Составим алгоритм, используя арифметический цикл, в котором правило изменения параметра i=1,10, 1. т. е. начальное значение параметра i=1; конечное значение i=10; шаг изменения h=1. На рис. 6 представлена блок-схема алгоритма решения данной задачи.

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

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

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

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

Как и в цикле с предусловием, в циклической конструкции с постусловием заранее не определено число повторений тела цикла, оно зависит от входных данных задачи. В отличие от цикла с предусловием, тело цикла с постусловием всегда будет выполнено хотя бы один раз, после чего проверяется условие. В этой конструкции тело цикла будет выполняться до тех пор, пока значение условного выражения ложно. Как только оно становится истинным, выполнение команды прекращается. Блок-схема данной конструкции представлена на рис. 8 двумя способами: с помощью условного блока а и с помощью блока управления б.

Рекурсивный алгоритм

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

Простые типы данных: переменные и константы

Переменная – есть именованный объект (ячейка памяти), который может изменять свое значение. Имя переменной указывает на зн ачение, а способ ее хранения и адрес остаются скрытыми от программиста. Кроме имени и значения, переменная имеет тип, определяющий, какая информация находится в памяти. Тип переменной задает:

Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от О до 255, что в двоичном коде (255₍₁₀₎=11111111₍₂₎) соответствует ячейке памяти длиной в 8 бит (или 1 байт).

В описанных выше алгоритмах (примеры 1-3) все данные хранятся в виде переменных. Например, инструкция «Ввод двух чисел а, b » означает введение пользователем значений двух переменных, а инструкция «К=К + 1» означает увеличение значения переменной К на единицу.

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

Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции «К=К+1» 1 есть константа, или для удобства обозначать идентификаторами: pi=3,1415926536. Только значение pi нельзя изменить, так как это константа, а не переменная.

Структурированные данные и алгоритмы их обработки

Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (а_i) и геометрическая (b_i) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив A (10)», это означает, что даны элементы: a ₁ , a ₂ , …, a ₁₀ . Рассмотрим алгоритмы обработки элементов одномерных массивов.

Ввод элементов одномерного массива осуществляется поэлементно, в порядке, необходимом для решения конкретной задачи. Обычно, когда требуется ввести весь массив, порядок ввода элементов не важен, и элементы вводятся в порядке возрастания их индексов. Алгоритм ввода элементов массива А(10) представлен на рис.9.

В заданном числовом массиве A(l0) найти наибольший элемент и его индекс, при условии, что такой элемент в массиве существует, и единственный.

Обозначим индекс наибольшего элемента т. Будем считать, что первый элемент массива является наибольшим (т = 1). Сравним поочередно наибольший с остальными элементами массива. Если оказывается, что текущий элемент массива а _i (тот, c которым идет сравнение) больше выбранного нами наибольшего а_т, то считаем его наибольшим (т=i) (рис.10).

Рассмотрим двумерный массив (шкаф с множеством ящиков, положение которых определяется двумя координатами – по горизонтали и по вертикали). В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса а _ij , первый индекс i определяет номер строки, в которой находится элемент (координата по горизонтали), а второй j – номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и М, определяющими число строк и столбцов соответственно (рис. 11).

Задана матрица символов (100х100), представляющая собой карту ночного неба; звездам на карте соответствует символы «*». Определить: сколько звезд на карте?

Алгоритм решения задачи достаточно прост, необходимо перебрать все элементы матрицы и посчитать, сколько среди них символов «*». Обозначим К переменную – счетчик. На рис 13. представлена блок-схема решения этой задачи.

Источник