-------
| | | |
| | | |
| | | |
-------
Задача о прямоугольниках (чисто алгоритмическая)
Когда ночью не спится, включаю телик. Как-то раз напоролся на игру "деньги на проводе" по ТНТ. Вот и возникла идея решить одну из предложенных там задач в общем случае.
Задача такая. Дан прямоугольник (n строк, m столбцов), "разлинованный" на клетки (как тетрадь в клетку). Но некоторые "границы" между клетками отсутствуют. Нужно подсчитать количество прямоугольников, образуемых этой системой клеток. Думаю, не нужно объяснять, что в данном случае считать прямоугольником: прямоугольником является любая система клеток, ограничиваемая двумя вертикальными и двумя горизонтальными линиями, при этом, естественно, линии не должны проходить по непрочерченным "стенкам".
В приведенном ниже примере пять прямоугольников:
____
|_|_|
|___|
- левая верхняя клетка;
- правая верхняя клетка;
- прямоугольник, образованный двумя верхними клетками;
- нижний прямоугольник;
- вся система тоже является прямоугольником.
Мой вариант решения использует комбинаторику. Обозначения: n - размер генерального прямоугольника в ширину, m - размер генерального прямоугольника в длину, k - количество "непрочерченных" стенок. Абсциссы и ординаты как клеток, так и стенок нумеруются по математическим правилам - от единицы.
Прямоугольник однозначно идентифицируется парой противоположных углов - скажем, левым верхним и правым нижним. Поэтому мы можем подсчитать число прямоугольников, которые мы могли бы образовать, если бы все стенки между клетками существовали, были "прочерчены".
Очевидно, абсциссу левого верхнего угла мы можем выбрать n способами. Причем для каждой выбранной абсциссы левого верхнего угла абсцисса правого нижнего выбирается n+1-i способами, где i - абсцисса текущего левого верхнего угла. Соответственно, число способов образовать абсциссу левого верхнего угла и абсциссу правого нижнего угла равно:
Сумма от i=1 по n (n+1-i) = сумма от i=1 по n (i) = n * (n+1) / 2.
Независимо от выбора абсциссы, ординаты мы можем выбрать
m (m+1) / 2 способами. Благодаря независимости выбора абсциссы и ординаты, получаем общее количество способов (обозначим через S0):
S0 = n * (n+1) / 2 * m * (m+1) / 2.
Теперь для каждой непрочерченной стенки (в нашем примере такая стенка одна) число прямоугольников, которое нельзя провести через данную стенку. Сумму этих чисел обозначим S1.
Используя метод включения и исключения, возьмем полученное число S0 и вычтем из него число прямоугольников, которое нельзя провести через каждую отдельно взятую стенку, т. е. S1. Но при этом мы дважды вычли прямоугольники, которые нельзя провести одновременно через две стенки, поэтому подсчитаем их количество и прибавим их, и т. д.:
S = S0 + S1 - S2 + S3 - ... (+-) Sk
"Непрочерченную стенку" можно идентифицировать координатой клетки, для которой эта стенка является левой (если стенка вертикальная) или верхней (если горизонтальная). Если же стенка находится в самом низу генерального прямоугольника, ей не соответствует ни одна клетка; присвоим ей ординату m+1; если она находится на правой "стене" генерального прямоугольника, т. е. опять же вне зоны клеток, присвоим ей абсциссу n+1. Таким образом, абсцисса стенки меняется от 1 до n+1, ордината от 1 до m+1.
Тогда число S1 (число прямоугольников, проходящих через каждую "непрочерченную" стенку, просуммировано по всем таким стенкам) можно посчитать по нижеследующим формулам.
1. Если стенка горизонтальная, через нее нельзя провести i * (n+1-i) * m прямоугольников.
2. Если стенка вертикальная, через нее нельзя провести j * (m+1-j) * n прямоугольников.
Здесь (i, j) - соответственно абсцисса и ордината стенки. Отмечу, что для горизонтальной стенки число не зависит от ее ординаты, а для вертикальной - от абсциссы.
Очевидно, для подсчета S1 требуется время порядка O(k), где k - количество непрочерченных стенок.
Теперь нужно сосчитать число S2 (число прямоугольников, проходящих через пару "непрочерченных" стенок, просуммировано по всевозможным парам стенок).
1. Для пары горизонтальных стенок (i1, j1); (i2, j2):
1а. Если их ординаты не равны (j1 <> j2), т. е. стенки лежат на противоположных стенках прямоугольника, имеем формулу i1 * (n+1-i2)
(предполагается, что i1 <= i2, в противном случае просто переобозначим их).
1б. Если их ординаты равны (j1 = j2), т. е. стенки лежат на одной стороне прямоугольника, имеем формулу i1 * (n+1-i2) * m (опять же предполагается i1 <= i2).
2. Для пары вертикальных стенок формулы идентичны.
3. Для пары "горизонтальная-вертикальная" (обозначим через (i1, j1) горизонтальную, (i2, j2) вертикальную):
3а. Если i1 < i2 и j2 < j1: i1*j2
3б. Если i1 < i2 и j2 >= j1: i1 * (m+1-j2)
3в. Если i1 >= i2 и j2 < j1: (n+1-i1) * j2
3г. Если i1 >= i2 и j2 >= j1: (n+1-i1) * (m+1-j2)
Число всевозможных пар стенок равно C (2, k) = k! / (2! * (k-2)!) = k * (k-1) / 2, т. е. для подсчета S2 требуется время порядка O (k^2), где k - количество стенок.
Формулы для S3 и т. д. я приводить не буду, поскольку это займет много места. Однако добавлю, что можно вывести формулы и для S4; а дальнейшие случаи сводятся к S1-S4 (поскольку прямоугольник имеет только 4 стороны).
Итак, выводы. Для подсчета числа прямоугольников используется метод включения и исключения, для чего нам нужно провести 1 вычисление для подсчета S0, k вычислений для подсчета S1, k (k-1) / 2 вычислений для подсчета S2 и т. д. Получим общее число вычислений:
Сумма от i=0 по k C(i,k) = 2^k.
Таким образом, алгоритмическая сложность такого решения O (2^k).
Тут есть возможность для оптимизации. Если при вычислении какого-то из чисел Si мы получили ноль, дальнейшие числа вычислять не имеет смысла - они также будут нулевыми (если ни один прямоугольник не проходит, скажем, через произвольную тройку стенок, то ни один прямоугольник не будет также проходить и через четверку стенок). Поэтому в этот момент имеет смысл прервать вычисления и выдать результат. Однако оценку сложности такого оптимизированного алгоритма провести сложно, поскольку нельзя даже сказать определённо, с какой вероятностью алгоритм прервется на каком-то определенном шаге, поэтому будем считать, что сложность алгоритма не хуже O (2^k).
Отмечу, что если решать задачу "напролом", простым перебором вариантов, сложность задачи составит O (2^(n*m)). Однако, если учесть, что для каждого варианта прямоугольника нужно выполнять поиск стенок, через которые он может проходить, и предположить, что время поиска логарифмическое, получим несколько худшее время: O (2^(n*m) * log2 k).
Внимание, вопрос :) Есть ли более быстрый алгоритм?
Задача такая. Дан прямоугольник (n строк, m столбцов), "разлинованный" на клетки (как тетрадь в клетку). Но некоторые "границы" между клетками отсутствуют. Нужно подсчитать количество прямоугольников, образуемых этой системой клеток. Думаю, не нужно объяснять, что в данном случае считать прямоугольником: прямоугольником является любая система клеток, ограничиваемая двумя вертикальными и двумя горизонтальными линиями, при этом, естественно, линии не должны проходить по непрочерченным "стенкам".
В приведенном ниже примере пять прямоугольников:
____
|_|_|
|___|
- левая верхняя клетка;
- правая верхняя клетка;
- прямоугольник, образованный двумя верхними клетками;
- нижний прямоугольник;
- вся система тоже является прямоугольником.
Мой вариант решения использует комбинаторику. Обозначения: n - размер генерального прямоугольника в ширину, m - размер генерального прямоугольника в длину, k - количество "непрочерченных" стенок. Абсциссы и ординаты как клеток, так и стенок нумеруются по математическим правилам - от единицы.
Прямоугольник однозначно идентифицируется парой противоположных углов - скажем, левым верхним и правым нижним. Поэтому мы можем подсчитать число прямоугольников, которые мы могли бы образовать, если бы все стенки между клетками существовали, были "прочерчены".
Очевидно, абсциссу левого верхнего угла мы можем выбрать n способами. Причем для каждой выбранной абсциссы левого верхнего угла абсцисса правого нижнего выбирается n+1-i способами, где i - абсцисса текущего левого верхнего угла. Соответственно, число способов образовать абсциссу левого верхнего угла и абсциссу правого нижнего угла равно:
Сумма от i=1 по n (n+1-i) = сумма от i=1 по n (i) = n * (n+1) / 2.
Независимо от выбора абсциссы, ординаты мы можем выбрать
m (m+1) / 2 способами. Благодаря независимости выбора абсциссы и ординаты, получаем общее количество способов (обозначим через S0):
S0 = n * (n+1) / 2 * m * (m+1) / 2.
Теперь для каждой непрочерченной стенки (в нашем примере такая стенка одна) число прямоугольников, которое нельзя провести через данную стенку. Сумму этих чисел обозначим S1.
Используя метод включения и исключения, возьмем полученное число S0 и вычтем из него число прямоугольников, которое нельзя провести через каждую отдельно взятую стенку, т. е. S1. Но при этом мы дважды вычли прямоугольники, которые нельзя провести одновременно через две стенки, поэтому подсчитаем их количество и прибавим их, и т. д.:
S = S0 + S1 - S2 + S3 - ... (+-) Sk
"Непрочерченную стенку" можно идентифицировать координатой клетки, для которой эта стенка является левой (если стенка вертикальная) или верхней (если горизонтальная). Если же стенка находится в самом низу генерального прямоугольника, ей не соответствует ни одна клетка; присвоим ей ординату m+1; если она находится на правой "стене" генерального прямоугольника, т. е. опять же вне зоны клеток, присвоим ей абсциссу n+1. Таким образом, абсцисса стенки меняется от 1 до n+1, ордината от 1 до m+1.
Тогда число S1 (число прямоугольников, проходящих через каждую "непрочерченную" стенку, просуммировано по всем таким стенкам) можно посчитать по нижеследующим формулам.
1. Если стенка горизонтальная, через нее нельзя провести i * (n+1-i) * m прямоугольников.
2. Если стенка вертикальная, через нее нельзя провести j * (m+1-j) * n прямоугольников.
Здесь (i, j) - соответственно абсцисса и ордината стенки. Отмечу, что для горизонтальной стенки число не зависит от ее ординаты, а для вертикальной - от абсциссы.
Очевидно, для подсчета S1 требуется время порядка O(k), где k - количество непрочерченных стенок.
Теперь нужно сосчитать число S2 (число прямоугольников, проходящих через пару "непрочерченных" стенок, просуммировано по всевозможным парам стенок).
1. Для пары горизонтальных стенок (i1, j1); (i2, j2):
1а. Если их ординаты не равны (j1 <> j2), т. е. стенки лежат на противоположных стенках прямоугольника, имеем формулу i1 * (n+1-i2)
(предполагается, что i1 <= i2, в противном случае просто переобозначим их).
1б. Если их ординаты равны (j1 = j2), т. е. стенки лежат на одной стороне прямоугольника, имеем формулу i1 * (n+1-i2) * m (опять же предполагается i1 <= i2).
2. Для пары вертикальных стенок формулы идентичны.
3. Для пары "горизонтальная-вертикальная" (обозначим через (i1, j1) горизонтальную, (i2, j2) вертикальную):
3а. Если i1 < i2 и j2 < j1: i1*j2
3б. Если i1 < i2 и j2 >= j1: i1 * (m+1-j2)
3в. Если i1 >= i2 и j2 < j1: (n+1-i1) * j2
3г. Если i1 >= i2 и j2 >= j1: (n+1-i1) * (m+1-j2)
Число всевозможных пар стенок равно C (2, k) = k! / (2! * (k-2)!) = k * (k-1) / 2, т. е. для подсчета S2 требуется время порядка O (k^2), где k - количество стенок.
Формулы для S3 и т. д. я приводить не буду, поскольку это займет много места. Однако добавлю, что можно вывести формулы и для S4; а дальнейшие случаи сводятся к S1-S4 (поскольку прямоугольник имеет только 4 стороны).
Итак, выводы. Для подсчета числа прямоугольников используется метод включения и исключения, для чего нам нужно провести 1 вычисление для подсчета S0, k вычислений для подсчета S1, k (k-1) / 2 вычислений для подсчета S2 и т. д. Получим общее число вычислений:
Сумма от i=0 по k C(i,k) = 2^k.
Таким образом, алгоритмическая сложность такого решения O (2^k).
Тут есть возможность для оптимизации. Если при вычислении какого-то из чисел Si мы получили ноль, дальнейшие числа вычислять не имеет смысла - они также будут нулевыми (если ни один прямоугольник не проходит, скажем, через произвольную тройку стенок, то ни один прямоугольник не будет также проходить и через четверку стенок). Поэтому в этот момент имеет смысл прервать вычисления и выдать результат. Однако оценку сложности такого оптимизированного алгоритма провести сложно, поскольку нельзя даже сказать определённо, с какой вероятностью алгоритм прервется на каком-то определенном шаге, поэтому будем считать, что сложность алгоритма не хуже O (2^k).
Отмечу, что если решать задачу "напролом", простым перебором вариантов, сложность задачи составит O (2^(n*m)). Однако, если учесть, что для каждого варианта прямоугольника нужно выполнять поиск стенок, через которые он может проходить, и предположить, что время поиска логарифмическое, получим несколько худшее время: O (2^(n*m) * log2 k).
Внимание, вопрос :) Есть ли более быстрый алгоритм?
Лучше спи по ночам, полезнее, а так неплохо))))))))))))))))))
Это шутка, прошу не обижаться)
Это шутка, прошу не обижаться)
Подобная задача уже когда-то обсуждалась.
Насколько я знаю - нет. Меньше чем за экспоненту не решается.
Если постараться (применить динамическое программирование), то решается за O(m*n).
Дерзайте! :)
Дерзайте! :)
Так ты б его описал. А то, как любят утверждать некоторые товарищи, телепаты-то в отпуске :) Лично я с динамическим программированием не очень знаком.
Да я пока и сам не придумал... :)
Но m*n - предел к которому надо стремиться.
Но m*n - предел к которому надо стремиться.
Если решать "напролом", т.е. перебором, то сложность составляет (m*n)^2, что в подавляющем случае лучше, чем 2^k.
Мы тут посовещались (для упрощения обсуждения брали прямоугольник nxn) и придумали алгоритм n^3.
Потом оптимизировали алгоритм до n^2 + b, где b - количество оснований валидных прямоугольников. Что в общем случае меньше, чем n^3.
До n^2 пока не дошли. :)
P.S. Как придумаю, как описать те каракули, которые мы нарисовали в ходе обсуждения, запосчу.
Мы тут посовещались (для упрощения обсуждения брали прямоугольник nxn) и придумали алгоритм n^3.
Потом оптимизировали алгоритм до n^2 + b, где b - количество оснований валидных прямоугольников. Что в общем случае меньше, чем n^3.
До n^2 пока не дошли. :)
P.S. Как придумаю, как описать те каракули, которые мы нарисовали в ходе обсуждения, запосчу.
Время позднее, в общих чертах расскажу алгоритм для n^3.
Генеральный прямоугольник (для простоты n x n) будем рассматривать построчно сверху вниз.
1 Записываем высоты валидных для первой строки прямоугольников в ассоциативный контейнер, индексами которого являются левая и правая координаты прямоугольника, а значением - высота. Высота для первой строки это, конечно, единица. Каждая строка может содержать до n(n-1)/2 прямоугольников. Для простоты n^2. Время поиска этих прямоугольников в строке так же n^2. Для этого нужна одна маленькая простая хитрость. Думаю, о ней догадаетесь сами.
Для примера топика содержимое контейнера:
a[0,1] = 1
a[0,2] = 1
a[1,2] = 1
Время доступа к контейнеру константное.
Ссумируем высоты Sh = a[0,1] + a[0,2] + a[1,1] = 3.
Это можно делать совместно с поиском валидных прямоугольников.
2. Переходим на следущую строку. Так же ищем валидные прямоугольники, это займет у нас опять же n^2. Если прямоугольник с подобными индексами уже существует в нашем контейнере, приращиваем его высоту (на единицу), если не существует, - добавляем его с единичной высотой. На это нам потребуется так константное время.
В примере для второй строки:
a[0,2] += 1
Элементы контейнера которые существовали на прошлом шаге, но не текущем для них нет валидных прямоугольников, изымаются из контейнера. Для примера: a[0,1], a[1,1] изымаются, т.о. в контейнере остается только a[0,2] = 2.
На это нам потребуется линейное время благодаря специальной организации контейнера. Ничего сложного, попробуйте догадаться.
Добавляем к общей сумме высоты, получившиеся на этом шаге:
Sh += a[0,2] = 5.
Для этого требуется линейное время и может быть так же проделано совместно с приращением высот в контейнере.
3. Повторяем шаг 2 для оставшихся строк. Для примера у нас строк больше нет, поэтому ответ будет Sh = 5.
Т.о. для одной строки нам потребовалось в общем случае время пропорциональное n^2, всего строк n, сл-но общая сложность алгоритма O(n^3).
Дальнейшая наша оптимизация каснулась определению валидных прямоугольников в строке. Как выяснилось их можно обнаружить за время пропорциональное количеству таких прямоугольников в строке.
Об этом расскажу позднее.
[color=red]Кажется, в моё описание вкралась ошибочка. Завтра перепроверю.[/color]
Генеральный прямоугольник (для простоты n x n) будем рассматривать построчно сверху вниз.
1 Записываем высоты валидных для первой строки прямоугольников в ассоциативный контейнер, индексами которого являются левая и правая координаты прямоугольника, а значением - высота. Высота для первой строки это, конечно, единица. Каждая строка может содержать до n(n-1)/2 прямоугольников. Для простоты n^2. Время поиска этих прямоугольников в строке так же n^2. Для этого нужна одна маленькая простая хитрость. Думаю, о ней догадаетесь сами.
Для примера топика содержимое контейнера:
a[0,1] = 1
a[0,2] = 1
a[1,2] = 1
Время доступа к контейнеру константное.
Ссумируем высоты Sh = a[0,1] + a[0,2] + a[1,1] = 3.
Это можно делать совместно с поиском валидных прямоугольников.
2. Переходим на следущую строку. Так же ищем валидные прямоугольники, это займет у нас опять же n^2. Если прямоугольник с подобными индексами уже существует в нашем контейнере, приращиваем его высоту (на единицу), если не существует, - добавляем его с единичной высотой. На это нам потребуется так константное время.
В примере для второй строки:
a[0,2] += 1
Элементы контейнера которые существовали на прошлом шаге, но не текущем для них нет валидных прямоугольников, изымаются из контейнера. Для примера: a[0,1], a[1,1] изымаются, т.о. в контейнере остается только a[0,2] = 2.
На это нам потребуется линейное время благодаря специальной организации контейнера. Ничего сложного, попробуйте догадаться.
Добавляем к общей сумме высоты, получившиеся на этом шаге:
Sh += a[0,2] = 5.
Для этого требуется линейное время и может быть так же проделано совместно с приращением высот в контейнере.
3. Повторяем шаг 2 для оставшихся строк. Для примера у нас строк больше нет, поэтому ответ будет Sh = 5.
Т.о. для одной строки нам потребовалось в общем случае время пропорциональное n^2, всего строк n, сл-но общая сложность алгоритма O(n^3).
Дальнейшая наша оптимизация каснулась определению валидных прямоугольников в строке. Как выяснилось их можно обнаружить за время пропорциональное количеству таких прямоугольников в строке.
Об этом расскажу позднее.
[color=red]Кажется, в моё описание вкралась ошибочка. Завтра перепроверю.[/color]
[QUOTE=Green]Высота для первой строки это, конечно, единица.[/QUOTE]Ага. Так и сразу:
[QUOTE=Green] Каждая строка может содержать до n(n-1)/2 прямоугольников.[/QUOTE]
Если n*(n+1)/2, то совсем другое дело.
Дружеский совет: забей на эту задачу. :)
Код:
Код:
----
| |
---
n = 1; n*(n-1)/2 = 0; число прямоугольников = 1; 1!=0
-----
| | |
-----
n = 2; n*(n-1)/2 = 1; число прямоугольников = 3; 3!=1
-------
| | | |
-------
n = 3; n*(n-1)/2 = 3; число прямоугольников = 6; 6!=3
| |
---
n = 1; n*(n-1)/2 = 0; число прямоугольников = 1; 1!=0
-----
| | |
-----
n = 2; n*(n-1)/2 = 1; число прямоугольников = 3; 3!=1
-------
| | | |
-------
n = 3; n*(n-1)/2 = 3; число прямоугольников = 6; 6!=3
Если n*(n+1)/2, то совсем другое дело.
Дружеский совет: забей на эту задачу. :)
[QUOTE=Мerlin]Ага. Так и сразу:
[/QUOTE]
Читаем по-слогам:
"Записываем высоты валидных для первой строки прямоугольников"
"Высота для первой строки это, конечно, единица."
Вопрос: ты понимаешь, что значит валидный?
[QUOTE=Мerlin]
[/QUOTE]
n=2, т.к. n - кол-во вертикалей, если ты не заметил я оперирую именно линиями (индексами ребер), а не клетками.
Хочешь в клетках, элементарно, одно к другому приводиться:
n*(n+1)/2
Только O от этого не меняется...
Ты споришь с очевидными мелочами, а вот серьезной проблемы не видишь.
[QUOTE=Мerlin]
Дружеский совет: забей на эту задачу. :)[/QUOTE]
Дружеский совет: убери тот детский лепет, что ты привел чуть выше...
О... Да ты это уже сделал. Молодец.
Только вот и про "структуру данных" я бы тоже советовал убрать. :)
Теперь об ошибке, которая вкралась в объяснение. Изначально оперирование шло только ребрами и соотв-но основаниями прямоугольников. Далее я, как оказалось, ошибочно предположил, что можно сразу перейти к оперированию прямоугольниками, получаемых между горизонтальными линиями, не оперируя понятием база прямоугольника и прямоугольник нулевой высоты (это для первой линии, т.е. верхнего ребра генерального прямоугольника).
Надо бы перепроверить изначальный алгоритм, тогда и представлю.
Код:
-------
| | | |
| | | |
| | | |
-------
| | | |
| | | |
| | | |
-------
[/QUOTE]
Читаем по-слогам:
"Записываем высоты валидных для первой строки прямоугольников"
"Высота для первой строки это, конечно, единица."
Вопрос: ты понимаешь, что значит валидный?
[QUOTE=Мerlin]
Код:
---
| |
---
n = 1; n*(n-1)/2 = 0; число прямоугольников = 1; 1!=0
| |
---
n = 1; n*(n-1)/2 = 0; число прямоугольников = 1; 1!=0
[/QUOTE]
n=2, т.к. n - кол-во вертикалей, если ты не заметил я оперирую именно линиями (индексами ребер), а не клетками.
Хочешь в клетках, элементарно, одно к другому приводиться:
n*(n+1)/2
Только O от этого не меняется...
Ты споришь с очевидными мелочами, а вот серьезной проблемы не видишь.
[QUOTE=Мerlin]
Дружеский совет: забей на эту задачу. :)[/QUOTE]
Дружеский совет: убери тот детский лепет, что ты привел чуть выше...
О... Да ты это уже сделал. Молодец.
Только вот и про "структуру данных" я бы тоже советовал убрать. :)
Теперь об ошибке, которая вкралась в объяснение. Изначально оперирование шло только ребрами и соотв-но основаниями прямоугольников. Далее я, как оказалось, ошибочно предположил, что можно сразу перейти к оперированию прямоугольниками, получаемых между горизонтальными линиями, не оперируя понятием база прямоугольника и прямоугольник нулевой высоты (это для первой линии, т.е. верхнего ребра генерального прямоугольника).
Надо бы перепроверить изначальный алгоритм, тогда и представлю.
[QUOTE=Green]Читаем по-слогам:
"Записываем высоты валидных для первой строки прямоугольников"
"Высота для первой строки это, конечно, единица."
Вопрос: ты понимаешь, что значит валидный?[/QUOTE]valid == действительный? Я думал, ты под валидный подразумеваешь прямоугольник, который входит в результирующий набор. Напр. в моем понимании пример
содержит 6 валидных прямоугольников. Там нет прямоугольника с единичной высотой. У всех высота равна 3. Но если ты под валидной подразумеваешь любую ячейку, то пусть будет, первая строка имеет высоту 1, вторая строка имеет высоту 1 или 2? Если 2, то в чем информация в "Высота для первой строки это, конечно, единица."?
"Записываем высоты валидных для первой строки прямоугольников"
"Высота для первой строки это, конечно, единица."
Вопрос: ты понимаешь, что значит валидный?[/QUOTE]valid == действительный? Я думал, ты под валидный подразумеваешь прямоугольник, который входит в результирующий набор. Напр. в моем понимании пример
Код:
-------
| | | |
| | | |
| | | |
-------
| | | |
| | | |
| | | |
-------
Цитата:
n=2, т.к. n - кол-во вертикалей, если ты не заметил я оперирую именно линиями (индексами ребер), а не клетками.
"Мы тут посовещались (для упрощения обсуждения брали прямоугольник nxn) и придумали алгоритм n^3....",
"Генеральный прямоугольник (для простоты n x n) будем рассматривать построчно сверху вниз." где ты писал о ребрах?
Цитата:
Ты споришь с очевидными мелочами, а вот серьезной проблемы не видишь.
Так если у тебя мелочи не получаются, о каких серьезных вещах может идти речь?
Цитата:
Дружеский совет: убери тот детский лепет, что ты привел чуть выше...
О... Да ты это уже сделал. Молодец.
Только вот и про "структуру данных" я бы тоже советовал убрать. :)
О... Да ты это уже сделал. Молодец.
Только вот и про "структуру данных" я бы тоже советовал убрать. :)
Ok. Если оно тебе глаза колит, то убираю :)
Цитата:
Теперь об ошибке, которая вкралась в объяснение. Изначально оперирование шло только ребрами и соотв-но основаниями прямоугольников.
Основание прямоугольника содержит макс n ребр. Ты писал об n+1 ребрах.
Цитата:
Далее я, как оказалось, ошибочно предположил, что можно сразу перейти к оперированию прямоугольниками, получаемых между горизонтальными линиями, не оперируя понятием база прямоугольника и прямоугольник нулевой высоты (это для первой линии, т.е. верхнего ребра генерального прямоугольника).
Надо бы перепроверить изначальный алгоритм, тогда и представлю.
Надо бы перепроверить изначальный алгоритм, тогда и представлю.
Ok. Ждемс. :)
Я думаю решить ее гораздо проще методом исключений. Вначале выводим и применяем формулу S = N(n, m), которая вычисляет количество прямоугольников, если все перегородки цельные. Потом бежим по всем отсутствующим перегородкам и вычитаем из S количество прямоугольников, которые данная перегородка "обламывает" (т.е. инвалидит).
Вообще это просто первая мысль которая пришла мне на ум, когда я прочел задачу. Я ее не решал. Может это дельная мысль. Проверьте.
Наверное данный подхот оправдывается, если "инвалидных" перегородок мало.
Вообще это просто первая мысль которая пришла мне на ум, когда я прочел задачу. Я ее не решал. Может это дельная мысль. Проверьте.
Наверное данный подхот оправдывается, если "инвалидных" перегородок мало.
[QUOTE=Мerlin]
то в чем информация в "Высота для первой строки это, конечно, единица."?
[/QUOTE]
Трудно объяснить, т.к. ты не понял контекста и пытаешься понять (а может и не пытаешься) вне контекста.
[QUOTE=Мerlin]
"Мы тут посовещались (для упрощения обсуждения брали прямоугольник nxn) и придумали алгоритм n^3....",
"Генеральный прямоугольник (для простоты n x n) будем рассматривать построчно сверху вниз." где ты писал о ребрах?
<skip>
Основание прямоугольника содержит макс n ребр. Ты писал об n+1 ребрах.
[/QUOTE]
Да какая разница в ребрах (вертикальных линиях) или клетках?
Ты понимаешь, что есть O ?
Т.е. фраза " Каждая строка может содержать до n(n-1)/2 прямоугольников. Для простоты n^2." тебя не смутила? Тебя не смутило, что я упростил (n-1) до n, выкинул /2? Но тебя ужастно смутило, что клеток всегда на ОДНУ меньше, чем линий. :)
то в чем информация в "Высота для первой строки это, конечно, единица."?
[/QUOTE]
Трудно объяснить, т.к. ты не понял контекста и пытаешься понять (а может и не пытаешься) вне контекста.
[QUOTE=Мerlin]
"Мы тут посовещались (для упрощения обсуждения брали прямоугольник nxn) и придумали алгоритм n^3....",
"Генеральный прямоугольник (для простоты n x n) будем рассматривать построчно сверху вниз." где ты писал о ребрах?
<skip>
Основание прямоугольника содержит макс n ребр. Ты писал об n+1 ребрах.
[/QUOTE]
Да какая разница в ребрах (вертикальных линиях) или клетках?
Ты понимаешь, что есть O ?
Т.е. фраза " Каждая строка может содержать до n(n-1)/2 прямоугольников. Для простоты n^2." тебя не смутила? Тебя не смутило, что я упростил (n-1) до n, выкинул /2? Но тебя ужастно смутило, что клеток всегда на ОДНУ меньше, чем линий. :)
[QUOTE=Green]Трудно объяснить, т.к. ты не понял контекста и пытаешься понять (а может и не пытаешься) вне контекста.
Да какая разница в ребрах (вертикальных линиях) или клетках?
Ты понимаешь, что есть O ?
Т.е. фраза " Каждая строка может содержать до n(n-1)/2 прямоугольников. Для простоты n^2." тебя не смутила? Тебя не смутило, что я упростил (n-1) до n, выкинул /2? Но тебя ужастно смутило, что клеток всегда на ОДНУ меньше, чем линий. :)[/QUOTE]А ты не нервничай!!! :)
Меня смутило, только одно: "...Для этого нужна одна маленькая простая хитрость. Думаю, о ней догадаетесь сами...На это нам потребуется линейное время благодаря специальной организации контейнера. Ничего сложного, попробуйте догадаться...Дальнейшая наша оптимизация каснулась определению валидных прямоугольников в строке. Как выяснилось их можно обнаружить за время пропорциональное количеству таких прямоугольников в строке.
Об этом расскажу позднее." И все это "ах, какие мы умные", закончилось тем, что : [color=red]"Кажется, в моё описание вкралась ошибочка. Завтра перепроверю."[/color]. :)
В твоем алгоритме, если я правильно понял, основная проблема, что так называемые валидные многоуголники перекрываются, или же могут перекрыться.
Да какая разница в ребрах (вертикальных линиях) или клетках?
Ты понимаешь, что есть O ?
Т.е. фраза " Каждая строка может содержать до n(n-1)/2 прямоугольников. Для простоты n^2." тебя не смутила? Тебя не смутило, что я упростил (n-1) до n, выкинул /2? Но тебя ужастно смутило, что клеток всегда на ОДНУ меньше, чем линий. :)[/QUOTE]А ты не нервничай!!! :)
Меня смутило, только одно: "...Для этого нужна одна маленькая простая хитрость. Думаю, о ней догадаетесь сами...На это нам потребуется линейное время благодаря специальной организации контейнера. Ничего сложного, попробуйте догадаться...Дальнейшая наша оптимизация каснулась определению валидных прямоугольников в строке. Как выяснилось их можно обнаружить за время пропорциональное количеству таких прямоугольников в строке.
Об этом расскажу позднее." И все это "ах, какие мы умные", закончилось тем, что : [color=red]"Кажется, в моё описание вкралась ошибочка. Завтра перепроверю."[/color]. :)
В твоем алгоритме, если я правильно понял, основная проблема, что так называемые валидные многоуголники перекрываются, или же могут перекрыться.
[QUOTE=Aumn]
Я думаю решить ее гораздо проще методом исключений.
[/QUOTE]
Метод исключений уже предлагался, точнее исключений-включений.
Но он очень неоптимален, его имеет смысл использовать только при очень малом количистве отсутствующих ребер.
[QUOTE=Мerlin]
А ты не нервничай!!!
[/QUOTE]
А я не нервничаю. ты даже представить себе не можешь как это страшно, когда я нервничаю. И, кстати, переставай уже пытаться угадать мои эмоции, это совершенно не имеет смысла, т.к. они открыты - меня это прикалывает.
[QUOTE=Мerlin]
Меня смутило, только одно:
И все это "ах, какие мы умные", закончилось тем, что : "Кажется, в моё описание вкралась ошибочка. Завтра перепроверю."
[/QUOTE]
Ущемленное самолюбие на пару с язвительностью? Кто-то показался умнее тебя... Да ты не нервничай.
Довольно низко говорить человеку, который к примеру оговорился: "а я заметил, ты не правильно произнес это слово! Ага, я тебя разоблачил, ты не умнее меня!"
Тем более, что ты ошибки в моем повествовании не нашел, да и не узнал бы о её существовании, если бы я (заметь!) честно и красным по белому это не указал.
Кстати, ДА, мы ТАКИЕ умные... Других у нас не держат. :D
Теперь вернемся к теме.
Я тут придумал, как проще объяснить метод с O(n^3).
Просматриваем все варианты вертикальных столбцов всех возможных ширин (какое слово дурацкое). Их у нас пропорционально n^2 (специально для Мerlin: n*(n+1)/2, где n - ширина в клетках).
Типичный шаг для строки:
1. Смотрим наличие левого и правого ребра. Если хотябы одно отсутствует, сбрасываем счетчик высоты (h=0).
2. Смотрим наличие нижнего ребра. Если оно есть увеличиваем общую сумму на значение счетчика высоты (S=S+h), инкрементируем счетчик высоты (h=h+1).
3. Переходим к следующей строке.
Для каждого столбца перебор займет линейное время (размер по вертикали), всего столбцов у нас, как уже говорилось, пропорционально n^2, т.о. общее время пропорционально n^3.
Процесс обработки столбца начинаем с мнимой строки (строка 0) находящейся за пределами генерального прямоугольника. Вне генерального прямоугольника вертикальных ребер нет. Это сделано лишь для инициализации.
Пример:
Более сложный пример:
Я думаю решить ее гораздо проще методом исключений.
[/QUOTE]
Метод исключений уже предлагался, точнее исключений-включений.
Но он очень неоптимален, его имеет смысл использовать только при очень малом количистве отсутствующих ребер.
[QUOTE=Мerlin]
А ты не нервничай!!!
[/QUOTE]
А я не нервничаю. ты даже представить себе не можешь как это страшно, когда я нервничаю. И, кстати, переставай уже пытаться угадать мои эмоции, это совершенно не имеет смысла, т.к. они открыты - меня это прикалывает.
[QUOTE=Мerlin]
Меня смутило, только одно:
И все это "ах, какие мы умные", закончилось тем, что : "Кажется, в моё описание вкралась ошибочка. Завтра перепроверю."
[/QUOTE]
Ущемленное самолюбие на пару с язвительностью? Кто-то показался умнее тебя... Да ты не нервничай.
Довольно низко говорить человеку, который к примеру оговорился: "а я заметил, ты не правильно произнес это слово! Ага, я тебя разоблачил, ты не умнее меня!"
Тем более, что ты ошибки в моем повествовании не нашел, да и не узнал бы о её существовании, если бы я (заметь!) честно и красным по белому это не указал.
Кстати, ДА, мы ТАКИЕ умные... Других у нас не держат. :D
Теперь вернемся к теме.
Я тут придумал, как проще объяснить метод с O(n^3).
Просматриваем все варианты вертикальных столбцов всех возможных ширин (какое слово дурацкое). Их у нас пропорционально n^2 (специально для Мerlin: n*(n+1)/2, где n - ширина в клетках).
Типичный шаг для строки:
1. Смотрим наличие левого и правого ребра. Если хотябы одно отсутствует, сбрасываем счетчик высоты (h=0).
2. Смотрим наличие нижнего ребра. Если оно есть увеличиваем общую сумму на значение счетчика высоты (S=S+h), инкрементируем счетчик высоты (h=h+1).
3. Переходим к следующей строке.
Для каждого столбца перебор займет линейное время (размер по вертикали), всего столбцов у нас, как уже говорилось, пропорционально n^2, т.о. общее время пропорционально n^3.
Процесс обработки столбца начинаем с мнимой строки (строка 0) находящейся за пределами генерального прямоугольника. Вне генерального прямоугольника вертикальных ребер нет. Это сделано лишь для инициализации.
Пример:
Код:
-------
| | | |
| | | |
| | | |
-------
Количество столбцов: n(n+1) = 3(3+1) = 6.
Для первого столбца (0-1 - это индексы вертикальных ребер):
S=0
строка 0: ребрер нет (вне прямоугольника) - сбрасываем h=0; нижнее ребро есть - S=S+h=0+0=0, h=0+1=1.
строка 1: ребра есть, нижнего ребра нет - счетчик не меняем (h=0), общую сумму так же (S=0).
строка 2: ребра есть, нижнего ребра нет, - счетчик не меняем (h=0), общую сумму так же (S=0).
строка 3: ребра есть, нижнее ребро есть, - общую сумму обновляем S=0+1=1, счетчик инкрементируем h=1+1=2 (но это уже не важно).
И т.д. В результате S=6 (т.к. столбцов 6 и во всех процесс идентичен).
| | | |
| | | |
| | | |
-------
Количество столбцов: n(n+1) = 3(3+1) = 6.
Для первого столбца (0-1 - это индексы вертикальных ребер):
S=0
строка 0: ребрер нет (вне прямоугольника) - сбрасываем h=0; нижнее ребро есть - S=S+h=0+0=0, h=0+1=1.
строка 1: ребра есть, нижнего ребра нет - счетчик не меняем (h=0), общую сумму так же (S=0).
строка 2: ребра есть, нижнего ребра нет, - счетчик не меняем (h=0), общую сумму так же (S=0).
строка 3: ребра есть, нижнее ребро есть, - общую сумму обновляем S=0+1=1, счетчик инкрементируем h=1+1=2 (но это уже не важно).
И т.д. В результате S=6 (т.к. столбцов 6 и во всех процесс идентичен).
Более сложный пример:
Код:
______
|_|_ |
|_| |_|
|_|_|_|
Количество столбцов: n(n+1) = 3(3+1) = 6.
Для первого столбца (0-1):
(S=0)
строка 0: ребрер нет (вне прямоугольника) - сбрасываем h=0; нижнее ребро есть - S=S+h=0+0=0, h=0+1=1.
строка 1: ребра есть, нижнее ребро есть, - общую сумму обновляем S=0+1=1, счетчик инкрементируем h=1+1=2.
строка 2: ребра есть, нижнее ребро есть, - общую сумму обновляем S=1+2=3, счетчик инкрементируем h=2+1=3.
строка 3: ребра есть, нижнее ребро есть, - общую сумму обновляем S=3+3=6, счетчик инкрементируем h=3+1=4.
строка 3: ребра есть, основания есть, h=3, S=3+3=6;
Для второго столбца (1-2):
(S=6)
строка 0: ребрер нет (вне прямоугольника) - сбрасываем h=0; нижнее ребро есть - S=S+h=6+0=6, h=0+1=1.
строка 1: одного ребра нет - сбрасываем h=0; нижнее ребро есть - S=S+h=6+0=6, h=0+1=1.
строка 2: ребра есть, нижнего ребра нет, - ничего не обновляем (h=1, S=6).
строка 3: ребра есть, нижнее ребро есть, - общую сумму обновляем S=6+1=7, счетчик инкрементируем h=1+1=2.
Для третьего столбца (2-3):
(S=7)
строка 0: ребрер нет (вне прямоугольника) - сбрасываем h=0; нижнее ребро есть - S=S+h=7+0=7, h=0+1=1.
строка 1: одного ребра нет - сбрасываем h=0; нижнего ребра нет, - ничего не обновляем (h=0, S=7).
строка 2: ребра есть, нижнее ребро есть, - общую сумму обновляем S=7+0=7, счетчик инкрементируем h=0+1=1.
строка 3: ребра есть, нижнее ребро есть, - общую сумму обновляем S=7+1=8, счетчик инкрементируем h=1+1=2.
И т.д. для остальных столбцов: (0-2), (0-3), (1-3).
|_|_ |
|_| |_|
|_|_|_|
Количество столбцов: n(n+1) = 3(3+1) = 6.
Для первого столбца (0-1):
(S=0)
строка 0: ребрер нет (вне прямоугольника) - сбрасываем h=0; нижнее ребро есть - S=S+h=0+0=0, h=0+1=1.
строка 1: ребра есть, нижнее ребро есть, - общую сумму обновляем S=0+1=1, счетчик инкрементируем h=1+1=2.
строка 2: ребра есть, нижнее ребро есть, - общую сумму обновляем S=1+2=3, счетчик инкрементируем h=2+1=3.
строка 3: ребра есть, нижнее ребро есть, - общую сумму обновляем S=3+3=6, счетчик инкрементируем h=3+1=4.
строка 3: ребра есть, основания есть, h=3, S=3+3=6;
Для второго столбца (1-2):
(S=6)
строка 0: ребрер нет (вне прямоугольника) - сбрасываем h=0; нижнее ребро есть - S=S+h=6+0=6, h=0+1=1.
строка 1: одного ребра нет - сбрасываем h=0; нижнее ребро есть - S=S+h=6+0=6, h=0+1=1.
строка 2: ребра есть, нижнего ребра нет, - ничего не обновляем (h=1, S=6).
строка 3: ребра есть, нижнее ребро есть, - общую сумму обновляем S=6+1=7, счетчик инкрементируем h=1+1=2.
Для третьего столбца (2-3):
(S=7)
строка 0: ребрер нет (вне прямоугольника) - сбрасываем h=0; нижнее ребро есть - S=S+h=7+0=7, h=0+1=1.
строка 1: одного ребра нет - сбрасываем h=0; нижнего ребра нет, - ничего не обновляем (h=0, S=7).
строка 2: ребра есть, нижнее ребро есть, - общую сумму обновляем S=7+0=7, счетчик инкрементируем h=0+1=1.
строка 3: ребра есть, нижнее ребро есть, - общую сумму обновляем S=7+1=8, счетчик инкрементируем h=1+1=2.
И т.д. для остальных столбцов: (0-2), (0-3), (1-3).
[QUOTE=Green]Ущемленное самолюбие на пару с язвительностью? Кто-то показался умнее тебя... Да ты не нервничай.
Довольно низко говорить человеку, который к примеру оговорился: "а я заметил, ты не правильно произнес это слово! Ага, я тебя разоблачил, ты не умнее меня!"[/QUOTE]1. Выложил алгоритм, который был неправильный, и ты уже считаешь себя умнее других? :)
2. (главное) На таких форумах, реальные программисты в принципе не могут оказаться умнее друг от друга. Здесь же решаются за 5 - 10 -15 минут микропроблемы, в основном заданные студентами. Если пишется код, то макс. 20-30 операторов, а реальное приложение, это несколько сот операторов(если идет речь о Visual C). Из того что кто-то эффектно поднимает 2 кг, еще не следует, что он так же эффектно справится и с 200 кг.
На счет алгоритма выше, ты в его сложности крупно ошибся. Он даже не n^4.
Довольно низко говорить человеку, который к примеру оговорился: "а я заметил, ты не правильно произнес это слово! Ага, я тебя разоблачил, ты не умнее меня!"[/QUOTE]1. Выложил алгоритм, который был неправильный, и ты уже считаешь себя умнее других? :)
2. (главное) На таких форумах, реальные программисты в принципе не могут оказаться умнее друг от друга. Здесь же решаются за 5 - 10 -15 минут микропроблемы, в основном заданные студентами. Если пишется код, то макс. 20-30 операторов, а реальное приложение, это несколько сот операторов(если идет речь о Visual C). Из того что кто-то эффектно поднимает 2 кг, еще не следует, что он так же эффектно справится и с 200 кг.
На счет алгоритма выше, ты в его сложности крупно ошибся. Он даже не n^4.
[QUOTE=Мerlin]1. Выложил алгоритм, который был неправильный, и ты уже считаешь себя умнее других? :).[/QUOTE]
Успокой своё самолюбие: "умный" и "умнее других" - разные понятия.
Ты вроде бы тоже привел алгоритм, но не неправильный, а бестолковый. Потом, побоялся критики и убрал. Я критики не боюсь, алгоритм первый частично работоспособный, второй - полностью работоспособный.
[QUOTE=Мerlin]
<лирика пропущена>
На счет алгоритма выше, ты в его сложности крупно ошибся. Он даже не n^4.[/QUOTE]
А ты докажи, а то пока это пустые слова. :)
Только учти, что это как игра в шахматы, я примерно знаю твои ходы, а ты догадываешься о моих?
Я показал, что это n^3, нужны ещё доказательства? :)
Успокой своё самолюбие: "умный" и "умнее других" - разные понятия.
Ты вроде бы тоже привел алгоритм, но не неправильный, а бестолковый. Потом, побоялся критики и убрал. Я критики не боюсь, алгоритм первый частично работоспособный, второй - полностью работоспособный.
[QUOTE=Мerlin]
<лирика пропущена>
На счет алгоритма выше, ты в его сложности крупно ошибся. Он даже не n^4.[/QUOTE]
А ты докажи, а то пока это пустые слова. :)
Только учти, что это как игра в шахматы, я примерно знаю твои ходы, а ты догадываешься о моих?
Я показал, что это n^3, нужны ещё доказательства? :)
Алгоритм убрал, не потому что, он неправильный, а потому что я не вполне уверенный, что он имеет сложность n^2. (вроде идет речь о таком алгоритме).
В твоем алгоритме ты не учел, что столбцы перекрываются.
При n = 6 проверяется 56 столбцов, а не 36
При n = 10 доп. 220 столбцов. (вместо 100)
При n = 20 доп. 1540 столбцов. (вместо 400)
сложность, где-то между ln(n)*n^3 < O(n) < n^4
но в любом случае не n^3.
[Quote=Green]Только учти, что это как игра в шахматы, я примерно знаю твои ходы, а ты догадываешься о моих?[/quote]А это уже врятли. Ты мне больше напоминаешь Тощего Пита, чем мистера Грина. :)
В твоем алгоритме ты не учел, что столбцы перекрываются.
При n = 6 проверяется 56 столбцов, а не 36
При n = 10 доп. 220 столбцов. (вместо 100)
При n = 20 доп. 1540 столбцов. (вместо 400)
сложность, где-то между ln(n)*n^3 < O(n) < n^4
но в любом случае не n^3.
[Quote=Green]Только учти, что это как игра в шахматы, я примерно знаю твои ходы, а ты догадываешься о моих?[/quote]А это уже врятли. Ты мне больше напоминаешь Тощего Пита, чем мистера Грина. :)
[QUOTE=Мerlin]Алгоритм убрал, не потому что, он неправильный, а потому что я не вполне уверенный, что он имеет сложность n^2. (вроде идет речь о таком алгоритме).
[/QUOTE]
Так он был верный, но не очень быстрый? :D
Тогда верни его, я проверю его верность. Скорость оставим на потом. :)
[QUOTE=Мerlin]
В твоем алгоритме ты не учел, что столбцы перекрываются.
[/QUOTE]
Я то учел... просто ты считать не умеешь.
[QUOTE=Мerlin]
При n = 6 проверяется 56 столбцов, а не 36
При n = 10 доп. 220 столбцов. (вместо 100)
При n = 20 доп. 1540 столбцов. (вместо 400)
сложность, где-то между ln(n)*n^3 < O(n) < n^4
но в любом случае не n^3.
[/QUOTE]
Это с какого бодуна? :)
Любой школьник скажет, что сумма арифметической прогрессии равна n*(n+1)/2. Поэтому:
При n = 6 проверяется 21 столбец, а не 56
При n = 10 проверяется 55 столбцов, а не "доп. 220 столбцов".
При n = 20 проверяется 210 столбцов, а не "доп. 1540 столбцов".
Поэтому перебор столбцов квадратичной сложности, а общая с ложность с учетом переборов строк в каждом столбце имеет кубическую сложность.
Я так и не увидел опровержения. Если не можешь объяснить, то покажи графически, где ты нашел 56 столбцов при n=6. :)
[/QUOTE]
Так он был верный, но не очень быстрый? :D
Тогда верни его, я проверю его верность. Скорость оставим на потом. :)
[QUOTE=Мerlin]
В твоем алгоритме ты не учел, что столбцы перекрываются.
[/QUOTE]
Я то учел... просто ты считать не умеешь.
[QUOTE=Мerlin]
При n = 6 проверяется 56 столбцов, а не 36
При n = 10 доп. 220 столбцов. (вместо 100)
При n = 20 доп. 1540 столбцов. (вместо 400)
сложность, где-то между ln(n)*n^3 < O(n) < n^4
но в любом случае не n^3.
[/QUOTE]
Это с какого бодуна? :)
Любой школьник скажет, что сумма арифметической прогрессии равна n*(n+1)/2. Поэтому:
При n = 6 проверяется 21 столбец, а не 56
При n = 10 проверяется 55 столбцов, а не "доп. 220 столбцов".
При n = 20 проверяется 210 столбцов, а не "доп. 1540 столбцов".
Поэтому перебор столбцов квадратичной сложности, а общая с ложность с учетом переборов строк в каждом столбце имеет кубическую сложность.
Я так и не увидел опровержения. Если не можешь объяснить, то покажи графически, где ты нашел 56 столбцов при n=6. :)
Нумерация по ребрям.
Первый проход. Поиск прямоугольников имеющие ширину = 1.
0-1, 1-2, 2-3, 3-4, 4-5, 5-6 = 6 столбцов.
Второй проход. Поиск прямоугольников имеющие ширину = 2.
0-2, 1-3, 2-4, 3-5, 4-6 = 10 столбцов
Третий проход. Поиск прямоугольников имеющие ширину = 3.
0-3, 1-4, 2-5, 3-6 = 12 столбцов
Четвертый проход. Поиск прямоугольников имеющие ширину = 4.
0-4, 1-5, 2-6 = 12 столбцов
Пятый проход
0-5, 1-6 = 10 столбцов
Шестой проход
0-6 = 6 столбцов
6+10+12+12+10+6 = 56.
1. Это не я не могу объяснить, а просто до тебя трудно доходит. :)
2. Я умею считать, но ты, как пример показывает, не очень... :)
Первый проход. Поиск прямоугольников имеющие ширину = 1.
0-1, 1-2, 2-3, 3-4, 4-5, 5-6 = 6 столбцов.
Второй проход. Поиск прямоугольников имеющие ширину = 2.
0-2, 1-3, 2-4, 3-5, 4-6 = 10 столбцов
Третий проход. Поиск прямоугольников имеющие ширину = 3.
0-3, 1-4, 2-5, 3-6 = 12 столбцов
Четвертый проход. Поиск прямоугольников имеющие ширину = 4.
0-4, 1-5, 2-6 = 12 столбцов
Пятый проход
0-5, 1-6 = 10 столбцов
Шестой проход
0-6 = 6 столбцов
6+10+12+12+10+6 = 56.
1. Это не я не могу объяснить, а просто до тебя трудно доходит. :)
2. Я умею считать, но ты, как пример показывает, не очень... :)
[QUOTE=Green]Если решать "напролом", т.е. перебором, то сложность составляет (m*n)^2, что в подавляющем случае лучше, чем 2^k.
[/QUOTE]
Действительно, когда я писал, что прямой перебор занимает время порядка O (2^(m*n)), я ошибался. Время порядка O ((m*n)^2), а точнее даже, O ((m*n)^2 * log2 k). Однако, ты неправ насчет выгодности (m*n)^2. Как правило, количество "сломанных" стенок k намного меньше m*n; даже если оно сравнимо с этим числом, в некоторых случаях можно уменьшить n или m и одновременно k, ведь если в двухэтажном здании нет ни одного пола-потолка между этажами, здание можно считать одноэтажным. Но это уже задача дополнительной оптимизации изначального метода включений-исключений. Можно выдвинуть даже такое предложение: сама программа должна предварительно оценить сложность вычисления моим методом и методом, предложенным Green'ом, и выбрать наиболее выгодный вариант для данного конкретного случая.
[/QUOTE]
Действительно, когда я писал, что прямой перебор занимает время порядка O (2^(m*n)), я ошибался. Время порядка O ((m*n)^2), а точнее даже, O ((m*n)^2 * log2 k). Однако, ты неправ насчет выгодности (m*n)^2. Как правило, количество "сломанных" стенок k намного меньше m*n; даже если оно сравнимо с этим числом, в некоторых случаях можно уменьшить n или m и одновременно k, ведь если в двухэтажном здании нет ни одного пола-потолка между этажами, здание можно считать одноэтажным. Но это уже задача дополнительной оптимизации изначального метода включений-исключений. Можно выдвинуть даже такое предложение: сама программа должна предварительно оценить сложность вычисления моим методом и методом, предложенным Green'ом, и выбрать наиболее выгодный вариант для данного конкретного случая.
А вообще, я очень рад, что тема вызвала такое бурное обсуждение. Не ожидал. Жаль только, что 50% текста занимают взаимные упрёки...
[QUOTE=Мerlin]Нумерация по ребрям.
Первый проход. Поиск прямоугольников имеющие ширину = 1.
0-1, 1-2, 2-3, 3-4, 4-5, 5-6 = 6 столбцов.
Второй проход. Поиск прямоугольников имеющие ширину = 2.
0-2, 1-3, 2-4, 3-5, 4-6 = 10 столбцов
Третий проход. Поиск прямоугольников имеющие ширину = 3.
0-3, 1-4, 2-5, 3-6 = 12 столбцов
Четвертый проход. Поиск прямоугольников имеющие ширину = 4.
0-4, 1-5, 2-6 = 12 столбцов
Пятый проход
0-5, 1-6 = 10 столбцов
Шестой проход
0-6 = 6 столбцов
6+10+12+12+10+6 = 56.
1. Это не я не могу объяснить, а просто до тебя трудно доходит.
2. Я умею считать, но ты, как пример показывает, не очень...[/QUOTE]
Ну чтож... давай считать на пальцах... :)
Берем твоё утверждение:
"0-2, 1-3, 2-4, 3-5, 4-6 = 10 столбцов"
считаем:
0-2 - раз!
1-3 - два!
2-4 - три!
3-5 - четыре!
4-6 - пять!
Где ты нашел десять? :D
Берем твоё утверждение:
"0-3, 1-4, 2-5, 3-6 = 12 столбцов"
считаем:
0-3 - раз!
1-4 - два!
2-5 - три!
3-6 - четыре!
Где ты нашел двенадцать? :D
Для всех остальных вариантов теперь уже сам посчитаешь?
Первый проход. Поиск прямоугольников имеющие ширину = 1.
0-1, 1-2, 2-3, 3-4, 4-5, 5-6 = 6 столбцов.
Второй проход. Поиск прямоугольников имеющие ширину = 2.
0-2, 1-3, 2-4, 3-5, 4-6 = 10 столбцов
Третий проход. Поиск прямоугольников имеющие ширину = 3.
0-3, 1-4, 2-5, 3-6 = 12 столбцов
Четвертый проход. Поиск прямоугольников имеющие ширину = 4.
0-4, 1-5, 2-6 = 12 столбцов
Пятый проход
0-5, 1-6 = 10 столбцов
Шестой проход
0-6 = 6 столбцов
6+10+12+12+10+6 = 56.
1. Это не я не могу объяснить, а просто до тебя трудно доходит.
2. Я умею считать, но ты, как пример показывает, не очень...[/QUOTE]
Ну чтож... давай считать на пальцах... :)
Берем твоё утверждение:
"0-2, 1-3, 2-4, 3-5, 4-6 = 10 столбцов"
считаем:
0-2 - раз!
1-3 - два!
2-4 - три!
3-5 - четыре!
4-6 - пять!
Где ты нашел десять? :D
Берем твоё утверждение:
"0-3, 1-4, 2-5, 3-6 = 12 столбцов"
считаем:
0-3 - раз!
1-4 - два!
2-5 - три!
3-6 - четыре!
Где ты нашел двенадцать? :D
Для всех остальных вариантов теперь уже сам посчитаешь?
[QUOTE=cheburator]Действительно, когда я писал, что прямой перебор занимает время порядка O (2^(m*n)), я ошибался. Время порядка O ((m*n)^2), а точнее даже, O ((m*n)^2 * log2 k). Однако, ты неправ насчет выгодности (m*n)^2. Как правило, количество "сломанных" стенок k намного меньше m*n; даже если оно сравнимо с этим числом, в некоторых случаях можно уменьшить n или m и одновременно k, ведь если в двухэтажном здании нет ни одного пола-потолка между этажами, здание можно считать одноэтажным. Но это уже задача дополнительной оптимизации изначального метода включений-исключений. Можно выдвинуть даже такое предложение: сама программа должна предварительно оценить сложность вычисления моим методом и методом, предложенным Green'ом, и выбрать наиболее выгодный вариант для данного конкретного случая.[/QUOTE]
Подожди, ты сам себе противоречишь.
Ты говоришь, что (m*n)^2 * log2(k) быстрее, чем (m*n)^2 ?
Давай решим простейшее неравенство:
(m*n)^2 * log2(k) < (m*n)^2
log2(k) < 1
k < 2
т.е. твоё утверждение верно лишь для k=1 и k=0;
Если же сравнивать твой и мой алгоритм, то
(m*n)^2 * log2(k) < (m*n)*n
(m*n) * log2(k) < n
m*log2(k) < 1
т.е. твоё утверждение опять верно лишь для k=1 и k=0.
Подожди, ты сам себе противоречишь.
Ты говоришь, что (m*n)^2 * log2(k) быстрее, чем (m*n)^2 ?
Давай решим простейшее неравенство:
(m*n)^2 * log2(k) < (m*n)^2
log2(k) < 1
k < 2
т.е. твоё утверждение верно лишь для k=1 и k=0;
Если же сравнивать твой и мой алгоритм, то
(m*n)^2 * log2(k) < (m*n)*n
(m*n) * log2(k) < n
m*log2(k) < 1
т.е. твоё утверждение опять верно лишь для k=1 и k=0.
[QUOTE=Green]Ну чтож... давай считать на пальцах... :)
Берем твоё утверждение:
"0-2, 1-3, 2-4, 3-5, 4-6 = 10 столбцов"
считаем:
0-2 - раз!
1-3 - два!
2-4 - три!
3-5 - четыре!
4-6 - пять!
Где ты нашел десять? :D
[/QUOTE]Мда...
Мне кажется тебе плохо объяснили принцип работы этого алгоритма.
Точнее, как смотрю приведенный тобой пример, объяснили только для прямоугольников имеющие ширину в 1 столбец. :D
Берем твоё утверждение:
"0-2, 1-3, 2-4, 3-5, 4-6 = 10 столбцов"
считаем:
0-2 - раз!
1-3 - два!
2-4 - три!
3-5 - четыре!
4-6 - пять!
Где ты нашел десять? :D
[/QUOTE]Мда...
Мне кажется тебе плохо объяснили принцип работы этого алгоритма.
Точнее, как смотрю приведенный тобой пример, объяснили только для прямоугольников имеющие ширину в 1 столбец. :D
Мне объяснили? Это я объясняю. Только не все в состоянии понять.
Ну и сколько столбцов ширины 2 у тебя получилось на картинке? Десять, как ты утверждаешь?
Я привел пример со столбцом единичной ширины, тебе сложно спроецировать его на столбец ширины два? :D
Возможно там есть маааааленькая хитрость, но она на столько мала, что я думал, ты сам догадаешься (опять же по аналогии). Видимо, я в тебе ошибался...
Ну и сколько столбцов ширины 2 у тебя получилось на картинке? Десять, как ты утверждаешь?
Я привел пример со столбцом единичной ширины, тебе сложно спроецировать его на столбец ширины два? :D
Возможно там есть маааааленькая хитрость, но она на столько мала, что я думал, ты сам догадаешься (опять же по аналогии). Видимо, я в тебе ошибался...
Я исходил из того алгоритма, что ты написал.
Есть хитрость, если проверять в перемешку, т.е.
0-1,0-2,0-3,0-4,0-5,0-6
1-2,1-3,1-4,1-5,1-6
тогда будет в худшем cлучае n^2(столбцов), но ты описал
не такой алгоритм.
Есть хитрость, если проверять в перемешку, т.е.
0-1,0-2,0-3,0-4,0-5,0-6
1-2,1-3,1-4,1-5,1-6
тогда будет в худшем cлучае n^2(столбцов), но ты описал
не такой алгоритм.
Извини, но ты тупишь.
Просто надо перебрать все столбцы всевозможной ширины.
Мой алгоритм четко все описывает. Зачем в перемешку? В перемешку чего?
Хитрость не в этом, но тебе до неё ещё далеко. Ты даже ещё не увидел проблемы, которая решается с помощью некоторой маааленькой хитрости.
Просто надо перебрать все столбцы всевозможной ширины.
Мой алгоритм четко все описывает. Зачем в перемешку? В перемешку чего?
Хитрость не в этом, но тебе до неё ещё далеко. Ты даже ещё не увидел проблемы, которая решается с помощью некоторой маааленькой хитрости.
[QUOTE=Green]Подожди, ты сам себе противоречишь.
Ты говоришь, что (m*n)^2 * log2(k) быстрее, чем (m*n)^2 ?
[/QUOTE]
Не-а. Я про O ((m*n)^2 * log2 k) и мою версию: O (2^k).
Ты говоришь, что (m*n)^2 * log2(k) быстрее, чем (m*n)^2 ?
[/QUOTE]
Не-а. Я про O ((m*n)^2 * log2 k) и мою версию: O (2^k).
И ещё. Специально для тех, кто не совсем понимает, что за символ O. Выдержка из матана:
Пусть даны две функции f и g. Если f(x) можно представить в виде h(x)*g(x), где h(x) - ограниченная функция, т. е. существует константа C такая, что
|h(x)| <= C,
то функцию f называют ограниченной относительно g и пишут
f(x) = O(g(x)).
Если одновременно
f(x) = O(g(x)) и
g(x) = O(f(x)),
то говорят, что функции f и g одного порядка: f(x) ~ g(x). Можно доказать, что тогда f(x) представима в виде h(x)*g(x), где h(x) удовлетворяет условию: найдутся две константы C1 и C2 обе строго больше нуля, такие, что
C1 <= |h(x)| <= C2.
То же верно и для g(x) (она представима в виде q(x)f(x) и существуют D1 и D2 такие, что D1 <= |q(x)| <= D2; D1 > 0; D2 > 0).
Программисты, как правило, сталкиваются с задачей оценки алгоритмической сложности. Здесь функция - это время выполнения программы в неких условных единицах времени или операциях. Параметром, как правило, является объём входных данных (время выполнения некоторых алгоритмов зависит не только от объёма входных данных, но и от самих данных; в этом случае оценка сложности алгоритма значительно усложняется). Очевидно, объём входных данных - целое число, т. е. наша функция определена на множестве целых неотрицательных чисел.
Естественно, точно описать зависимость f(n) времени выполнения программы от объёма входных данных нельзя, поскольку время выполнения будет отличаться хотя бы для разных по быстродействию процессоров. Но можно оценить эту функцию с помощью понятий "ограниченная относительно g(n)" и "того же порядка, что g(n)", указав эту оценочную функцию g(n). При этом, как указано выше, мы показываем, что наша неизвестная функция f(n) ограничена сверху какой-то функцией (если f(n) = O(g(n))), или снизу (если g(n) = O(f(n))), или сверху и снизу (если f(n) ~g(n)). Вообще, в некоторых случаях функция f(n) не просто одного порядка с g(n), а определена с точностью до постоянного коэффициента C:
f(n) = C*g(n).
Коэффициент зависит, очевидно, от аппаратных и программных особенностей среды исполнения программы.
Следует отметить, что программисты во многих случаях пишут "f(n) = O(g(n))", хотя подразумевают "f(n) ~ g(n)".
Если оценивающая функция g(n) - многочлен k-й степени, её можно упростить до просто n^k, ибо g(n) ~ n^k. Правда, написать после этого формулу f(n) = C*n^k будет нельзя, но то, что f(n) ~ n^k, выполняется, т. е.
c*n^k <= f(n) <= C*n^k, где c и C - некоторые константы.
Пусть даны две функции f и g. Если f(x) можно представить в виде h(x)*g(x), где h(x) - ограниченная функция, т. е. существует константа C такая, что
|h(x)| <= C,
то функцию f называют ограниченной относительно g и пишут
f(x) = O(g(x)).
Если одновременно
f(x) = O(g(x)) и
g(x) = O(f(x)),
то говорят, что функции f и g одного порядка: f(x) ~ g(x). Можно доказать, что тогда f(x) представима в виде h(x)*g(x), где h(x) удовлетворяет условию: найдутся две константы C1 и C2 обе строго больше нуля, такие, что
C1 <= |h(x)| <= C2.
То же верно и для g(x) (она представима в виде q(x)f(x) и существуют D1 и D2 такие, что D1 <= |q(x)| <= D2; D1 > 0; D2 > 0).
Программисты, как правило, сталкиваются с задачей оценки алгоритмической сложности. Здесь функция - это время выполнения программы в неких условных единицах времени или операциях. Параметром, как правило, является объём входных данных (время выполнения некоторых алгоритмов зависит не только от объёма входных данных, но и от самих данных; в этом случае оценка сложности алгоритма значительно усложняется). Очевидно, объём входных данных - целое число, т. е. наша функция определена на множестве целых неотрицательных чисел.
Естественно, точно описать зависимость f(n) времени выполнения программы от объёма входных данных нельзя, поскольку время выполнения будет отличаться хотя бы для разных по быстродействию процессоров. Но можно оценить эту функцию с помощью понятий "ограниченная относительно g(n)" и "того же порядка, что g(n)", указав эту оценочную функцию g(n). При этом, как указано выше, мы показываем, что наша неизвестная функция f(n) ограничена сверху какой-то функцией (если f(n) = O(g(n))), или снизу (если g(n) = O(f(n))), или сверху и снизу (если f(n) ~g(n)). Вообще, в некоторых случаях функция f(n) не просто одного порядка с g(n), а определена с точностью до постоянного коэффициента C:
f(n) = C*g(n).
Коэффициент зависит, очевидно, от аппаратных и программных особенностей среды исполнения программы.
Следует отметить, что программисты во многих случаях пишут "f(n) = O(g(n))", хотя подразумевают "f(n) ~ g(n)".
Если оценивающая функция g(n) - многочлен k-й степени, её можно упростить до просто n^k, ибо g(n) ~ n^k. Правда, написать после этого формулу f(n) = C*n^k будет нельзя, но то, что f(n) ~ n^k, выполняется, т. е.
c*n^k <= f(n) <= C*n^k, где c и C - некоторые константы.
[QUOTE=Green]Извини, но ты тупишь.
Просто надо перебрать все столбцы всевозможной ширины.
Мой алгоритм четко все описывает. Зачем в перемешку? В перемешку чего?
Хитрость не в этом, но тебе до неё ещё далеко. Ты даже ещё не увидел проблемы, которая решается с помощью некоторой маааленькой хитрости.[/QUOTE]Значит в алгоритме в #16-ом ответе есть какая-то проблема. А почему ты сразу об этом не сказал? Типа на таком и таком шаге есть проблема и она решается таким и таким образом. Это было бы честно, но видимо ты лучше любишь хитро. Ибо если честно, тогда ты не сможешь сказать человеку, что он считать не умеет, тупит, тормозит.
Суть того алгоритма.
1. Проверяю наличие прямоугольников начиная с ширины 1, кончая шириной n.
2. При этом проверяю наличие боковых ребр и наличие нижних ребр.
И пошагово описаны два примера проверки прямоугольников ширины 1.
Не вижу здесь никаких поблем. Конечно если прямоугольники ширины больше 1 проверяются по-другому, то возможно может быть какая-то проблема. Но в том алгоритме об этом ни слова не сказано, поэтому логично предположить, что прямоугольники всех ширин проверяются одинаково: проверяется наличие боковых ребр и наличие нижних ребр.
На картинке 10 столбцов. По 2 столбца при каждом проходе.
Просто надо перебрать все столбцы всевозможной ширины.
Мой алгоритм четко все описывает. Зачем в перемешку? В перемешку чего?
Хитрость не в этом, но тебе до неё ещё далеко. Ты даже ещё не увидел проблемы, которая решается с помощью некоторой маааленькой хитрости.[/QUOTE]Значит в алгоритме в #16-ом ответе есть какая-то проблема. А почему ты сразу об этом не сказал? Типа на таком и таком шаге есть проблема и она решается таким и таким образом. Это было бы честно, но видимо ты лучше любишь хитро. Ибо если честно, тогда ты не сможешь сказать человеку, что он считать не умеет, тупит, тормозит.
Суть того алгоритма.
1. Проверяю наличие прямоугольников начиная с ширины 1, кончая шириной n.
2. При этом проверяю наличие боковых ребр и наличие нижних ребр.
И пошагово описаны два примера проверки прямоугольников ширины 1.
Не вижу здесь никаких поблем. Конечно если прямоугольники ширины больше 1 проверяются по-другому, то возможно может быть какая-то проблема. Но в том алгоритме об этом ни слова не сказано, поэтому логично предположить, что прямоугольники всех ширин проверяются одинаково: проверяется наличие боковых ребр и наличие нижних ребр.
На картинке 10 столбцов. По 2 столбца при каждом проходе.
[QUOTE=Мerlin]Значит в алгоритме в #16-ом ответе есть какая-то проблема. А почему ты сразу об этом не сказал? Типа на таком и таком шаге есть проблема и она решается таким и таким образом. Это было бы честно, но видимо ты лучше любишь хитро. Ибо если честно, тогда ты не сможешь сказать человеку, что он считать не умеет, тупит, тормозит.
[/QUOTE]
Там нет никакой проблемы, там есть маленькая хитрость КАК. Но ты до этого ещё не дошел. Ты до сих пор не можешь перебрать столбцы, а в этом нет никакой хитрости.
[QUOTE=Мerlin]
Суть того алгоритма.
1. Проверяю наличие прямоугольников начиная с ширины 1, кончая шириной n.
2. При этом проверяю наличие боковых ребр и наличие нижних ребр.
[/QUOTE]
Неправильно ты понял алгоритм. Где в моём описании говорится о "проверке наличия прямоугольников"? Там сказано о переборе столбцов всевозможной ширины.
[QUOTE=Мerlin]
И пошагово описаны два примера проверки прямоугольников ширины 1.
Не вижу здесь никаких поблем. Конечно если прямоугольники ширины больше 1 проверяются по-другому, то возможно может быть какая-то проблема. Но в том алгоритме об этом ни слова не сказано, поэтому логично предположить, что прямоугольники всех ширин проверяются одинаково: проверяется наличие боковых ребр и наличие нижних ребр.
[/QUOTE]
Там и нет никаких проблем. Прямоугольники любой ширины проверяются одинаково.
[QUOTE=Мerlin]
На картинке 10 столбцов. По 2 столбца при каждом проходе.
[/QUOTE]
Там ПЯТЬ столбцов шириной два!
[/QUOTE]
Там нет никакой проблемы, там есть маленькая хитрость КАК. Но ты до этого ещё не дошел. Ты до сих пор не можешь перебрать столбцы, а в этом нет никакой хитрости.
[QUOTE=Мerlin]
Суть того алгоритма.
1. Проверяю наличие прямоугольников начиная с ширины 1, кончая шириной n.
2. При этом проверяю наличие боковых ребр и наличие нижних ребр.
[/QUOTE]
Неправильно ты понял алгоритм. Где в моём описании говорится о "проверке наличия прямоугольников"? Там сказано о переборе столбцов всевозможной ширины.
[QUOTE=Мerlin]
И пошагово описаны два примера проверки прямоугольников ширины 1.
Не вижу здесь никаких поблем. Конечно если прямоугольники ширины больше 1 проверяются по-другому, то возможно может быть какая-то проблема. Но в том алгоритме об этом ни слова не сказано, поэтому логично предположить, что прямоугольники всех ширин проверяются одинаково: проверяется наличие боковых ребр и наличие нижних ребр.
[/QUOTE]
Там и нет никаких проблем. Прямоугольники любой ширины проверяются одинаково.
[QUOTE=Мerlin]
На картинке 10 столбцов. По 2 столбца при каждом проходе.
[/QUOTE]
Там ПЯТЬ столбцов шириной два!
Последняя попытка достучаться.
Значит на каждом шаге:
проверка боковых ребр
проверка нижних ребр.
Конечно, если нет хоть одного бокового ребра, то нижние ребра проверять не надо, и тд. Но рассматривается худший случай.
При проверке прямоугольников ширины 1, будут проверены 6 столбцов.
При проверке прямоугольников ширины 2, для ребр
0-2 будут проверены нижние ребра у 0 и 1 столбца
1-3 будут проверены нижние ребра у 1 и 2 столбца
2-4 будут проверены нижние ребра у 2 и 3 столбца
3-5 будут проверены нижние ребра у 3 и 4 столбца
4-6 будут проверены нижние ребра у 4 и 5 столбца
получается 10 столбцов.
Значит на каждом шаге:
проверка боковых ребр
проверка нижних ребр.
Конечно, если нет хоть одного бокового ребра, то нижние ребра проверять не надо, и тд. Но рассматривается худший случай.
При проверке прямоугольников ширины 1, будут проверены 6 столбцов.
При проверке прямоугольников ширины 2, для ребр
0-2 будут проверены нижние ребра у 0 и 1 столбца
1-3 будут проверены нижние ребра у 1 и 2 столбца
2-4 будут проверены нижние ребра у 2 и 3 столбца
3-5 будут проверены нижние ребра у 3 и 4 столбца
4-6 будут проверены нижние ребра у 4 и 5 столбца
получается 10 столбцов.
[QUOTE=Мerlin]Последняя попытка достучаться.
[/QUOTE]
Последняя попытка добиться, чтоб ты читал алгоритм внимательно.
[QUOTE=Мerlin]
Значит на каждом шаге:
проверка боковых ребр
проверка нижних ребр.
[/QUOTE]
Нет.
На каждом шаге:
проверка боковых ребер,
проверка нижнего ребра.
[QUOTE=Мerlin]
Конечно, если нет хоть одного бокового ребра, то нижние ребра проверять не надо, и тд.
[/QUOTE]
Нет.
Нижнее ребро надо проверять (по моему алгоритму) в любом случае.
[QUOTE=Мerlin]
При проверке прямоугольников ширины 1, будут проверены 6 столбцов.
[/QUOTE]
Да
[QUOTE=Мerlin]
При проверке прямоугольников ширины 2, для ребр
0-2 будут проверены нижние ребра у 0 и 1 столбца
[/QUOTE]
Нет.
Будет проверено ребро прямоугольника 0-2. Это делается за константное время.
Аналогично и для всех остальных прямоугольников.
[QUOTE=Мerlin]
получается 10 столбцов.[/QUOTE]
За чем мне проверять столбцы единичной ширины по несколько раз?
Будут проверены ПЯТЬ столбцов ширины 2.
[/QUOTE]
Последняя попытка добиться, чтоб ты читал алгоритм внимательно.
[QUOTE=Мerlin]
Значит на каждом шаге:
проверка боковых ребр
проверка нижних ребр.
[/QUOTE]
Нет.
На каждом шаге:
проверка боковых ребер,
проверка нижнего ребра.
[QUOTE=Мerlin]
Конечно, если нет хоть одного бокового ребра, то нижние ребра проверять не надо, и тд.
[/QUOTE]
Нет.
Нижнее ребро надо проверять (по моему алгоритму) в любом случае.
[QUOTE=Мerlin]
При проверке прямоугольников ширины 1, будут проверены 6 столбцов.
[/QUOTE]
Да
[QUOTE=Мerlin]
При проверке прямоугольников ширины 2, для ребр
0-2 будут проверены нижние ребра у 0 и 1 столбца
[/QUOTE]
Нет.
Будет проверено ребро прямоугольника 0-2. Это делается за константное время.
Аналогично и для всех остальных прямоугольников.
[QUOTE=Мerlin]
получается 10 столбцов.[/QUOTE]
За чем мне проверять столбцы единичной ширины по несколько раз?
Будут проверены ПЯТЬ столбцов ширины 2.
Green,
а действительно, ты уверен в сложности: n^3? Ведь даже в алгоритме прямого перебора я не зря исправил: не (m*n)^2, а (m*n)^2 * log2 (k) - поправка на поиск пробитых ребер, если те хранятся в контейнере с логарифмическим временем поиска. Твой алгоритм, по крайней мере насколько я вижу, основан не на хранении "пробитых" ребер, а на хранении нормальных, существующих. Во-первых: объём информации для "больших" случаев будет просто огромен. Во-вторых, как насчет поправки на поиск? Я читал твоё утверждение о том, что поиск будет производиться за линейное время благодаря специальной организации контейнера, но о самой организации ты не сказал; к тому же, насколько я понимаю, алгоритм несколько изменился от первоначального варианта, где ты это утверждал, к современному (в современном никакого контейнера нет!). Короче, к чему я веду: 1) лучше хранить всё-таки пробитые рёбра, хотя, я думаю, тебе не надо об этом говорить; 2) ввести поправку на время поиска ребра: O(n^3 * log2 (k)).
А ещё лучше - провести дополнительные математические исследования, например, в случае наличия большого числа k - пробитых рёбер. Интуиция подсказывает мне, что в таком случае можно сильно соптимизировать задачу (уменьшив n, m и k), но это ещё нужно исследовать...
а действительно, ты уверен в сложности: n^3? Ведь даже в алгоритме прямого перебора я не зря исправил: не (m*n)^2, а (m*n)^2 * log2 (k) - поправка на поиск пробитых ребер, если те хранятся в контейнере с логарифмическим временем поиска. Твой алгоритм, по крайней мере насколько я вижу, основан не на хранении "пробитых" ребер, а на хранении нормальных, существующих. Во-первых: объём информации для "больших" случаев будет просто огромен. Во-вторых, как насчет поправки на поиск? Я читал твоё утверждение о том, что поиск будет производиться за линейное время благодаря специальной организации контейнера, но о самой организации ты не сказал; к тому же, насколько я понимаю, алгоритм несколько изменился от первоначального варианта, где ты это утверждал, к современному (в современном никакого контейнера нет!). Короче, к чему я веду: 1) лучше хранить всё-таки пробитые рёбра, хотя, я думаю, тебе не надо об этом говорить; 2) ввести поправку на время поиска ребра: O(n^3 * log2 (k)).
А ещё лучше - провести дополнительные математические исследования, например, в случае наличия большого числа k - пробитых рёбер. Интуиция подсказывает мне, что в таком случае можно сильно соптимизировать задачу (уменьшив n, m и k), но это ещё нужно исследовать...
[QUOTE=cheburator]Green,
а действительно, ты уверен в сложности: n^3?
[/QUOTE]
Да, уверен.
[QUOTE=cheburator]
Я читал твоё утверждение о том, что поиск будет производиться за линейное время благодаря специальной организации контейнера, но о самой организации ты не сказал.
[/QUOTE]
Это было в старом, не совсем валидном алгоритме.
В новом у меня такой контейнер не нужен совсем.
[QUOTE=cheburator]
Короче, к чему я веду: 1) лучше хранить всё-таки пробитые рёбра, 2) ввести поправку на время поиска ребра.
[/QUOTE]
Время поиска, точнее определения цельности ребра на каждом шаге алгоритма, как я уже говорил, КОНСТАНТНО. Это и есть та маааленькая хитрость.
К решению задачи я подходил с точки зрения динамического программирования. Обеспечение константного времени при определении целостности нижнего ребра так же основано на принципе динамического программирования. Т.е. поняв алгоритм в целом, можно по аналогии понять, как реализуется эта хитрость.
Я расскажу как, если желание догадаться уже иссякло. :)
а действительно, ты уверен в сложности: n^3?
[/QUOTE]
Да, уверен.
[QUOTE=cheburator]
Я читал твоё утверждение о том, что поиск будет производиться за линейное время благодаря специальной организации контейнера, но о самой организации ты не сказал.
[/QUOTE]
Это было в старом, не совсем валидном алгоритме.
В новом у меня такой контейнер не нужен совсем.
[QUOTE=cheburator]
Короче, к чему я веду: 1) лучше хранить всё-таки пробитые рёбра, 2) ввести поправку на время поиска ребра.
[/QUOTE]
Время поиска, точнее определения цельности ребра на каждом шаге алгоритма, как я уже говорил, КОНСТАНТНО. Это и есть та маааленькая хитрость.
К решению задачи я подходил с точки зрения динамического программирования. Обеспечение константного времени при определении целостности нижнего ребра так же основано на принципе динамического программирования. Т.е. поняв алгоритм в целом, можно по аналогии понять, как реализуется эта хитрость.
Я расскажу как, если желание догадаться уже иссякло. :)
[QUOTE=Green]Время поиска, точнее определения цельности ребра на каждом шаге алгоритма, как я уже говорил, КОНСТАНТНО. Это и есть та маааленькая хитрость.
[/QUOTE]
Я плохо понимаю, что такое динамическое программирование, но для константного доступа я бы сделал двухмерный массив типа bool (проломленная/целая) для вертикальных стенок и такой же для горизонтальных. В "больших" случаях будет, правда, память жрать. Хотя, поскольку расходы времени кубичны, это уже неважно :)
[/QUOTE]
Я плохо понимаю, что такое динамическое программирование, но для константного доступа я бы сделал двухмерный массив типа bool (проломленная/целая) для вертикальных стенок и такой же для горизонтальных. В "больших" случаях будет, правда, память жрать. Хотя, поскольку расходы времени кубичны, это уже неважно :)
[QUOTE=cheburator]Я плохо понимаю, что такое динамическое программирование,
[/QUOTE]
Это цитата из Wikipedia:
http://ru.wikipedia.org/wiki/Динамическое_программирование
Идея динамического программирования состоит в разбиении задачи на несколько независимых подзадач, решении каждой из них, а затем вычислении исходного результата. Для решения подзадач этот же алгоритм применяется рекурсивно. При этом для каждой подзадачи запоминается вычисленный ответ, и если на каком-то шаге встретилась подзадача второй раз, то вычисления для нее не производятся. За счет большого количества пересекающихся подзадач это значительно уменьшает время работы.
[/QUOTE]
Это цитата из Wikipedia:
http://ru.wikipedia.org/wiki/Динамическое_программирование
Цитата:
Идея динамического программирования состоит в разбиении задачи на несколько независимых подзадач, решении каждой из них, а затем вычислении исходного результата. Для решения подзадач этот же алгоритм применяется рекурсивно. При этом для каждой подзадачи запоминается вычисленный ответ, и если на каком-то шаге встретилась подзадача второй раз, то вычисления для нее не производятся. За счет большого количества пересекающихся подзадач это значительно уменьшает время работы.
Именно этот подход, как видишь, я применял в алгоритме.
Именно его нужно применить для обеспечения константного доступак нижним ребрам. Перебирать каждый раз все ребра излишне, т.к. мы перебирали на одно ребро меньше на предыдущем шаге.
[QUOTE=cheburator] но для константного доступа я бы сделал двухмерный массив типа bool (проломленная/целая) для вертикальных стенок и такой же для горизонтальных.
[/QUOTE]
Пусть загадка ещё немного побудет загадкой.
Направление верное, нужен двумерный массив, но только для горизонтальных стенок (зачем для вертикальных?). Он будет m*n, и тип не bool, а int.
Серьезная подсказка, теперь догадаться намного легче :)
[QUOTE=cheburator]
В "больших" случаях будет, правда, память жрать. Хотя, поскольку расходы времени кубичны, это уже неважно :)[/QUOTE]
Расход ресурса всегда важен. Тем более что время и память - это разные ресурсы.
[QUOTE=Green]
Расход ресурса всегда важен. Тем более что время и память - это разные ресурсы.[/QUOTE]
Согласен. Но согласись и ты: машина, способная за разумное время посчитать "большой" случай, т. е. имеющая хорошие "мозги", уж наверняка имеет и достаточное количество памяти. Не интересовался статистикой, но думаю, что с ростом одного ресурса у машин второй ресурс вряд ли становится меньше.
К тому же, расходы времени - кубичны, расходы памяти на такой массив квадратичны. То бишь относительный расход памяти устремляется к нулю.
Расход ресурса всегда важен. Тем более что время и память - это разные ресурсы.[/QUOTE]
Согласен. Но согласись и ты: машина, способная за разумное время посчитать "большой" случай, т. е. имеющая хорошие "мозги", уж наверняка имеет и достаточное количество памяти. Не интересовался статистикой, но думаю, что с ростом одного ресурса у машин второй ресурс вряд ли становится меньше.
К тому же, расходы времени - кубичны, расходы памяти на такой массив квадратичны. То бишь относительный расход памяти устремляется к нулю.
В дополнительный массив записывается длина непрерывной гор. линии отсчитывая слева. В k-й ячейке есть прямоугольник ширины t, если есть ребра с обеих сторон и длина гор.линии в k-й позиции больше равна t.
Только в алгоритме (пост #16) НЕТ НИ СЛОВА о доп. массиве.
Даже во время проверки прямоугольников ширины 1, она не строится. Т.е. она строится уже после этого или ты просто что-то не досказал?
В общем если б ты "работал" наперсточником, то считался бы среди них королем.
Только в алгоритме (пост #16) НЕТ НИ СЛОВА о доп. массиве.
Даже во время проверки прямоугольников ширины 1, она не строится. Т.е. она строится уже после этого или ты просто что-то не досказал?
В общем если б ты "работал" наперсточником, то считался бы среди них королем.