IPB
ЛогинПароль:

> ВНИМАНИЕ!

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

3 страниц V  1 2 3 >  
 Ответить  Открыть новую тему 
> реализуемо ли
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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


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


 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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

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

следующий вопрос: как проверять, вычеркнуто ли то или иное число?
у меня есть 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 - находится на пересечении).

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

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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

а что, если "зачеркнутые значения" в процессе зачеркивания умножить, напр, на те же 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.

будет оно правильно работать? а вот с этим поиском строк/столбцов с макс. кол-вом нулей я все равно туплю..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

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

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

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

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

Сообщение отредактировано: .helga -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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

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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


ну да. если в моем примере проводить только горизонтальные линии, то все эл-ты зачеркнуться.
или ты предлагаешь делать это рекурсивно (по одному зачеркиванию за раз) и по ходу дела уже анализировать ситуацию?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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

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

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

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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

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

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

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

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

имхо, проще было бы каждый раз искать строку/столбец с наиб. кол-вом нулей и вычеркивать его..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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

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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

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

м?) можно зачеркнуть тремя линиями. а по твоему алгоритму он 4 сделает.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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

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

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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

Сообщение отредактировано: .helga -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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


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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


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

полный код - это код всех 5 шагов? или только "вычеркивания"?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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

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


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

3 страниц V  1 2 3 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 5.11.2024 12:53
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name