Разветвляющиеся алгоритмы алгоритмический язык

Алгоритмизация | Лекция №3

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

Содержание:

Данные. Понятие типа данных

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

Данные делятся на переменные и константы.

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

Константы – это данные, значения которых не меняются в процессе выполнения алгоритма.

вычислить площадь круга по формуле S=пR 2

В данном алгоритме необходимо объявить две переменные:

Константой является число п.

Любая константа, как и переменная, занимает ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

Типы констант определяются по контексту, т.е. по форме записи в тексте. А типы переменных устанавливаются в описаниях переменных.

Операции

Внутр.представле ние

Целые положительные и отрицательные числа.

Формат с фиксированной точкой

Любые (целые и дробные) числа.

Формат с плавающей точкой

Логические операции: И(and), ИЛИ(or), НЕ(not).

Любые символы компьютерного алфавита.

Коды таблицы символьной кодировки. 1 символ – 1 байт.

ЭВМ – исполнитель алгоритмов

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

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

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

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

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

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

Присваивание – это операция, которая значение выражения, стоящее справа от символа «=» запоминает в переменной или элементе массива, стоящем слева. При присваивании происходит преобразование типов данных, если они не совпадают.

Присваивание может осуществляться двумя способами:

Например : вычислить дробь

Формат команды присваивания следующий:

Переменная := выражение

Знак « :=» нужно читать как «присвоить».

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

1. вычисляется выражение ;

2. полученное значение присваивается переменной.

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

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

Источник

Урок по теме «Разветвляющиеся алгоритмы». 9-й класс

Класс: 9

Презентация к уроку

Загрузить презентацию (859,2 кБ)

Тип урока: урок получения новых знаний.

Вид урока: комбинированный.

Оборудование: компьютеры, мультимедийный проектор, мультимедийная презентация (Презентация), листы оценок групп (Приложение 1), карточки с заданиями для групп (Приложение 2), опорный конспект урока для учащихся (Приложение 3), задания для самостоятельной работы (Приложение 4), смайлики для рефлексии (желтые и красные)

В начале урока класс делится на три группы:

1 гр. – 1 уровень сложности (базовый уровень),
2 гр. – 2 уровень сложности (повышенный уровень),
3 гр. – 3 уровень сложности (углубленный уровень).

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

План урока:

V. Подведение итогов урока (3 мин).
VI. Рефлексия (1 мин.)
VII. Домашнее задание (1 мин.)

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

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

Читайте также:  Словообразование нормы современного русского языка

II. Актуализация опорных знаний

III. Изучение нового материала

Вступительное слово учителя: Каждый день, совершая определенные действия, мы выполняем какой-либо алгоритм.
Приведите, пожалуйста, примеры, из повседневной жизни, относящиеся к линейным алгоритмам. (Ученики приводят примеры линейных алгоритмов: посадки саженца в саду, приготовление кофе и т.д.)
К сожалению, в жизни линейные алгоритмы встречаются довольно редко. Всегда появляются какие-нибудь условия, которые изменяют алгоритм.
Например: вы умываетесь, чистите зубы и вдруг перестала идти вода или закончилась паста. Утром, собираясь в школу, мы обязательно посмотрим в окно: если идет дождь, то берем с собой зонт… (Ребята продолжают приводить примеры). Такие условия встречаются в нашей жизни довольно часто.
Находясь на развилке двух (и более) дорог, русский богатырь выберет только одну в зависимости от своей цели и некоторого условия, написанного на камне.
Таким образом, появляется новый вид алгоритма.
– Как бы вы его назвали? (Разветвляющимся или «развилкой»).
– Попробуйте дать ему определение. (Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий)
– Ниже приведены формы ветвлений. Чем они отличаются? Как бы вы их назвали? (Полная и неполная форма ветвления).

– А теперь попробуйте сформулировать тему и цели нашего урока:

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

Полная Неполная
Если условие то действие 1 иначе действие 2 Если условие то действие 1
if условие then действие 1 else действие 2 if условие then действие 1

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

IV. Закрепление изученного

1. Работа в группах

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

Если крикнет рать святая:
«Кинь ты Русь, живи в раю!»
Я скажу: «Не надо рая,
Дайте родину мою»

С.Есенин «Гой ты, Русь, моя родная»

