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

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

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

Для записи цикла с параметром в языках программирования существует специальный оператор – оператор цикла с параметром.

Пример 9.48. Составим алгоритм табулирования сложной функции, приведенный на Рис. 9 .30, используя структуру цикла с параметром. Алгоритм представлен на Рис. 9 .39. Тело цикла в этом алгоритме представляет собой композицию двух вложенных структур ветвления и структуры следования.

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

Рис. 9.39. Алгоритм табулирования сложной функции

Пример 9.49. Вычислить степень Y = aⁿ действительного числа a с натуральным показателем n. Воспользоваться для вычислений следующей формулой: aⁿ = a  a  … a – n раз.

Компактно произведение может быть записано в виде

Для вычисления Y организуем цикл с параметром i, в котором будем накапливать искомое произведение по следующему правилу: до начала цикла положим Y = 1, а в цикле будем домножать n раз накопленное ранее произведение на a, т. е. Y := Y·a. Алгоритм представлен на Рис. 9 .40. □

Пример 9.50. Вычислим сумму квадратов всех целых чисел из заданного интервала [m, n]. В компактной форме записи:

Для вычисления указанной суммы организуем цикл с параметром, в котором будем n раз вычислять значение очередного слагаемого y := i² и накапливать искомую сумму S := S + y. До начала цикла положим S := 0. Алгоритм приведен на Рис. 9 .41. □

П ример 9.51. Определим, какое количество точек (x, y) из заданного множества x = x₀ + ih_x; y = y₀ + ih_y; i = 0, 1, ..., 20, находится в каждой из заштрихованных областей D1 и D2, включая их границы (Рис. 9 .42).

Пример иллюстрирует цикл с несколькими переменными цикла. Число анализируемых точек определяется количеством значений переменной i. Организуем цикл с параметром i, в котором будем изменять значения переменных x, y и для каждой очередной пары (x, y) проверять условия её принадлежности к одной из заданных областей.

Рис. 9.42. Области определения

Условие попадания точки (x, y) в область D1 – окружность радиусом 2 с центром в точке (5, 4): (x  5)² + (y  4)²  4.

Условие попадания точки (x, y) в область D2 – окружность радиусом 3 с центром в точке (5, 4): (x + 5)² + (y + 4)²  9.

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

9.6.4.Итерационные циклы

Среди циклов с неизвестным числом повторений большое место занимают циклы, в которых в процессе повторения тела цикла образуется последовательность значений a₁, a₂, ..., a_n, ..., сходящаяся к некоторому пределу a:

Каждое новое значение a_n в такой последовательности является более точным приближением к искомому результату a. Циклы, реализующие такую последовательность приближений/итераций, называют итерационными.

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

|a_n – a_n–1|  ,

где  – допустимая погрешность вычислений. При этом результат отождествляют со значением a_n, т. е. считают, что a_n = a.

Рис. 9.43. Алгоритм подсчета числа точек,
принадлежащих заданным областям

Пример 9.52. Составим алгоритм вычисления с заданной погрешностью , используя следующее рекуррентное соотношение:

y_n = y_n1  (x/y_n1  y_n1)/2; y₁ = x/2.

Условием окончания данного итерационного цикла будет условие |y_n – y_n–1|  . Для его проверки необходимо иметь два приближения: текущее y_n и предыдущее y_n1. Алгоритм можно упростить, если ввести вспомогательную переменную d = y_n  y_n1 = (x/y_n1  y_n1)/2 и использовать ее в условии окончания цикла: | d |  . Для проверки такого условия достаточно иметь лишь одно приближение, которое обозначим через y.

Алгоритм вычисления квадратного корня представлен на Рис. 9 .44. Для организации итерационного процесса использована структура цикла с постусловием. □

Рис. 9.44. Алгоритм вычисления квадратного корня

9.6.5.Вложенные циклы

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

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

Пример 9.53. Составим алгоритм табулирования сложной функции двух переменных:

для x = x₀(h_x) x_n и y = y₀(h_y) y_n.

Вычисление значений функции z для всех различных пар (x, y) необходимо организовать следующим образом. Вначале при фиксированном значении одного из аргументов, например, при x = x₀, вычислить значения z для всех заданных y: y₀, y₀ + h_y, y₀ + 2h_y, ..., y_n. Затем, изменив значение x на x₀ + h_x, вновь перейти к полному циклу изменения переменной y. Данные действия повторить для всех x: x₀, x₀ + h_x, x₀ + 2h_x, ..., x_n.

Для записи алгоритма необходима структура вложенных циклов, например, с параметром: внешнего – с параметром x и внутреннего – с параметром y. В данной задаче внешний и внутренний циклы можно поменять местами, при этом изменится только порядок изменения аргументов.

Общее количество значений z равно N_z = N_xּN_y, где

N_x = [(x_n – x₀)/h_x] + 1, N_y = [(y_n – y₀)/h_y] + 1.

Алгоритм табулирования функции, выполненный по технологии нисходящего проектирования, представлен на Рис. 9 .45.

Рис. 9.45. Алгоритм табулирования функции двух переменных

На первом этапе составлена укрупненная схема решения задачи с выделением операции ввода исходных данных и структуры вложенных циклов. На втором этапе раскрывается тело внутреннего цикла как композиция структур ветвления. □

Пример 9.54. Найти совершенное число в интервале [2, n]. Совершенное число равно сумме всех своих делителей, включая единицу. Например, 28 – совершенное число, так как 28 = 1 + 2 + 4 + 7 + 14.

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

Для реализации такого алгоритма необходима структура вложенных циклов: внешнего, для просмотра заданного интервала, и внутреннего, для вычисления суммы (Рис. 9 .46, а). Построенный алгоритм не является структурированным. Рассмотрим один из способов приведения циклического алгоритма к структурному виду. Внешний цикл имеет два условия окончания: исчерпание всех целых чисел из заданного интервала и выполнение равенства k = S. В зависимости от того, какое условие привело к окончанию цикла, необходимо предпринять различные действия. Объединим оба условия окончания цикла в одно: k > n или k = S. Для принятия окончательного решения после завершения цикла проверим, какое же условие привело к его окончанию (Рис. 9 .46, б).

Рис. 9.46. Алгоритм поиска совершенного числа

Можно структурировать алгоритм иначе: в цикле с параметром k ввести дополнительную переменную Pr, установив до цикла Pr = 0. Как только совершенное число будет найдено, присвоить Pr значение этого числа. Окончательное решение в этом случае принимается уже на основании анализа признака Pr.

Структура внутреннего цикла для вычисления суммы S раскрывается на втором этапе детализации алгоритма. Поскольку все числа делятся на единицу, то сначала устанавливается S = 1. В цикле с параметром i, изменяющимся от 2 до [k/2], суммируются все делители числа k. В интервале от [k/2]+1 до k–1 не может быть делителей числа k. □

9.6.6.Вспомогательные алгоритмы

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

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

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

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

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