Задача 45. Поиск упорядоченных по возрастанию строк матрицы

Условие задачи. В заданной матрице определить количество строк, которые упорядочены по возрастанию.

В данной задаче исходным данным является матрица вещественных чисел А. Её размер в условии не определён. Поэтому число строк и число столбцов матрицы (целочисленные N и M) также являются исходными данными и должны вводиться пользователем. Результатом должно стать найденное количество упорядоченных по возрастанию строк матрицы – целое число К.

Для подсчёта количества упорядоченных строк необходимо использовать переменную–счётчик К, которая будет увеличиваться на 1 при выполнении условия упорядоченности каждой строки. Для анализа всех строк действия по их проверке должны производиться в цикле, изменяющем номер строки i от первого до последнего.

Чтобы узнать, упорядочены ли по возрастанию элементы одной строки, требуется сравнить все пары стоящих рядом элементов этой строки: последующий элемент в паре должен быть больше предыдущего. Такие сравнения в строке нужно сделать по количеству пар, т.е. в цикле M -1 раз (на 1 раз меньше, чем количество элементов в строке). Но вывод об упорядоченности строки можно сделать только после проведения всех сравнений в ней или досрочно в случае, если какой-то элемент оказался не больше предыдущего. В такой ситуации, как правило, используют логическую переменную (f), которой до начала сравнений присваивают одно из двух её возможных значений, например, истина. Далее в цикле М -1 раз сравнивают пары соседних элементов, и если требуемое соотношение элементов нарушено, то значение переменной f меняют на ложь (при этом сравнения в данной строке можно прервать, так как уже ясно, что она не упорядочена). После окончания цикла проверяют f: если она осталась с исходным значением истина, то это значит, что в каждой паре следующий элемент больше предыдущего, и, следовательно, строка упорядочена по возрастанию, а значит счётчик К надо увеличить на 1. Если же f поменяла значение на ложь, то это значит, что требуемое условие в данной строке было нарушено, и увеличивать К не надо.

 Структурированная запись алгоритма 45

1. Ввести размеры матрицы N и M и элементы самой матрицы А.

2. Обнулить счётчик К =0.

3. В цикле для каждой строки i = 1,N повторять:

3.1. Присвоить начальное значение истина переменной f.

3.2. В цикле для j=1,M-1 повторять

3.2.1. Сравнивать соседние элементы, и если A[i,j] ³ A [ i, j +1], то переменная f меняет своё значение на ложь, и цикл прерывается.

3.3. По окончании цикла проверить: если f имеет значение истина, то К=К+1.               

4. Вывести К.

Схема алгоритма

Текст программы на языке Си

#include <stdio.h>

#include <math.h>

#define N 25

int main (void)

{

int n,m,i,j,k,f;

double a[N][N];

printf ("\nВведите n и m\n");

scanf ("%d%d", &n,&m);

for (i=0; i<n; i++)

{

printf ("Введите элементы %d строки\n",i);

for (j=0; j<m; j++)

scanf ("%lf", &a[i][j]);

}

k=0;

for (i=0; i<n; i++)

{

f=1;

for (j=0; j<m-1; j++)

    if (a[i][j]>=a[i][j+1])

    {

      f=0;break;

    }

      if (f)

       k++;

}

printf ("Кол-во упорядоченных строк - %d",k);

return 0;

}

Текст программы на языке Паскаль

Program Pr_45;

Var

A: array of array of real;

N, M, i, j, K: integer;

f: boolean;

begin

writeln(‘ Введите размеры матрицы');

readln(N,M);

SetLengh(A,N,M);

N:=N-1; M:=M-1;

for i:=0 to N do

begin

writeln(‘Введите элементы ‘,i,’ строки’);

for j:=0 to M do

    read(A[i,j]);

end;

K:=0;

for i:=0 to N do

begin

 f:=true;

for j:=0 to M-1 do

    if A[i,j]>=A[i,j+1] then

    begin f:=false; break end;

if f then K:=K+1

end;

writeln(‘Кол-во упорядоченных строк - ’,K);

A:=nil;

end.

Текст программы на языке Фортран

Program Pr_45

Implicit none

real, allocatable:: A(:,:)

integer N, M, i, j, K

logical f

print *,‘ Введите размеры матрицы’

read *, N,M

allocate(A(N,M))

do i=1,N

print *, ‘Введите элементы ‘,i,’ строки’)

read(A(i,j),j=1,M)

enddo

K=0

do i=1, N

f=.true.

do j=1, M-1

    if (A(i,j)>=A(i,j+1)) then

       f=.false.

       exit

    endif

enddo

if (f) K=K+1

enddo

print *, ‘Кол-во упорядоченных строк - ’,K

deallocate(A)

end

Программа на языке Python

# В качестве матрицы используется стандартный тип

# list (список), элементами которого являются списки

print("Введите N -- число строк матрицы A: ")

N=int(input())  

print("Введите M -- число столбцов матрицы A: ")

M=int(input())  

A = [] # Создаем пустой список строк

# в Python списки индексируются с 0:

for i in range(0, N):

A.append([])

# Добавляем пустой список элементов i-й строки

for j in range(0, M):

    print("Введите A[{0},{1}]: ".format(i+1,j+1))

    A[i].append(float(input()))

K = 0

for i in range(0, N):

f = True

for j in range(0, M-1):

    if A[i][j] >= A[i][j+1]:

f = False

break

if f:

    K += 1 # K = K + 1

print("Количество строк, строго", end=' ')

print("упорядоченных по",end=' ')

print("возрастанию - {0}".format(K))

Программа в системе Матлаб

N=input('Введите N=');

M=input('Введите M=');

for i=1:N

disp(sprintf('Введите эл. %d строки матрицы',i))

for j=1:M

A(i,j)=input('A(i,j)=');

end

end

K=0;

for i=1:N

f=true;

for j=1:M-1

    if A(i,j)>=A(i,j+1)

    f=false;

    break;

end

end

if f

K=K+1;

end

end

disp(sprintf('Кол-во упорядоченных строк - %d',K))