Инвертирование массива

Инвертирование массива – это запись его элементов в другом порядке, обычно обратном.

Пример 8.1 Программа читает массив символов и печатает их в обратном порядке.

program p81;

const n = 10;

var ch : array [1..n] of char; i : integer;

Begin

for i := 1 to n do read(ch[i]);

for i := n to 1 do writeln(ch[i])

End.

Поиск элемента в массиве

Поиск в массиве элемента с заданными свойствами организуется как последовательное испытание каждого элемента массива.

Пример 8.2 Среди чисел найдите максимальное.

program p82;

const n = 20;

var i : integer; a : array [1..n] of real; max : real;

begin for i := 1 to n do read(a[i]);

max := a[1];

for i := 2 to n do

if a[i] > max then max := a[i];

writeln(max)

End.

Суммирование элементов массива

Для суммирования элементов массива на каждом шаге к накапливаемой сумме добавляется одно слагаемое.

Пример 8.3 Вычислите скалярный квадрат вектора a c координатами (a₁, a₂, …, a_n), который вычисляется по формуле s = (a, a) = a₁×a₁ + a₂×a₂ +…+ a_n×a_n.

program p83;

const n = 10;

var s : real; i : integer; a : array [1..n] of real;

Begin

for i := 1 to n do read(a[i]);

s := 0; for i := 1 to n do

s := s + a[i]*a[i]; write(s:5)

End.

Пример 8.4 Вычислить сумму элементов квадратной матрицы.

program p84;

const n = 5;

var i, j : integer; a : array [1..n, 1..n] of real; s : real;

Begin

for i := 1 to n do

for j := 1 to n do read(a[i, j]);

s := 0; for i := 1 to n do

for j := 1 to n dos := s + a[i, j];

writeln(s:5)

End.

В целях экономии времени выполнения программы не рекомендуется в одном операторе цикла совмещать ввод-вывод массива с другими действиями.

Упакованные массивы

Для уменьшения потерь памяти значения данных смещаются так, чтобы между ними не оставалось свободных от информации битов. Этот процесс называют упаковкой массива. Для этого достаточно перед словом array поставить слово packed. На печать можно выводить только неупакованные массивы.

Для копирования упакованного массива в неупакованный и наоборот предназначены процедуры pack и unpack.

Пример 8.5 Программа упаковывания массива и копирования упакованного массива в неупакованный.

program p85;

const n =10;

var i, x : integer; xa : array[1..n] of integer; xp : packed array[1..n] of integer;

Begin

for i := 1 to n do begin read(x); xp[i] := x end;

unpack(xp, xa, 1);

for i := 1 to n do write(‘xa[‘:5, i:2, ‘]=’:3, xa[i]:5)

End.

Алгоритмы обработки массивов

Алгоритмы, предназначенные для обработки массивов, могут быть структурированы так:

1) алгоритмы поиска;

2) алгоритмы выборки;

3) алгоритмы сортировки;

4) алгоритмы преобразования в виде поворота или зеркального отражения относительно какой-либо оси.

Рассмотрим несколько примеров реализации приведенных алгоритмов.

Пример 8.6 (Алгоритм поиска). Дана матрица mxn, состоящая из натуральных чисел. Найти в ней наименьший элемент и определить его местоположение. Если таких элементов несколько, то вывести на экран положение каждого из них.

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

program p86;

const t = 100; s = 100;

var a : array [1..t, 1..s] of integer;

m, n, im, jm, i, j, min, k : integer;

Begin

write(‘Введите количество строк m =’); readln(m);

write(‘Введите количество столбцов n =’); readln(n);

for i := 1 to m do

Begin

write(‘Вводите через пробел ‘, n, ‘чисел’);

for j := 1 to n do read(a[i,j])

end;

min := a[1,1];

im := 1; jm := 1; k := 0;

for i := 1 to m do

for j := 1 to n do

if min > a[i, j] then

begin k := 1; im := i; jm := j; min := a[i,j] end

else if min = a[i,j] then k := k+1;

if k = 1 then begin

writeln(‘В матрице один элемент min =’, min);

writeln(‘в ’, im, ‘строке, в‘, jm, ‘столбце’) end

Else begin

writeln(‘В матрице’, k, ‘минимальных элемент min =’, min);

for i := im to m do

for j := 1 to n do

