Вторник, 04.08.2020, 20:57
Вы вошли как Гость | Группа "Не зарегистрированный"Приветствую Вас Гость | RSS
Главная | Каталог статей | Мой профиль | Регистрация | Выход | Вход
QO.DO.AM
 >>>мир предметника 050202

Форма входа

Основное меню

Меню 050202

Учительская OnLine

Категории раздела
8 класс-теория [49]
Теоретический материал по Информатики и ИКТ
9 класс [40]
10 класс [34]
11 класс [37]
Лабораторный практикум [23]
Из математической логики
Алексеев Е.Г., Богатырев С.Д. [97]
Алексеев Е.Г., Богатырев С.Д. Информатика. Мультимедийный электронный учебник, содержит: теорию по Информатике и ИКТ, закрепляющие тесты, иллюстративные материалы для урока Информатики и ИКТ
ИНФОРМАТИКА И ИКТ "Учебное пособие" [17]
Содержательный материал по Информатике и ИКТ. Преподается краткое и отборочное содержание для подготовки и проведения уроков Информатики и ИКТ 8-9 классы, 10-11 классы
Технические средства информатизации [31]
Данное учебное пособие предназначено для изучения дисциплины «Технические средства информатизации» в средних специальных учебных заведениях на специальности 2203- «Программное обеспечение вычислительной техники и автоматизированных систем».
Материалы к урокам ИНФОРМАТИКИ И ИКТ для учащихся с 8-11 классы [57]
Переработанный материал по Информатике и ИКТ, блок схемы, выделение основных понятий информатики красочно и кратко, автор разработок Давыдова Елена Владимировна

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
// Your SEO optimized title page contents

Счетчики

Главная » Архив Информатики и ИКТ » Теория » 9 класс [ Добавить статью ]

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

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


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

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

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

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

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

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


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

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

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

ШагОперацияАВСПроверка условия
1ввод А, В58  
2А>В58 5 > 8, нет (ложь)
3С:=В588 
4вывод С588 

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

В алгоритме на рис. 3.6 используется полное ветвление. Эту же самую задачу можно решить, применяя структурную команду неполного ветвления. Блок-схема такого алгоритма изображена на рис. 3.7.

Рис. 3.7. Алгоритм выбора большего из двух значений (с неполным ветвлением)


Выполните самостоятельно трассировку этого алгоритма для вариантов 1) А = 0,2, В = 0,3; 2) А = 7, В = 4; 3) А = 5, В = 5. Если вы все проделаете правильно, то убедитесь, что алгоритм верный.

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

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

Как выглядит команда ветвления, вы уже знаете. Вот два алгоритма на АЯ, соответствующие блок-схемам на рис. 3.6 и 3.7:

алг БИД1
вещ А, В, С
нач ввод А, В 
     если А>В 
     то С:=А 
     иначе С:=В 
     кв 
     вывод С
кон
алг БИД2 
вещ А, В, С
нач ввод А, В
     С:=А
     если В>А
     то С:=В
     кв
     вывод С 
кон

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

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

Следующая задача: упорядочить значения двух переменных X и Y по возрастанию. Смысл этой задачи следующий: если для исходных значений переменных справедливо отношение X < Y (например, X = 1, Y = 2), то оставить их без изменения; если же X > Y (например, X = 2, Y = 1), то выполнить обмен значениями.

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

В алгоритме решения данной задачи используется неполное ветвление. Приведем блок-схему (рис. 3.8) и алгоритм на АЯ.

алг СОРТИРОВКА 
вещ X, Y, С
нач ввод X, Y
     если X>Y 
     то С:=Х
         Х:=Y
         Y:=С
     кв
     вывод X, Y 
кон

Рис. 3.8. Блок-схема алгоритма упорядочения двух величин

Здесь роль вспомогательной переменной для обмена выполняет С.

Сложные ветвящиеся алгоритмы

Получим алгоритм решения еще одной задачи: найти наибольшее значение среди трех величин: А, В, С.

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

Решение задачи сводится к двукратному применению уже знакомого алгоритма нахождения большего из двух значений. Блок-схема алгоритма - на рис. 3.9

алг БИТ1
вещ А, В, С, D
нач ввод А, B, С
     если А>В
     то D:=A
     иначе D:=B
     кв
     если C>D
     то D:=C
     кв
     вывод D 
кон

Рис. 3.9. Блок-схема алгоритма "БИТ" с последовательными ветвлениями

Нетрудно догадаться, что "БИТ" обозначает "Большее из трех". В структуре этого алгоритма содержатся два последовательных ветвления: первое - полное, второе - неполное.

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

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

Алг БИТ2 
вещ А, В, С, D 
нач ввод А, В, С
     если А>В
     то если A>C то D:=A иначе D:=С кв 
     иначе если В>С то D:=B иначе D:=С кв
     кв
       вывод D
кон

ШагОперацияАВСDПроверка условия
1ввод А, В, С572- 
2А>В572-5 > 7, нет
3В>С572-7 > 2, да
4D:=B5727 
5вывод D5727 
Вопросы и задания

1. Какую структуру имеет алгоритм нахождения большего из двух значений?

2. Почему отношение неравенства можно назвать логическим выражением?

3. В каком случае для числовой переменной следует указывать цб лый тип, в каком - вещественный?

4. Составьте алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего из двух значений.

5. Составьте алгоритм нахождения наименьшего из трех значений.

6. Для вывода на экран произвольной символьной строки нужно в команде вывода записать эту строку в апострофах. Например, по команде

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

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

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

7. Составьте алгоритм, по которому на компьютере будет происходить следующее: в переменную S вводится возраст Саши, в переменную М вводится возраст Маши. В качестве результата на экран выводится фраза "Саша старше Маши" или "Маша старше Саши" (предполагаем, что кто-нибудь из них обязательно старше).

8. Решите предыдущую задачу, учитывая возможность одинакового возраста Саши и Маши. В таком случае может быть получен ответ: "Саша и Маша - ровесники".

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


Категория: 9 класс | Добавил: metalworker (20.02.2013)
Просмотров: 5644
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]


qo.do.am © 2020