Поиск элемента в матрице — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Задача |definition = Дана матрица, в которой отсортированы все столбцы и строки. Требуется на...»)
 
 
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
|definition = Дана матрица, в которой отсортированы все столбцы и строки. Требуется найти заданный элемент <tex>x</tex>.}}
+
|definition = Дана матрица <math>\alpha_k^m</math>. Все столбцы и строки матрицы отсортированы. Требуется найти заданный элемент <tex>x</tex>.}}
  
 
== Варианты решения ==
 
== Варианты решения ==
 
=== Наивное решение ===
 
=== Наивное решение ===
==== Описание алгоритма ====
 
 
Нам известно:
 
  
 +
'''Заметим, что:'''
 
* Если первый элемент столбца больше <tex>x</tex>, то <tex>x</tex> находится в колонке слева.
 
* Если первый элемент столбца больше <tex>x</tex>, то <tex>x</tex> находится в колонке слева.
* Если последний элемент столбца меньше <tex>x</tex>, то <tex>x</tex> находится в колонке справа.
 
* Если первый элемент строки больше <tex>x</tex>, то <tex>x</tex> находится в строке, расположенной выше.
 
 
* Если последний элемент строки меньше <tex>x</tex>, то <tex>x</tex> находится в строке, расположенной ниже.
 
* Если последний элемент строки меньше <tex>x</tex>, то <tex>x</tex> находится в строке, расположенной ниже.
 +
 +
Изначально рассматриваем матрицу <math>\alpha_k^m</math>.
 +
 +
==== Описание алгоритма ====
 +
 +
* Начнем с правого столбца и будем двигаться влево, рассматривая первые элементы этих столбцов.
 +
* Если первый элемент столбца меньше искомого, то по правилу (1) мы можем выкинуть этот столбец.
 +
* После того, как мы выкинули некоторые столбцы, получили новую матрицу. Будем рассматривать последние элементы ее строк.
 +
* Если элемент меньше искомого, то нам нужно "двигаться вниз".
 +
* Если не можем применить ни одно из правил, то поиск закончен. Осталось проверить элемент на равенство искомому.
 +
Заметим, что мы можем применять эти правила, постепенно сокращая матрицу, пока в левом верхнем углу подматрицы не останется элемент, равный искомому.
 +
 +
====Рассмотрим решение на примере ====
 +
[[Файл:Slice 1.png|280px|thumb|left|Состояние матрицы после первого шага]]
 +
[[Файл:Slice2.png|280px|thumb|right|Состояние матрицы после второго шага]]
 +
 +
Будем искать элемент, значение которого - 46.
 +
 +
* Рассмотрим первые 3 строки. По правилу (2), искомый элемент находится ниже. Значит остаются только строки с 4 по 6.
 +
* Рассмотрим последние 2 столбца. По правилу (1) искомый элемент находится левее. Значит остаются столбцы с 1 по 4.
 +
* В левом верхнем углу матрицы остался элемент равный 46. Успех.

Текущая версия на 22:03, 1 июня 2015

Задача:
Дана матрица [math]\alpha_k^m[/math]. Все столбцы и строки матрицы отсортированы. Требуется найти заданный элемент [math]x[/math].


Варианты решения[править]

Наивное решение[править]

Заметим, что:

  • Если первый элемент столбца больше [math]x[/math], то [math]x[/math] находится в колонке слева.
  • Если последний элемент строки меньше [math]x[/math], то [math]x[/math] находится в строке, расположенной ниже.

Изначально рассматриваем матрицу [math]\alpha_k^m[/math].

Описание алгоритма[править]

  • Начнем с правого столбца и будем двигаться влево, рассматривая первые элементы этих столбцов.
  • Если первый элемент столбца меньше искомого, то по правилу (1) мы можем выкинуть этот столбец.
  • После того, как мы выкинули некоторые столбцы, получили новую матрицу. Будем рассматривать последние элементы ее строк.
  • Если элемент меньше искомого, то нам нужно "двигаться вниз".
  • Если не можем применить ни одно из правил, то поиск закончен. Осталось проверить элемент на равенство искомому.

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

Рассмотрим решение на примере[править]

Состояние матрицы после первого шага
Состояние матрицы после второго шага

Будем искать элемент, значение которого - 46.

  • Рассмотрим первые 3 строки. По правилу (2), искомый элемент находится ниже. Значит остаются только строки с 4 по 6.
  • Рассмотрим последние 2 столбца. По правилу (1) искомый элемент находится левее. Значит остаются столбцы с 1 по 4.
  • В левом верхнем углу матрицы остался элемент равный 46. Успех.