реализуемо ли Опции

[.helga]

Реализуемо ли это в Делфи??


1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице
2 Найти наименьший из элементов, через которые не проходит ни одна прямая
3 Вычесть его из всех элементов, через которые не проходят прямые
4 Прибавить его ко всем элементам, лежащим на пересечении прямых
5 Элементы, через которые проходит только одна прямая, оставить неизменными

[мисс_граффити]

Реализуемо.
Скажи, у тебя есть идеи, каким алгоритмом надо пользоваться, чтобы минимизировать количество прямых? (Вне связи с языком реализации - как бы ты действовала, если бы тебе дали таблицу с числами и попросили провести такие прямые?)

[.helga]

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

max:=0;
counter:=0;

for i:=1 to m do
begin
for ii:=1 to m do
if matr[i,ii]=0 then
inc(counter);
if counter>max then
begin
max:=counter;
b:=ii; {запоминаем строку}
counter:=0;
end;
end;

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

Сообщение отредактировано: .helga - 2.01.2007 4:15

[мисс_граффити]

в принципе, думала примерно так же.
единственное уточнение - надо будет параллельно анализировать строки и столбцы.
то есть как-то так: нашли самую "нулевую" строку, потом - самый "нулевый" столбец, и только после этого решаем, что вычеркивать.
и на следующем этапе уже вычеркнутые нули не принимать во внимание.

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

Цикл заканчивается, когда не осталось невычеркнутых нулей. То есть, если идем вторым путем, массив обнулился. Если первым - можно хранить кол-во оставшихся нулей в отдельной переменной.

следующий вопрос: как проверять, вычеркнуто ли то или иное число?
у меня есть 2 идеи:
1) создаем дополнительный массив, в который записываем номера вычеркнутых строк и столбцов.
2) исходный массив объявляем не так:

matr: array[1..m,1..m] of integer;

а так:

type
element=record
info,checked: integer;
end;
var matr: array[1..m,1..m] of element;

причем в поле info храним собственно значение (цифру), а в checked - информацию о зачеркнутости (0 - не зачеркнуто, 1 - зачеркнуто, 2 - находится на пересечении).

мне кажется, со вторым будет несколько проще работать.
как считаешь?

в общем, попробуй...
если что получится - выкладывай. если нет - напиши об этом...

Сообщение отредактировано: мисс_граффити - 2.01.2007 4:46

[.helga]

о, пришла бредовая мысля!

а что, если "зачеркнутые значения" в процессе зачеркивания умножить, напр, на те же 100. у меня ограничение по вводу меньше трех цифр, так что тогда будет сразу видно, что мы "зачеркивали", + довольно легко найдутся пересечения. и поиску мин. значений это не будет мешать.

потом:
if a[i,ii]<100 then a[i,ii]:=a[i,ii]-min;

затем ищем пересечения:
if a[i,ii]>=10000 then a[i,ii]:=a[i,ii]/10000+min

а остальные: двойной вложенный цикл
if a[i,ii]>=100 then a[i,ii]:=a[i,ii]/100.

будет оно правильно работать? а вот с этим поиском строк/столбцов с макс. кол-вом нулей я все равно туплю..

[Bokul]

Вот мое решение:
Пойдём от обратного: какое максимальное число n линий нужно провести, чтобы вычеркнуть все нули с квадратной матрицы (потом легко можно перейти к общему случаю)? Ответ прост - число линий будет отвечать размерности матрицы (количеству столбцов или строк). Тогда когда же мы сможем получить выигрыш (число вычеркиваний будет меньшим чем n)? Ответ тоже прост - только в том случае, когда на каком-нибудь столбце или строке вообще не будет нулей.
Алгоритм таковой: находим все "безнулевые" строки и столбцы, одновременно считая их количество(NColumn, NLine). Сравниваем NColumn и NLine, если NLine больше проводим горизонтальные линии через все строки, не помечены как "безнулевые", если же NColumn - тоже самое, только вертикальные линии. В случае равенства - запускаем random з 2.. - направление не имеет значения.

[.helga]

а если безнулевых строк/столбцов не окажется?

1 1 1 0
1 0 1 1
0 0 1 1
1 1 0 1

хорошо, пусть в этом случае будет равенство. 0=0, => рандом. но рандом на то и рандом, что никак не угадать, что он начеркает. может оказаться, что вычеркнуться все элементы матрицы, как в таком, например, случае. а можно (нужно!) вычеркнуть минимальным кол-вом линий, чтобы эл-ты остались.

напрмер так;
1 - 1 -
1 - 1 -
- - - -
- - - -

