If (b<a[1,1]) or(b>a[m,n]) then

Goto 10;

For i:=2 tom do

If b<a[i,1] then

Begin

For j:=1 to n do

If b=a[i-1,j] then

Begin

is:=i-1; js:=j; { найден элемент, равный b }

Goto10

End;

Goto 10; { в строке нет элемента, равного b }

End;

For j:=1 to n do{ просмотр эл-тов последней строки }

Ifb=a[m,j] then

Begin

is:=i-1; js:=j; Goto 10

End;

10:

Writeln('is = ',is,' js = ',js);

End.

В программе Task208a среди 20 строк раздела операторов содержатся четыре оператора Goto. Хотя эти операторы использованы для принудительного выхода из цикла, столь большая их плотность вызывает сомнения в хорошем стиле программы. Если вместо цикла Forиспользовать цикл While,то операторы Gotoможно исключить из программы:

Begin

В в о д m, n, A, b

is:=0; js:=0;

If (b>=a[1,1]) and (b<=a[m,n]) then

Begin

i:=2; Cond:=true;

While(i<=m) and Cond do

Begin

Ifb<a[i,1] then

Begin

j:=1;

While (j<=n) and Cond do

Begin

If b=a[i-1,j] then

Begin

is:=i-1; js:=j; { найден элемент, }

Cond:=false { равный b }

End;

Inc(j);

End;

Cond:=false; { в строке нет элемента,равного b }

End;

Inc(i);

End;

If is=0 then { просмотр эл-тов последней строки }

Begin

j:=1; Cond:=true;

While(j<=n) and Cond do

Begin

Ifb=a[m,j] then

Begin

is:=i-1; js:=j; Cond:=false

End;

Inc(j);

End;

End;

End;

Writeln('is = ',is,' js = ',js);

End.

Вариант 2. Более эффективным является двоичный поиск, для которого среднее количество сравнений равно ln( )/ln(2) (см.Task116). Однако алгоритм двоичного поиска, использованный в задаче 1.18, определен лишь по отношению к одномерному массиву.

По индексам и элемента матрицы можно определить его порядковый номер , где - количество элементов в строке матрицы (количество столбцов). Тогда появляется возможность обработки матрицы как одномерного массива.

В программе требуется решать также обратную задачу: по порядковому номеру определить индексы соответствующего элемента . Для этого можно использовать формулы

i = (k-1) div n + 1; .

ProgramTask208b;

Label10;

ConstMmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of integer;

Var m,n, { размер матрицы }

is,js, { позиция элемента, равного b }

i,j : byte;

k,k1,k2 : word;

b : integer;

A : Matrix; { исходная матрица }

Begin

В в о д m, n, A, b

k1:=1; k2:=m*n;

is:=0; js:=0;

While k1<=k2 do

Begin

k:=(k1+k2) div2;

i:=(k-1) divn + 1; j:=k-(i-1)*n;

If b=a[i,j] then

Begin

is:=i; js:=j; Goto 10

End

Else

If b<a[i,j] then

k2:=k-1

Else

k1:=k+1;

End;

10:

Writeln('is = ',is,' js = ',js);

End.

Пример 9.

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

Например, для строки

6 12 -4 17 1 0 9 11 14

получим

14 6 12 17 -4 1 0 9 11

Program Task209;

Label10;

ConstMmax = 30; Nmax = 50;

TypeMatrix = array[1..Mmax,1..Nmax] ofreal;

Var i,j,jmax,m,n : byte;

Amax,R : real;

A : Matrix;

Begin

В в о д m, n, A

Fori:=1 to m do{ Перебор строк матрицы }

Begin

Amax:=a[i,1]; jmax:=1; { Определение положения }

For j:=2 to n do{ макс.элемента в i-ой строке }

If a[i,j]>Amax then

Begin

Amax:=a[i,j]; jmax:=j

End;

If jmax=1 then{ Максимальный элемент - }

Begin {первый в строке}

R:=a[i,n];

Forj:=n downto 3 do

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

a[i,2]:=R;

End

Else

If jmax=n then{ Максимальный элемент - }

