Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритмы линейной структурыСодержание книги
Похожие статьи вашей тематики Поиск на нашем сайте
Реализуют линейные вычислительные процессы, в которых отдельные этапы вычислений должны выполняться последовательно друг за другом. Линейные алгоритмы содержат только команды обработки данных. При исполнении алгоритма команды выполняются в порядке их записи. Линейный алгоритм вычисления коэффициентов приведенного квадратного уравнения рассмотрен в предыдущем разделе (рис. 9.2). Для построения таких алгоритмов используется структура следования. Ветвления Вычислительные процессы, в которых в зависимости от тех или иных условий должны выполняться различные этапы вычислений, называются разветвляющимися. Для построения алгоритмов, реализующих такие вычислительные процессы, необходимы специальные команды (управляющие структуры), позволяющие управлять ходом выполнения алгоритма, а менно, осуществлять выбор одного из нескольких возможных действий. Основной такой конструкцией является структура простого ветвления, реализующая принятие двоичного, или дихотомического, решения. Примером алгоритма с простыми ветвлениями является рассмотренный ранее алгоритм выбора максимального числа. Рассмотрим алгоритмы с более сложными ветвлениями. Пример 9.5. Вычислить значение функции, график которой изображен на рис. 9.11. Рис. 9.11. График функции Область определения функции разбивается на 4 участка, на каждом из которых значение функции определяется по различным формулам: Для построения схемы алгоритма решения данной задачи используем вложенную конструкцию структур ветвления (рис. 9.12). Проверяем заданные условия последовательно. Первым проверим условие 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.12. Алгоритм вычисления значения функции Пример 9.6. Вычислить корни квадратного уравнения ax2 + bx + c = 0, a ¹ 0, в области действительных чисел. В зависимости от значения дискриминанта D = b2 - 4ac возможны три случая: 1) квадратное уравнение не имеет действительных корней, если D < 0; 2) квадратное уравнение имеет два действительных равных корня, если D = 0: x1 = x2 = -b/2a; 3) квадратное уравнение имеет два действительных различных корня, если D > 0: Схема алгоритма приведена на рис. 9.13. Алгоритм содержит сложное ветвление, являющееся композицией двух простых ветвлений. Рис. 9.13. Алгоритм решения квадратного уравнения К операндам вещественного типа не следует применять операцию отношения «=» (равно), условие может не выполняться из-за неточного представления вещественных чисел в памяти ЭВМ и неизбежных ошибок округления при вычислениях. В алгоритме отношение D = 0 заменено отношением |D| < e, где e – допустимая погрешность округления. □ Пример 9.7. Даны три числа а, b, с. Определить, имеется ли среди них хотя бы одна пара взаимно-обратных чисел. Числа будут взаимно-обратными, если их произведение равно единице. В алгоритме производятся попарные проверки данных чисел. Если искомая пара найдена, выдается ответ «Да». Если же ни одна проверка не выявит пары взаимно-обратных чисел, выдается ответ «Нет». Алгоритм изображен на рис. 9.14, а. Этот алгоритм верно решает задачу, но не является структурным. Алгоритм легко преобразовать к структурному виду, если продублировать блок печати «Да» и вывести при этом найденные числа (рис. 9.14, б). Дублирование блоков – распространенный прием приведения алгоритмов с ветвлениями к структурному виду. Можно применить другой способ - введение сложных условий (рис. 9.14, в). □ Рис. 9.14. Алгоритм поиска взаимно-обратных чисел Циклы Вычислительные процессы с многократным повторением однотипных вычислений/действий для различных значений входящих величин/данных называются циклическими, повторяемые участки вычислений – циклами, изменяющиеся в цикле величины – переменными цикла. Для организации циклов в алгоритмах необходимо предусмотреть (рис. 9.15): - подготовку цикла – задание начальных значений переменным цикла перед первым его выполнением; - тело цикла – вычислении/действия, повторяемые в цикле для различных значений переменных цикла; - модификацию/изменение значений переменных цикла перед каждым новым его повторением; - управление циклом – проверку условия продолжения/окончания цикла и переход на повторение цикла или его окончание. Рис. 9.15. Общие схемы циклического алгоритма В зависимости от того, где осуществляется проверка условия продолжения или окончания цикла, последний относят к виду: - цикла с предусловием, когда цикл начинается с проверки условия продолжения цикла (рис. 9.15, а); - цикла с постусловием, когда условие проверяется после выполнения тела цикла (рис. 9.15, б). Наиболее наглядным примером циклического вычислительного процесса является задача табулирования функции: вычисления значений функции y = f(x) для значений аргумента x, изменяющихся от начального x0 до конечного xn с постоянным шагом hx (рис. 9.16). Здесь многократно повторяемые действия (тело цикла) – это вычисление значения функции f(x) для очередного значения аргумента x и вывод полученного результата на печать; переменная цикла – переменная x. Цикл выполняется для значений x, равных x0, x0 + hx, x0 + 2hx,..., xn. Для модификации переменной x в цикле её значение надо увеличивать на значение шага: x:= x + hx. Для управления циклом можно использовать структуру цикла как с предусловием, где x <= xn – условие продолжения цикла (рис. 9.16, а), так и с постусловием, где x > xn – условие окончания цикла (рис. 9.16, б). Рис. 9.16. Общие схемы алгоритма табулирования функции Алгоритмы табулирования функции с пред- и постусловием дают, вообще говоря, одинаковый результат. Но тело цикла с предусловием в определенной ситуации может не выполниться ни разу, а тело цикла с постусловием обязательно выполняется хотя бы один раз. Рассмотрим случай, когда нижняя граница x0 переменной x превышает верхнюю xn. В этой ситуации цикл не должен выполняться ни разу. Поэтому в задаче табулирования функции лучше использовать цикл с предусловием, цикл же с постусловием может дать неверный результат. Приведем пример целесообразного использования цикла с постусловием. Пример 9.8. Составим алгоритм вычисления суммы всех целых чисел, вводимых с терминала до тех пор, пока не будет введен нуль. Накопление суммы S будем осуществлять в цикле путем прибавления очередного введенного числа k к сумме всех предыдущих: S:= S + k. Перед началом цикла значение переменной S обнулим: S:= 0. Проверка условия окончания цикла возможна лишь после ввода хотя бы одного числа, поэтому лучше использовать цикл с постусловием. Алгоритм вычисления искомой суммы представлен на рис. 9.17. □ Рис. 9.17. Алгоритм вычисления суммы вводимых чисел Помимо циклов с пред- и постусловием принято различать циклы с заранее неизвестным и известным числом повторений. Примером цикла первого типа могут служить алгоритм вычисления суммы (пример 9.8) и алгоритм Евклида. Примером цикла второго типа – алгоритм табулирования функции, где число повторений цикла Nx определяется как Nx = [(xn – x0)/hx] + 1, где квадратные скобки [ ] означают целую часть числа. В циклах с известным числом повторений всегда можно выделить переменную, определяющую число повторений цикла, значение которой изменяется по заданному закону, например, от начального до конечного с постоянным шагом. Такая переменная используется для управления циклом: в условии окончания цикла осуществляется сравнение текущего значения переменной с заданным порогом. Эту переменную именуют параметром цикла, а сам цикл - циклом с параметром. Для схемного представления цикла с параметром используют специальную управ ляющую структуру с блоком модификации (рис. 9.18), где указывают закон изменения параметра цикла. Например, в задаче табулирования функции y = f(x) параметром цикла является переменная x, закон изменения которой можно представить в виде x = x0 (hx) xn. Схема цикла с параметром для табулирования функции одной переменной приведена на рис. 9.18. На схеме вход 1 в блок i – первоначальный вход в цикл, вход 2 – очередное повторение цикла, выход 3 – окончание цикла. Рис. 9.18. Схема цикла с параметром Блок модификации включает в себя подготовку цикла (x:= x0), изменение параметра цикла при его очередном повторении (x:= x + hx), управление циклом – проверку условия его продолжения (x < xn) и переход на продолжение или окончание цикла. При этом явно выделено тело цикла. Проверка условия x < xn проводится перед каждым, в том числе первым, выполнением цикла, как в цикле с предусловием. И если начальное значение параметра цикла больше конечного, то цикл не выполняется ни разу. Для записи цикла с параметром в языках программирования существует специальный оператор – оператор цикла с параметром. Пример 9.9. Составим алгоритм табулирования сложной функции, приведенный на рис. 9.10, используя структуру цикла с параметром. Алгоритм представлен на рис. 9.19. Тело цикла в этом алгоритме представляет собой композицию двух вложенных структур ветвления и структуры следования. В схеме алгоритма в качестве параметра цикла может выступать переменная любого типа. При реализации этой структуры в различных языках программирования синтаксис оператора цикла с параметром может не допускать использование параметра цикла вещественного типа, как, например, в языке Паскаль. Тогда необходимо введение дополнительной переменной целого типа, определяющей количество значений x, y и используемой в качестве параметра цикла. □ Рис. 9.19. Алгоритм табулирования сложной функции Пример 9.10. Вычислить степень Y = an действительного числа a с натуральным показателем n. Воспользоваться для вычислений следующей формулой: an = a × a × …× a – n раз. Компактно произведение может быть записано в виде Для вычисления Y организуем цикл с параметром i, в котором будем накапливать искомое произведение по следующему правилу: до начала цикла положим Y = 1, а в цикле будем домножать n раз накопленное ранее произведение на a, т. е. Y:= Y·a. Алгоритм представлен на рис. 9.20. □ Пример 9.11. Вычислим сумму квадратов всех целых чисел из заданного интервала [m, n]. В компактной форме записи:
Для вычисления указанной суммы организуем цикл с параметром, в котором будем n раз вычислять значение очередного слагаемого y:= i2 и накапливать искомую сумму S:= S + y. До начала цикла положим S:= 0. Алгоритм приведен на рис. 9.21. □
Пример 9.12. Определим, какое количество точек (x, y) из заданного множества x = x0 + ihx; y = y0 + ihy; i = 0, 1,..., 20, находится в каждой из заштрихованных областей D1 и D2, включая их границы (рис. 9.22). Пример иллюстрирует цикл с несколькими переменными цикла. Число анализируемых точек определяется количеством значений переменной i. Организуем цикл с параметром i, в котором будем изменять значения переменных x, y и для каждой очередной пары (x, y) проверять условия её принадлежности к одной из заданных областей. Рис. 9.22. Области определения Условие попадания точки (x, y) в область D1 – окружность радиусом 2 с центром в точке (5, 4): (x - 5)2 + (y - 4)2 £ 4. Условие попадания точки (x, y) в область D2 – окружность радиусом 3 с центром в точке (-5, -4): (x + 5)2 + (y + 4)2 £ 9. Для проверки условий и подсчета количества KolD1, KolD2 точек, попавших в каждую из областей, используем структуры сокращенного ветвления. Перед циклом надо задать переменным их начальные значения (рис. 9.23). □ Итерационные циклы Среди циклов с неизвестным числом повторений большое место занимают циклы, в которых в процессе повторения тела цикла образуется последовательность значений a1, a2,..., an,..., сходящаяся к некоторому пределу a: Каждое новое значение an в такой последовательности является более точным приближением к искомому результату a. Циклы, реализующие такую последовательность приближений/итераций, называют итерационными. В итерационных циклах условие окончания цикла основывается на свойстве безграничного приближения значений an к искомому пределу с увеличением n. Итерационный цикл заканчивают, если для некоторого значения n выполняется условие |an – an–1| £ e, где e – допустимая погрешность вычислений. При этом результат отождествляют со значением an, т. е. считают, что an = a. Рис. 9.23. Алгоритм подсчета числа точек, Пример 9.13. Составим алгоритм вычисления с заданной погрешностью e, используя следующее рекуррентное соотношение: yn = yn-1 - (x/yn-1 - yn-1)/2; y1 = x/2. Условием окончания данного итерационного цикла будет условие |yn – yn–1| £ e. Для его проверки необходимо иметь два приближения: текущее yn и предыдущее yn-1. Алгоритм можно упростить, если ввести вспомогательную переменную d = yn - yn-1 = (x/yn-1 - yn-1)/2 и использовать ее в условии окончания цикла: | d | £ e. Для проверки такого условия достаточно иметь лишь одно приближение, которое обозначим через y. Алгоритм вычисления квадратного корня представлен на рис. 9.23. Для организации итерационного процесса использована структура цикла с постусловием. □ Рис. 9.23. Алгоритм вычисления квадратного корня Вложенные циклы В практике алгоритмизации достаточно часто встречаются задачи, при решении которых необходимо проектировать алгоритмы с несколькими циклами. Если в теле цикла содержится один или несколько других циклов, то такие циклы называют вложенными. Цикл, содержащий в себе другой цикл, называют внешним. Цикл, содержащийся в теле другого цикла, называют внутренним. Выполняются вложенные циклы следующим образом. Сначала при фиксированных начальных значениях переменных внешнего цикла полностью выполнится внутренний цикл и его переменные «пробегут» все свои значения. Затем переменные внешнего цикла примут следующие значения и, если условие окончания внешнего цикла не будет достигнуто, снова полностью выполнится внутренний цикл и его переменные опять «пробегут» все свои значения и т. д. до тех пор, пока не выполнится условие окончания внешнего цикла. Пример 9.14. Составим алгоритм табулирования сложной функции двух переменных: для x = x0(hx) xn и y = y0(hy) yn. Вычисление значений функции z для всех различных пар (x, y) необходимо организовать следующим образом. Вначале при фиксированном значении одного из аргументов, например, при x = x0, вычислить значения z для всех заданных y: y0, y0 + hy, y0 + 2hy,..., yn. Затем, изменив значение x на x0 + hx, вновь перейти к полному циклу изменения переменной y. Данные действия повторить для всех x: x0, x0 + hx, x0 + 2hx,..., xn. Для записи алгоритма необходима структура вложенных циклов, например, с параметром: внешнего – с параметром x и внутреннего – с параметром y. В данной задаче внешний и внутренний циклы можно поменять местами, при этом изменится только порядок изменения аргументов. Общее количество значений z равно Nz = Nx ּ Ny, где Nx = [(xn – x0)/hx] + 1, Ny = [(yn – y0)/hy] + 1. Алгоритм табулирования функции, выполненный по технологии нисходящего проектирования, представлен на рис. 9.25. Рис. 9.25. Алгоритм табулирования функции двух переменных На первом этапе составлена укрупненная схема решения задачи с выделением операции ввода исходных данных и структуры вложенных циклов. На втором этапе раскрывается тело внутреннего цикла как композиция структур ветвления. □ Пример 9.15. Найти совершенное число в интервале [2, n]. Совершенное число равно сумме всех своих делителей, включая единицу. Например, 28 – совершенное число, так как 28 = 1 + 2 + 4 + 7 + 14. В алгоритме для каждого целого k из заданного интервала будем определять сумму S всех его делителей и сравнивать значения S и k. Если они равны, то анализируемое k есть искомое совершенное число, надо его вывести и закончить поиск, в противном случае, перейти к следующему целому числу из заданного интервала. Для реализации такого алгоритма необходима структура вложенных циклов: внешнего, для просмотра заданного интервала, и внутреннего, для вычисления суммы (рис. 9.26, а). Построенный алгоритм не является структурированным. Рассмотрим один из способов приведения циклического алгоритма к структурному виду. Внешний цикл имеет два условия окончания: исчерпание всех целых чисел из заданного интервала и выполнение равенства k = S. В зависимости от того, какое условие привело к окончанию цикла, необходимо предпринять различные действия. Объединим оба условия окончания цикла в одно: k > n или k = S. Для принятия окончательного решения после завершения цикла проверим, какое же условие привело к его окончанию (рис. 9.26, б). Рис. 9.26. Алгоритм поиска совершенного числа Можно структурировать алгоритм иначе: в цикле с параметром k ввести дополнительную переменную Pr, установив до цикла Pr = 0. Как только совершенное число будет найдено, присвоить Pr значение этого числа. Окончательное решение в этом случае принимается уже на основании анализа признака Pr. Структура внутреннего цикла для вычисления суммы S раскрывается на втором этапе детализации алгоритма. Поскольку все числа делятся на единицу, то сначала устанавливается S = 1. В цикле с параметром i, изменяющимся от 2 до [k/2], суммируются все делители числа k. В интервале от [k/2]+1 до k–1 не может быть делителей числа k. □ Вспомогательные алгоритмы При нисходящем проектировании алгоритма решения сложной задачи исходную задачу разбивают на более простые подзадачи. Каждой такой подзадаче соответствует функционально законченная часть алгоритма. Если оформить эту часть алгоритма в виде самостоятельной алгоритмической единицы со своими входными и выходными данными и, таким образом, что к ней будут возможны многократные обращения (ссылки) из основного алгоритма, то такую алгоритмическую единицу можно назвать вспомогательным или подчиненным алгоритмом (в программировании – подпрограмма). Если для какой-то подзадачи уже известен алгоритм ее решения, то он может быть включен в состав вновь разрабатываемого алгоритма в качестве вспомогательного. Если в алгоритме или в разных алгоритмах встречаются фрагменты, одинаковые по выполняемым действиям и различающиеся только значениями обрабатываемых данных, то такого рода фрагменты могут быть оформлены в виде отдельного алгоритма. В соответствующих местах основного алгоритма будут осуществляться лишь обращения к ним. Это позволяет сократить объем и улучшить структуру всего алгоритма в целом. При использовании вспомогательных алгоритмов возникают вопросы их оформления (таким образом, чтобы в дальнейшем можно было ссылаться на них из других алгоритмов) и техники включения в основные алгоритмы в процессе исполнения последних. В схемах алгоритмов полная формализация в оформлении подчиненных алгоритмов не производится. Однако установлены некоторые общие правила их оформления. Для подчиненного алгоритма определяется его имя, входные и выходные данные. В блок-схеме в блоке начала указывается имя алгоритма и имена его входных величин – исходных данных, а в блоке конца указываются имена выходных величин – результатов. Переменные, перечисленные в блоках начала и конца, называются формальными параметрами. Их введение необходимо для того, чтобы при многократных вызовах подчиненного алгоритма можно было задавать различные значения исходных данных, а после его исполнения воспользоваться полученными результатами. В качестве примера рассмотрим алгоритм вычисления степени y:= an с натуральным показателем n (см. рис. 9.20). Оформим его как вспомогательный алгоритм. На рис. 9.27 приведена схема вспомогательного алгоритма, его имя – Step, его входные параметры – n, a, выходной параметр – y. Рис. 9.27. Вспомогательный алгоритм вычисления степени Вызов вспомогательного алгоритма (ссылка из основного алгоритма) осуществляется с помощью специального блока (см. табл. 9.2). В блоке вызова вспомогательного алгоритма указываются его имя и список фактических параметров: конкретных значений и имен исходных данных и имен вычисляемых результатов, которые должны быть подставлены вместо формальных параметров при исполнении вспомогательного алгоритма. Количество и порядок формальных и фактических параметров должны совпадать. Далее рассмотрим алгоритм вычисления степени z = xk, x ¹ 0, с целым показателем k, пользуясь следующим определением: Алгоритм вычисления z = xk построим, используя вспомогательный алгоритм Step вычисления степени с натуральным показателем. Схема алгоритма приведена на рис. 9.28. Ссылка на вспомогательный алгоритм Step производится дважды: с фактическими параметрами k, x, z при k > 0 и с фактическими параметрами -k, 1/x, z при k < 0. Исполняется вспомогательный алгоритм Step один раз в зависимости от введенного в основной программе значения k. После выполнения совокупности действий, предусмотренных в Step, осуществляется возврат в основной алгоритм к блоку вывода, следующему за блоком обращения к вспомогательному алгоритму. Рис. 9.28. Алгоритм вычисления степени с целым показателем Очень важно понимать суть и механизм замены формальных параметров фактическими. Формальные параметры – это переменные, формально присутствующие во вспомогательном алгоритме и определяющие тип и место подстановки фактических параметров. Фактические параметры – это реальные величины основного алгоритма (константы, переменные, выражения), заменяющие при вызове вспомогательного алгоритма его формальные параметры. Над этими величинами и производятся действия, предусмотренные командами вспомогательного алгоритма. Замена формальных параметров фактическими осуществляется по порядку их следования, число и тип формальных и фактических параметров должны совпадать.
|
||||||
Последнее изменение этой страницы: 2016-04-20; просмотров: 648; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.138.123.240 (0.01 с.) |