lab6

Каждый студент выполняет по 5 заданий.

Номера заданий вычисляются по формуле:

( N + (K-1)*35 ) + 902, где

N – порядковый номер студента по журналу,

К – порядковый номер выполняемой задачи (от 1 до 6),

Выполнение ошибочного варианта считается злонамеренным деянием и карается выполнением своего варианта ☺

Студенты, претендующие на повышенную оценку (>75 баллов),

изучают дополнительную теорию и выполняют 2 дополнительных задания.

Номера заданий выбираются произвольно из задач: 1078-1081

Теоретические сведения

Двумерные массивы

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

Формат записи Двумерного массива в языке Паскаль:

<имя>: array [<н_индекс_1>..<в_индекс_1>,

<н_индекс_2>..<в_индекс_2>]

of <тип>;

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

for i:=1 to n do

for j:=1 to n do

a[i,j]:=random(100);

Для ввода многомерных массивов, так же как и одномерных, можно использовать генератор случайных чисел, константы и файлы. При описании массивов удобно использовать именованные константы в качестве значений верхних индексов массивов.

Аналогом массивов языка Паскаль в математике являются матрицы. Матрицы, у которых число строк равно числу столбцов, называются квадратными. A(n, n) — квадратная матрица.

Перечислим основные свойства квадратных матриц.

1. Квадратные матрицы имеют главную и побочную диагонали.

Например, для матрицы А на главной диагонали лежат элементы 1, 5 и 9, а на побочной — 3, 5 и 7.

Если:

• i = j — элементы расположены на главное диагонали;

• i > j — элементы расположены ниже главное диагонали;

• i < j — элементы расположены выше главной диагонали;

• i ≥ j — элементы расположены на главной диагонали и ниже;

• i ≤ j — элементы расположены на главной диагонали и выше;

• i + j = n + 1 — элементы расположены на побочной диагонали;

• i + j < n + 1 — элементы расположены над побочной диагональю;

• i + j > n + 1 — элементы расположены под побочной диагональю.

2. Квадратная матрица, у которой все элементы, исключая элементы главной диагонали, равны нулю, называется диагональной матрицей:

3. Диагональная матрица, у которой все элементы, стоящие на главной диагонали равны 1, называется единичной матрицей:

4. Если в матрице А(m, n) поменять местами строки и столбцы, то получится матрица A^T(m, n), которая называется транспонированной матрицей:

Над матрицами можно выполнять следующие действия.

• Суммой однотипных матриц A(a_ij) и B(b_ij) называют матрицу C(a_ij + b_ij) = C(c_ij), каждый элемент которой равен сумме соответствующих элементов матриц А и В, С = А + В, c_ij = a_ij + b_ij.

• Разностью матриц A(a_ij) и B(b_ij) называют матрицу C(a_ij – b_ij), каждый элемент которой равен разности соответствующих элементов матриц А и В: C = A – B, c_ij = a_ij – b_ij.

• Произведением матрицы A на некоторое число α называют матрицу А · α, у которой каждый элемент равен А_ij · α.

• Произведением двух матриц A(a_ij) и B(b_ij) называется такая матрица (число столбцов матрицы А должно равняться числу строк матрицы В), у которой элементы определяются по формуле , где , . То есть нужно перемножить соответствующие элементы i-й строки матрицы А на элементы j-го столбца матрицы В и полученные произведения сложить: .

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

Вывод матрицы в виде таблицы:

for i:=1 to n do

begin

for j:=1 to m do

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

writeln

end;

Еще один способ:

for i:=1 to n do

for j:=1 to m do

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

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

Суммирование матриц:

for i:=1 to n do

begin

for j:=1 to m do

c[i,j]:=a[i,j]+b[i,j]

end;

Умножение матриц:

for i:=1 to n do

for j:=1 to n do

begin

s:=0;

for k:=1 to n do

s:=s+a[i,k]*b[k,j];

c[i,j]:=s

end;

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

for i:=1 to n do

for j:=1 to n do

b[i,j]:=a[j,i];

Очень часто встречаются задачи на повороты матриц. Рассмотрим метод их решения.

Пусть дана квадратная матрица А_nn, состоящая из целых чисел. Повернем ее на 90° по часовой стрелке.

Для наглядности используем матрицу А_3,3:

Матрица после поворота:

Установим соответствие между элементами матриц A и A'.

