Поиск элемента в матрице — различия между версиями
(Новая страница: «{{Задача |definition = Дана матрица, в которой отсортированы все столбцы и строки. Требуется на...») |
|||
| Строка 1: | Строка 1: | ||
{{Задача | {{Задача | ||
| − | |definition = Дана матрица | + | |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> находится в строке, расположенной ниже. | ||
| + | |||
| + | Изначально рассматриваем матрицу <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
| Задача: |
| Дана матрица . Все столбцы и строки матрицы отсортированы. Требуется найти заданный элемент . |
Содержание
Варианты решения
Наивное решение
Заметим, что:
- Если первый элемент столбца больше , то находится в колонке слева.
- Если последний элемент строки меньше , то находится в строке, расположенной ниже.
Изначально рассматриваем матрицу .
Описание алгоритма
- Начнем с правого столбца и будем двигаться влево, рассматривая первые элементы этих столбцов.
- Если первый элемент столбца меньше искомого, то по правилу (1) мы можем выкинуть этот столбец.
- После того, как мы выкинули некоторые столбцы, получили новую матрицу. Будем рассматривать последние элементы ее строк.
- Если элемент меньше искомого, то нам нужно "двигаться вниз".
- Если не можем применить ни одно из правил, то поиск закончен. Осталось проверить элемент на равенство искомому.
Заметим, что мы можем применять эти правила, постепенно сокращая матрицу, пока в левом верхнем углу подматрицы не останется элемент, равный искомому.
Рассмотрим решение на примере
Будем искать элемент, значение которого - 46.
- Рассмотрим первые 3 строки. По правилу (2), искомый элемент находится ниже. Значит остаются только строки с 4 по 6.
- Рассмотрим последние 2 столбца. По правилу (1) искомый элемент находится левее. Значит остаются столбцы с 1 по 4.
- В левом верхнем углу матрицы остался элемент равный 46. Успех.
