Как в двумерном массиве найти необходимое значение?

Alex_Movchan, 160 просмотров

-1

Как в двумерном массиве найти необходимое значение. Значение можно сравнивать не более, чем с m+n элементами массива (m,n - размерность массива)?

Примечание:
Помогите, пожалуйста, с алгоритмом.

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

Примечание:
Элементы массива - любые числа.

Примечание:
Я думаю, массив сначала отсортируем по горизонтали и вертикали.

Примечание:
По условию сначала массив необохидимо отсортировать. Потом поиск с условием числа сравнений не более (m+n). Поэтому можно допустить, что поиск производим в уже отсортированом массиве чисел.

Примечание:
По условию сначала массив необохидимо отсортировать. Потом поиск с условием числа сравнений не более (m+n). Поэтому можно допустить, что поиск производим в уже отсортированом массиве чисел.

Ответы:

Dark_OberoN

Массив имеет какую-нибудь закономерность, или элементы абсолютно случайные числа?

AntiPetya

значения числовые?

Dark_OberoN

А сортировка не является сравнением элементов? Просто если является, то думаю сравнений m+n маловато будет

ixpict

какие такие стандартные функции и какого языка?

Light_keeper

сначала перепишем массив в линейный, тоесть был a[n][m] а стал b[n*m]... потом отсортируем, мы можем это сделать, так как со значинием для этого ниразу сравнивать не нужно. потом бинарным поиском найдем искомое значение. о поиске почитай тут: http://ru.wikipedia.org/wiki/Двоичный_поиск

Blakman

Пусть массив отсортирован так, что отсортирован каждый столбец по возрастанию сверху вниз и отсортирована каждая строка по возрастанию слева направо.
Тогда: начнем с левого нижнего элемента и будем делать следующее:
1) если элемент равен нашему, все отлично, мы его нашли.
2) если элемент меньше нашего, пойдем направо.
3) если элемент больше нашего, пойдем влево.
всего переходов не более (m+n-1), а значит сравнений не более (m+n).
Если требуется, могу еще объяснить почему это верно, но думаю, что и так понятно :)

Без имени

Массив отсортирован так, что отсортирован каждый столбец по возрастанию сверху вниз и отсортирована каждая строка по возрастанию слева направо.
Тогда: начнем с левого верхнего элемента и будем делать следующее:
1) если искомый элемент равен нашему, все отлично, мы его нашли.
2) если искомый элемент больше нашего, и меньше чем первый элемент в строке ниже, то искомый элемент находится в текущей строке (отправляемся искать его по строке), иначе - опускаемся на строку ниже и выполняем опять п.1 потом п.2

Web

Думаю, что вам, молодой человек, нужно сначала разобраться с базовыми алгоритмами, а там уже и решение само созреет. Неужели вам самому не хочеться написать программу, без чьей либо помощи))
Вот ссылки на описание и исходники реализации базовых алгоритмов
Линейный поиск: http://iguania.ru/algoritmi-programmirovaniya/lineyniy-poisk.html
Двоичный поиск: http://iguania.ru/algoritmi-programmirovaniya/dvoichniy-poisk.html
Интерполирующий поиск: http://iguania.ru/algoritmi-programmirovaniya/dvoichniy-poisk.html

15 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.