Элементу а₁₁ матрицы А соответствует элемент a'₃₁ матрицы A'; элементу а₁₂ матрицы А соответствует элемент a'₂₁ матрицы A'; элементу а₁₃ матрицы А соответствует элемент a'₁₁ матрицы A' и т. д.

Значит отношение матриц A(i, j) и A'(i', j') следующее: i = j', j + i' = n + 1 ® A'(i', j') = A(n + 1 – j, i).

Теперь можно написать программу для заданной матрицы А₃₃:

const n=3;

var a,b: array [1..n,1..n] of integer;

i,j: integer;

BEGIN

randomize;

for i:=1 to n do

begin

for j:=1 to n do

begin

a[i,j]:=random(20);

write(a[i,j]:4)

end;

writeln

end;

writeln;

for i:=1 to n do

begin

for j:=1 to n do

begin

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

write(b[i,j]:4)

end;

writeln

end;

END.

Приведем другие соотношения матриц при поворотах.

При повороте на 90° против часовой стрелки: j' = i', i + j' = n + 1 ® A'(i', j') = A(j', n + 1 – i).

При повороте на 180° по часовой стрелке: j + j' = n + 1, i + i' = n + 1 ® A'(i', j') = A(n + 1 – i, n + 1 – j).

Отобразим элементы матрицы относительно горизонтальной оси симметрии (принцип решения тот же): j = j', i + i' = n + 1 ® A'(i', j') = A(n + 1 – i, j).

Теперь то же самое, но относительно вертикальной оси симметрии: j + j' = n + 1, i = i' ® A'(i', j') = A(i, n + 1 – j).

Зеркально отобразим элементы матрицы относительно побочной диагонали: i + j' = n + 1, j + i' = n + 1 ® A'(i', j') = A(n + 1 – j, n + 1 – i).

Примеры

Пример 6.1. Составить программу, которая осуществляет перестановку одномерного массива без использования дополнительного массива.

Листинг 6.1.

const n=20;

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

i,c: integer;

BEGIN

randomize;

for i:=1 to n do

begin

a[i]:=random(30)-4;

write(a[i]:4)

end;

for i:=1 to n div 2 do

begin

c:=a[i];

a[i]:=a[n-i+1];

a[n-i+1]:=c

end;

writeln;

for i:=1 to n do

write(a[i]:4);

writeln

END.

Пример 6.2. Найти сумму всех элементов массива A, больших заданного числа.

Листинг 6.2.

var a: array [1..100] of integer;

i,ch,n,s: integer;

BEGIN

randomize;

write('Введите размер массива -> ');

readln(n);

for i:=1 to n do

begin

a[i]:=random(20)-5;

write(a[i]:4)

end;

writeln;

write('Введите число -> ');

readln(ch);

s:=0;

for i:=1 to n do

if a[i]>ch then s:=s+a[i];

writeln('Сумма элементов, больших числа ',ch,' равна ',s)

END.

Пример 6.3. Заполнить массив, применив для его заполнения следующее значение: .

Листинг 6.3.

const n=10;

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

i: integer;

x: real;

BEGIN

write('Введите значение х -> ');

readln(x);

for i:=1 to n do

begin

a[i]:=x*sqr(i)/(i+x);

write(a[i]:8:4)

end;

END.

Пример 6.4. В одномерном массиве целых чисел заменить все элементы, меньшие среднего арифметического, значением среднего арифметического, округленного до целого. Массив заполняется случайным образом.

Листинг 6.4.

const n=10;

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

i,s: integer;

sred: real;

BEGIN

randomize;

s:=0;

for i:=1 to n do

begin

a[i]:=random(20)-5;

write(a[i]:4);

s:=s+a[i];

end;

writeln;

sred:=s/n;

for i:=1 to n do

begin

if a[i]<sred then a[i]:=round(sred);

write(a[i]:4)

end;

writeln

END.

Пример 5. В одномерном массиве целых чисел удалить k-й элемент массива.

Листинг 6.5.

const n=10;

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

i,k: integer;

BEGIN

randomize;

for i:=1 to n do

begin

a[i]:=random(20)-5;

write(a[i]:4)

end;

writeln;

write('Введите номер элемента для удаления

(k < ',n,')->');

readln(k);

for i:=k to n-1 do

a[i]:=a[i+1];

for i:=1 to n-1 do

write(a[i]:4);

writeln

END.

Пример 6.6. В одномерном массиве целых чисел удалить элемент, равный заданному числу, если он есть. Если таких элементов несколько, то удалить последний из найденных.

Листинг 6.6.

const n=10;

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

i,k,kk: integer;

BEGIN

randomize;

for i:=1 to n do

begin

a[i]:=random(20)-5;

write(a[i]:4)

end;

writeln;

write('Введите число ->');

readln(kk);

for i:=1 to n do

if a[i]=kk then k:=i;

for i:=k to n-1 do

a[i]:=a[i+1];

for i:=1 to n-1 do

write(a[i]:4);

writeln

END.

Пример 6.7. Вставить на k-е место массива целых чисел элемент, равный наименьшему элементу массива.

Листинг 6.7.

const n=10;

var a: array [1..n+1] of integer;

i,k,min: integer;

BEGIN

randomize;

for i:=1 to n do

begin

a[i]:=random(20)-5;

write(a[i]:4)

end;

writeln;

min:=a[1];

for i:=2 to n do

if a[i]<a[min] then min:=a[i];

write('Введите значение k (k < ',n,') ->');

readln(k);

for i:=n+1 downto k do

a[i]:=a[i-1];

a[k]:=min;

for i:=1 to n+1 do

write(a[i]:4);

writeln

END.

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

Решим задачу следующим образом. Соединим два массива в один, а затем упорядочим полученный массив, используя «пузырьковый» метод сортировки.

Листинг 6.8.

const n=10;

var a,b: array [1..n] of integer;

c: array [1..2*n] of integer;

i,j,k: integer;

BEGIN

randomize;

for i:=1 to n do

begin

a[i]:=random(20)-5;

b[i]:=random(12)

end;

writeln('Массив А');

for i:=1 to n do

write(a[i]:4);

writeln;

writeln('Массив B');

for i:=1 to n do

write(b[i]:4);

writeln;

for i:=1 to n do

c[i]:=a[i];

k:=1;

for i:=n+1 to 2*n do

begin

c[i]:=b[k];

inc(k)

end;

for i:=1 to 2*n-1 do

for j:=1 to 2*n-1 do

if c[j]>c[j+1] then

begin

k:=c[j];

c[j]:=c[j+1];

c[j+1]:=k

end;

writeln('Массив С');

for i:=1 to 2*n do

write(c[i]:4);

writeln

END.

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

Листинг 6.9.

const n=10;

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

i,k: integer;

BEGIN

randomize;

for i:=1 to n do

begin

a[i]:=random(20)-5;

write(a[i]:4)

end;

writeln;

k:=0;

for i:=1 to n-1 do

if a[i] = a[i+1] then k:=k+1;

writeln('Одинаковых пар соседних элементов

в массиве ',k)

END.

Пример 6.10. Даны три одномерных числовых массива A, B, C. Сформировать массив K такой же длины, элементы которого вычисляются по формуле: [15].

Листинг 6.10.

const n=10;

var a,b,c: array [1..n] of integer;

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

i: integer;

BEGIN

randomize;

writeln;

writeln('МАССИВ А');

for i:=1 to n do

begin

a[i]:=random(20)-5;

b[i]:=random(30)-2;

c[i]:=random(40);

write(a[i]:4)

end;

writeln;

writeln('МАССИВ В');

for i:=1 to n do

write(b[i]:4);

writeln;

writeln('МАССИВ C');

for i:=1 to n do

write(c[i]:4);

writeln;

writeln('МАССИВ K');

for i:=1 to n do

begin

k[i]:=(a[i]-b[i])/(1+c[i]);

write(k[i]:8:4)

end

END.

Пример 6.11. Даны натуральные числа A₁, A₂, …, A_N (N = 10). Не создавая дополнительные массивы, определить, какой из элементов повторяется в последовательности A₁, A₂, …, A_N наибольшее число раз, и найти его порядковый номер, ближайший к началу последовательности [32].

Листинг 6.11.

const n=10;

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

i,j,max,k,q: integer;

BEGIN

randomize;

for i:=1 to n do

begin

a[i]:=random(20);

write(a[i]:4)

end;

writeln;

max:=0;

for i:=1 to n-1 do

begin

k:=1;

for j:=i+1 to n do

if a[i]=a[j] then inc(k);

if k>max then

begin

max:=k;

q:=i

end

end;

write(a[q]:6,q:6,max:6);

writeln

END.

Пример 6.12. В заполненном наполовину массиве, не создавая дополнительный массив, продублировать все элементы с сохранением порядка их следования. Например, из массива А (1, 2, 3, …) необходимо получить массив (1, 1, 2, 2, 3, 3) [32].

Листинг 6.12.

const n=5;

var a: array [1..2*n] of integer;

i: integer;

BEGIN

randomize;

for i:=1 to n do

begin

a[i]:=random(20);

write(a[i]:4)

end;

writeln;

i:=2*n;

while (i<=2*n) and (i>=2) do

begin

a[i]:=a[i div 2];

a[i-1]:=a[i];

dec(i,2);

end;

for i:=1 to 2*n do

write(a[i]:4);

writeln

END.

Пример 6.13. Заданы два одномерных массива различных размеров M и N и число K (K < M). Не создавая дополнительный массив, включить второй массив в первый между K-м и (К+1)-м его элементами [32].

Листинг 6.13.

const m=5; n=5;

var a: array [1..m+n] of integer;

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

i,k: integer;

BEGIN

randomize;

write('Введите значение k -> ');

readln(k);

for i:=1 to m do

begin

a[i]:=random(20)-2;

write(a[i]:4)

end;

writeln;

for i:=1 to n do

begin

b[i]:=random(15)+4;

write(b[i]:4)

end;

writeln;

for i:=m+n downto (m+n)-(m-k)+1 do

a[i]:=a[i-n];

for i:=1 to n do

a[k+i]:=b[i];

for i:=1 to m+n do

write(a[i]:4);

writeln

END.

Пример 6.14. Сообщество роботов живет по следующим законам: один раз в год они объединяются в группы по 3 или 5 роботов; за год группа из 3 роботов собирает 5, а группа из 5 — 9 новых собратьев; каждый робот живет 3 года после сборки. Известно начальное количество роботов (K > 7), все они только что собраны. Определить, сколько роботов будет через N лет. [13]

Листинг 6.14.

var k,n,i,r: byte;

new: LongInt;

d,q: array [-2..100] of LongInt;

BEGIN

write('Введите начальное кол-во роботов и кол-во лет -> ');

readln(k,n);

write('Всего роботов: ');

if k<3 then

if n in [0,1,2] then write(k) else write ('0')

else

begin

d[-2]:=0; d[-1]:=0; d[0]:=k; q[0]:=k;

for i:=1 to n do

begin

r:=q[i-1] mod 5;

new:=q[i-1] div 5*9+r;

if r in [3,4] then inc(new,5-r);

d[i]:=new;

q[i]:=q[i-1]+new-d[i-3]

end;

write(q[n])

end;

END.

Пример 6.15. Даны натуральные числа А₁, …, А₁₀. Предположим, что имеется 10 видов монет достоинством А₁, …, А₁₀. Обозначим через N число способов, которыми можно выплатить сумму K этими монетами, то есть N — это число решений уравнения A₁X₁ + … + A₁₀X₁₀ = K, где X_i может принимать целые неотрицательные значения. Требуется найти N [32].

Листинг 6.15.

label 1;

var a,b,c: array [1..10] of integer;

i,j,n,s,k: integer;

BEGIN

write('Введите сумму -> ');

readln(k);

for i:=1 to 10 do

begin

write('a[',i,'] = ');

readln(a[i])

end;

for i:=1 to 10 do

b[i]:=k div a[i];

n:=0;

for i:=1 to 10 do

c[i]:=0;

1: s:=0;

for i:=1 to 10 do

s:=s+a[i]*c[i];

if s=k then inc(n);

for i:=10 downto 1 do

begin

if c[i]=b[i] then

for j:=i to 10 do

c[j]:=0 else

begin

c[i]:=c[i]+1;

goto 1

end;

end;

writeln('N = ',n);

END.

Пример 6.16. Составить программу для вычисления полинома y = 2x⁸ – x⁶ – 4x⁵ – 5x² + 6x + 1, используя формулу Горнера [5].

Формула Горнера для полинома n-й степени y = a₁xⁿ + a₂x^n–1 + … + a_nx + a_n+1 выглядит следующим образом:

y = (…((a₁x + a₂)x + a₃)x + … + a_n)x + a_n+1

Листинг 6.16.

var a: array [1..10] of real;

md,i: integer;

x,y: real;

BEGIN

write('Введите старшую степень полинома

(она не должна быть больше 9) -> ');

readln(md);

writeln('Введите коэффициенты полинома

(начиная с коэффициента при

свободном члене) ');

for i:=1 to md do

read(a[i]);

y:=a[1];

for i:=2 to md do

begin

x:=i;

y:=y*x+a[i]

end;

writeln(y:8:6);

END.

Пример 6.17. Заданный массив А сдвинуть циклически на m элементов вправо [7].

При циклическом сдвиге вправо выталкиваемые элементы с конца массива заполняют освобождающиеся места в начале массива. Например, при сдвиге вправо на 3 разряда массива А (1, 2, 3, 4, 5, 6, 7) получаем массив А (5, 6, 7, 1, 2, 3, 4).

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

Листинг 6.17.1.

const n=5;

var a,b: array [1..n] of integer;

i,c,k: integer;

BEGIN

write('На сколько элементов сдвигать вправо? -> ');

readln(c);

for i:=1 to n do

begin

a[i]:=random(20)-3;

write(a[i]:4)

end;

writeln;

for i:=1 to n do

begin

k:=(i+c-1) mod n+1;

b[k]:=a[i]

end;

for i:=1 to n do

write(b[i]:4)

END.

Листинг 6.17.2.

const n=5;

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

i,c,k,j: integer;

BEGIN

write('На сколько сдвигать вправо -> ');

readln(c);

for i:=1 to n do

begin

a[i]:=random(20)-3;

write(a[i]:4)

end;

writeln;

for i:=1 to c do

begin

k:=a[n];

for j:=n downto 2 do

a[j]:=a[j-1];

a[1]:=k

end;

for i:=1 to n do

write(a[i]:4);

END.

Пример 6.18. Билет с шестизначным цифровым номером считается «счастливым», если сумма трех старших цифр совпадает с сумой трех младших цифр. В предположении, что в билетной кассе находится миллион билетов с номерами от 000000 до 999999, надо определить количество потенциально осчастливленных пассажиров [18].

Можно организовать шесть вложенных циклов, в каждом из которых перебирается очередная цифра номера. В самом внутреннем цикле можно проверять суммы старших и младших цифр номера и вести подсчет счастливых билетов, но такая проверка нерациональна. Гораздо меньше операций можно проделать, если подсчитать, сколько раз сумма трех цифр равна 0, 1, 2, …, 27.

Листинг 6.18.

const m=9;

var b: array [0..3*m] of integer;

a1,a2,a3,k: integer;

n: longint;

BEGIN

for a1:=0 to m do

for a2:=0 to m do

for a3:=0 to m do

inc(b[a1+a2+a3]);

for k:=0 to 3*m do

n:=n+b[k]*b[k];

writeln('Количество счастливых билетов = ',n);

END.

В результате получим ответ: 55 252 билета.

Пример 6.19. Дана матрица А_5,5, содержащая случайные элементы. Найти сумму всех элементов матрицы [11].

Листинг 6.19.

const n=5;

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

i,j,s: integer;

BEGIN

randomize;

s:=0;

for i:=1 to n do

begin

for j:=1 to n do

begin

a[i,j]:=random(20);

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

s:=s+a[i,j]

end;

writeln

end;

writeln('Сумма элементов матрицы = ',s);

END.

Пример 6.20. Дана матрица А_5,5, состоящая из случайных чисел. Составить одномерный массив S, в котором будут содержаться значения суммы элементов каждого столбца матрицы [11].

Листинг 6.20.

const n=5;

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

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

i,j,ss: integer;

BEGIN

randomize;

for i:=1 to n do

begin

for j:=1 to n do

begin

a[i,j]:=random(20);

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

end;

writeln

end;

for i:=1 to n do

begin

ss:=0;

for j:=1 to n do

ss:=ss+a[j,i];

s[i]:=ss

end;

writeln;

for i:=1 to n do

write(s[i]:4);

writeln;

END.

Пример 6.21. Вывести на экран таблицу Пифагора.

Листинг 6.21.

const n=9;

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

i,j: integer;

BEGIN

for i:=1 to n do

begin

for j:=1 to n do

begin

a[i,j]:=i*j;

write(a[i,j]:4)

end;

writeln

end;

END.

Пример 6.22. Найти сумму положительных элементов указанного столбца матрицы А_5,5 целых чисел.

Листинг 6.22.

const n=5;

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

i,j,num,s: integer;

BEGIN

randomize;

for i:=1 to n do

begin

for j:=1 to n do

begin

a[i,j]:=random(20);

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

end;

writeln

end;

write('Введите номер столбца для

суммирования -> ');