2. Одномерные массивы

2.1 Составить программу вычисления значения полинома n-ой степени:

y = a₀ xⁿ + a₁ x^n-1 + … + a_n-1 x + a_n .

Для вычисления полинома удобно использовать формулу Горнера (гнездовую процедуру)

y = (…( (a₀ x + a₁ ) x + a₂ ) x + … + a_n-1 ) x + a_n .

Если выражение, стоящее внутри скобок, обозначить y _i, то зна­чение выражения в следующих скобках можно вычислить, используя ре­куррентную формулу

y_i+1 = y_i x + a_n-1.

Значение полинома y получается после повторения этого процесса в цикле n раз. Начальное значение y_i целесообразно взять равным a₀, а цикл начинать с i = 1. Все коэффи­циенты полинома и свободный член, как правило, сводятся в массив, состоящий из элементов n + 1 (n — порядок полинома).

program GORNER (Input, output);

{ вычисление значения полинома по схеме Горнера }

Var

I, N : Integer; { параметр цикла и степень полинома }

X, Y : Real; { аргумент и значение полинома }

А : Array[0..100] of Real;{массив коэффициентов полинома}

Begin

{ Ввод исходных данных }

Writeln ( ’Введите порядок полинома N < 100’ );

Readln ( N );

Writeln (’Введите аргумент’);

Readin ( X );

Writeln (’Введите коэффициенты полинома, ’);

Writeln (’начиная с коэффициента при старшей степени’);

for i := 0 to N do

Read ( A[i] );

Y := A[0];

for i := 1 to N do

Y := Y*X + A[i];

{ вывод результата }

Writeln ('Значение полинома =', Y:10:2)

End.

2.2 Заданы два вектора X = { x_i } и Y = { y_i }, i = 1  n. Написать программу формирования третьего вектора Z = { z_i }, каж­дый элемент которого z_i = max ( x_i, y_i ).

2.3 Задана последовательность величин x₁, x₂, ..., x_n. Написать программу вычисления суммы элементов из указанной после­довательности, удовлетворяющих неравенству x_k > р , где р за­данная величина.

2.4 Написать программу вычисления скалярного произведения двух векторов

_ _ n

( a, b) =  a_i b_i .

ⁱ⁼¹

2.5 Пусть дано натуральное число п и вещественные числа а₁, а₂, ..., а_n. В последовательности а₁, а₂, ..., а_n все отрицательные члены увеличить на 0,5, а все неотрицательные, меньшие среднего арифметического, заменить на 0,1.

2.6 Пусть даны натуральное число п, целые числа а₁, а₂, ..., а_n. Получить сумму положительных, число отрицательных и число нулевых членов последовательности а₁, а₂, ..., а_n..

2.7 Пусть даны целые числа а₁, а₂, ..., а_n, b₁, b₂, ..., b_n. Преобразовать последовательность b₁, b₂, ..., b_n по правилу, согласно которому если а_i  0, то b_i увеличивается в 10 раз, иначе b_i, заменяется нулем (i = 1,..., n).

2.8 С помощью следующего фрагмента программы вычислить сумму тех элементов массива х, индексы которых совпадают со значениями элементов массива а (а_i  а_j при i  j).

Var

x: аrrау [1..100] of real:

а: аrrау [1..30] of 1..100;

2.9 Пусть даны целые числа а₁, а₂, ..., а_n, каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются, то ответом должна служить сама исходная последовательность. Иначе — получите все отрицательные члены последовательности, сохранив порядок их следования.

2.10 Пусть дано натуральное число п и вещественные числа а₁, а₂, ..., а_n. Найти максимальное значение в массиве A и его индекс.

program Maximum ( Input, Output );

Const

MinIndex = 1; MaxIndex = 10;

Type

Index = MinIndex .. MaxIndex;

Massiv = Array [ Index ] of Real;

Var

i, K : Index;

Max : Real;

A : Massiv;

Begin

Writeln ('Введите элементы массива "A"');

for i := MinIndex to MaxIndex do

Read ( A[ i ] );

Max := A[ MinIndex ]; K := MinIndex;

for i := MinIndex + 1 to MaxIndex do

if A[ i ] > Max then

Begin Max := A[ i ]; K := i end;

Write ('Максимумом явл-ся',K:3,' элемент массива "А"');

Writeln (', его значение =', Max:6:2)

End.

2.11 Пусть даны вещественные числа а₁, а₂, ..., а_n.Требуется умножить все члены последовательности а₁, а₂, ..., а_n на квадрат ее наименьшего члена, если а_i  0, и на квадрат ее наибольшего члена, если а_i < 0.

2.12 Пусть даны целые числа а₁, а₂, ..., а_n. Получите новую последовательность, выбросив из исходной максимальный и минимальный члены.

2.13 Пусть дана последовательность из 100 различных целых чисел. Найдите среднее арифметическое чисел этой последовательности, расположенных между максимальным и минимальным числами (в сумму включить и оба этих числа).

2.14 Используя следующий фрагмент программы, преобразуйте массив x по ука­занному ниже правилу, воспользовавшись массивом y как вспомогательным:

Var

х, у: array [1..70] of real;

