реализуемо ли |
Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.
реализуемо ли |
.helga |
1.01.2007 22:55
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 26 Пол: Женский Репутация: 1 |
Реализуемо ли это в Делфи??
1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице 2 Найти наименьший из элементов, через которые не проходит ни одна прямая 3 Вычесть его из всех элементов, через которые не проходят прямые 4 Прибавить его ко всем элементам, лежащим на пересечении прямых 5 Элементы, через которые проходит только одна прямая, оставить неизменными |
мисс_граффити |
1.01.2007 23:35
Сообщение
#2
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
Реализуемо.
Скажи, у тебя есть идеи, каким алгоритмом надо пользоваться, чтобы минимизировать количество прямых? (Вне связи с языком реализации - как бы ты действовала, если бы тебе дали таблицу с числами и попросили провести такие прямые?) -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
.helga |
2.01.2007 0:05
Сообщение
#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 - 2.01.2007 0:15 |
мисс_граффити |
2.01.2007 0:44
Сообщение
#4
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
в принципе, думала примерно так же.
единственное уточнение - надо будет параллельно анализировать строки и столбцы. то есть как-то так: нашли самую "нулевую" строку, потом - самый "нулевый" столбец, и только после этого решаем, что вычеркивать. и на следующем этапе уже вычеркнутые нули не принимать во внимание. Очень много лишних проходов. Может быть, имеет смысл потратить некоторое количество памяти и, посчитав количество нулей в каждой строке и столбце, записать их отдельно? а потом по мере вычеркивания корректировать? Цикл заканчивается, когда не осталось невычеркнутых нулей. То есть, если идем вторым путем, массив обнулился. Если первым - можно хранить кол-во оставшихся нулей в отдельной переменной. следующий вопрос: как проверять, вычеркнуто ли то или иное число? у меня есть 2 идеи: 1) создаем дополнительный массив, в который записываем номера вычеркнутых строк и столбцов. 2) исходный массив объявляем не так: matr: array[1..m,1..m] of integer; а так:
причем в поле info храним собственно значение (цифру), а в checked - информацию о зачеркнутости (0 - не зачеркнуто, 1 - зачеркнуто, 2 - находится на пересечении). мне кажется, со вторым будет несколько проще работать. как считаешь? в общем, попробуй... если что получится - выкладывай. если нет - напиши об этом... Сообщение отредактировано: мисс_граффити - 2.01.2007 0:46 -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
.helga |
2.01.2007 1:07
Сообщение
#5
|
Новичок Группа: Пользователи Сообщений: 26 Пол: Женский Репутация: 1 |
о, пришла бредовая мысля!
а что, если "зачеркнутые значения" в процессе зачеркивания умножить, напр, на те же 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 |
2.01.2007 4:21
Сообщение
#6
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
Вот мое решение:
Пойдём от обратного: какое максимальное число n линий нужно провести, чтобы вычеркнуть все нули с квадратной матрицы (потом легко можно перейти к общему случаю)? Ответ прост - число линий будет отвечать размерности матрицы (количеству столбцов или строк). Тогда когда же мы сможем получить выигрыш (число вычеркиваний будет меньшим чем n)? Ответ тоже прост - только в том случае, когда на каком-нибудь столбце или строке вообще не будет нулей. Алгоритм таковой: находим все "безнулевые" строки и столбцы, одновременно считая их количество(NColumn, NLine). Сравниваем NColumn и NLine, если NLine больше проводим горизонтальные линии через все строки, не помечены как "безнулевые", если же NColumn - тоже самое, только вертикальные линии. В случае равенства - запускаем random з 2.. - направление не имеет значения. -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
.helga |
2.01.2007 4:39
Сообщение
#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 - 2.01.2007 4:41 |
Bokul |
2.01.2007 4:47
Сообщение
#8
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
Ты не поняла шутки с random-ом - если безнулевых строк/столбцов не будет, то все-равно, проведём ли мы 4 вертикальных или 4 горизонтальных линий. Его мы используем чтобы узнать проводить горизонтальные или вертикальные линии. Ты можешь вообще не использовать random, тогда в случае равенства всегда проводить, например, только горизонтальные линии, хотя с тем же успехом можешь использовать только вертикальные.
Сообщение отредактировано: Bokul - 2.01.2007 4:49 -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
.helga |
2.01.2007 4:50
Сообщение
#9
|
Новичок Группа: Пользователи Сообщений: 26 Пол: Женский Репутация: 1 |
ну да. если в моем примере проводить только горизонтальные линии, то все эл-ты зачеркнуться.
или ты предлагаешь делать это рекурсивно (по одному зачеркиванию за раз) и по ходу дела уже анализировать ситуацию? |
Bokul |
2.01.2007 5:02
Сообщение
#10
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
Цитата или ты предлагаешь делать это рекурсивно (по одному зачеркиванию за раз) и по ходу дела уже анализировать ситуацию? .helga, почему ты так хочешь усложнить все? Хватит того, что я описал в 6 посте. Цитата ну да. если в моем примере проводить только горизонтальные линии, то все эл-ты зачеркнуться. Сделай еще примеры, пройдись по ним с моим алгоритмом, если найдешь ситуацию, когда он дает не минимальное число зачеркиваний - повышу рейтинг.. -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
.helga |
2.01.2007 5:18
Сообщение
#11
|
Новичок Группа: Пользователи Сообщений: 26 Пол: Женский Репутация: 1 |
не хватит! потому что при некоторых примерах оно не выполняется. как в том, что я привела. или в матрице, трансп. из этой:
1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 хоть вычеркивай только вертикальные, хоть только горизонтальные, будет совсем не то, что требуется. таких примеров можно привести кучу (таких - когда нет ненулевых строк/столбцов=> алгоритм не работает). алгоритм должен подходить по все возможные варианты, за исключением парочки, что можно описать в else. вот если есть безнулевые строки или столбцы, все работает, но если нету.. вот тут-то и прокол. дело в том, в этой задаче предыдущие два этапа как раз такие, что безнулевых строк/столбцов как раз не окажется.. (до этого находятся максы и мины в каждых строках/столбцах и вычитаются из всех эл-тов строки/столбца). имхо, проще было бы каждый раз искать строку/столбец с наиб. кол-вом нулей и вычеркивать его.. |
Bokul |
2.01.2007 5:27
Сообщение
#12
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
Цитата будет совсем не то, что требуется Что требуется? Найти минимальное количество зачеркиваний, правильно? Какой ответ даст мой алгоритм для твоего случая? Ответ-четыре. Неужели ты видишь как сделать меньше? -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
.helga |
2.01.2007 5:33
Сообщение
#13
|
Новичок Группа: Пользователи Сообщений: 26 Пол: Женский Репутация: 1 |
Но зачеркивать-то с умом нужно) Чтобы остались элементы, над которыми производить потом разные действия.
0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 м?) можно зачеркнуть тремя линиями. а по твоему алгоритму он 4 сделает. |
Bokul |
2.01.2007 5:35
Сообщение
#14
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
.helga, покажи как ты с умом зачеркнёшь все нули в твоем примере.
Цитата м?) можно зачеркнуть тремя линиями. а по твоему алгоритму он 4 сделает. Так бы сразу, действительно мой алгоритм - не правильный. -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
.helga |
2.01.2007 5:42
Сообщение
#15
|
Новичок Группа: Пользователи Сообщений: 26 Пол: Женский Репутация: 1 |
насчет тех примеров:
зачеркну. сначала вычеркиваем столбец/строку с максимальным кол-вом нулей, а потом, когда появляются ненулевые строки/столбцы, можно рассуждать по твоему алгоритму. проблема в том, что его можно применять только при наличии этих самых безнулевых столбцов. Сообщение отредактировано: .helga - 2.01.2007 5:43 |
Bokul |
2.01.2007 6:05
Сообщение
#16
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
Нет мой алгоритм и для такого не годится:
1111 1101 1101 1000 он даст 3, хотя можно обойтись и двумя линиями. -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
.helga |
2.01.2007 6:16
Сообщение
#17
|
Новичок Группа: Пользователи Сообщений: 26 Пол: Женский Репутация: 1 |
хм. тогда кроме вычеркивания строк/столбцов с максимальным кол-вом нулей, я решений не вижу..
вот так?
выполнять пока есть нули. чет как-то громоздко получилось.. Сообщение отредактировано: .helga - 2.01.2007 6:23 |
Bokul |
2.01.2007 6:18
Сообщение
#18
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
А полный код можешь привести?
-------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
.helga |
2.01.2007 6:22
Сообщение
#19
|
Новичок Группа: Пользователи Сообщений: 26 Пол: Женский Репутация: 1 |
отредактировала чуток предыдущее. спать все-таки иногда надо, прокалываюсь на мелочах)
полный код - это код всех 5 шагов? или только "вычеркивания"? |
Bokul |
2.01.2007 6:28
Сообщение
#20
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
Цитата полный код - это код всех 5 шагов? Тот который будет компилироваться.. -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
Текстовая версия | 11.06.2024 21:09 |