KNOWLEDGE HYPERMARKET


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

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



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


Основные темы параграфа:

♦ представление ветвлений на АЯ. Трассировка ветвящихся алгоритмов;
♦ сложные ветвящиеся алгоритмы.


Представление ветвлений на АЯ. Трассировка ветвящихся алгоритмов

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

Первая задача: даны два числа; выбрать большее из них.

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

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


Алгоритм выбора большего из двух чисел

Нетрудно понять смысл этого алгоритма. Если значение переменной А больше, чем B, то переменной С присвоится значение А. В противном случае, когда А < В, переменной С присвоится значение В.

Условием, по которому разветвляется алгоритм, является отношение неравенства А > В. Изучая базы данных и электронные таблицы, вы узнали, что такое отношение является логическим выражением. Если оно справедливо, то результатом будет логическая величина «истина» и выполнение алгоритма продолжится по ветви «да»; в противном случае логическое выражение примет значение «ложь» и выполнение алгоритма пойдет по ветви «нет».

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

Шаг Операция A B C Проверка условия
1 ввод  А, В 5 8
2 А>B 5 8 5 > 8, нет (ложь)
3 C:=B 5 8 8
4 вывод С 5 8 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.


Алгоритм

Шаг Операция A B C D Проверка условия
1 ввод A, B, C 5 7 2 -
2 A > B 5 7 2 - 5 > 7, нет
3 B >C 5 7 2 - 7 > 2, да
4 D:=B 5 7 2 7
5 вывод D 5 7 2 7

<u</u>

Коротко о главном

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

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

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

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


Вопросы и задания

1. Какую структуру имеет алгоритм нахождения большего из двух значений?
2. Почему отношение неравенства можно назвать логическим выражением?
3. В каком случае для числовой переменной следует указывать целый тип, в каком — вещественный?
4. Составьте алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего из двух значений.
5. Составьте алгоритм нахождения наименьшего из трех значений.
6. Для вывода на экран произвольной символьной строки нужно в команде вывода записать эту строку в апострофах. Например, по команде

вывод "ОТВЕТ"

на экран выведется слово ОТВЕТ.

Определите, какая задача решается по следующему алгоритму:

алг Задача-6
вещ  X
нач  ввод X
        если Х<0
        то вывод "отрицательное число'
        иначе вывод “положительное число”
        кв
кон

7. Составьте алгоритм, по которому на компьютере будет происходить следующее: в переменную S вводится возраст Саши, в переменную М вводится возраст Маши. В качестве результата на экран выводится фраза «Саша старше Маши» или «Маша старше Саши» (предполагаем, что кто-нибудь из них обязательно старше).
8. Решите предыдущую задачу, учитывая возможность одинакового возраста Саши и Маши. В таком случае может быть получен ответ: «Саша и Маша — ровесники».
9. Составьте алгоритм упорядочения значений трех переменных по возрастанию, т. е. при любых исходных значениях А, B, C отсортируйте их так, чтобы стало: А < В < С. Проверьте алгоритм трассировкой при разных вариантах значений исходных данных.



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


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


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

Практика
1236084776 kr.jpg задачи и упражнения 
1236084776 kr.jpg самопроверка
1236084776 kr.jpg практикумы, тренинги, кейсы, квесты
1236084776 kr.jpg домашние задания
1236084776 kr.jpg дискуссионные вопросы
1236084776 kr.jpg риторические вопросы от учеников

Иллюстрации
1236084776 kr.jpg аудио-, видеоклипы и мультимедиа 
1236084776 kr.jpg фотографии, картинки 
1236084776 kr.jpg графики, таблицы, схемы
1236084776 kr.jpg юмор, анекдоты, приколы, комиксы
1236084776 kr.jpg притчи, поговорки, кроссворды, цитаты

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

Совершенствование учебников и уроков
1236084776 kr.jpg исправление ошибок в учебнике
1236084776 kr.jpg обновление фрагмента в учебнике 
1236084776 kr.jpg элементы новаторства на уроке 
1236084776 kr.jpg замена устаревших знаний новыми 

Только для учителей
1236084776 kr.jpg идеальные уроки 
1236084776 kr.jpg календарный план на год  
1236084776 kr.jpg методические рекомендации  
1236084776 kr.jpg программы
1236084776 kr.jpg обсуждения


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


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

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