k: 1..69;

а) все отрицательные элементы массива x перенесите в его начало, а все ос­тальные — в конец, сохраняя исходное взаимное расположение как среди отрицательных, так и среди остальных элементов;

б) элементы массива х циклически сдвиньте на k позиций влево.

2.15 Пусть элементы из массива хупорядочены по неубыванию, а элементы мас­сивау— по невозрастанию. Используя следующий фрагмент программы, объедините элементы этих двух массивов в один массивzтак, чтобы они ока­зались упорядоченными по неубыванию:

Const

k = 10:

m = 20;

n = k + m;

Var

x : array[ 1..k ] of real;

у : array[ 1..m ] of real;

z : array[ 1..n ] of real;

2.16 Пусть даны вещественные числа а₁, а₂, ..., а_2n. Получите:

а) max ( а₁ + а_2n, а₂ + а_2n - 1, ..., а_n + а_n +1 ) ;

б) min ( а₁а_n+1, а₂а_n+2, ... , а_nа_2n ) .

2.17 Пусть даны вещественные числа а₁, а₂, ..., а₂₀. Преобразуйте последовательность по правилу: большее из а _i и а _i+10 (i = 1,...,10) примите в ка­честве нового значения а _i, меньшее — в качестве нового значения а _i+10.

2.18 Пусть даны целые числа а₁, а₂, ..., а_n. Если в данной последовательности ни одно четное число не расположено после нечетного, то получите все отрицатель­ные члены последовательности, иначе — все положительные. Порядок сле­дования чисел в обоих случаях замените обратным.

2.19 Пусть дан фрагмент программы:

Var

k : 0 .. 9999:

d : array [ 1..4 ] of '0' .. '9';

а) запишите в массив d цифры числа k;

б) получите целое k, составленное из цифр массива d.

2.20 В массиве из 20 целых чисел найдите наибольший элемент среди отрицатель­ных (считайте, что такой элемент один) и поменяйте его местами с первым элементом.

2.21 Пусть даны натуральные числа п, а₁, а₂, ..., а_n. Определите количество членов а _i последовательности а₁, а₂, ..., а_n:

а) являющихся нечетными числами;

б) кратных 3 и не кратных 5;

в) являющихся квадратами четных чисел;

г) удовлетворяющих условию: а _i < (а _i + а _i+1)/2;

2.22 Составить программу для подсчета числа компонент логичес­кого вектора В = { b_i }, i = 1  n, имеющих значение false.

2.23 Составить программу формирования из вектора A = { a_i }, i = 1  3n вектора В = { b_i }, i = 1  n, очередная компонента которого равна среднему арифметическому очередной тройки компонент вектора А.

2.24 Составить программу осуществления циклического сдвига влево на одну позицию компонент вектора В = { b_i }, i = 1 ¸ n.

2.25 Составить программу присвоения логической переменной A значения true, если элементы вещественного вектора В = { b_i }, i = 1 ¸ n образуют неубывающую последовательность (b₁ ≤ b₂ ≤ ... ≤ b_n) и значение false — в противном случае.

2.26 Задан вектор A = { a_i }, i = 1  n. Составить программу для формирования нового вектора A = { a_i }, i = 1  n-1, получаемого из вектора А путем исключения минимального элемента (с сохранением поряд­ка расположения оставшихся элементов).

2.27 Составить программу преобразования вектора A = { a_i }, i = 1  n так, чтобы его компоненты располагались в обратном порядке, т.е. получить вектор A = { a_n , a_n-1,…, a₁ }.

2.28 Составить программу подсчета у логического вектора В = { b_i }, i = 1 ¸ n максимального количества стоящих подряд компонент с зна­чением false.

2.29 Задан вектор В = { b_i }, i = 1 ¸ n. Составить программу вы­числения наибольшего и наименьшего значения модуля разности между соседними элементами.

2.30 Составить программу объединения двух упорядоченных последо­вательностей чисел a₁ ≤ a₂ ≤ ... ≤ a_n и b₁ ≤ b₂ ≤ ... ≤ b_m в одну упо­рядоченную последовательность.

2.31 Пусть даны вещественные числа а₁, а₂, ..., а_n, b₁, b₂, ..., b_n. Вычислите произведение ( а₁ + b_n )( а₂ + b_n -1 )...( а_n + b₁ ).

2.32 Используя следующий фрагмент, напишите программы для решения пере­численных ниже задач:

Const

n = 20;

Var

x: array [1..n] of integer;

y, k : integer; t: Boolean;

а) переменной t присвоить значение true, если элементы массива x упорядо­чены по возрастанию, иначе значение false;

б) переменной t присвоить значение true, если в массиве x нет нулевых эле­ментов и при этом положительные элементы чередуются с отрицатель­ными, иначе значение false;

в) переменной k присвоить либо номер первого вхождения у в массив х, либо число n+1, если у не входит в х;

г) вычислить y = x₁ + x₁х₂ + x₁х₂х₃ + ... + x₁х₂...х_т, где т — либо номер пер­вого отрицательного элемента массива х, либо число n, если в массиве x нет отрицательных элементов.

