Версия 14:53, 27 июля 2010

Гипермаркет знаний>>Информатика>>Информатика 9 класс>>Информатика: Алгоритмы с ветвящейся структурой

АЛГОРИТМЫ С ВЕТВЯЩЕЙСЯ СТРУКТУРОЙ

§ 36. Алгоритмы с ветвящейся структурой

Основные темы параграфа:
представление ветвлений на АЯ. Трассировка
ветвящихся алгоритмов;
сложные ветвящиеся алгоритмы.
Представление ветвлений на АЯ.
Трассировка ветвящихся алгоритмов
Рассмотрим несколько задач, решение которых на компьютере получается с помощью ветвящихся алгоритмов.
Первая задача: даны два числа; выбрать большее из них.
Пусть исходными данными являются переменные А и. В. Их значения будут задаваться вводом. Значение большего из них должно быть присвоено переменной С и выведено на экран компьютера. Например, если A = 5, В = 8, то должно получиться: С = 8.

Блок-схема алгоритма решения этой задачи изображена на рис. 6.2.


Нетрудно понять смысл этого алгоритма, Если значение переменной А больше, чем B, то переменной С  присвоится значение А. В противном случае, когда А < В, переменной С присвоится значение В.
Условием, по которому разветвляется алгоритм, является отношение неравенства А> В. Изучая базы данных и электронные таблицы, вы узнали, что такое отношение является логическим выражением. Если оно справедливо, то результатом будет логическая величина «истина» и выполнение алгоритма продолжится по ветви «да»; в противном случае логическое выражение примет значение «ложь» и выполнение алгоритма пойдет по ветви «нет».
До выполнения на компьютере правильность алгоритма можно проверить путем заполнения трассировочной таблицы. Вот как будет выглядеть трассировка нашего алгоритма для исходных значений A = 5, В = 8.
Ветвление является структурной командой. Его исполнение происходит в несколько шагов; проверка условия (выполнение логического выражения) и выполнение команд на одной из ветвей «да» или «нет». Поэтому в трассировочной таблице записываются не команды алгоритма, а отдельные операции, выполняемые компьютером на каждом шаге.
В алгоритме на рис. 6.2 используется полное ветвление. Эту же самую задачу можно решить, применяя структурную команду неполного ветвления. Блок-схема такого алгоритма изображена на рис. 6.3.
Выполните самостоятельно трассировку этого алгоритма для вариантов 1)А = 0,2, В = 0,3; 2) А = 7, В = 4; 3) А = 5, В = 5. Если вы все проделаете правильно, то убедитесь, что алгоритм верный.
А теперь запишем рассмотренные алгоритмы на Алгоритмическом языке (АЯ). Во-первых, нужно решить вопрос о том, как описать переменные в этом алгоритме. Вспомним, что для всех переменных в алгоритме на Алгоритмическом языке необходимо указать их тип.


Переменные А, В, С — числовые величины. В этой задаче они могут принимать любые значения. В программировании числовые величины, которые могут иметь любые значения — целые, дробные, — называются вещественными. Им ставится в соответствие вещественный тип. На Алгоритмическом языке этот тип указывается служебным словом вещ.
Как выглядит команда ветвления, вы уже знаете. Вот два алгоритма на АЯ, соответствующие блок-схемам на рис. 6.2 и 6.3:


Под сокращенным названием алгоритмов БИД подразумевается «Большее из двух».


Для программирования характерно то, что одна и та же задача может быть решена с помощью разных алгоритмов. И чем сложнее задача, тем больше можно придумать различных алгоритмов ее решения. Для больших задач (производственных, научных) практически невозможно точное совпадение алгоритмов, составленных разными программистами.
Следующая задача: упорядочить значения двух переменных X и Y по возрастанию. Смысл этой задачи следующий:
если для исходных значении переменных справедливо отношение X < Y (например, X — 1, Y = 2), то оставить их без изменения; если же X > Y (например, X = 2, Y = 1), то выполнить обмен значениями.
Алгоритм обмена значениями двух переменных был рассмотрен в предыдущем параграфе. Вспомним, что для обмена нужна третья вспомогательная переменная.
В алгоритме решения данной задачи используется неполное ветвление. Приведем блок-схему (рис. 6.4) и алгоритм на АЯ.
Здесь роль вспомогательной переменной для обмена выполняет С.


Сложные ветвящиеся алгоритмы
Получим алгоритм решения еще одной задачи: найти наибольшее значение среди трех величин: А, В, С.
Естественно, возникает следующая идея этого алгоритма: сначала нужно найти большее из значений A и В и присвоить его какой-то дополнительной переменной, например D; затем найти большее среди D и С. Это значение можно присвоить той же переменной D.
Решение задачи сводится к двукратному применению уже знакомого алгоритма нахождения большего из двух значений. Блок-схема алгоритма — на рис. 6.5.

Нетрудно догадаться, что «БИТ» обозначает «Большее из трех». В структуре этого алгоритма содержатся два последовательных ветвления: первое — полное, второе — неполное.
Эту же задачу можно решить с помощью алгоритма, имеющего структуру вложенных ветвлении. Его блок-схема приведенная в следующем параграфе на рис. 6.6.


А БОТ как выглядят описание этого алгоритма на АЯ и трассировочная таблица при А = 5, В = 7, С = 2.

Коротко о главном
В команде ветвления в качестве условия может использоваться отношение неравенства между величинами.
Числовые величины, которые могут принимать любые значения (целые и дробные), имеют вещественный тип.
Для решения одной и той же задачи можно построить несколько вариантов алгоритмов.
Несколько ветвлений в одном алгоритме могут быть последовательными и вложенными.
Вопросы и задания
1. Какую структуру имеет алгоритм нахождения большего из двух значений?
2. Почему отношение неравенства можно назвать логическим выражением?
3. В каком случае для числовой переменной следует указывать целый тип, в каком — вещественный?
4. Составьте алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего из двух значений.
5. Составьте алгоритм нахождения наименьшего из трех значений.
6. Для вывода на экран произвольной символьной строки нужно в команде вывода записать эту строку в апострофах. Например, по команде
вывод "ОТВЕТ"
на экран выведется слово ОТВЕТ.
Определите, какая задача решается по следующему алгоритму: алг Задача-6
вещ X
нач ввод X
если Х<0
то вывод "отрицательное число'
иначе вывод "положительное число
кв
кон
7. Составьте алгоритм, по которому на компьютере будет происходить следующее: в переменную S вводится возраст Саши, в переменную М вводится возраст Маши. В качестве результата на экран выводится фраза «Саша старше Маши» или «Маша старше Саши» (предполагаем, что кто-нибудь из них обязательно старше).
8. Решите предыдущую задачу, учитывая возможность одинакового возраста Саши и Маши. В таком случае может быть получен ответ: «Саша и Маша — ровесники».
9. Составьте алгоритм упорядочения значений трех переменных по возрастанию, т. е. при любых исходных значениях А, B, c отсортируйте их так, чтобы стало: А < В < С. Проверьте алгоритм трассировкой при разных вариантах значений исходных данных.

И. Семакин, Л. Залогова, С. Русаков, Л. Шестакова, Информатика, 9 класс
Отослано читателями из интернет-сайтов

_{Сборник конспектов уроков информатики, учебная программа по информатике 9 класс, материалы для подготовки к урокам, готовые домашние задания}

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

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

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

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


Интегрированные уроки

Если у вас есть исправления или предложения к данному уроку, напишите нам.

Если вы хотите увидеть другие корректировки и пожелания к урокам, смотрите здесь - Образовательный форум.