if min = a[i, j] then

writeln(‘в строке ‘, i, ‘в столбце’, j) end

End.

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

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

program p87;

const t = 100; s = 100;

var a : array [1..t, 1..s] of integer;

m, n, jn, i, j, min : integer;

Begin

write(‘Введите количество строк m =’); readln(m);

write(‘Введите количество столбцов n =’); readln(n);

for i := 1 to m do

Begin

write(‘Вводите через пробел ‘, n, ‘чисел’);

for j := 1 to n do read(a[i,j])

end;

for i := 1 to m do

begin min := a[1,1];

jn := 1;

for j := 1 to n do

if min > a[i, j] then

begin jn := j; min := a[i,j] end;

a[i, jn] := a[i, 1];

a[i, 1] := min

end;

for i := 1 to m do

Begin

for j := 1 to n do

writeln(a[i, j]:4); writeln

End

End.

Существует несколько методов сортировки (упорядочивания) массивов:

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

2) сортировка обменом (метод пузырька) – последовательно сравниваются пары соседних элементов x_k и x_k+1 (k = 1, 2, 3, …, n-1) и, если x_k > x_k+1, то они переставляются; тем самым наибольший элемент окажется на своем месте в конце массива; затем этот метод применяется ко всем элементам, кроме последнего, и т.д.;

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

4) сортировка по методу Шелла.

Пример 8.8 (Алгоритм сортировки выбором). Дан массив из 100 вещественных чисел. Упорядочить массив по неубыванию (т.е. переставить его элементы так, чтобы для всех k выполнялось x_k £ x_k+1).

program p88;

const n = 100;

var x : array[1..n] of real; i, k, m : integer; r : real;

Begin

for k := 1 to n do read(x[k]);

for k := n downto 2 do

Begin

m := 1; {поиск номера m максимального элемента}

for i := 2 to k do if x[i] > x[m] then m := i;

r := x[k]; x[k] := x[m]; x[m] := r

end;

for k := 1 to n do write(x[k])

End.

Пример 8.9 (Алгоритм сортировки по методу Шелла).

program p89;

const n = 10;

var i, m : integer; r : real; b : boolean; a : array[1..n] of real;

Begin

for i := 1 to n do read(a[i]);

m := n; b := false;

repeat m := m div 2;

repeat for i := 1 to n – m do

begin b := a[i] < a[i+m];

if b then begin r := a[i]; a[i] := a[i+m]; a[i+m] := r end

until not

until m = 0;

for i := 1 to n do write(a[i])

End.

Пример 8.10 (Алгоритм преобразования). Дана квадратная матрица nxn, состоящая из натуральных чисел. Поверните ее на 90⁰ по часовой стрелке и выведите результат на экран в матричном виде.

A = ® B =

Основная задача, которую нужно решить в этом случае, состоит в определении преобразования индексов элементов матрицы: b₁₁® a₃₁, b₁₂® a₂₁, b₂₁® a₃₂, b₂₂® a₂₂ и т.д. b[i, j] ® a[l, m].

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

~ , откуда b[i, j] = a[n + 1 - j, i].

Тогда программа поворота квадратной матрицы на 90⁰ по часовой стрелке примет вид:

program p810;

const n = 100;

var a, b : array[1..n, 1..n] of integer; k, m, i, j : integer;

Begin

write(‘Введите размер матрицы m =’); readln(m);

writeln(‘Исходная матрица’);

k := 1;

for i := 1 to m do

for j := 1 to m do

Begin

a[i, j] := 1;

k := k + 1;

if j < m then write(a[i,j]:4)

else writeln(a[i,j]:4)

end;

writeln(‘Матрица после ввода на поворота на 90⁰’);

for i := 1 to m do

for j := 1 to m do

Begin

b[i,j] := a[m+1-j, i];

if j < m then write(b[i, j]:4)

else writeln

end;

End.

Задание 8.1

1. Имеются описания:

type день = (вчера, сегодня, завтра);

вектор = array[1..30] of real;

var a : вектор;

b : packed array [-2..2] of (x, y, z);

c : array[‘0’..’9’] of вектор;

d : array [день] of 0..23;

Для каждого из массивов и укажите:

а) сколько в нем элементов;

б) какие значения могут принимать его элементы;

в) как указать его первый и последний элементы.

