Удаление и вставка членов последовательности

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

Пример 1.15. Дана последовательность натуральных чисел X ₁ X₂ , ..., X_N и натуральное число А. Найти и удалить из последовательности элементы, рапные А.

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

Пример 1.16. Дана упорядоченная по возрас­танию последовательность попарно различных нату­ральных чисел Х_1,X ₂,..., X _N и число А. Вставить в эту последовательность число А, не изменяя ее упорядо­ченности.

Для решения задачи требуется организовать два цикла: один для определения места, куда необходимо вставить число А, а второй -для перестановки элементов с этого места и до конца

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

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

Вычисление степенных многочленов (по схеме Горнера) типа Y = A_1*X^N + A_2*X^N-1+A₃-X^N-2+...

+A_N-1*X²+A_N-X + A_N+1, (например, Y = 5Х⁴ - 8Х³ + ЗХ² + 9Х - 4) часто приходится производить при переводе чисел из одной системы счисления в другую с основанием, большим исходного. Организация вычислений непосредственно по приведенному выражению приводит к значительному накоплению ошибки результата из-за многократного возведения в степень. Использование схемы Горнера значительно уменьшает ошибку и сокращает количество операций, поскольку возведение переменной X в любую степень заменяется простым умножением.

Схема Горнера основана на изменении вида представления степенного многочлена, исклю­чающего операции возведения в степень: Y = (...(A_1*X + A₂)*X + A₃ )*X+...+A_N._l)*X + A_N)*X+ A_N+1 например, Y = ((((5 *Х - 8)*X + 3)*X + 9)* X - 4). Обозначив через Y арифметическое выражение в любых внутренних скобках и используя операцию присваивания: Y= Y*X + А₁, легко получим выражение в смежных внешних скобках. При этом для получения результата приведенная операция должна повториться в цикле N раз при изменении переменной цикла I = 2,3,..., N+1 и начальном значении Y = A,.Схема алгоритма вычисления значения степенного многочлена по схеме Горнера представлена на рис. 1.22. Здесь коэффициенты многочлена заданы в виде массива, содержащего N+1 элемент. Начальное значение переменной Y, определенное перед началом цикла, равно коэффициенту А,. Если в многочлене отсутствуют члены с некоторыми степенями переменной X, то соответствующие элементы массива коэффициентов задаются при вводе равными нулю.

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

Пример 1.17. Вычислить сумму членов бесконечного ряда

Вычисления прекратить, как только значение очередного члена ряда станет по модулю меньше заданной заранее погрешности e.

Вариант алгоритма решения задачи представлен на рис.1.23. В алгоритме для получения требуемой суммы вначале вычисляется значение очередного члена ряда (h) и, после его сравнения со значением заданной погрешности, с использованием операции присваивания s =s + h прибавляется к сумме предыдущих членов ряда. Вычисления прекращаются, как только значение очередного члена ряда по абсолютной величине окажется меньше заданной погрешности e.

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

Учитывая, что N!=(N-1)!-N, x^N=x^(N-1)-x и (-1)^N+1 = (-1)^N *(-1), после элементарных сокращений получаем Dh =-x/N. Следовательно, каждый последующий член N рассматриваемого ряда может быть получен простым перемножением значения предыдущего члена ряда на найденное приращение с использованием при этом операции присваиваниях h= -x/N*h. Как видим, эта операция избавила нас от необходимости вычисления факториала N! и N-й степени числа X^N, что существенно уменьшило количество производимых операций и повысило точность вычислений.

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

Пример 1.18. По окончании приемных экзаменов был составлен список группы абитуриентов, содержащий 25 фамилий и экзаменационные оценки каждого абитуриента по 5 дисциплинам. Требуется определить средний балл каждого абитуриента.

Таблицу оценок 25 абитуриентов по 5 предметам представим в виде двумерного массива А_25;, содержащего 25 строк и 5 столбцов:

Каждая строка массива содержит оценки соответствующего абитуриента по всем дисциплинам, столбец - оценки всей группы по одной соответствующей дисциплине. Элемент массива Aj_t -это оценка 1-го абитуриента по J-й дисциплине 1=1, 2,..., 25; J = 1, 2,..., 5.

Задача сводится к определению среднего арифметического значения элементов каждой строки матрицы, для чего предварительно необходимо вычислить сумму значений элементов

2,..., 25. Для вычисления суммы элементов одной строки организуем вложенный цикл с переменной цикла J = 1, 2,..., 5. По завершении работы вложенного цикла определим среднее арифметическое значение элементов строки. Повторяя приведенные действия для каждой строки, вычислим все искомые значения среднего балла каждого абитуриента. Для который будет внешним по отношению к вложенному циклу спеременной.1. Схема алгоритма приведена на рис. 1.24.