2.33 Пусть дан массив из n элементов. Каждый отрицательный элемент замените полусуммой тех двух элементов, которые стоят рядом с ним справа и слева.

2.34 Пусть дана последовательность из n элементов. Уменьшите ее, удалив пер­вый из отрицательных и минимальный из положительных (считайте, что та­кой элемент один) и сдвинув все остальные к началу.

2.35 Пусть дана последовательность из n элементов. Уменьшите ее, удалив все минимальные и максимальные элементы и сдвинув все остальные к началу последовательности.

2.36 Замените каждый элемент массива средним арифметическим всех предшест­вующих ему элементов.

2.37 Пусть даны вещественные числа а₁, а₂, ..., а_n. Получите числа b₁, b₂, ..., b_n, где b_i — среднее арифметическое всех членов последовательности а₁, а₂, ..., а_n, кроме а_i (i =1,..., n).

2.38 Используя следующий фрагмент программы, упорядочьте массив x по не­убыванию (то есть переставьте его элементы так, чтобы для всех i выполня­лось условие х_i  х_i+1) в соответствии с перечисленными ниже алгоритмами сортировки (упорядочения):

const

n = 20;

Var

x : array [1..n] of real;

а) сортировка выбором — отыскивается максимальный элемент и переносится в конец массива; затем этот метод применяется ко всем элементам, кроме последнего (он уже находится на своем месте), и т. д.;

б) сортировка обменом (пузырьковая сортировка) — последовательно срав­ниваются пары соседних элементов х_i ≤ х_i+1 (i = 1, 2, ..., n-1), и если х_i > х_i+1 то они переставляются; тем самым наибольший элемент ока­зывается на своем месте в конце массива; затем этот метод применяется ко всем элементам, кроме последнего, и т. д.;

в) сортировка вставками — пусть первые k элементов массива уже упорядо­чены по неубыванию; берется (k+1)-й элемент и размещается среди первых k элементов так, чтобы упорядоченными оказались уже k+1 первых элементов; этот метод применяется при k от 1 до п - 1.

2.39 Пусть элементы массива х упорядочены по возрастанию. С помощью представленного ниже фрагмента программы присвойте переменной k номер эле­мента массива х, равного числу y, или 0, если такого элемента нет. При этом использовать следующий метод двоичного (бинарного) поиска: сравнить y со средним элементом массива (или элементом около середины); если эти числа равны, поиск завершается, если же y меньше среднего элемента, то y надо искать в левой половине массива, а иначе — в правой. Далее к выбранной половине применяется этот же алгоритм.

2.40 Пусть даны две последовательности по n целых чисел в каждой. Найдите наименьшее среди тех чисел первой после­довательности, которые не входят во вторую последователь­ность, считая, что хотя бы одно такое число есть.

2.41 Пусть дана последовательность из n целых чисел. Определите количество инверсий в этой последовательности (то есть таких пар элементов, в кото­рых большее число находится слева от меньшего: х _i > х_j при i < j).

2.42 Пусть даны вещественные числа а₁, а₂, ..., а_n. Если в результате замены отрицательных членов последо­вательности а₁, а₂, ..., а_n их квадратами члены будут обра­зовывать неубывающую последовательность, то получите сумму членов ис­ходной последовательности; в противном случае получите их произведение.

2.43 Пусть даны целые числа а₁, а₂, ..., а_n. Пусть М — наиболь­шее, т — наименьшее из них. Получите в порядке возрастания все целые числа из интервала (т, М), которые не входят в последовательность а₁, а₂, ..., а_n.

2.44 Присвойте переменной f значение true, если в некотором массиве нет нуле­вых элементов и при этом положительные элементы чередуются с отрицательными, в противном случае присвойте значение false.

2.45 Пусть даны натуральное число п, целые числа а, х₁, х₂,..., х_п. Если в последовательности х₁, х₂, ..., х_п есть хотя бы один член, равный а, то получите сумму всех членов, следующих за первым таким членом, иначе найдите минималь­ный среди нечетных чисел последовательности х₁, х₂, ..., х_п.

2.46 Пусть даны целые числа а₁, а₂, ..., а_n, среди которых могут быть повторяю­щиеся. Составьте новый массив из чисел, которые входят в последователь­ность по одному разу.

2.47 Пусть даны целые числа а₁, а₂, ..., а_n,среди которых могут быть повторяю­щиеся. Составьте новый массив из чисел, взятых по одному из каждой груп­пы равных членов данной последовательности.

2.48 Пусть даны натуральные числа k, п, вещественные числа а₁, а₂, ..., а_k n. Получите последовательность max(а₁, а₂, ..., а_k), max(а_k+1, а_k+2, ..., а_2k), ..., max(а_k(n-1)+1, ..., а_k n).

2.49 В массиве из п элементов подсчитайте количество четверок а_i, а_i+1, а_i+2, а_i+3, идущих подряд членов, из которых:

а) все члены равны;

б) все члены различны.

2.50 Пусть дан фрагмент программы:

var

k : 0 .. 9999:

d : array [ 1..4 ] of '0' .. '9';

а) запишите в массив d цифры числа k;

б) получите целое k, составленное из цифр массива d.