|
|
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
я так понимаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2013, 18:30 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
denis_stellя так понимаю. Сектор 2 и 4 можно объединять разными способами. Кст. задачка внезапно напомнила мне оптимизацию Карно или Вейча. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2013, 18:40 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
denis_stell, Вы пытаетесь решить задачу разбиения (то есть построить одновременно кучу зданий). А задача совсем в другом - сколькими способами можно построить одно здание. И достаточно, например, расположить три непригодных участка по диагонали, чтобы ответы на то и другое разъехались. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2013, 18:47 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
Непонятная картинка. Мы считаем варианты или что? Если варианты, то здания могут упираться только в границы, но не друг в друга - и, разумеется, разные варианты зданий могут занимать один и тот же сектор. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2013, 18:49 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
softwarer, полностью согласен, ошибся. нужно построить одно здание ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2013, 19:40 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
maytonНу ты и старичелло, браза. Скоро уже пенсию приносить будут а ты всё на ПТ.... хех ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2013, 19:56 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
К нам не собираесси? В нашу Уркаину. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.03.2013, 19:58 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
Abstraction, Да, ляпнул недодумавши... Критерий нужен для границ, а не углов. И чтобы получить его, надо два прохода по матрице... Надо будет сравнить с количеством итераций при втором подходе (с построением списка) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.03.2013, 03:00 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
ребят,ну подскажите как подсчитать? сделал так: ввел матрицу, в дэволтном значении все значения матрицы =1 затем спрашиваю у ползователя "введи сколько не пригодных участков" вводим затем,в зависимости от того сколько участков, вводим для каждого участка координаты после того как определили координаты - заменяем эти значения 0 т.е. 1 пригодный участок. 0 не пригодный получается что-то типа этого: 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 допустим так, потом например иду в цикле по строкам +столбцам, проверяю если элемент например a[i][j]!=0 иду дальше и считаю элементы, как только в строке встретил элемент = 0 выхожу из цикла,но что-то не улавливаю... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.03.2013, 22:46 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
denis_stellребят,ну подскажите как подсчитать?schwa написал на предыдущей странице. Алгоритм как минимум неплохой, а скорее всего, вряд ли есть лучше. Сложности алгоритма, по крайней мере, зависит от К, а не от M х N. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.03.2013, 08:23 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
schwaВсе поле это один прямоугольник N на M. L - список, который содержит пригодные участки. Вначале он стоит из всего участка. 1) Берем первый непригодный участок. В соответствие с ним разбиваем (NxM) на нужно число частей. И добавляем полученные участки пригодные в L, удалив из него NxM. 2) Берем следующий непригодный участок. Находим какие он затрагивает участки из L и разбиваем их также как на шаге 1. Дальше снова 2. До тех пор, пока не закончатся непригодные участки. можете привести пример алгоритма, который вы написали? интересует п.1 (В соответствие с ним разбиваем (NxM) на нужно число частей. И добавляем полученные участки пригодные в L, удалив из него NxM.) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.03.2013, 14:36 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
denis_stell,  ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.03.2013, 18:06 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
визуально я понимаю как должно быть,спасибо. а как например вычислить эти зоны?варианты между например 1,2,3 непригодными участками?если не трудно или на псевдо-коде или C,pascal ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.03.2013, 22:25 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
Usman, Суть алгоритма понятна, но пропускаете варианты... Ну и главный вопрос-то (что для варианта schwa, что для вашего) - как выявить именно нужный "пригодный" вариант при анализе разрезов. rockclimberschwa написал на предыдущей странице... Сложности алгоритма, по крайней мере, зависит от К, а не от M х N.В указанном виде - от K зависит количество итераций для разбиения (в худшем случае - на каждой итерации список возрастает на 6 элементов), а от NxM зависит как раз анализ "пригодности". Так что сложность алгоритма - надо посмотреть... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.03.2013, 09:55 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
AndreTM, тогда как быть? я не совсем понимаю как получить варианты пригодных зданий?в контексте например той же матрицы? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.03.2013, 10:08 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
AndreTMrockclimberschwa написал на предыдущей странице... Сложности алгоритма, по крайней мере, зависит от К, а не от M х N.В указанном виде - от K зависит количество итераций для разбиения (в худшем случае - на каждой итерации список возрастает на 6 элементов), а от NxM зависит как раз анализ "пригодности". Так что сложность алгоритма - надо посмотреть...Не увидел в том алгоритме "анализа пригодности". Сначала пригодно все поле. Потом добавляем один непригодный сектор. Все поле делится на 2, 3 или 4 поля в зависимости от положения непригодного сектора. Потом добавляем второй. И т. д. Вроде как сложность должна быть O(K 2 ). Вариант алгоритма ТС-а - чуть ли не O(N 2 * M 2 ). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.03.2013, 13:50 |
|
||
|
алгоритм - Застройка
|
|||
|---|---|---|---|
|
#18+
rockclimber, Ну да, алгоритм ТС не пойдёт. А вот алгоритм с последовательным добавлением "непригодных" секторов попробую попозже изобразить... Там действительно получается похоже на ДП: - исходное положение: список из одного "пригодного" элемента (NxM) (это нулевое положение [K-1]). - считая, что для [K-1] элементов - список "пригоден", добавляем [K]-элемент: проходим список, находим элементы, куда попадает "непригодный", заменяем эти элементы на 2/3/4 новых элемента, и так далее. - составленный список надо проанализировать, и выбросить те элементы, которые полностью покрываются каким-либо другим элементом . Я вот интуитивно понимаю, что результат будет около дела, но надо это доказать... Инвариантность порядка добавления "непригодных, невозможность существования "составных" ответов (прямоугольник, сложенный из неполностью пересекающихся элементов списка); плюс неплохо бы оптимизировать последовательность действий - например, анализ попарного пересечения-покрытия элементов проводить в момент добавления в список. Тогда можно вплотную приблизиться к сложности O(K*lnK). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.03.2013, 15:03 |
|
||
|
|
start [/forum/moderation_log.php?user_name=%D1%85%D0%B5%D0%BB%D0%BF%D1%81]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
get settings: |
9ms |
get forum list: |
18ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
68ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
74ms |
get tp. blocked users: |
2ms |
| others: | 964ms |
| total: | 1182ms |
| 0 / 0 |