2. Запишите регулярный тип R, объединяющий в себе массивы, элементами которых являются натуральные числа, а индексами – любые литеры.

3. Напишите фрагмент программы для вычисления:

а) y = ;

б) y = x_i;

в) y = x₁ – x₂ + x₃ - … - x_n-1+ x_n;

г) y = x₁ x_n + x₂ x_n-1 + … x_n x₁;

д) y = x₁² – x₂² + x₃² - … - x_n-1²+ x_n²;

е) y = x_n (x_n + x_n-1) (x_n + x_n-1 + x_n-2)… (x_n + … + x₁).

4. Дана 100 целых чисел. Распечатайте их в обратном порядке по 6 чисел в строке.

5. Перепишите элементы массива x в массив y, где

x : array [1..40] of char; y: array [0..39] of char;

6. Вычислите величину

(x₁ y₁ + x₃ y₃ + … + x₂₉ y₂₉) / (x₂ y₂ + x₄ y₄ + … + x₃₀ y₃₀),

если числа для вода заданы в следующем порядке:

а) x₁, x₂, …, x₃₀, y₁, y₂, … , y_30;

б) x₁, y₁, x₂, y₂, … , x₃₀, y_30.

7. Напечатайте те элементы массива s, индексы которых являются степенями двойки (1, 2, 4, 8, 16, …), где const n = 1000; s : packed array of char;.

8. const n = 30;

type vector = array [1.. n] of integer;

var a, b, c : vector;

Если векторы а и b различны, то вектору с присвойте их сумму, иначе в вектор с перепишите элементы массива а.

9. Дан массив чисел. Найдите значение максимального элемента. Если таких элементов несколько, то определить, сколько их.

10. Дан массив чисел. Найдите, сколько в нем пар одинаковых соседних элементов.

11. Дан массив чисел. Найдите наибольший элемент и поставьте его первым.

12. Дан массив чисел. Расставьте их по убыванию.

13. Имеются данные об успеваемости не более чем 24 учебных групп (в процентах). Определите, на сколько нужно повысить успеваемость в самой отстающей группе, чтобы достичь среднего уровня успеваемости.

14. Известны данные о среднемесячной температуре за год. Определите, какая самая высокая температура летом и самая низкая зимой.

15. В коллекции нумизмата не более чем 90 монет всех достоинств. Определите, сколько монет достоинством в 20 и 50 тенге и каковы их порядковые номера.

Задание 8.2

1. Одинаковы ли типы array [1..15, 0..3] of char и array [1..15] of array [0..3] of char?

2. Введите квадратную вещественную матрицу 4-го порядка, элементы которой заданы для ввода построчно, и распечатайте ее по столбцам.

3. const n = 20;

var A, B, C : array [1..n, 1..n] of real;

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

Вычислите:

а) С = А + В; б) у = Ах; в) С = А×В;

г) В = В^Т (транспонировать).

4. type vector = array [1.. 20] of integer;

matrica = array [1.. 20] of vector;

var A : matrica; x : vector;

B ; array[1..20, 1.. 20] of integer;

Выпишите фрагмент программы для решения следующей задачи:

а) нечетные строки матрицы А замените на х;

б) четные столбцы матрицы А замените на х;

в) первые шесть строк массива В замените на х;

г) в матрице А поменяйте местами 1-ю и 2-ю строки, 3-ю и 4-ю,…,19-ю и 20-ю строки (воспользоваться х как вспомогательным массивом).

5. Дана вещественная матрица размером 20х30. Упорядочите ее строки по неубыванию ее первых элементов.

6. Программа. Элемент матрицы назовём седловой точкой, если он является наименьшим в своей строке и одновременно наибольшим в своём столбце или, наоборот, является наибольшим в своей строке и наименьшим в своём столбце. Для заданной целой матрицы размером 10х15 напечатайте индексы всех ее седловых точек.

7. Дана матрица mxn, состоящая из натуральных чисел. Выберите в строках самые правые наименьшие элементы и определите их местоположение.

8. Дана матрица mxn, состоящая из латинских букв. Отсортируйте каждую строку в алфавитном порядке.

9. Дана матрица nxn, состоящая из натуральных чисел. Расставьте строки таким образом, чтобы элементы в первом столбце были упорядочены по убыванию.

