Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Удаление серии одинаковых элементов матрицы

Автор: NAGGANO 5.5.2012, 18:14

Помогите разобраться с алгоритмом удаления серии одинаковых элементов в матрице. Например, есть матрица

1 0 0 1 1 1
1 1 1 0 0 0
1 2 2 1 1 0
1 0 1 0 1 0
1 1 1 1 0 0
0 2 2 2 2 2

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

Автор: W4FhLF 5.5.2012, 18:47

Что должно остаться после удаления?

Автор: Akina 5.5.2012, 18:49

Код


count=0
prev=mass(1)
pointer=0
for i = 1 to N
  if mass(i)=prev then
    count=count+1
    if count<3 then
      pointer=pointer+1
    end if
  else
    prev=mass(i)
    count=1
    pointer=pointer+1
  end if
  mass(pointer)=mass(i)
next

Автор: NAGGANO 5.5.2012, 18:51

Можно удаляемые просто на null (n) заменить. Например, получится должно так:

n 0 0 n n n
n n n n n n
n 2 2 1 1 n
n 0 1 0 1 n
n n n n 0 n
0 n n n n n

Добавлено через 3 минуты и 7 секунд

Цитата(Akina @ 5.5.2012, 18:49)

Код


count=0
prev=mass(1)
pointer=0
for i = 1 to N
  if mass(i)=prev then
    count=count+1
    if count<3 then
      pointer=pointer+1
    end if
  else
    prev=mass(i)
    count=1
    pointer=pointer+1
  end if
  mass(pointer)=mass(i)
next

Это ж для одномерного массива, а мне для матрицы надо

Автор: W4FhLF 5.5.2012, 18:57

Матрицы то какого размера?

Автор: NAGGANO 5.5.2012, 19:00

Ну как в примере, например, 6х6 размер.

Автор: W4FhLF 5.5.2012, 19:03

Ну в общем вы никаких ограничений на сложность алгоритма не поставили. Почему бы тогда не реализовать простейший перебор всех элементов (сложность будет О(N^2), N -- кол-во элементов матрицы)? На каком языке вы пишете?

Автор: NAGGANO 5.5.2012, 19:08

Мне кажется слишком уж фпс нервничать будет - в двойном цикле еще вложенных два цикла. Пишу на Actionscript 3.0
Возможно если обойтись только тремя циклами то нормально будет:

Код


for ( var i:int = 0; i < 6; i++ )
{
    for ( var j:int = 0; j < 6; j++ )
    {
         for ( var k:int = 0; k < 6; k++ )
        {
            ....
        }
    }
}

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

Автор: W4FhLF 5.5.2012, 19:17

Преждевременная оптимизация -- зло)
Реализуйте простейший вариант, будет тормозить тогда уже надо думать как оптимизировать.

Для перебора потребуется 36^2 сравнений. Если сравнение двух объектов вашей матрицы операция быстрая (можно сравнивать указатели или хеши для сложных объектов), то 1300 сравнений это немного.

Автор: NAGGANO 5.5.2012, 19:20

У меня вообще в игре матрица 10х10 smile

Ну попробую сделать сейчас такой перебор - может сильно и не будет тормозить)
Но если есть еще какие-нить предложения - очень жду)

Автор: W4FhLF 5.5.2012, 19:26

А сколько возможных состояний может принять каждый элемент матрицы?
Если число небольшое, то можно хранить количество объектов определённого значения в каждой строке и столбце и обновлять эти значения при добавлении/удалении объекта. Когда понадобится выполнить замену всех элементов встречающихся более трёх раз вы уже будете знать какие элементы в каких строках и столбцах надо заменить.

Автор: NAGGANO 5.5.2012, 19:30

Он может либо существовать либо нет. Других состояний нет.У него есть переменная type - и вот именно эти поля мне и надо сравнивать.
Спасибо за идею - опробую и ее smile