Begin { последний в строке }

R:=a[i,n-1];

For j:=n-1 downto2 do

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

a[i,1]:=R;

End

Else{ Максимальный элемент занимает }

Begin { промежуточное положение }

R:=a[i,n]; { в строке }

For j:=n downto jmax+2 do

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

a[i,jmax+1]:=a[i,jmax-1];

For j:=jmax-1 downto 2 do

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

a[i,1]:=R;

End;

End;

П е ч а т ь A

End.

Пример 10.

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

Program Task210;

Const Mmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of integer;

Vari,j,iz,k,m,n : byte;

A : Matrix;

Begin

В в о д m, n, A

For j:=1 to n do

Begin

k:=0;

For i:=1 tom do

If a[i,j]=0 then

Begin

Inc(k);

For iz:=i downto k+1 do

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

a[k,j]:=0;

End;

End;

П е ч а т ь А

End.

Пример 11.

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

ProgramTask211;

Const Mmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of real;

Vector = array[1..Mmax] of real;

Var i,j,k,m,n : byte;

S : real;

Cond : boolean;

A : Matrix;

D : Vector;

Begin

В в о д m, n, A

For j:=1 to n do

Begin

S:=0; { Определение среднего }

For i:=1 to m do{ арифметического значения S }

S:=S+a[i,j]; { элементов j-го столбца }

S:=S/m;

For i:=1 to m do{ Определение расстояний d }

d[i]:=abs(S-a[i,j]); { для элементов столбца }

Cond:=true; k:=m-1;

While Cond do{ Группировка элементов }

Begin { столбца по возрастанию }

Cond:=false; k:=m-1;{ параметра d }

For i:=1 to k do

If d[i]>d[i+1] then

Begin

S:=a[i,j]; a[i,j]:=a[i+1,j]; a[i+1,j]:=S;

S:=d[i]; d[i]:=d[i+1]; d[i+1]:=S;

Cond:=true;

End;

Dec(k);

End;

End;

П е ч а т ь A

End.

Пример 12.

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

ProgramTask212;

Const Mmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of real;

Var i,j,m,n : byte;

R : real;

A : Matrix;

Begin

В в о д m, n, A

R:=a[1,1]; { Сохранение левого верхнего эл-та }

For i:=1 tom-1 do{ Сдвиг левого столбца вверх }

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

For j:=1 to n-1 do { Сдвиг нижней строки влево }

a[m,j]:=a[m,j+1];

Fori:=m downto 2 do { Сдвиг правого столбца вниз }

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

Forj:=n downto3 do{ Сдвиг первой строки вправо }

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

a[1,2]:=R; { Запись сохраненного элемента }

П е ч а т ь А

End.

Пример 13.

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

Program Task213;

Const Mmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of integer;

Vari,j,imax,jmax,m,n : byte;

R,Amax : integer;

A : Matrix;

Begin

В в о д m, n, A

Amax:=abs(a[1,1]); { Определение положения }

imax:=1; jmax:=1; { максимального элемента }

For i:=1 tom do

For j:=1 to n do

If abs(a[i,j])>Amax then

Begin

Amax:=a[i,j]; imax:=i; jmax:=j;

End;

Ifimax>1 then{ Обмен элементов строк }

For j:=1 ton do { с номерами 1 и imax }

Begin

R:=a[1,j]; a[1,j]:=a[imax,j]; a[imax,j]:=R;

End;

Ifjmax>1 then{ Обмен элементов столбцов }

For i:=1 tom do{ с номерами 1 и jmax }

Begin

R:=a[i,1]; a[i,1]:=a[i,jmax]; a[i,jmax]:=R;

End;

П е ч а т ь imax, jmax, Amax, A

End.

Пример 14.

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

Числовая последовательность считается упорядоченной по возрастанию, если

(в отличие от строгой упорядоченности, при которой должны соблюдаться отношения ).