пс. матрица и так квадратная. забыла уточнить в теме.

Сообщение отредактировано: .helga - 2.01.2007 8:41

[Bokul]

Ты не поняла шутки с random-ом - если безнулевых строк/столбцов не будет, то все-равно, проведём ли мы 4 вертикальных или 4 горизонтальных линий. Его мы используем чтобы узнать проводить горизонтальные или вертикальные линии. Ты можешь вообще не использовать random, тогда в случае равенства всегда проводить, например, только горизонтальные линии, хотя с тем же успехом можешь использовать только вертикальные.

Сообщение отредактировано: Bokul - 2.01.2007 8:49

[.helga]

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

[Bokul]

или ты предлагаешь делать это рекурсивно (по одному зачеркиванию за раз) и по ходу дела уже анализировать ситуацию?

.helga, почему ты так хочешь усложнить все? Хватит того, что я описал в 6 посте.

ну да. если в моем примере проводить только горизонтальные линии, то все эл-ты зачеркнуться.

Сделай еще примеры, пройдись по ним с моим алгоритмом, если найдешь ситуацию, когда он дает не минимальное число зачеркиваний - повышу рейтинг..

[.helga]

не хватит! потому что при некоторых примерах оно не выполняется. как в том, что я привела. или в матрице, трансп. из этой:

1 0 1 1
1 0 0 1
0 1 1 1
1 1 1 0

хоть вычеркивай только вертикальные, хоть только горизонтальные, будет совсем не то, что требуется. таких примеров можно привести кучу (таких - когда нет ненулевых строк/столбцов=> алгоритм не работает).

алгоритм должен подходить по все возможные варианты, за исключением парочки, что можно описать в else. вот

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

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

[Bokul]

будет совсем не то, что требуется

Что требуется? Найти минимальное количество зачеркиваний, правильно? Какой ответ даст мой алгоритм для твоего случая? Ответ-четыре. Неужели ты видишь как сделать меньше?

[.helga]

Но зачеркивать-то с умом нужно) Чтобы остались элементы, над которыми производить потом разные действия.

0 1 1 1
0 1 1 1
1 1 0 1
1 0 0 0

м?) можно зачеркнуть тремя линиями. а по твоему алгоритму он 4 сделает.

[Bokul]

.helga, покажи как ты с умом зачеркнёшь все нули в твоем примере.

м?) можно зачеркнуть тремя линиями. а по твоему алгоритму он 4 сделает.

Так бы сразу, действительно мой алгоритм - не правильный.

[.helga]

насчет тех примеров:
зачеркну. сначала вычеркиваем столбец/строку с максимальным кол-вом нулей, а потом, когда появляются ненулевые строки/столбцы, можно рассуждать по твоему алгоритму.
проблема в том, что его можно применять только при наличии этих самых безнулевых столбцов.

Сообщение отредактировано: .helga - 2.01.2007 9:43

[Bokul]

Нет мой алгоритм и для такого не годится:
1111
1101
1101
1000
он даст 3, хотя можно обойтись и двумя линиями.

[.helga]

хм. тогда кроме вычеркивания строк/столбцов с максимальным кол-вом нулей, я решений не вижу..
вот так?

max_a, max_b, counter, i, ii, m: integer;

begin
max_b:=0;
counter:=0;

for i:=1 to m do
 begin
  for ii:=1 to m do
   if matr[i,ii]=0 then
    inc(counter);
   if counter>max_b then
    begin
     max_b:=counter;
     b:=ii; {запоминаем строку}
     counter:=0;
    end;
 end;

max_a:=0;

for ii:=1 to m do
 begin
  for i:=1 to m do
   if matr[i,ii]=0 then
    inc(counter);
   if counter>max_a then
    begin
     max_a:=counter;
     a:=i; {запоминаем столбец}
     counter:=0;
    end;
 end;

if max_a<max_b then 
 begin
  for i:=1 to m do
   if matr[i,b]=0 then matr[i,b]:=matr[i,b]*100;
 end
else
 begin
  for ii:=1 to m do
   if matr[a,ii]=0 then matr[a,ii]:=matr[a,ii]*100;  
  end;
end;

выполнять пока есть нули.
чет как-то громоздко получилось..

Сообщение отредактировано: .helga - 2.01.2007 10:23

[Bokul]

А полный код можешь привести?

[.helga]

отредактировала чуток предыдущее. спать все-таки иногда надо, прокалываюсь на мелочах)

полный код - это код всех 5 шагов? или только "вычеркивания"?

[Bokul]

полный код - это код всех 5 шагов?

Тот который будет компилироваться..