Задача 76259

Тема:    [ Многомерные массивы ]

Сложность: 3- Классы:

Условие

(Из книги Д. Гриса) Имеется массив x: array [1..n] of array [1..m] of integer, упорядоченный по строкам и по столбцам:
x[i][j]≤x[i][j+1], x[i][j]≤x[i+1][j],
и число a. Требуется выяснить, встречается ли a среди x[i][j].

Решение

Представляя себе массив x как матрицу (прямоугольник, заполненный числами), мы выберем прямоугольник, в котором только и может содержаться a, и будем его сужать. Прямоугольник этот будет содержать x[i][j] при 1≤i≤l и  k≤j≤m

(допускаются пустые прямоугольники при l = 0 и  k = m + 1).

        l:=n; k:=1;
        {l>=0, k<=m+1, если a есть, то в описанном прямоугольнике}
        while (l > 0) and (k < m+1) and (x[l][k] <> a) do begin
        | if x[l][k] < a then begin
        | | k := k + 1; {левый столбец не содержит a, удаляем его}
        | end else begin {x[l][k] > a}
        | | l := l - 1; {нижняя строка не содержит a, удаляем её}
        | end;
        end;
        {x[l][k] = a или прямоугольник пуст }
        answer:= (l > 0) and (k < m+1) ;

Замечание. Здесь та же ошибка: x[l][k] может оказаться неопределённым. (Её исправление предоставляется читателю.)

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	2
Название	Массивы
задача
Номер	1.2.28