Информатика и программирование - Основы информатики (926517), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

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

б

Рис. 9 .30. Окончание. Алгоритм вычисления сложной функции

9.6.Структуры алгоритмов

9.6.1.Алгоритмы линейной структуры

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

9.6.2.Ветвления

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

Пример 9.44. Вычислить значение функции, график которой изображен на Рис. 9 .31.

Рис. 9.31. График функции

Область определения функции разбивается на 4 участка, на каждом из которых значение функции определяется по различным формулам:

Для построения схемы алгоритма решения данной задачи используем вложенную конструкцию структур ветвления (Рис. 9 .32). Проверяем заданные условия последовательно. Первым проверим условие x  0 и, если оно выполняется, то вычислим y:= –x. Если первое условие не выполняется, то, следовательно, x > 0, и надо проверить следующее условие, x  3. Часть второго условия 0 < x можно не проверять, так как, если дело дошло до проверки этого условия, то заведомо 0 < x. Если условие x  3 выполняется, то вычислим y:= 0, иначе 3 < x, и проверяется условие x  5, проверка 3 < x исключается. Если действительно x  5, то вычисляем y:= x–3, а иначе 5 < x и вычисляем y:= 2, исключая проверку этого последнего условия. □

Рис. 9.32. Алгоритм вычисления значения функции
по заданному графику

Пример 9.45. Вычислить корни квадратного уравнения ax2 + bx + c = 0, a  0, в области действительных чисел. В зависимости от значения дискриминанта D = b²  4ac возможны три случая:

1) квадратное уравнение не имеет действительных корней, если D < 0;

2) квадратное уравнение имеет два действительных равных корня, если D = 0: x₁ = x₂ = b/2a;

3) квадратное уравнение имеет два действительных различных корня, если D > 0:

Схема алгоритма приведена на Рис. 9 .33. Алгоритм содержит сложное ветвление, являющееся композицией двух простых ветвлений.

Рис. 9.33. Алгоритм решения квадратного уравнения

К операндам вещественного типа не следует применять операцию отношения «=» (равно), условие может не выполняться из-за неточного представления вещественных чисел в памяти ЭВМ и неизбежных ошибок округления при вычислениях. В алгоритме отношение D = 0 заменено отношением |D| < , где  – допустимая погрешность округления. □

Пример 9.46. Даны три числа а, b, с. Определить, имеется ли среди них хотя бы одна пара взаимно-обратных чисел.

Числа будут взаимно-обратными, если их произведение равно единице. В алгоритме производятся попарные проверки данных чисел. Если искомая пара найдена, выдается ответ «Да». Если же ни одна проверка не выявит пары взаимно-обратных чисел, выдается ответ «Нет». Алгоритм изображен на Рис. 9 .34, а. Этот алгоритм верно решает задачу, но не является структурным. Алгоритм легко преобразовать к структурному виду, если продублировать блок печати «Да» и вывести при этом найденные числа (Рис. 9 .34, б). Дублирование блоков – распространенный прием приведения алгоритмов с ветвлениями к структурному виду. Можно применить другой способ  введение сложных условий (Рис. 9 .34, в). □

Рис. 9.34. Алгоритм поиска взаимно-обратных чисел

9.6.3.Циклы

Вычислительные процессы с многократным повторением однотипных вычислений/действий для различных значений входящих величин/данных называются циклическими, повторяемые участки вычислений – циклами, изменяющиеся в цикле величины – переменными цикла. Для организации циклов в алгоритмах необходимо предусмотреть (Рис. 9 .35):

- подготовку цикла – задание начальных значений переменным цикла перед первым его выполнением;

- тело цикла – вычислении/действия, повторяемые в цикле для различных значений переменных цикла;

- модификацию/изменение значений переменных цикла перед каждым новым его повторением;

- управление циклом – проверку условия продолжения/окончания цикла и переход на повторение цикла или его окончание.

Рис. 9.35. Общие схемы циклического алгоритма

В зависимости от того, где осуществляется проверка условия продолжения или окончания цикла, последний относят к виду:

- цикла с предусловием, когда цикл начинается с проверки условия продолжения цикла (Рис. 9 .35, а);

- цикла с постусловием, когда условие проверяется после выполнения тела цикла (Рис. 9 .35, б).

Наиболее наглядным примером циклического вычислительного процесса является задача табулирования функции: вычисления значений функции y = f(x) для значений аргумента x, изменяющихся от начального x₀ до конечного x_n с постоянным шагом h_x (Рис. 9 .36). Здесь многократно повторяемые действия (тело цикла) – это вычисление значения функции f(x) для очередного значения аргумента x и вывод полученного результата на печать; переменная цикла – переменная x. Цикл выполняется для значений x, равных x₀, x₀ + h_x, x₀ + 2h_x, ..., x_n. Для модификации переменной x в цикле её значение надо увеличивать на значение шага: x := x + h_x. Для управления циклом можно использовать структуру цикла как с предусловием, где x <= x_n – условие продолжения цикла (Рис. 9 .36, а), так и с постусловием, где x > x_n – условие окончания цикла (Рис. 9 .36, б).

Рис. 9.36. Общие схемы алгоритма табулирования функции

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

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

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

Накопление суммы S будем осуществлять в цикле путем прибавления очередного введенного числа k к сумме всех предыдущих: S := S + k. Перед началом цикла значение переменной S обнулим: S := 0. Проверка условия окончания цикла возможна лишь после ввода хотя бы одного числа, поэтому лучше использовать цикл с постусловием. Алгоритм вычисления искомой суммы представлен на Рис. 9 .37. □

Рис. 9.37. Алгоритм вычисления суммы вводимых чисел

Помимо циклов с пред- и постусловием принято различать циклы с заранее неизвестным и известным числом повторений. Примером цикла первого типа могут служить алгоритм вычисления суммы (пример 9 .47) и алгоритм Евклида. Примером цикла второго типа – алгоритм табулирования функции, где число повторений цикла N_x определяется как

N_x = [(x_n – x₀)/h_x] + 1,

где квадратные скобки [ ] означают целую часть числа.

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

Для схемного представления цикла с п араметром используют специальную управл яющую структуру с блоком модификации ( Рис. 9 .38), где указывают закон изменения п араметра цикла. Например, в задаче т абулирования функции y = f(x) параметром цикла является переменная x, закон изменения которой можно представить в виде x = x₀ (h_x) x_n.

Схема цикла с параметром для табулирования функции одной переменной приведена на Рис. 9 .38. На схеме вход 1 в блок i – первоначальный вход в цикл, вход 2 – очередное повторение цикла, выход 3 – окончание цикла.

Рис. 9.38. Схема цикла с параметром

Блок модификации включает в себя подготовку цикла (x := x₀), изменение параметра цикла при его очередном повторении (x := x + h_x), управление циклом – проверку условия его продолжения (x < x_n) и переход на продолжение или окончание цикла. При этом явно выделено тело цикла. Проверка условия x < x_n проводится перед каждым, в том числе первым, выполнением цикла, как в цикле с предусловием. И если начальное значение параметра цикла больше конечного, то цикл не выполняется ни разу.

Характеристики

Список файлов книги