Функция SignGroup в программе Task214 для -ой строки матрицы вначале производит поиск первой пары неравных друг другу элементов. При этом булевской переменной присваивается значение true, если второй элемент этой пары больше первого элемента, и значение false в противном случае. После этого проверяется, нет ли нарушения установленного порядка между остальными парами элементов -ой строки. Если в строке все элементы одинаковы, то такая строка считается упорядоченной.

ProgramTask214;

ConstMmax = 30; Nmax = 50;

TypeMatrix = array[1..Mmax,1..Nmax] of integer;

Vari,j,imax,jmax,m,n : byte;

Amax : integer;

A : Matrix;

{ ------------------------------------ }

Function SignGroup(k:byte):boolean;

{ Определение упорядоченности элементов k-ой строки }

Label10;

Varj : byte;

b : boolean;

Begin

b:=true;

Forj:=1 to n-1 do

If a[k,j]<>a[k,j+1] then

Begin

b:=a[k,j]<a[k,j+1]; Goto 10

End;

10:

SignGroup:=true;

If b then

Forj:=2 ton-1 do

If a[k,j]>=a[k,j+1] then

Begin

SignGroup:=false; Exit

End;

If not b then

For j:=2 to n-1 do

If a[k,j]<=a[k,j+1] then

Begin

SignGroup:=false; Exit

End;

End { SignGroup };

{ ------------------------------------ }

Begin

В в о д m, n, A

imax:=0; jmax:=0; Amax:=0;

For i:=1 to m do

IfSignGroup(i) then

If imax=0 then{ встретилась первая }

Begin { упорядоченная строка }

Amax:=a[i,1]; imax:=i; jmax:=1;

For j:=2 to n do

If a[i,j]>Amax then

Begin

Amax:=a[i,j]; jmax:=j;

End;

End

Else

For j:=1 ton do{ рассматривается очередная }

If a[i,j]>Amax then{ упорядоченная строка }

Begin

Amax:=a[i,j]; imax:=i; jmax:=j;

End;

Writeln('imax = ',imax,' jmax = ',jmax,' Amax = ',Amax);

End.

Пример 15.

В прямоугольной матрице рассмотреть квадратные подматрицы размерностью 1, 2, 3, ... , причем для всех подматриц левым верхним элементом является элемент исходной матрицы с индексами (1,1). Определить номер подматрицы, среднее арифметическое значение элементов которой является максимальным.

Program Task215;

ConstMmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of integer;

Vari,j,k,kmax,m,n,p : byte;

S,Smax : real;

A : Matrix;

Begin

В в о д m, n, A

Ifm>n then{ p = min(m,n) }

p:=n

Else

p:=m;

Smax:=a[1,1]; kmax:=1;

For k:=2 top do

Begin

S:=0;

For i:=1 to k do

Forj:=1 tok do

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

S:=S/sqr(k);

If S>Smax then

Begin

Smax:=S; kmax:=k;

End;

End;

П е ч а т ь kmax, Smax

End.

Пример 16.

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

Program Task216;

Const Mmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of real;

Var i,j,m,n,

Count : byte; { счетчик локальных минимумов }

R : real;

Cond : boolean;

A : Matrix;

Begin

В в о д m, n, A

Count:=0;

For i:=2 tom-1 do

For j:=2 to n-1 do

Begin

R:=a[i,j];

Cond:=(R<a[i,j-1]) and (R<a[i,j+1]) and

(R<a[i-1,j]) and (R<a[i+1,j]);

If Cond then

Inc(Count);

End;

Writeln('Count = ',Count);

End.

Пример 17.

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

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

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

Program Task217;

Label10;

Const Mmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of integer;

Var i1,j1, { индексы эл-та с порядковым номером k1 }

i2,j2, { индексы эл-та с порядковым номером k2 }

m,n : byte; { кол-во строк и столбцов матрицы }

k1,k2, { порядковые номера элементов матрицы }

p : word; { количество элементов матрицы }

Cond : boolean;

A : Matrix; { исходная матрица }

Begin

В в о д m, n, A

p:=m*n; Cond:=false;

For k1:=1 top-1 do

Begin

i1:=(k1-1) div n + 1; j1:=k1-(i1-1)*n;

For k2:=k1+1 to p do