10.Дана квадратная матрица nxn, состоящая из натуральных чисел. Поверните ее на 90⁰ против часовой стрелке и выведите результат на экран в матричном виде.

11.Дана квадратная матрица nxn, состоящая из натуральных чисел. Поверните ее на 180⁰ и выведите результат на экран в матричном виде.

12.Дана квадратная матрица nxn, состоящая из натуральных чисел. Зеркально отразите ее элементы относительно горизонтальной оси симметрии. Выведите результат на экран в матричном виде.

13.Дана квадратная матрица nxn, состоящая из натуральных чисел. Зеркально отразите ее элементы относительно вертикальной оси симметрии. Выведите результат на экран в матричном виде.

14.Дана квадратная матрица nxn, состоящая из натуральных чисел. Зеркально отразите ее элементы относительно главной диагонали симметрии. Выведите результат на экран в матричном виде.

15.Дана квадратная матрица nxn, состоящая из натуральных чисел. Зеркально отразите ее элементы относительно побочной диагонали симметрии. Выведите результат на экран в матричном виде.

Процедуры и функции

В Паскале существуют два типа подпрограмм – процедуры и функции. Любая подпрограмма имеет ту же структуру, что и вся программа. При вызове подпрограммы выполнение основной программы приостанавливается и управление передается в подпрограмму. По окончании работы подпрограммы управление возвращается. Отличие процедур и функций:

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

Функция и выполняет действия, и возвращает результат.

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

Все переменные, которые использует программа, могут быть либо глобальными (объявленные в основной программе и доступные как программе, так и всем ее подпрограммам), либо локальными (объявленные внутри подпрограммы и доступные только ей самой).

Имена глобальных и локальных переменных не должны совпадать.

Пример 9.1 По заданным вещественным числам a_0, a₁, …, a₃₀, b_0, b₁, …, b₃₀, c_0, c₁, …, c₃₀, x, y, z вычислите величину

program p91;

const n = 30;

type vect = array [0..n] of real;

var a, b, c : vect; x, y, z, d : real;

procedure vvod(var v : vect);

var i : integer;

begin for i := 0 to n do read(v[i]) end;

function znach(var v : vect; t : real) : real;

var s : real; i : integer;

Begin

s := v[0]; for i := 1 to n do s := s*t+v[i];

znach := s

end;

Begin

vvod(a); vvod(b); vvod(c); read(x, y, z);

d := (sqr(znach(a, x)) – znach(b, y)) / znach(c, x+z);

writeln(d)

end.

Пример 9.2 Напишите функцию, которая находит сумму цифр целого числа.

program p92;

var n : longint; k : integer;

function num (n : longint) : integer;

var s : integer;

begin s := 0; repeat s := s + n mod 10;

n := n div 10

until n = 0;

num := s

end;

Begin

write(‘Введите целое число n =’); readln(n);

k := num (n);

writeln(‘Сумма его цифр равна ‘, k)

End.

Пример 9.3По вещественному х вычислите величину:

sh(x)× tg(x) – tg²(2 + sh(x-1).

program p93;

var x, y : real;

function sh (z : real) : real;

var e : real;

begin e := exp(z); sh := (e – 1 / e)/2 end;

function tg (z : real) : real;

begin tg := sin(z)/ cos(z) end;

Begin

read(x);

y := sh(x) * tg(x+1) – sqr(tg(2 + sh(x-1)));

writeln(y)

End.

Задание 9.1

1. Напишите процедуру ввода-вывода элементов матрицы.

2. Опишите функцию от вещественного x и натурального n, вычисляющую (через умножение) величину xⁿ, и используйте ее для вычисления b = 2.7^k + (a+1)^-k.

3. Даны отрезки a, b, c и d. Для каждой тройки этих отрезков, из которых можно построить треугольник, напечатайте площадь данного треугольника. (Определите процедуру pechplos(x, y, z), печатающую площадь треугольника со сторонами x, y и z, если такой треугольник существует).

4. Напишите функцию, которая находит цифровой корень целого числа.

5. Напишите функцию, которая из двух целых чисел выбирает наименьшее число.

6. Напишите функцию, которая из двух целых чисел выбирает наибольшее число.

7. Вычислите i–тое число Фиббоначи. Известно, что каждое последующее число Фиббоначи равняется сумме двух предыдущих, а нулевое число равно нулю, первое – единице.