Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Графическое задание алгоритмов. Блок-схемы. Исполнение алгоритмов

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

1. Назовите основные типы алгоритмов и соответствующие им базовые структуры.

2. Что означает термин “линейный алгоритм”?

3. Что означает термин “ветвящийся алгоритм”?

4. Что означает термин “циклический алгоритм”?

5. Что называют итерацией?

6. Опишите структуру оператора присваивания.

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

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

1. Блоки “Начало” и “Конец” (рис.1.1 а) задают вход и выход в алгоритм.

2. Расчетные блоки прямоугольной формы предназначены для расчетов, ввода начальных данных. Примеры показаны на рис. 1.1 б).

а) б)

Рис.1.1

3. Блоки ветвления (рис.1.2 а), имеющие вид ромбов, осуществляют передачу управления при условии выполнения заданных в них логических условий. При выполнении условия управление передается по направлению, указанному стрелкой “да”, иначе – по стрелке “нет”.

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

 

а) б)

Рис.1.2

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

На рис.1.3 а) в качестве примера показана блок-схема алгоритма расчета площади прямоугольника, рассмотренного в примерах 1 и 3, на рис.1.3 б) - блок-схема алгоритма определения величины и номера минимального элемента в вещественном числовом массиве, рассмотренного выше в примерах 2 и 4.

а) б)

Рис.1.3

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

1) изменение значений переменных,

2) передача управления (в случае нарушения последовательного выполнения шагов),

3) циклическое выполнение группы вычислений.

Проиллюстрировать процесс исполнения можно путем словесного описания выполняемых действий либо сведением их в таблицу. Присвоение конкретных значений Е¢ входным параметрам алгоритма осуществляется в начале его исполнения. Результатом применения алгоритма к заданным значениям Е¢ (R¢ = A(Е¢)) являются последние значения результирующих данных R, полученные при исполнении алгоритма. Если какой-либо результирующей переменной ни разу не было присвоено значений, то она после завершения исполнения алгоритма считается не определенной.

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

Пример 5. Исполнить алгоритм определения величины и номера минимального элемента в вещественном числовом массиве по блок-схеме из примера 4 при следующих значениях аргументов: Е = { n = 4, М [1: n ] = { 5,2; 7,4; 3,2; 1,6 }}.

Решение.

М_min = М [1] = 5,2; i_min = 1; i = 1.

Итерация 1. i = i +1 = 2. Условие i £ n = 4 выполняется.

Условие М [ i ] = М [2] = 7,4 < М_min = 5,2 не выполняется, поэтому минимум не изменяем.

Итерация 2. i = i +1 = 3. Условие i £ n = 4 выполняется.

Условие М [ i ] = М [3] = 3,2 < М_min = 5,2 выполняется, поэтому выполняем следующие присваивания: М_min = М [3] = 3,2; i_min = i = 3.

Итерация 3. i = i +1 = 4. Условие i £ n = 4 выполняется.

Условие М [ i ] = М [4] = 1,6 < М_min = 3,2 выполняется, поэтому выполняем присваивания: М_min = М [4] = 1,6; i_min = i = 4.

Итерация 4. i = i +1 = 5. Условие i £ n = 4 не выполняется, поэтому выходим из алгоритма.

Ответ.Искомые значения М_min = 1,6; i_min = i = 4. – последние значения данных переменных, которые были им присвоены на итерации 3.

Пример 6. На рис.1.4 задана блок-схема алгоритма, у которого множество исходных данных Е = { A,B }, множество выходных данных R. = { C }. Определить, чему равен результат применения алгоритма (величина С) к Е¢ = { A= 10, B= 2}:

1) 6; 2) 8; 3) 10; 4) 12; 5) 16.

Решение. Алгоритм содержит два расчетных блока (Б1 и Б2) и один блок ветвления, в котором проверяется логическое условие (А< - 40).

Алгоритм в процессе решения задачи выполняет следующие действия.

Начальные присваивания: A= 10, B= 2

Итерация 1. С= 2 ·В = 4, A= A - 3 ·С = -2, В=В+ 1=3. A = -2 > - 40, продолжение расчетов.

Итерация 2. В=В+ 1= 4. С= 2 ·В = 8, A= A - 3 ·С = -26, В=В+ 1=5. A = -26 > - 40, продолжение расчетов.

Итерация 3. В=В+ 1= 6. С= 2 ·В = 12, A= A - 3 ·С = -62, В=В+ 1=7. A = -62 < - 40, следовательно, условие конца цикла выполнено. Завершение работы алгоритма.

Рис.1.4

Ответ: результат С применения алгоритма к Е¢ = { A= 10, B= 2} равен 12 (это последнее значение, присвоенное С на итерации 3), правильный вариант ответа - 4).

Пример 7. На рис.1.5 задана блок-схема алгоритма, у которого множество исходных данных задано числовым массивом A длины n, Е = { n, A [0: (n- 1)]}, множество выходных данных – сумма S элементов массива A, R = { S }. Определить, чему равен результат применения (величина S) алгоритма A к Е¢ = { n =5, A ={3; 8; -2; 5; -3}}:

1) 13; 2) 11; 3) 14; 4) 15; 5) 19.

Рис.1.5

Решение. Кратко изложим исполнение алгоритма при заданных начальных значениях. Начальные присваивания: i = 0; S=A [0] = 3.

Итерация 1. i = i +1 = 1; S = S+A [1] = 3 + 8 = 11. i = 1 ¹ (n- 1) = 4, продолжение расчетов.

Итерация 2. i = i +1 = 2; S = S+A [2] = 11 + (- 2) = 9. i = 2 ¹ (n-1) = 4, продолжение расчетов.

Итерация 3. i = i +1 = 3; S = S+A [3] = 9 + 5 = 14. i = 3 ¹ (n-1) = 4, продолжение расчетов.

Итерация 4. i = i +1 = 4; S = S+A [4] = 14 + (- 3) = 11. i = 4 = (n-1) = 4, завершение расчетов.

Ответ: результат применения алгоритма к Е¢ = { n =5, A ={3,8,-2,5,-3}}равен 11, правильный вариант ответа - 2).

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

1. Как графически задают алгоритм?

2. Что в блок-схеме обозначают: а)прямоугольниками, б)ромбами, в)параллелограммами?

3. Что означает термин “ исполнение алгоритма ”?

Практические задания.

1. Построить блок-схему алгоритма решения практического задания 1 из п.1.1.

2. Построить блок-схему алгоритма решения практического задания 2 из п.1.1.

3. Построить блок-схему алгоритма решения практического задания 3 из п.1.1.

4. Определить результат (K) применения алгоритма, заданного блок-схемой на рис. 1.6 а, к множеству исходных данных { L= 5}.

5. Определить результат (j) применения алгоритма, заданного блок-схемой на рис. 1.6 б, к множеству исходных данных { i= 4}.

6. Определить результат (массив В длины 4) применения алгоритма, заданного блок-схемой к множеству исходных данных { n= 4, A [0:3] = {2,1,4,2}:

а) б) в)

Рис.1.6


 

<== предыдущая лекция | следующая лекция ==>
Типы алгоритмов. Операция присваивания | Предпосылки появления и основные принципы структурного программирования
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 340; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.015 сек.