Begin

i2:=(k2-1) div n + 1; j2:=k2-(i2-1)*n;

If a[i1,j1]=a[i2,j2] then

Begin

Cond:=true; Goto10;

End;

End;

End;

10:

IfCond then

Writeln('i1=',i1,' j1=',j1,' i2=',i2,' j2=',j2)

Else

Writeln('В матрице нет одинаковых элементов');

End.

Пример 18.

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

Program Task218;

Label 10;

Const Nmax = 40;

TypeMatrix = array[1..Nmax,1..Nmax] of integer;

Var j,k,n : byte;

Cond : boolean;

A : Matrix;

Begin

В в о д m, n, A

k:=0;

Repeat

Cond:=true; Inc(k);

For j:=1 ton do

If a[k,j]<>a[j,k] then { Выход из цикла просмотра }

Begin{ строки при обнаружении }

Cond:=false; Goto10 { несовпадающих элементов }

End;

10:

Until Cond or(k=n);

IfCond then

Writeln('Cовпадение строки и столбца с номером ',k)

Else

Writeln('Нет совпадающих строки и столбца');

End.

Цикл Repeatзаканчивает свою работу, если найдены совпадающие строка и столбец (Cond = true) или просмотрены все строки и соответствующие им столбцы (k = n).

Пример 19.

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

ProgramTask219;

Label 10;

Const eps = 0.001; Mmax = 30; Nmax = 50;

TypeMatrix = array[1..Mmax,1..Nmax] ofreal;

Var i,j,k,i1,i2,m,n : byte;

R,R1 : real;

Cond : boolean;

A : Matrix;

Begin

В в о д m, n, A

For i:=1 to n-1 do

Fork:=i+1 to n do

Begin

R:=a[i,1]/a[k,1]; Cond:=true;

Forj:=2 to n do

Begin

R1:=a[i,j]/a[k,j];

Ifabs(R-R1)>eps then

Cond:=false;

End;

IfCond then Goto 10;

End;

10:

IfCond then

Writeln('Линейно зависимы строки ',i,' и ',k)

Else

Writeln('В матрице нет линейно зависимых строк');

End.

Сравнение вещественных переменных R и производится по параметру .

Пример 20.

Подсчитать количество строк целочисленной прямоугольной матрицы , элементы которых являются перестановкой чисел 1, 2, ..., .

Program Task220;

Const Mmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of integer;

Var i,j,k,m,n : byte;

Cond : boolean;

A : Matrix;

{ --------------------------------- }

Function Permut(k:byte):boolean;

{ true, если k-ая строка является перестановкой 1 .. n }

Var j,nk : byte;

R : integer;

Bol : boolean;

Begin

Bol:=true; nk:=n-1; { Группировка строки }

While Bol do{ по возрастанию }

Begin

Bol:=false;

For j:=1 tonk do

Ifa[k,j]>a[k,j+1] then

Begin

R:=a[k,j]; a[k,j]:=a[k,j+1]; a[k,j+1]:=R;

Bol:=true;

End;

Dec(nk);

End;

Permut:=true; { Проверка равенства между }

For j:=1 ton do{ значением элемента и его }

If a[k,j]<>j then { порядковым номером }

Begin

Permut:=false; Exit;

End;

End{ Permut };

{ --------------------------------- }

Begin

В в о д m, n, A

k:=0;

Fori:=1 to m do

IfPermut(i) then

Inc(k);

Writeln('k = ',k);

End.

Пример 21.

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

ProgramTask221;

Label 10;

ConstMmax = 30; Nmax = 50;

Type Matrix = array[1..Mmax,1..Nmax] of integer;

Var i,k,m,n : byte;

Cond : boolean;

A : Matrix;

{ --------------------------------- }

Function SignRow(k:byte):boolean;

{ Проверка симметричности и строгой упорядоченности }

{ элементов k-ой строки }

Var i,j : byte;

CondSim,CondHigh : boolean;

Begin

CondSim:=true; SignRow:=true;{Проверка симметричности}

i:=1; j:=n; { элементов строки }

While i<j do