2017-11-01
1054
Лабораторная работа №9.
Тема: Обработка одномерных и двумерных массивов.
Цель: Развить навыки обработки одномерных и двумерных массивов. Уметь использовать различные методы описания массивов и сортировки массивов.
Оборудование и материалы: Методическое пособие, ПЭВМ, ручка, карандаш, линейка, ластик, шаблон А4.
Ход работы
Методические рекомендации.
Необходимая информация содержится в лекции № 12.
Решение задач представить в следующем порядке: постановка задачи, построение математической модели, блок-схемы, программный код, тестирование.
Задание для лабораторной работы выбрать согласно варианту по приведённой таблице. Вариант определяется порядковым номером в журнале группы.
! Внимательно изучите алгоритм пузырьковой сортировки.
!! Рассмотрите подробно задачу №2. В ней рассмотрены алгоритмы генерации различного числа наборов данных.
Образцы решения типовых задач.
Рассмотрим алгоритм пузырьковой сортировки.
|
|
|
Сравним первый элемент массива со вторым. Если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвертого, I-го и (I + 1)-го, (n - 1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее (n-e) место. Теперь повторим данный алгоритм сначала, но последний (n-й) элемент, рассматривать не будем, так как он уже занял свое место. После проведения данной операции самый большой элемент оставшегося массива встанет на (n - 1)-е место. Так повторяем до тех пор, пока не упорядочим весь массив.
Обратите внимание на то, что для перестановки элементов (блок 4) используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.
Процесс упорядочивания элементов в массиве по возрастанию представим в таблице:
| Номер элемента | |||||
| Исходный массив | |||||
| Первый просмотр | |||||
| Второй просмотр | |||||
| Третий просмотр | |||||
| Четвертый просмотр | |||||
|
Листинг программы упорядочивания элементов в массиве по возрастанию их значений.
Var
i, n, j: integer;
b:word;
y: array [1.. 100] of word;
Begin
writeln ('введите размер массива');
readln (n);
for i:=1 to n do
Begin
write ('y[', I, ']=');
readln (y[i]);
end;
writeln ('массив y');
for i:=1 to n dowrite (y [ i ], ' ');
writeln;
for j:=1 to n-1 do
for i:=1 to n-j do
if y[ i ] > y [i + 1] then { Если текущий элемент больше следующего, то }
begin {поменять их местами. }
b:=y[ i ]; { Сохранит значение текущего элемента. }
y[ i ]:=y[i + 1]; { Заменить текущий элемент следующим. }
у[i + 1]:=b; { Заменить следующий элемент текущим. }
|
|
|
end;
writeln ('упорядоченный массив');
for i:=1 to n do
write (y[ i ], ' ');
writeln;
End.
Пример 2. Разработать программу генерации следующих комбинаций: 1111, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211,..., 3333.
Вариант 1. Для генерации комбинаций используем вложенные циклы. Количество разрядов - 4. Следовательно, для генерации всех комбинаций понадобится 4 цикла, вложенных один в другой (рис. а). Если ввести параметр m - максимальное значение в каждом разряде, то эта же программа будет генерировать комбинации от 1111 до mmmm.
Если количество разрядов генерируемой комбинации изменить, то придется переписывать программу, увеличивая или уменьшая количество вложенных циклов.
Вариант 2. С точки зрения увеличения универсальности программы для генерации всех комбинаций лучше использовать программно реализуемый счетчик в общем случае на n разрядов, который в каждом разряде считает от 1 до n. Каждое состояние такого счетчика соответствует комбинации. Для генерации следующего варианта в младший разряд счетчика добавляют 1 и осуществляют межразрядные переносы в соответствии с характеристиками каждого разряда.
Ниже представлена программа, реализующая данный алгоритм для n < 10.
 | |||||||
 | |||||||
 | |||||||
 | |||||||
|
 | |||||||||
 | |||||||||
| |||||||||
 | |||||||||
 | |||||||||
Два варианта алгоритма генерации комбинаций:
а - с использованием вложенных циклов; б - программно реализуемый счетчик.
Program ex2;
Const
a:array[1..10] of byte=(l, 1,1,1,1,1,1,1,1,1);
var i,m,n:integer;
Begin
readLn (n,m);
while a[ 1 ]<m +1 do {условие «сброса» счетчика}
begin
for i:=l to n do write (a[i]); {вывод комбинации}
write (' ');
a[n]:=a[n]+l; {добавление 1 в последний разряд}
for i:=n downto 2 do {анализ и осуществление переносов}
if a[i]>m then
Begin
a[i]:=1;
a[i-1]:=a[i-1]+1;
end;
end;
End.
Ассоциируя комбинации счетчика с вариантами данных и проверяя полученные комбинации по критериям конкретной задачи, можно осуществить полный перебор вариантов.
Как уже упоминалось выше, для реализации ограниченного перебора используется вторая стратегия, при которой генерацию и анализ комбинаций исходных данных выполняют поэтапно. С этой целью удобно использовать рекурсию, при которой процесс генерации комбинации продолжается, пока полученная часть комбинации перспективна, или не исчерпаны все варианты.
Для генерации всех комбинаций исходных данных можно использовать вложенные циклы или программно реализуемый счетчик (по типу, например, электросчетчика). Второй способ позволяет получить более общее решение.
Ограниченный перебор, реализованный с использованием рекурсии. Для генерации комбинаций будем использовать древовидную рекурсию, на каждом уровне которой ставится один ферзь m различными способами. При этом появляется возможность проверки перспективности уже имеющейся комбинации. Поясним сказанное на примере доски 4x4.
На первом шаге первого ферзя можно поставить на одно из четырех полей первого вертикального ряда, что соответствует комбинациям
1..., 2...,3...,4....
На втором шаге второго ферзя можно поставить на одно из четырех полей второго вертикального ряда. При этом мы получим 4 комбинации для каждого варианта установки первого ферзя:
11.., 12.., 13., 14.. 21., 22.., 23., 24.. 31., 32., 33., 34.. 41., 42., 43., 44..
На этом этапе уже можно исключить все варианты, для которых первые два ферзя бьют друг друга: 11., 12., 21., 22., 23., 32., 33., 34., 43., 44.. Генерацию остальных комбинаций необходимо продолжить, установив третьего ферзя одним из четырех способов и исключив неперспективные решения. На последнем этапе необходимо установить четвертого ферзя и опять исключить варианты, в которых ферзи бьют друг друга. Оставшиеся варианты являются решениями задачи.
|
|
|
На рисункке показан фрагмент дерева генерации вариантов для m = 4 с отсечением неперспективных ветвей. Первое найденное решение - комбинация 2413.
 |
1421 1422 1423 1424 2411 2412 2413 2414
Program ex21;
Type p=array[l..100] of integer;
Var
Pole: p;
k,m: integer;
{функция проверки перспективности комбинации}
function new_r(n:integer;pole:p):boolean;
var j: integer;
begin
new _ r:=false;
for j:=l to n-1 do
if (pole[j]=pole[n]) or (abs(pole[j]-pole[n])=n-j) then exit;
new _r:-true;
End;
{рекурсивная функция генерации комбинации }
procedure ferz (n,m:integer; var pole.p);
var i.integer;
begin
if n=m+l then {если установлено m ферзей, то вывести решение}
begin
for i:=l to m do write (polefi]:2);
writeln;
end
else {иначе - пытаемся установить следующего ферзя}
for i:=l to m do {m способами}
Begin
pole[n]:=i; {установка n-го ферзя}
if new_r(n,pole) {проверка перспективности комбинации}
thenferz (n+l,m,pole); {рекурсивный вызов установки
следующего ферзя}
end;
end;
{основная программа}
Begin
writeLn ('Введите размер доски:');
readLn (m);
к:=0;
ferz(l,m,pole);
End.
| Размер доски | Количество вариантов, которое проверяется при полном переборе | Количество вариантов, рассмотренных при ограниченном переборе | Количество полученных решений |
| 4x4 | 44 = 256 | ||
| 5x5 | 55 = 3125 | ||
| 6x6 | б6 = 46656 | ||
| 7x7 | 77 = 823543 | ||
| 8x8 | 88= 16777216 |
Пример 3. Задан массив из n элементов. Сформировать массивы номеров положительных и отрицательных элементов.
program mas_six;
Type
massiv= array [1..20] of real;
massiv= array [1..20] of integer;
Var
a,s: massiv1;
y: massiv;
i,k,l,n: integer;
Begin
write (‘n=’);
readln (n);
for i:=1 to n do
Begin
write (‘y[‘,i,’]=’);
readln (y[i]);
end;
|
|
|
|
Пример 4. Задан массив y из n целых чисел. Сформировать массив z таким образом, чтобы вначале шли отрицательные элементы массива y, затем положительные и наконец нулевые.
program ex4;
Var
Y, z: array [1…50] of integer;
I, k, n: integer;
Begin
writeln (‘введите n<=50’)
readln (n);
for i: =1 to n do
Begin
write (‘y [‘, I,’] =’);
readln (y [i]);
end;
k:=0;
for i:=1 to n do
if y [i] < 0 then
begin
k:=k+1;
z [k]: = y [i];
end;
for i:=1 to n do
if y [i] > 0 then
Begin
k:=k+1;
z [k]: = y [i];
end;
for i:=1 to n do
if y [i] = 0 then
Begin
k:=k+1;
z [k]: = y [i];
end;
Пример 5. Переписать элементы массива х в обратном порядке. Блок-схема Представлена на рис.4.7. Алгоритм состоит в следующем: меняем местами 1-й и n-й элемент, затем 2-й и (n-1)-й и т.д. середины массива (элемент с номером I следует обменять с элементом (n+1-i)).
program mas_5;
type
massiv= array [1..100] of real;
Var
x:massiv;
i, n: integer;
b: real;
Begin
writeln (‘введите размер массива’);
readln (n);
for i:=1 to n do
Begin
write (‘x[‘,i,’]=’);
readln (x [ i ]);
end;
{Элементы массива меняются местами: 1- й – с n-м,2-й- с (n-1) и т.д.}
for i:=1 to n div 2 do
Begin
b:=x[n+1-i];
x[n+1-i ]:=x[i];
x[i]:=b;
end;
writeln (‘ преобразованный массив’);
for i:=1 to n do
write (x [i]:1:2,’’);
end.
Пример 6. Найти сумму элементов матрицы, лежащих выше главной диагонали.
Алгоритм решения главной задачи построен следующим образом: обнуляется ячейка для накапливания суммы (переменная s).Затем с помощью двух циклом(первый по строкам, второй по столбцам) просматривается каждый элемент матрицы, но суммирование происходит только в том случае, если этот элемент находится выше главной диагонали, то есть выполняется свойство i<j.
program ex6;
Var
a: array [1..15,1..10] of real;
i,j,n,m: integer;
s: real;
Begin
writeln (‘ введите размеры матрицы’);
writeln (‘n-количество строк, m-количество столбцов’);
readln (n,m);
for i:=1 to n do
for j:=1 to m do
Begin
write (‘a[‘,i, ‘, ‘, j, ‘ ]=’);
readln (a[i,j]);
end;
S:=0;
for i:=1 to n do
for j:=1 to n do
if j>i then {Если элемент лежит выше главной диагонали, то }
s:=s+a [i,j]; {наращиваем сумму. }
writeln (‘матрица А’);
for i:=1 to m do
{Здесь важен формат, особенно общая ширина поля! }
write (a[i, j]:8:3, ‘ ‘);
Writeln
end;
writeln (‘сумма элементов матрицы’, s:8:3);
End.
Пример 7. преобразовать матрицу А (m,n) так, чтобы строки были упорядочены по убыванию, с четными – по возрастанию.
program ex7;
Var
a: array [1...15,1..15] of real;
j, i. k. m, n: byte;
b: real;
Begin
writeln (‘введите m и n’);
readln (m,n);
for i:=1 to m do
for j:=1 to n do
begin
write (‘a[‘,I,’,’,j,’] =’);
readln (a[i,j]);
end;
writeln (‘матрица а’);
for i:=1 to m do
Begin
for j:=1 to n do
write (a[I,j]:7:3,’ ‘);
writeln;
end;
for i:=1 to m do
if (I mod 2)=0 then {если номер строки четный, то упорядочить ее элементы по
возрастанию.}
begin
for k:1 to n-1 do
for j:1 to n-k do
if a[i,j] >a[i,j+1] then
begin
b:=a[i,j];
a [i,j]:=a [i,j+1];
a[I,j+1]:=b;
end;
end;
else {если номер строки нечетный, то упорядочить ее элементы по убыванию.}
for k:=1 to n-1 do
for j:=1 to n-k do
if a[I;j]< a[i,j+1] then
Begin
b:=a[I,j];
a[i,j]:=a [i,j+1];
a[I,j+1]:=b;
end;
writeln (‘преобразованная марица а);
for i:=1 to m do
Begin
for j:=1 to m do
write (a [I,j]:7:3,’ ‘);
writeln;
end;
End.
Пример 8. Написать программу умножения двух матриц A(n, m) и B(m, l).Например, необходимо перемножить две матрицы:
Воспользуемся правилом «строка на столбец», получим матрицу
В общем виде формула для нахождения элемента 
матрицы выглядит следующим образом:
= 
,
где 
, 
и 
.Обратите внимание, что проводить операцию умножения можно только в том случае, если количество строк левой матрицы совпадает с количеством столбцов правой. Кроме того, 
.
Var
Begin
writeln 
readln 
for 
to 
d o
begin
write (‘a[‘, i,’,’,j,’]=’);
readln (a[i, j]);
end;
for i:=1 to m do
for j:=1 to 1 do
Begin
write (‘b[‘, i, ’,’,j,’]=’);
readln (b[I,j]);
end;
for i:=1 to n do
for j:=1 to l do
begin
{В переменной S будет храниться результат скалярного произведения i-й строки на j- й столбец.}
S:=0;
for k:=1 to m do s:=s+a[I,k]*b[k,j];
c[I,j]:=s;
end;
writeln (‘Матрица а’);
for i:=1 to n do
Begin
for j:=1 to m do writeln (a[I, j]:7:3,’ ‘);
writeln;
end;
writeln (‘Матрица b’);
for i:=1 to m do
Begin
for j:=1 to l do write (b[i, j]:7:3,’ ’);
writeln;
end;
writeln (‘Матрица с=a*b’);
for i:=1 to n do
begin
for j:=1 to l do write (c[I,j]:7:3,’ ‘);
writeln;
end;
End.
Пример.9. Поменять местами n-й и 1-й столбцы матрицы A(k,m).
program ex9;
Type
matrica = array 
of real;
Var
a: matrica;
i, j, k, m, n, l:byte;
b: real;
Begin
write (‘k=’);
readln (k);
write (‘m=’);
readln (m);
for i:=1 to k do
for j:=1 to m do
Begin
write (‘a 
=’);
readln (a 
)
end;
Repeat
write (‘n=’);
readln (n);
write (‘l=’);
readln (l);
until (n<=m) and (l<=m) and (n<=l); {Ввод считается верным, если n и l меньше m и не верны друг другу.}
for I:=1 to k do {Элементы столбца с номером 1 заменить элементами столбца с номером n.}
Begin
b:=a[i,n];
a[i,n]:= a[i,l];
a[i,l]:=b
end;
for I:=1 to k do
Begin
for j:=1 to m do write (‘a :7:3,’ ‘);
writeln;
end;
End.
Пример 10. Преобразовать матрицу A (m,n) таким образом, чтобы каждый столбец был упорядочен по убыванию. Алгоритм решения этой задачи сводится к тому, что уже известный нам по предыдущей главе алгоритм упорядочивания элементов в массиве выполняется для каждого столбца матрицы.
program ex10;
Type
matrica = array [1..15,1..15] of real;
Var
a: matrica;
I,j,k,m,n: byte;
b: real;
Begin
write (‘m=’);
readln (m);
write (‘n=’);
readln (n);
for i:=1 to m do
for j: =1 to n do
begin
write (‘a[‘,i,’,’,j,’] =’);
readln (a[I,j]);
end;
writeln (‘матрица a’);
for i:=1 to m do
begin
for j:=1 to n dowrite (a[I, j]:7:3, ‘ ‘);
writeln;
end;
for j: =1 to n do {j- номер столбца.}
for k: =1 to m-1 do {k- номер просмотра.}
for i: =1 to m-k do {I – номер строки.}
if a [I,j] <a [i+1,j] then
Begin
b: = [a, j];
a [I,j]:=a[i+1,j];
a [i+1,j]:=b;
end;
writeln (‘ преобразованная матрица a’);
for i:= to n do
Begin
for j:= to n do write (a[I,j]:7:3, ‘ ‘);
writeln;
end;
end.
Пример 11. Вычислить количество положительных элементов квадратной матрицы, расположенных по ее периметру и на диагоналях. Напомним, что в данной матрице число строк равно числу столбцов.
Прежде чем преступить к решению задачи, обратимся к рис.1, на котором изображена схема квадратных матриц различной размерности. Из условия задачи понятно, что рассматривать все элементы заданной матрицы не нужно. Достаточно просмотреть первую и последнюю строки, первый и последний столбцы, а также диагонали. Все эти элементы отмечены на схеме, причем черным цветом выделены те, обращение к которым может произойти дважды. Например, элемент с номером (1,1) принадлежит как к первой строке, так и к первому столбцу, а элемент с номером (N,N) находится в последней строке и последнем столбце одновременно. Кроме того, если N- число нечетное (на рис.5.7 эта матрица расположена слева), то существует элемент с номером (N div 2+1,N div 2+1), который находится на пересечении главной и побочной диагоналей. При нечетном значении N диагонали не пересекаются.
Матрица из N строк и N столбцов
|
Для обращения к элементам главной диагонали вспомним, что номера их строк всегда равны номерам столбцов. Так как параметр i изменяется циклически от 1 до N, то 
- элемент главной диагонали. Воспользовавшись свойством, характерным для элементов побочной диагонали, получим: i+j-1=n 
j=n-i+1, следовательно, для i=1,2,….,n элемент 
- элемент побочной диагонали. Элементы, находящиеся по периметру матрицы, записываются следующим образом: 
- первая строка, 
- последняя строка, и соответственно 
- первый столбец, 
-последний столбец.
Рассмотрим блок –схему задачи. В блоке 1 организуется цикл для обращения к диагональным элементам матрицы. Причем в блоках 2-3 подчитывается количество положительных элементов на главной диагонали, а в блоках 5-6- на побочной. Цикл в блоке 6 задает изменение параметра I от 2 до N-1. Это необходимо для того, чтобы не обращаться к элементам, которые уже были рассмотрены: 
, 
, 
и 
. Блоки 7-8 подчитывают положительные элементы в первой строке, 9 и 10- в последней; 11 и 12- в первом столбце, а 13 и 14- в последнем. Блок 15 проверяет, не был ли элемент, находящийся на пересечении диагоналей, подчитан дважды. Напомним, что это могло произойти только в том случае, если N является нечетным числом и этот элемент был положительным. Эти условия и проверяются в блоке 16, который уменьшает вычисленное количество положительных элементов на единицу.
var a: array [1..10,1..10] of integer;
I, j, n, k: integer;
Begin
write (‘n=’); readln (n);
for i:= 1 to n do
for j:=1 to n do
readln (a[ i, j ]);
writeln (‘ Была введена матрица: ‘);
for i:=1 to n do
begin
for j:=1 to n do write (a[ i, j], ’ ‘);
writeln;
end;
k:=0;
for i:=1 to n do
Begin
if (a[ i, i ]>0) then k:=k+1; { Элемент лежит на главной диагонали}
if a[ i, n-i+1 ]>0 then k:=k+1; { Элемент лежит на побочной диагонали}
end;
for i:=2 to n-1 do
begin
If (a[ 1,i ]>0) then k:=k+1; {Элемент находится в первой строке}
If (a[ n,i ]>0) then k:=k+1; {Элемент находится в последней строке}
If (a[i,1]>0) then k:=k+1; {Элемент находится в первом столбце}
If (a[i,n]>0) then k:=k+1; {Элемент находится в последнем столбце}
end;
{Если элемент, находящийся на пересечении диагоналей, подчитан дважды, то уменьшить k на единицу}
if (n mod 2 <> 0) and (a[(n div 2)+1, (n div 2)+1]>0) then k:=k-1;
write (k); end.