У лукоморья дуб зеленый;
Златая цепь на дубе том:
И днем и ночью кот ученый
Все ходит по цепи кругом:
Идет направо – песнь заводит,
Налево – сказку говорит,
Там чудеса: там леший бродит,
Русалка на ветвях сидит…

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

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

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

Если ласточки летают низко, то будет дождь, иначе дождя не будет. Если погода будет хорошая, то перед тем, как делать уроки, покатаюсь на лыжах.
3 группа
х 5 –2
у 30 6 10

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

Ребята внутри каждой группы делятся на пары.

Задание: Вычислите алгоритм разветвленной структуры, представленной в виде блок-схемы, при заданном входном потоке исходных данных:

а 2 4 6 8
х –5 –1 3 18 22

Выслушиваются ответы всех пар и сравниваются с правильным. Если учащиеся допустили ошибки, то они разбираются.

2) Для более подготовленных учащихся

Ввод Х 4 148
Вывод Х 20 220

3. Самостоятельная работа. (Приложение 4). Каждый ученик садиться за компьютер. На рабочем столе открыв файл «Самостоятельная работа», он выбирает одно любое из предложенных заданий и строит в тетради блок-схему. Тетради в конце урока сдаются учителю на проверку.

V. Подведение итогов урока

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

Учитель: Приведите примеры из других областей наук, где вы встречались с разветвляющимися алгоритмами. (Физика: если ускорение равно нулю, то движение равномерное, иначе неравномерное. Химия: если на внешнем энергетическом уровне больше 3 электронов, то металл, иначе неметалл; Русский язык: если вопрос к глаголу содержит « ь», то глагол пишется с «ь» знаком, иначе без «ь» знака).

Учитель: Вся наша жизнь – это алгоритм сложной «ветвящейся» структуры и надо стремиться к тому, чтобы каждое наше действие было обдуманным и приводило к правильному, достойному результату!

VI. Рефлексия

– Каков же результат нашего урока?
Выполните алгоритм: Если понравился урок, то поднимите желтый смайлик, иначе красный смайлик.

Учитель: Какая это алгоритмическая структура? Какое ветвление вы сейчас выполнили?

VII. Домашнее задание в опорном конспекте (любые два задания)

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

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

Ещё раз о линейности

Линейная последовательность — самая простая из возможных структур. При наличии линейности команды выполняются в чёткой последовательности и в порядке их записи, то есть друг за другом. Вот линейная алгоритмическая последовательность посадки дерева: 1) выкапывание ямки в земле; 2) размещение в ямке саженца; 3) закапывание ямки; 4) поливание места посадки водой.

Такой линейный алгоритм имеет следующую блок-схему:

А вот и общая схема линейного алгоритма:

Ветвление в алгоритмических последовательностях

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

Подобная ситуация заставляет принимать решения с учётом определённого условия. Если нужна жена, то витязь идёт направо, если богатство, то налево, если жизнь не мила, то прямо. Условия, которые влияют на решение, располагаются между словами «если» и «то».

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

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

Логика разветвляющих алгоритмов

Логику можно описать следующим образом:

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

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

Для закрепления можно решить задачу.

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

Решение легко описывается посредством схематических блоков:

Следующий пример легко экстраполируется в жизнь. Речь идёт об алгоритме для перехода дороги при наличии светофора. Он имеет следующий вид: 1. Подходим к светофору. 2. Смотрим, какой горит свет. 3. Если зелёный, переходим дорогу. 4. Если красный, ждём, пока загорится зелёный, а потом переходим дорогу.

Программный способ записи

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

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

Простейший пример описания алгоритма с разветвляющейся структурой — условный оператор IF. Полная конструкция этого условного оператора имеет следующий вид:

Здесь if — это «если», then — это «то», else — «иначе».

Условный оператор работает просто: — вычисляется значение логического выражения, которое расположено после служебного слова IF; — если результат — истина, выполняется оператор 1, который размещён после THEN, причём действие после ELSE пропускается; — если результат — ложь, пропускается уже действие после THEN, а действие после ELSE выполняется с помощью оператора 2.

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

Попробовать этот алгоритм в работе можно на любом онлайн-компиляторе, поддерживающим Pascal. Но не стоит на этом останавливаться — лучше всего написать собственную программу, что позволит получить максимальную пользу от урока.

Источник

Ответы на самые частые вопросы пользователей рунета
Добавить комментарий

Adblock
detector