Матрица в Pascal'e

[Serge_Bliznykov]

#1

можно и так и так. Никакой приниципиальной разницы я не вижу (одно лишнее присвоение в моём случае, когда найден дубликат против одного лишнего присвоения в вашем случае, если дубликат не найден). Тут обсуждать нечего. Выбор любого удобного варианта.

2

isFoundDublicate := true

А мы ведь может сделать вывод об этом используя лишь result..

Вы не поверите. Мой первый вариант был без флажка. Именно по -1 и проверялось, были ли найдено искомое значение. НО! Массив вводится. Нам кто-то гарантировал, что не будет внесён массив с отрицательными числами, где повторяться будет максимальное число со значением -1 ?! Значит, при таком раскладе программа будет работать не корректно! Поэтому, лучше не учиться плохому сразу, изначально! (а то потом ракеты летят не туда, куда надо, спутники падают и т.д. )

А самым оптимальным какое решение будет являться?

не знаю... Правда...
уж, даже в моём случае, уж как минимум, нужно СНАЧАЛА проверять значение, что оно больше максимума (A[i,j]>result), и только потом искать, имеет ли это значение дубликаты ( isHasDublicate() )!

Но и то, что мой вариант осуществляет поиск для каждого числа - это, имхо, не есть оптимально.
Вариантов решения можно множество придумать.
Например, ещё один:
брать очередное значение массива i,j, переводить индексы в один (превратить двухмерный массив в одномерный плоский [1..N*M], искать если ли дубликаты ПРАВЕЕ текущего, и если есть, их уже рассматривать как максимум.

массивы маленькие, как их не перебирай, всё равно быстро получается

[orandzheviyman]

Сообщение от Serge_Bliznykov

ну, например, так:

....

p.s. решение крайне неоптимальное - то, что называется - "в лоб"!!

orandzheviyman, вариант кода по алгоритму BDA с сортировкой ещё нужен?

Спасибо, но, к сожалению, так как я паскаль учу около двух месяцев, я не могу прочитать ваш код доконца
Можете рассказать алгорит, а я уже сам себе закодю, как знаю) Препод сказал максимально оптимальный средствами, которые мы знаем.



__________________
Оверквотинг (overquoting) на форуме запрещён.
Не злоупотребляйте избыточным цитированием.
Если Вы отвечаете на предыдущее сообщение, нет необходимости приводить его полностью в своем ответе.
В крайнем случае выберите нужный фрагмент и процитируйте его.
Модератор.

[Serge_Bliznykov]

Можете рассказать алгорит, а я уже сам себе закодю, как знаю)

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

Дополнительно.
для того, чтобы определить, был ли хоть один дублирующий элемент в массиве - заводим дополнительный флаг. Перед циклом ставим ему признак false =="Нет дублирующих элементов в массиве", а в цикле взводим этот флаг в true если нашли дублирующий элемент.

p.s. Вы насчёт варианта с сортировкой ничего не сказали.. Не нужен?

[Poma][a]

Тут обсуждать нечего.

Мой вариант позволяет убрать begin - end.. (что очень любит acmp.ru
Закрыли вопрос..

Вы не поверите.

Верю.

Нам кто-то гарантировал, что не будет внесён массив с отрицательными числами, где повторяться будет максимальное число со значением -1 ?!

Спасибо! Мой косяк! Вопрос закрыт..

Мои мысли в слух :

И так..
Что если создать множество и сливать туда элементы? А далее бежать по массиву и искать максимум, в случае, если a[i, j] in MSet..
Множество в паскале имеет ограничение на 256 элементов, что делает этот вариант не очень легким в реализации..
Но если использовать массив MSet : array [-MaxInt div 8 .. MaxInt div 8] of Byte.. баловаться битами (где-то я выставлял код вывода).. НО такой массив слишком огромен для такой задачи..

Таким образом я избавился от своего первоначального варианта..
Думаем дальше..
Если сливать элементы в НЕ отсортированный массив?
И так.. проверить есть ли элемент в массиве за O(N)
Добавить элемент за O(1)

Красота..

А если сортировать массив?
Поиск в массиве - O(log N) (дихотомия)
Добавление - тут сложнее.. сначала за O(log N) ищем место.. далее сдвиг.. за O (N / ?).. // Прошу помощи!

Другой вариант.. сливать в кучу..
Поиск - я, увы, не могу предположить..
Добавление - O(log N)...

Выложу общий код

max := -MaxInt; // да не напишет это число в матрицу тестер
for i := 1 to n do
    for j := 1 to m do
         if Exist (MSet, a[i, j] ) then
                if a[i, j] > max then
                       max := a[i, j]
         else
                IncludeElem (MSet, a[i, j])

UPDATE
Боюсь поиск в куче элемента будет = N..