#include <iostream.h>
const int N = 4;
int M[N][N] = {1, 1, 0, 1,
1, 1, 1, 1,
0, 0, 1, 1,
1, 0, 1, 1};
int main()
{
int i, j, l, h, max = 0, s;
for (j = 0; j < N; j++)
for (i = 1; i < N; i++)
if (M[j]) M[j] = M[i-1][j]+1;
// до сих пор был первый шаг.
// Далее коментарии над строчками
// для каждой строчки
for (i = 0; i < N; i++)
// для начала проекции на строчку
for (j = 0; j < N; j++) {
// h - высота прямоугольника над строчкой
// изначально делаем больше чем вообще может быть
h = N + 1;
// l - конец проекции. изначально берем самую короткую проекцию
l = j;
// удленняем проекцию пока не наткнулись на черный квадратик
while (l < N && M[j]) {
// ещем максимальную висоту для етой проекции
if (h > M[l]) h = M[l];
// ищем площу прямоугольника с такой проекцией
// длинна проекции * висоту над строчкой = площадь
s = (l-j+1) * min;
// коректируем результат
if (max < s) max = s;
l++; // собственно увеличение проекции
}
}
// вот и все
cout << max;
return 0;
}
Разминка для ума
Интересную задачку подкинули:
Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника.
Цитата:
Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника.
Ну что, кто может предложить алгоритм, а заодно и определить его асимптотическую сложность?
Кстати, может кто предложит к какой сложности надо стремится? :)
P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли.
Цитата:
Originally posted by Green
давай, рассказывай.
Может это с моим решением и не сойдется.
давай, рассказывай.
Может это с моим решением и не сойдется.
Прочел он ево в книге Арсака "Программирование игр и головоломок". Собственно етот алгоритм использовался для решения более общей задачи.
Задана матрица MxN - ето матрица висот.
Нужно наити прямоугольний максимального размера на котором все точки имеют однаковую высоту.
Но для удобства я переделал под нашу задачу.
Код:
Ето еще можна чуть соптимизировать, но тогда будет тяжето понять суть алгоритма.
Хотел бы теперь увидеть Твой.
До сих пор не верю что ету задачу можно решить алгоритмом с квадратической сложностю.
В общем направление правильное, но алгоритм делает много лишних действий.
На первом шаге ты динамику (динамическое программирование) уяснил и не перебирал все клетки сначала в столбце для нахождения проекции для очередной строки. Ты просто брал предыдущий результат и инкрементировал его.
Но на втором шаге ты почему то отказался от динамики и начал считать перебором последующих проекций (while) для каждой текущей проекции (for j) в строке. Отсюда у тебя и вылезла третья степень, хотя вполне можно было бы обойтись и второй, как на шаге 1.
Сам переделаешь? ;)
Кстати, под min ты подразумевал h ?
s = (l-j+1) * min;
На первом шаге ты динамику (динамическое программирование) уяснил и не перебирал все клетки сначала в столбце для нахождения проекции для очередной строки. Ты просто брал предыдущий результат и инкрементировал его.
Но на втором шаге ты почему то отказался от динамики и начал считать перебором последующих проекций (while) для каждой текущей проекции (for j) в строке. Отсюда у тебя и вылезла третья степень, хотя вполне можно было бы обойтись и второй, как на шаге 1.
Сам переделаешь? ;)
Кстати, под min ты подразумевал h ?
s = (l-j+1) * min;
Цитата:
Originally posted by Green
под min ты подразумевал h ?
s = (l-j+1) * min;
под min ты подразумевал h ?
s = (l-j+1) * min;
Да. СОРИ
Цитата:
Сам переделаешь? ;)
Мне надо подумать некоторое время.
Скажы только. Ты используеш еще какието масивы для сбережения промежуточных результатов ?
Меня смущает тот факт, что проекций разных будет
N(N+1)/2 while помогает отсеч ненужные.
Но всеровно много останется.
Цитата:
Originally posted by Rebbit
Скажы только. Ты используеш еще какието масивы для сбережения промежуточных результатов ?
Меня смущает тот факт, что проекций разных будет
N(N+1)/2 while помогает отсеч ненужные.
Но всеровно много останется.
Скажы только. Ты используеш еще какието масивы для сбережения промежуточных результатов ?
Меня смущает тот факт, что проекций разных будет
N(N+1)/2 while помогает отсеч ненужные.
Но всеровно много останется.
:)
Серьезная подсказка...
Я использую стек размером N
Цитата:
Originally posted by Green
:)
Серьезная подсказка...
Я использую стек размером N
:)
Серьезная подсказка...
Я использую стек размером N
Не знаю я :( Розказывай все пожалуста. Если можно с кодом.
Все сдаюсь. за пару дней - никаких нормальных результатов по решению этой задачи. Подскажите, а, чего делать?
Цитата:
Originally posted by Greenering
Все сдаюсь. за пару дней - никаких нормальных результатов по решению этой задачи. Подскажите, а, чего делать?
Все сдаюсь. за пару дней - никаких нормальных результатов по решению этой задачи. Подскажите, а, чего делать?
Думаю, первый шаг понятен.
Поэтому перейду ко второму шагу.
Как я уже говорил, будем использовать стек размером N элементов, каждый элемент - это пара: координата (номер столбца) и высота проекции (число в этой ячейке):
Код:
максимальная площадь = 0;
для каждой строки:
для каждого столбца + 1:
повторяем пока текущая высота меньше, чем на вершине стека, или если это последняя итерация:
вычисляем площадь высота, которого на вершине стека;
определяем максимальная ли это на данный момент площадь;
снимаем элемент с вершины стека;
помещаем в стек новую пару (ячейка, высота);
для каждой строки:
для каждого столбца + 1:
повторяем пока текущая высота меньше, чем на вершине стека, или если это последняя итерация:
вычисляем площадь высота, которого на вершине стека;
определяем максимальная ли это на данный момент площадь;
снимаем элемент с вершины стека;
помещаем в стек новую пару (ячейка, высота);
Описание получилось достаточно запутанным, поэтому покажу на примере.
Т.к. концентрации больших величин вероятней всего в нижней части матрицы, полученной на первом шаге, то начнем с самой нижней строчки:
1 0 3 4
Код:
Итерация 1: помещаем в стек пару (0,1), где 0 - координата яцейки, 1 - высота.
Итерация 2: 0 меньше, чем 1,
вычисляем площадь 1 * (1-0) = 1;
заносим её в максимум;
снимаем со стека пару (0,1);
заносим в стек пару (1,0);
Итерация 3: 3 больше, чем 0
заносим в стек пару (2,3);
Итерация 4: 4 больше, чем 0
заносим в стек пару (3,4);
Последняя итерация:
состояние стека:
(3,4)
(2,3)
(1,0)
раскручиваем стек:
площадь = 4*(4-3) = 4
заносим в максимум, т.к. 4 > 1
площадь = 3*(4-2) = 6
заносим в максимум, т.к. 6 > 4
площадь = 0*(4-1) = 0
не заносим в максимум, т.к. 0 < 6
Итерация 2: 0 меньше, чем 1,
вычисляем площадь 1 * (1-0) = 1;
заносим её в максимум;
снимаем со стека пару (0,1);
заносим в стек пару (1,0);
Итерация 3: 3 больше, чем 0
заносим в стек пару (2,3);
Итерация 4: 4 больше, чем 0
заносим в стек пару (3,4);
Последняя итерация:
состояние стека:
(3,4)
(2,3)
(1,0)
раскручиваем стек:
площадь = 4*(4-3) = 4
заносим в максимум, т.к. 4 > 1
площадь = 3*(4-2) = 6
заносим в максимум, т.к. 6 > 4
площадь = 0*(4-1) = 0
не заносим в максимум, т.к. 0 < 6
Аналогично повторяем для всех остальных строк.
Очень показателен алгоритм для второй строки:
2 2 1 2
Код:
Итерация 1: помещаем в стек пару (0,2).
Итерация 2: помещаем в стек пару (1,2).
Итерация 3: текущая высота 1
состояние стека
(0,2)
(1,2)
1 меньше, чем 2,
вычисляем площадь 2 * (2-0) = 4;
снимаем со стека пару (0,2);
не заносим в максимум, т.к. 2 < 6
(6 мы получили при проходе самой нижней строки)
1 меньше, чем 2,
вычисляем площадь 2 * (2-1) = 2;
снимаем со стека пару (1,2);
не заносим в максимум, т.к. 2 < 6
заносим в стек пару (2,1);
Итерация 4: 2 больше, чем 1
заносим в стек пару (3,2);
Последняя итерация:
состояние стека:
(3,2)
(2,1)
раскручиваем стек:
площадь = 2*(4-3) = 2
не заносим в максимум, т.к. 2 < 6
площадь = 1*(4-2) = 2
не заносим в максимум, т.к. 2 < 6
Итерация 2: помещаем в стек пару (1,2).
Итерация 3: текущая высота 1
состояние стека
(0,2)
(1,2)
1 меньше, чем 2,
вычисляем площадь 2 * (2-0) = 4;
снимаем со стека пару (0,2);
не заносим в максимум, т.к. 2 < 6
(6 мы получили при проходе самой нижней строки)
1 меньше, чем 2,
вычисляем площадь 2 * (2-1) = 2;
снимаем со стека пару (1,2);
не заносим в максимум, т.к. 2 < 6
заносим в стек пару (2,1);
Итерация 4: 2 больше, чем 1
заносим в стек пару (3,2);
Последняя итерация:
состояние стека:
(3,2)
(2,1)
раскручиваем стек:
площадь = 2*(4-3) = 2
не заносим в максимум, т.к. 2 < 6
площадь = 1*(4-2) = 2
не заносим в максимум, т.к. 2 < 6
Может показаться, что раскручивание стека это еще одна степень сложности, но это не так.
Нужно объяснять почему это не так?
О, модная задачка и без Бобра. Вот что значит не быть больше недели на форуме. :(
Короче - первое что пришло мне в голову, еще не перечитав предлженых идей - разбивать поле на два равных под-поля рекурсивно. Дойдя до полей 1*1 и поднимаясь назад брать лучшееи смотреть или оно сопркасается с соседом. По идее сложность - С*log(n^2).
Короче - первое что пришло мне в голову, еще не перечитав предлженых идей - разбивать поле на два равных под-поля рекурсивно. Дойдя до полей 1*1 и поднимаясь назад брать лучшееи смотреть или оно сопркасается с соседом. По идее сложность - С*log(n^2).
Пусть дана матрица нулей и единиц (ну или белого и чёрного)
Шаг 1. Составить по ней граф.
Шаг 2. Найти контур с max кол-вом ветвей.
Шаг 3. Умножить это кол-во на площадь одного белого квадратика и приравнять эту величину к искомой площади.
Шаг 1. Составить по ней граф.
Шаг 2. Найти контур с max кол-вом ветвей.
Шаг 3. Умножить это кол-во на площадь одного белого квадратика и приравнять эту величину к искомой площади.
Цитата:
Originally posted by Dart Bobr
Короче - первое что пришло мне в голову, еще не перечитав предлженых идей - разбивать поле на два равных под-поля рекурсивно. Дойдя до полей 1*1 и поднимаясь назад брать лучшееи смотреть или оно сопркасается с соседом. По идее сложность - С*log(n^2).
Короче - первое что пришло мне в голову, еще не перечитав предлженых идей - разбивать поле на два равных под-поля рекурсивно. Дойдя до полей 1*1 и поднимаясь назад брать лучшееи смотреть или оно сопркасается с соседом. По идее сложность - С*log(n^2).
Что-то алгоритм мне совсем не понятен...
Продемонстрируй на примере, плз.
А вот оценка сложности однозначно неверна.
Ты утверждаешь, что сложность меньше N^2, тогда наводящий вопрос, а какая сложность алгоритма находящего минимум в неотсортированном массиве?
Цитата:
Originally posted by Helicopterr
Пусть дана матрица нулей и единиц (ну или белого и чёрного)
Шаг 1. Составить по ней граф.
Шаг 2. Найти контур с max кол-вом ветвей.
Шаг 3. Умножить это кол-во на площадь одного белого квадратика и приравнять эту величину к искомой площади.
Пусть дана матрица нулей и единиц (ну или белого и чёрного)
Шаг 1. Составить по ней граф.
Шаг 2. Найти контур с max кол-вом ветвей.
Шаг 3. Умножить это кол-во на площадь одного белого квадратика и приравнять эту величину к искомой площади.
Пример, пожалуйста, а то ничего не понятно. :)
И сложность.
Цитата:
Originally posted by Green
Код:
максимальная площадь = 0;
для каждой строки:
для каждого столбца + 1:
повторяем пока текущая высота меньше, чем на вершине стека, или если это последняя итерация:
вычисляем площадь высота, которого на вершине стека;
определяем максимальная ли это на данный момент площадь;
снимаем элемент с вершины стека;
помещаем в стек новую пару (ячейка, высота);
для каждой строки:
для каждого столбца + 1:
повторяем пока текущая высота меньше, чем на вершине стека, или если это последняя итерация:
вычисляем площадь высота, которого на вершине стека;
определяем максимальная ли это на данный момент площадь;
снимаем элемент с вершины стека;
помещаем в стек новую пару (ячейка, высота);
БРАВО !!! И бурные и продолжытельные аплодисменты для маесто. Ето надо запомнить и друзьям показать :)
Я был настолько уверен, что даже поcпорил что такое невозможно.
Цитата:
Originally posted by Green
Может показаться, что раскручивание стека это еще одна степень сложности, но это не так.
Нужно объяснять почему это не так?
Может показаться, что раскручивание стека это еще одна степень сложности, но это не так.
Нужно объяснять почему это не так?
Чыстый N^2
ЗЫ. Наверное многие знают, но всеже.
Есть много сайтов посвящених таким задачам, критическим к времени исполнения и памяти.
http://acm.timus.ru/
Цитата:
Originally posted by Green
Что-то алгоритм мне совсем не понятен...
Продемонстрируй на примере, плз.
Что-то алгоритм мне совсем не понятен...
Продемонстрируй на примере, плз.
А че тут непонятного. Сначала - рекурсивно спускаемся до квадратиков 1*1, потом поднимаемся назад, подсчитывая площади. К примеру если на даном шаге мы рассматриваем два квадрата 3*3, то для каждого из них мы знаем площадь наибольшей белой фигуры. Перейти к фигуре 6*3 мы можем только после проверки или соприкасаются белые фигуры в квадратах 3*3. Что можно сделать, сохраняя информацию об их контурах при рекурсивном поднятии. Вот только щас подумал, что алгоритм то жадный и не всегда проидет, хотя время у него должно по-любому быть лучше чем у динамического алгоритма. Еще подумаю, может можна че-то изменить что-б он работал всегда, но вот на таком примере он не проидет
000000000
011100000
001001100
000001100
001111000
000000000
Так как на последнем шаге будут рассмотрены такие области:
00000
01110
00100
00000
00111
00000
и
0000
0000
1100
1100
1000
0000
Алгоритм выберет верхюю фигуру первого квадрата и есс-но даст неправильный результат :(
ЕДинственный выход, который я вижу - сохранять данные обо всех фигурах, но это слишком гемморойно, к тому же приведет к очень многим дополнительным сравнениям.
Цитата:
Originally posted by Green
А вот оценка сложности однозначно неверна.
Ты утверждаешь, что сложность меньше N^2, тогда наводящий вопрос, а какая сложность алгоритма находящего минимум в неотсортированном массиве?
А вот оценка сложности однозначно неверна.
Ты утверждаешь, что сложность меньше N^2, тогда наводящий вопрос, а какая сложность алгоритма находящего минимум в неотсортированном массиве?
Не спорю, оценку я скорее всего сделал сгоряча.
O(N).
На счет алгоритма. N^2 - это норма.
Не разобрался в эффективности, только потому, что я неуверен в его правильности. А чтоб найти контрпример, нужно время, хотя бы пол часа и главное понять алгоритм.
(1)для каждой строки:
(2) для каждого столбца + 1:
(3) повторяем пока текущая высота меньше, чем на вершине стека, или если это
(1) - понятно
(2) - пусть будет, хоть не совсем ясно, для чего вводить +1 итерацию. Можно раскрытие стека организовать по-другому.
(3) - туманно немношко. Если прочитать руководство к алгоритму ниже, то становится ясно, что если высота больше, то в стек добавляется элемент.
В конечном итоге, имеем полный перебор. С тем отличием, что некоторые прямоугольники определяются сразу. А другие сперва заносятся в стек и определяются потом. И как минимум цвет прямоугольника определяется много раз. Хоть ты писал: "каждую ячейку будем просматривать только ОДИН РАЗ!"
Значит мне не понятно например. откуда
раскручиваем стек:
[color=red]площадь = 3*(4-2) = 6 [/color]
Т.е. каким образом определяешь площадь? Ведь в текущем столбце может стоять 3 белых ячеек подряд, но это ничего не значит, если в соседнем их только две.
Что-то я не читал в условиях задачи, что белые области могут быть только прямоугольными.
Не разобрался в эффективности, только потому, что я неуверен в его правильности. А чтоб найти контрпример, нужно время, хотя бы пол часа и главное понять алгоритм.
(1)для каждой строки:
(2) для каждого столбца + 1:
(3) повторяем пока текущая высота меньше, чем на вершине стека, или если это
(1) - понятно
(2) - пусть будет, хоть не совсем ясно, для чего вводить +1 итерацию. Можно раскрытие стека организовать по-другому.
(3) - туманно немношко. Если прочитать руководство к алгоритму ниже, то становится ясно, что если высота больше, то в стек добавляется элемент.
В конечном итоге, имеем полный перебор. С тем отличием, что некоторые прямоугольники определяются сразу. А другие сперва заносятся в стек и определяются потом. И как минимум цвет прямоугольника определяется много раз. Хоть ты писал: "каждую ячейку будем просматривать только ОДИН РАЗ!"
Значит мне не понятно например. откуда
раскручиваем стек:
[color=red]площадь = 3*(4-2) = 6 [/color]
Т.е. каким образом определяешь площадь? Ведь в текущем столбце может стоять 3 белых ячеек подряд, но это ничего не значит, если в соседнем их только две.
Что-то я не читал в условиях задачи, что белые области могут быть только прямоугольными.
Цитата:
Originally posted by Mоngооsе
На счет алгоритма. N^2 - это норма.
На счет алгоритма. N^2 - это норма.
Может, и норма, но только никто, в т.ч. и ты, не предложил другого алгоритма такой сложности.
Цитата:
Originally posted by Mоngооsе
Не разобрался в эффективности, только потому, что я неуверен в его правильности. А чтоб найти контрпример, нужно время, хотя бы пол часа и главное понять алгоритм.
Не разобрался в эффективности, только потому, что я неуверен в его правильности. А чтоб найти контрпример, нужно время, хотя бы пол часа и главное понять алгоритм.
Правильно, для того, что бы спорить, надо разобраться в теме.
Цитата:
Originally posted by Mоngооsе
Можно раскрытие стека организовать по-другому.
Можно раскрытие стека организовать по-другому.
Не вопрос, можно.
Но зачем?
Цитата:
Originally posted by Mоngооsе
(3) - туманно немношко. Если прочитать руководство к алгоритму ниже, то становится ясно, что если высота больше, то в стек добавляется элемент.
(3) - туманно немношко. Если прочитать руководство к алгоритму ниже, то становится ясно, что если высота больше, то в стек добавляется элемент.
Именно так, если высота больше, чем на вершине стека, то добавляется новый элемент.
Если меньше, то вычисляем площадь прямоугольника или прямоугольников соотв-но.
Цитата:
Originally posted by Mоngооsе
И как минимум цвет прямоугольника определяется много раз. Хоть ты писал: "каждую ячейку будем просматривать только ОДИН РАЗ!"
И как минимум цвет прямоугольника определяется много раз. Хоть ты писал: "каждую ячейку будем просматривать только ОДИН РАЗ!"
Именно один раз!
Покажи где ты видишь проход по исходной матрице дважды?
Или дважды проход по проекциям?
Или дважды проход по стеку?
Цитата:
Originally posted by Mоngооsе
Значит мне не понятно например. откуда
раскручиваем стек:
[color=red]площадь = 3*(4-2) = 6 [/color]
Т.е. каким образом определяешь площадь? Ведь в текущем столбце может стоять 3 белых ячеек подряд, но это ничего не значит, если в соседнем их только две.
Значит мне не понятно например. откуда
раскручиваем стек:
[color=red]площадь = 3*(4-2) = 6 [/color]
Т.е. каким образом определяешь площадь? Ведь в текущем столбце может стоять 3 белых ячеек подряд, но это ничего не значит, если в соседнем их только две.
Площадь определяю просто: умножаю высоту на ширину.
В данном случае 3 - это высота, а 4-2 - это ширина.
Что именно не понятно?
Цитата:
Originally posted by Mоngооsе
Что-то я не читал в условиях задачи, что белые области могут быть только прямоугольными.
Что-то я не читал в условиях задачи, что белые области могут быть только прямоугольными.
А там и нет условия, что белые области только прямоугольные.
Найти надо площадь белого ПРЯМОУГОЛЬНИКА.
Цитата:
Originally posted by Green
Может, и норма, но только никто, в т.ч. и ты, не предложил другого алгоритма такой сложности.
Может, и норма, но только никто, в т.ч. и ты, не предложил другого алгоритма такой сложности.
Я предложил. Выделение прямоугольных областей. Сложность N^2. Думаю это бесспорно. Нахождение среди выделенных областей макс. прямоугольника. Сложность меньше N^2. Сам алгоритм выделения я не описал по той причине, что алгоритм архи-сложный. И за мое время пребывания на этом форуме в меня сложилось впечатление, что сложный алгоритм --- это не твой мир. Перед тем, как Ты в очередной раз прилипнешь к потолку, хотел бы заметить, что это хотело бы быть шуткой. Я написал: определение макс. прямоугольника имеет сложность меньшее N^2. Ты не спросил почему, естественно я не ответил на незаданный вопрос. Но хоть по скриншоту можно догадаться.
Цитата:
Правильно, для того, что бы спорить, надо разобраться в теме.
Ты прав. Я с тобой согласен на все 100. Но не все такие. Напр. крутые спецы, до которых нам расти и расти, думают по-другому. http://forum.codenet.ru/showthread.php?s=&threadid=26811#post114218 Ключевое предложение: "у меня есть секретный метод давать правильные ответы в любой области вне зависимости от того насколько хорошо я его знаю". Мимоходом ты хотел мне дать совет по LabView. Ты видел хоть одну программу написанную на этом языке?
Цитата:
Именно один раз!
Покажи где ты видишь проход по исходной матрице дважды?
Или дважды проход по проекциям?
Или дважды проход по стеку?
Покажи где ты видишь проход по исходной матрице дважды?
Или дважды проход по проекциям?
Или дважды проход по стеку?
Для начала я писал только о цвете. В цикле несколько раз определяется, текущий прямоугольник черный или белый.
Цитата:
Площадь определяю просто: умножаю высоту на ширину.
В данном случае 3 - это высота, а 4-2 - это ширина.
Что именно не понятно?
В данном случае 3 - это высота, а 4-2 - это ширина.
Что именно не понятно?
Все понятно. Твой шедевр нерабочий. Ладно - пока еще. Значит область прямоугольника на скриншоте с красным нижним правым углом = 24?
Цитата:
Originally posted by Mоngооsе
Я предложил. Выделение прямоугольных областей. Сложность N^2. Думаю это бесспорно.
Я предложил. Выделение прямоугольных областей. Сложность N^2. Думаю это бесспорно.
Это бесспорно как минимум N^4.
Ты меняешь цвет ячейки, но при этом ты все равно просматриваешь её несколько раз. А с учетом копирования, можно сказать что этот алгоритм сложности N^6.
Цитата:
Originally posted by Mоngооsе
Нахождение среди выделенных областей макс. прямоугольника. Сложность меньше N^2.
Нахождение среди выделенных областей макс. прямоугольника. Сложность меньше N^2.
Только я что-то не припомню, что бы ты приводил этот алгоритм.
Цитата:
Originally posted by Mоngооsе
Сам алгоритм выделения я не описал по той причине, что алгоритм архи-сложный.
Сам алгоритм выделения я не описал по той причине, что алгоритм архи-сложный.
Архисложный - это нечитабельный код, где определяется много неннужных переменных и используется большой буфер под все сразу?
Кстати, твоя программа использует непроинициализированную область памяти, а потому сбоит. Плавающие ошибки - самые отвратительные ошибки, а их появление обычно из-за неумения структурировать и стилизировать.
И ещё, для чего такие нелепости с неявнем преобразованием типов: *iCurRes = (int)ipAr;
Цитата:
Originally posted by Mоngооsе
И за мое время пребывания на этом форуме в меня сложилось впечатление, что сложный алгоритм --- это не твой мир.
Перед тем, как Ты в очередной раз прилипнешь к потолку, хотел бы заметить, что это хотело бы быть шуткой.
И за мое время пребывания на этом форуме в меня сложилось впечатление, что сложный алгоритм --- это не твой мир.
Перед тем, как Ты в очередной раз прилипнешь к потолку, хотел бы заметить, что это хотело бы быть шуткой.
Мой мир - планета Земля.
Цитата:
Originally posted by Mоngооsе
Я написал: определение макс. прямоугольника имеет сложность меньшее N^2. Ты не спросил почему, естественно я не ответил на незаданный вопрос. Но хоть по скриншоту можно догадаться.
Я написал: определение макс. прямоугольника имеет сложность меньшее N^2. Ты не спросил почему, естественно я не ответил на незаданный вопрос. Но хоть по скриншоту можно догадаться.
Нет, нельзя. Объясни.
Цитата:
Originally posted by Mоngооsе
Ты прав. Я с тобой согласен на все 100. Но не все такие. Напр. крутые спецы, до которых нам расти и расти, думают по-другому. http://forum.codenet.ru/showthread.php?s=&threadid=26811#post114218 Ключевое предложение: "у меня есть секретный метод давать правильные ответы в любой области вне зависимости от того насколько хорошо я его знаю". Мимоходом ты хотел мне дать совет по LabView. Ты видел хоть одну программу написанную на этом языке?
Ты прав. Я с тобой согласен на все 100. Но не все такие. Напр. крутые спецы, до которых нам расти и расти, думают по-другому. http://forum.codenet.ru/showthread.php?s=&threadid=26811#post114218 Ключевое предложение: "у меня есть секретный метод давать правильные ответы в любой области вне зависимости от того насколько хорошо я его знаю". Мимоходом ты хотел мне дать совет по LabView. Ты видел хоть одну программу написанную на этом языке?
Что-то ты не ту ссылку дал....
Тема, на сколько помню, была про стилистику и общие принципы программирования, а не про LabView. А по этой области я могу дать совет.
Цитата:
Originally posted by Mоngооsе
Для начала я писал только о цвете. В цикле несколько раз определяется, текущий прямоугольник черный или белый.
Для начала я писал только о цвете. В цикле несколько раз определяется, текущий прямоугольник черный или белый.
Да ну?
В каком цикле?
Что-то у меня складывается впечатление, что ты вообще не во что не въехал...
Цитата:
Originally posted by Mоngооsе
Все понятно. Твой шедевр нерабочий. Ладно - пока еще.
Все понятно. Твой шедевр нерабочий. Ладно - пока еще.
Если ты НИАСИЛИЛ понять, то это ещё не значит, что мой шедевр не рабочий.
Ты не спеши найти за что зацепиться. Для начала попробуй понять, как работает мой алгоритм. Он же прост, как две копейки.
Цитата:
Originally posted by Mоngооsе
Значит область прямоугольника на скриншоте с красным нижним правым углом = 24?
Значит область прямоугольника на скриншоте с красным нижним правым углом = 24?
На сколько помню в задаче два цвета: белый и черный.
Красный - это белый или черный?
Допустим белый.
Как найти проекции, думаю тебе понятно.
Берем проекцию на нижнюю строку:
4 2 4 4 4 4
Теперь идем второй частью алгоритма по этой строке:
Позиция 0: заносим в стек (0,4), где 0 - позиция, 4 - высота.
Позиция 1: текущая высота (2) меньше, чем на вершине стека, поэтому считаем площадь 4*(1-0)=4, на даный момент это максимум; снимаем с вершины значение, добавляем новое (0,2).
Позиция 2: текущая высота больше, чем на вершине стека, поэтому просто помещаем (2,4).
Позиция 3: текущая высота не меньше, чем на вершине стека, поэтому просто помещаем (3,4).
Позиция 4: текущая высота не меньше, чем на вершине стека, поэтому просто помещаем (4,4).
Позиция 5: текущая высота не меньше, чем на вершине стека, поэтому просто помещаем (5,4).
Состояние стека:
(5,4)
(4,4)
(3,4)
(2,4)
(0,2)
Последняя итерация (позиция 6):
1) снимаем с вершины стека значение и для него вычисляем площадь 4*(6-5)=4;
2) снимаем с вершины следущее значение и для него вычисляем площадь 4*(6-4)=8;
3) снимаем с вершины следущее значение и для него вычисляем площадь 4*(6-3)=12;
4) снимаем с вершины следущее значение и для него вычисляем площадь 4*(6-2)=16;
5) берем из стека последнее значение и для него вычисляем площадь 2*(6-0)=12;
Максимум, как видно, 16.
Вопросы?
Цитата:
Originally posted by Mоngооsе
Не разобрался в эффективности, только потому, что я неуверен в его правильности. А чтоб найти контрпример, нужно время, хотя бы пол часа и главное понять алгоритм.
Не разобрался в эффективности, только потому, что я неуверен в его правильности. А чтоб найти контрпример, нужно время, хотя бы пол часа и главное понять алгоритм.
Не ищи черную кошку в темной комнате потому что ее там нет :)
Цитата:
Originally posted by Green
Это бесспорно как минимум N^4.
Ты меняешь цвет ячейки, но при этом ты все равно просматриваешь её несколько раз. А с учетом копирования, можно сказать что этот алгоритм сложности N^6.
Это бесспорно как минимум N^4.
Ты меняешь цвет ячейки, но при этом ты все равно просматриваешь её несколько раз. А с учетом копирования, можно сказать что этот алгоритм сложности N^6.
Значит проход по всем элементам матрицы, надеюсь признаешь за сложность N^2, даже если это в моей программе.
Смена цвета: 1 операция. Проверка того, какой цвет может иметь матрица в наихудшем случае происходит 5 раз - это когда ячейка черная и все соседи белые или наоборот. Пусть будет суммарное число операций 35. Тогда общая сложность 36*N^2. И если N=6, то ты даже прав на счет N^4. Потом копирование. Пусть для каждого белого прямоугольника это займет 5 операций. Ты снова пишешь N^2. А если N равно хотя бы 10? В Спт 5 = 100?
Очень мило, что в твоем алгоритме, даже определение макс. площади для текущей ячейки равно 1, а в моем любой мизер это N^2 на каждом шагу. :)
Цитата:
Кстати, твоя программа использует непроинициализированную область памяти, а потому сбоит.
Если ты имеешь в виду память выделенной ф-ей VirtualAlloc, то его инициализирует папа Карло(ОС).
Цитата:
Плавающие ошибки - самые отвратительные ошибки, а их появление обычно из-за неумения структурировать и стилизировать.
Ладно, как буду иметь время сразу займусь изучением стиллистики.
Цитата:
И ещё, для чего такие нелепости с неявнем преобразованием типов: *iCurRes = (int)ipAr;
А ты попробуй без (int) и поймешь.
Цитата:
Тема, на сколько помню, была про стилистику и общие принципы программирования, а не про LabView. А по этой области я могу дать совет.
Та тема была об одном из основных фишек Buildera: property. Ты сказал, что его не нужно использовать. Я спросил, как можешь давать такие категорические советы, если ни разу на Buildere не работал? Твой ответ, подобный тому, на что я дал сылку: так хорошо знаю другие среды, что могу давать совет по любым средам разработки.
Цитата:
Да ну?
В каком цикле?
Что-то у меня складывается впечатление, что ты вообще не во что не въехал...
В каком цикле?
Что-то у меня складывается впечатление, что ты вообще не во что не въехал...
Это в алгоритме определения макс.прямоугольника для текущей ячейки. Но пока ты его не приведешь, спорить не о чем.
Цитата:
Если ты НИАСИЛИЛ понять, то это ещё не значит, что мой шедевр не рабочий.
Ты не спеши найти за что зацепиться. Для начала попробуй понять, как работает мой алгоритм. Он же прост, как две копейки.
Ты не спеши найти за что зацепиться. Для начала попробуй понять, как работает мой алгоритм. Он же прост, как две копейки.
Если о единственном шаге, которая является сложной промолчать, тогда алгоритм действительно прост как 2 копейки и макс. столько же стоит.
(1) Записать во все ячейки число белых соседей сверху, считая и тек. ячейку
(2)для каждой строки:
(3)__для каждого столбца + 1:
(4)____повторяем пока текущая высота меньше, чем на вершине стека, или если это последняя итерация:
(5)______вычисляем площадь высота, которого на вершине стека;
(6)______определяем максимальная ли это на данный момент площадь;
(7)______снимаем элемент с вершины стека;
(8)______если высота больше от выс.верш.стека, тогда помещаем в стек новую пару (ячейка, высота);
Здесь 2х неясных моментов.
1. Как определяешь макс.прямоугольник для тек. ячейки. Единственно сложный момент в этом алгоритме.
2. Стек раскрывается в конце строки. Из этого следует, что перед раскрытием она будет содержать данные разных прямоугольных областей. Смысл? И вообще, какой смысл у этого стека, кроме того, что лишние операции? Или прямоугольник опред.сразу или же записывается и определяется в конце строки.
Цитата:
Вопросы?
Те же самые, что были. Ты же на них не ответил. Способ определения макс.прямоугольника для текущей ячейки. Напр. площадь для ячейки закрашенной для выделения красным, а так он белый.
Положительный эффект от исп. стека.
Цитата:
Originally posted by Green
Это бесспорно как минимум N^4.
Ты меняешь цвет ячейки, но при этом ты все равно просматриваешь её несколько раз. А с учетом копирования, можно сказать что этот алгоритм сложности N^6.
Только я что-то не припомню, что бы ты приводил этот алгоритм.
Архисложный - это нечитабельный код, где определяется много неннужных переменных и используется большой буфер под все сразу?
Кстати, твоя программа использует непроинициализированную область памяти, а потому сбоит. Плавающие ошибки - самые отвратительные ошибки, а их появление обычно из-за неумения структурировать и стилизировать.
И ещё, для чего такие нелепости с неявнем преобразованием типов: *iCurRes = (int)ipAr;
Мой мир - планета Земля.
Нет, нельзя. Объясни.
Что-то ты не ту ссылку дал....
Тема, на сколько помню, была про стилистику и общие принципы программирования, а не про LabView. А по этой области я могу дать совет.
Да ну?
В каком цикле?
Что-то у меня складывается впечатление, что ты вообще не во что не въехал...
Если ты НИАСИЛИЛ понять, то это ещё не значит, что мой шедевр не рабочий.
Ты не спеши найти за что зацепиться. Для начала попробуй понять, как работает мой алгоритм. Он же прост, как две копейки...
...Вопросы?
Это бесспорно как минимум N^4.
Ты меняешь цвет ячейки, но при этом ты все равно просматриваешь её несколько раз. А с учетом копирования, можно сказать что этот алгоритм сложности N^6.
Только я что-то не припомню, что бы ты приводил этот алгоритм.
Архисложный - это нечитабельный код, где определяется много неннужных переменных и используется большой буфер под все сразу?
Кстати, твоя программа использует непроинициализированную область памяти, а потому сбоит. Плавающие ошибки - самые отвратительные ошибки, а их появление обычно из-за неумения структурировать и стилизировать.
И ещё, для чего такие нелепости с неявнем преобразованием типов: *iCurRes = (int)ipAr;
Мой мир - планета Земля.
Нет, нельзя. Объясни.
Что-то ты не ту ссылку дал....
Тема, на сколько помню, была про стилистику и общие принципы программирования, а не про LabView. А по этой области я могу дать совет.
Да ну?
В каком цикле?
Что-то у меня складывается впечатление, что ты вообще не во что не въехал...
Если ты НИАСИЛИЛ понять, то это ещё не значит, что мой шедевр не рабочий.
Ты не спеши найти за что зацепиться. Для начала попробуй понять, как работает мой алгоритм. Он же прост, как две копейки...
...Вопросы?
Спокойно, Green. Странно, что тебя это так сильно задело... ;)
Цитата:
Originally posted by Mоngооsе
А ты попробуй без (int) и поймешь.
А ты попробуй без (int) и поймешь.
Да я не только попробовал, но и сделал рефакторинг твоего кода, чтоб его можно было ЧИТАТЬ.
Меня порадовало, что ты выделяешь в конце каждой строки ещё по три элемента, хотя вполне достаточно двух (один в начале, один в конце). Это наверное для надежности? :D
Кстати, используемый тобой метод прохода по массиву без проверки диапазона массива путем помещения концевого элемента, называется "часовой".
Я обратно свернул развернутую тобой рекурсию. Это чтоб не было иллюзий по поводу сложности.
И так твой алгоритм:
Код:
// Определение
struct Algorithm
{
struct Point
{
int x, y;
Point(int x, int y) :x(x), y(y) {}
};
Algorithm(int* box, int size);
void findMaxField();
void walk(int x, int y);
vector< vector<int> > field;
vector<Point> curField;
vector<Point> maxField;
};
struct Algorithm
{
struct Point
{
int x, y;
Point(int x, int y) :x(x), y(y) {}
};
Algorithm(int* box, int size);
void findMaxField();
void walk(int x, int y);
vector< vector<int> > field;
vector<Point> curField;
vector<Point> maxField;
};
Код:
// Реализация
Algorithm::Algorithm(int* pBox, int size)
: field(size+2, vector<int>(size+2, 0))
{
for(int y=1; y<=size; ++y)
{
for(int x=1; x<=size; ++x)
{
field[x][y] = *pBox;
++pBox;
}
}
}
void Algorithm::walk(int x, int y)
{
if(field[x][y]==1)
{
field[x][y] = 0;
curField.push_back( Point(x,y) );
walk(x+1, y);
walk(x-1, y);
walk(x, y+1);
walk(x, y-1);
}
}
void Algorithm::findMaxField()
{
for(int y=1; y<field[0].size()-1; ++y)
{
for(int x=1; x<field.size()-1; ++x)
{
curField.clear();
walk(x, y);
if(maxField.size() < curField.size()) {
maxField = curField;
}
}
}
}
Algorithm::Algorithm(int* pBox, int size)
: field(size+2, vector<int>(size+2, 0))
{
for(int y=1; y<=size; ++y)
{
for(int x=1; x<=size; ++x)
{
field[x][y] = *pBox;
++pBox;
}
}
}
void Algorithm::walk(int x, int y)
{
if(field[x][y]==1)
{
field[x][y] = 0;
curField.push_back( Point(x,y) );
walk(x+1, y);
walk(x-1, y);
walk(x, y+1);
walk(x, y-1);
}
}
void Algorithm::findMaxField()
{
for(int y=1; y<field[0].size()-1; ++y)
{
for(int x=1; x<field.size()-1; ++x)
{
curField.clear();
walk(x, y);
if(maxField.size() < curField.size()) {
maxField = curField;
}
}
}
}
Код:
// Пример спользования
int sourceField[10][10] = {
0, 0, 1, 0, 0, 0, 1, 1, 0, 0,
0, 1, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 1, 0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
1, 0, 0, 1, 0, 1, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 1, 0, 1, 0
};
int main(int argc, char* argv[])
{
Algorithm alg(sourceField[0], sizeof(sourceField)/sizeof(sourceField[0]) );
alg.findMaxField();
cout << "Cell number: " << alg.maxField.size() << endl;
for(int k=0; k < alg.maxField.size(); ++k)
{
cout << "cell (" << alg.maxField[k].x << ','
<< alg.maxField[k].y << ')' << endl;
}
return 0;
}
int sourceField[10][10] = {
0, 0, 1, 0, 0, 0, 1, 1, 0, 0,
0, 1, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 1, 0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
1, 0, 0, 1, 0, 1, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 1, 0, 1, 0
};
int main(int argc, char* argv[])
{
Algorithm alg(sourceField[0], sizeof(sourceField)/sizeof(sourceField[0]) );
alg.findMaxField();
cout << "Cell number: " << alg.maxField.size() << endl;
for(int k=0; k < alg.maxField.size(); ++k)
{
cout << "cell (" << alg.maxField[k].x << ','
<< alg.maxField[k].y << ')' << endl;
}
return 0;
}
Как теперь могут посмотреть другие, твой архисложный алгоритм весьма прост.
Ты идещь по всем ячейкам (вложение циклов в методе Algorithm::findMaxField) и для каждой белой крестообразно итерационно смотришь нет ли вокруг ещё белых ячеек. Т.о. выделяешь белые области.
Самая повторяющаяся часть здесь это рекурсивный метод Algorithm::walk. Для справедливости я посчитал только количество раз выполнения кода кода внутри условного оператора этого метода.
Да, я ошибся. Там не N^4, а в общем случае N^3, и лишь в лудшем случае N^2.
Но это только нахождение белых областей.
Хотелось бы посмотреть, что ты с ними будешь делать дальше, ведь условие задачи совсем другое.
Как вообще можно спорить о эффективности своего алгоритма, если он не делает того, что нужно по условию?
Цитата:
Originally posted by Mоngооsе
Твой ответ, подобный тому, на что я дал сылку: так хорошо знаю другие среды, что могу давать совет по любым средам разработки.
Твой ответ, подобный тому, на что я дал сылку: так хорошо знаю другие среды, что могу давать совет по любым средам разработки.
Ты плохо читающий или слабо понимающий?
Мой ответ был, что я хорошо знаю основы и принципы программирования, поэтому могу давать общие советы, не зависимо от конкретной области применения.
Но мне кажется этот пост не об этом. Хочешь поразглагольствовать на эту тему, заведи отдельную ветку.
Цитата:
Originally posted by Mоngооsе
Если о единственном шаге, которая является сложной промолчать, тогда алгоритм действительно прост как 2 копейки и макс. столько же стоит.
Здесь 2х неясных моментов.
1. Как определяешь макс.прямоугольник для тек. ячейки. Единственно сложный момент в этом алгоритме.
2. Стек раскрывается в конце строки. Из этого следует, что перед раскрытием она будет содержать данные разных прямоугольных областей. Смысл? И вообще, какой смысл у этого стека, кроме того, что лишние операции? Или прямоугольник опред.сразу или же записывается и определяется в конце строки.
Если о единственном шаге, которая является сложной промолчать, тогда алгоритм действительно прост как 2 копейки и макс. столько же стоит.
Здесь 2х неясных моментов.
1. Как определяешь макс.прямоугольник для тек. ячейки. Единственно сложный момент в этом алгоритме.
2. Стек раскрывается в конце строки. Из этого следует, что перед раскрытием она будет содержать данные разных прямоугольных областей. Смысл? И вообще, какой смысл у этого стека, кроме того, что лишние операции? Или прямоугольник опред.сразу или же записывается и определяется в конце строки.
Из этого следует, что ты совершенно не врубился в алгоритм, в отличие от других (Rebbit,REmindER).
Тогда какого ты споришь?
Спросил бы сначала, постарался понять, а не кричал бы об неэффективности моего алгоритма и крутости своего, который, кстати, решает другую задачу... :D
Вот реализация моего алгоритма.
Я там не использовал один огромный массив под входные, выходные и промежуточные данные разных типов, ты уж извини... :D
Кстати, у тебя такая привычка от бейсика осталась? Без сарказма, от куда у тебя такая одержимость валить всё в одну кучу?
И так алгоритм:
Код:
// Определение
class Algorithm
{
public:
static int findMaxArea(int* source, int sizeX, int sizeY);
private:
struct StackElement
{
int x;
int height;
StackElement(int x, int height) :x(x), height(height) {}
};
Algorithm(int* source, int sizeX, int sizeY);
void calcProjections();
void rollbackStack(int x, int height);
void processProjections();
vector< vector<int> > field;
vector<StackElement> stack;
int maxArea;
};
class Algorithm
{
public:
static int findMaxArea(int* source, int sizeX, int sizeY);
private:
struct StackElement
{
int x;
int height;
StackElement(int x, int height) :x(x), height(height) {}
};
Algorithm(int* source, int sizeX, int sizeY);
void calcProjections();
void rollbackStack(int x, int height);
void processProjections();
vector< vector<int> > field;
vector<StackElement> stack;
int maxArea;
};
Код:
// Реализация
Algorithm::Algorithm(int* source, int sizeX, int sizeY)
: field(sizeX, vector<int>(sizeY, 0)), maxArea(0)
{
for(int y=0; y<sizeY; ++y)
{
for(int x=0; x<sizeX; ++x)
{
field[x][y] = *source;
++source;
}
}
}
void Algorithm::calcProjections()
{
for(int x=0; x<field.size(); ++x)
{
for(int y=1; y<field[0].size(); ++y)
{
if(field[x][y]) {
field[x][y] = field[x][y-1]+1;
}
}
}
}
void Algorithm::rollbackStack(int x, int height)
{
while(height < stack.back().height)
{
int area = stack.back().height * (x - stack.back().x);
stack.pop_back();
if(area > maxArea) maxArea = area;
}
}
void Algorithm::processProjections()
{
for(int y=0; y<field[0].size(); ++y)
{
stack.clear();
stack.push_back( StackElement(0,0) );
for(int x=0; x<field.size(); ++x)
{
rollbackStack(x, field[x][y]);
stack.push_back( StackElement(x, field[x][y]) );
}
rollbackStack(field.size(), 0);
}
}
int Algorithm::findMaxArea(int* source, int sizeX, int sizeY)
{
Algorithm alg(source, sizeX, sizeY);
alg.calcProjections(); // first step
alg.processProjections(); // second step
return alg.maxArea;
}
Algorithm::Algorithm(int* source, int sizeX, int sizeY)
: field(sizeX, vector<int>(sizeY, 0)), maxArea(0)
{
for(int y=0; y<sizeY; ++y)
{
for(int x=0; x<sizeX; ++x)
{
field[x][y] = *source;
++source;
}
}
}
void Algorithm::calcProjections()
{
for(int x=0; x<field.size(); ++x)
{
for(int y=1; y<field[0].size(); ++y)
{
if(field[x][y]) {
field[x][y] = field[x][y-1]+1;
}
}
}
}
void Algorithm::rollbackStack(int x, int height)
{
while(height < stack.back().height)
{
int area = stack.back().height * (x - stack.back().x);
stack.pop_back();
if(area > maxArea) maxArea = area;
}
}
void Algorithm::processProjections()
{
for(int y=0; y<field[0].size(); ++y)
{
stack.clear();
stack.push_back( StackElement(0,0) );
for(int x=0; x<field.size(); ++x)
{
rollbackStack(x, field[x][y]);
stack.push_back( StackElement(x, field[x][y]) );
}
rollbackStack(field.size(), 0);
}
}
int Algorithm::findMaxArea(int* source, int sizeX, int sizeY)
{
Algorithm alg(source, sizeX, sizeY);
alg.calcProjections(); // first step
alg.processProjections(); // second step
return alg.maxArea;
}
Код:
// Пример использования для твоей матрицы
// и для матрицы, на котором ты пытаешься завалить мой алгоритм
int sourceField10[10][10] = {
0, 0, 1, 0, 0, 0, 1, 1, 0, 0,
0, 1, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 1, 0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
1, 0, 0, 1, 0, 1, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 1, 0, 1, 0
};
int sourceField7x5[7][5] = {
0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 0, 1,
0, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 1,
};
int main(int argc, char* argv[])
{
cout << "max area 10x10: " << Algorithm::findMaxArea(sourceField10[0], 10, 10) << endl;
cout << "max area 7x5: " << Algorithm::findMaxArea(sourceField7x5[0], 7, 5) << endl;
return 0;
}
// и для матрицы, на котором ты пытаешься завалить мой алгоритм
int sourceField10[10][10] = {
0, 0, 1, 0, 0, 0, 1, 1, 0, 0,
0, 1, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 1, 0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
1, 0, 0, 1, 0, 1, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 1, 0, 1, 0
};
int sourceField7x5[7][5] = {
0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 0, 1,
0, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 1,
};
int main(int argc, char* argv[])
{
cout << "max area 10x10: " << Algorithm::findMaxArea(sourceField10[0], 10, 10) << endl;
cout << "max area 7x5: " << Algorithm::findMaxArea(sourceField7x5[0], 7, 5) << endl;
return 0;
}
Думаю, код понятен, но для тех, кто в танке...
В методе Algorithm::findMaxArea вызывается два метода, которые являются реализацией первого и второго шагов описанного ранее алгоритма, соотв-но.
На первом шаге (Algorithm::calcProjections) вычисляются проекции. За комментариями обратись к первым постам ветки.
На втором шаге (Algorithm::processProjections) построчно обрабатываются проекции и вовсю используется, ненужный на твой взгляд, стек.
Первый шаг имеет сложность N^2. Спорить будешь?
На втором шаге самая повторяющаяся часть это метод (Algorithm::rollbackStack). Это как раз раскрутка стека. И общая сложность здесь не выше N^2. Спорить будешь?
Кстати, заметь алгоритм ищет то, что нужно по условию задачи, а не играет в "крестики-нолики". :D
Цитата:
Originally posted by Mоngооsе
Те же самые, что были. Ты же на них не ответил. Способ определения макс.прямоугольника для текущей ячейки. Напр. площадь для ячейки закрашенной для выделения красным, а так он белый.
Положительный эффект от исп. стека.
Те же самые, что были. Ты же на них не ответил. Способ определения макс.прямоугольника для текущей ячейки. Напр. площадь для ячейки закрашенной для выделения красным, а так он белый.
Положительный эффект от исп. стека.
Ну если ты и на примере конкретной реализации не поймешь, то это уже паталогия. ;)
P.S. Если кому-то непонятно, то в конструкторе Algorithm::Algorithm как в первом, так и во втором алгоритме происходит просто копирование пришедших данных (матрицы) во внутренний массив.
Сперва о менее важном. Об усовершенствованной версии моей программы.
Конечно, благодаря тебе, код стал таким красивым, что глаза радует.
А если его стилистику видел бы Цицерон, то от зависти наверно покончил бы с собой.
Respect.
Двух маленьких замечаний.
1. Двойной цикл, с 1 по 9 в обоих циклах.
матрица имеет вид
Я не проверял на компе, но исходя из исходного кода
думаю, что твоя прога вернет, что в матрице нет белых
прямоугольников.
Не сможешь это проверить? И мимоходом и мою прогу.
Если моя выдает правильный результат, а твоя нет, то сможем
сделать заключение, что ты испортил даже то, что работало. :)
Второе замечание. Вроде требовалась эффективная программа.
Но в твоей проге, для ячейки в любом случае вызывается ф-ия,
и уже внутри ф-ии определяется, нужен был ли этот вызов.
Потом всюду индексы (x,y). У меня указатель. Переход от текущей
ячейки к любой соседней, это одна операция. А у тебя, вызов ф-ии,
и по x и y находится конкретный элемент вектора. Сколько это требует
операций в STL, не знаю. Но во всяком случае, намного больше операций,
чем непосредственный доступ к элементам памяти.
Мы так по разному определяем сложность алгоритма, что лучше я напишу
как я определяю сложность. Может это я ошибаюсь.
Если есть матрица N*N, тогда сложность алгоритма просто перебирающего
все его элементы равна N^2. Допустим входе перебора, для конкретного элемента в
зависимости от его значения выпоняется 5 или 10 или 20 операций. Эти операции не
зависят от значения N. Тогда наихудшая сложность такого алгоритма равно 20*N^2.
Ты определил для конкретного случая N^3. Т.е. Было выполнено 1000 условных операций,
в среднем 10 операций при каждой итерации, значит сложность = 10*N^2.
А теперь твой шедевр.
Constructor - ясен
calcProjections - тоже ясна.
rollBackStack - мда...
processProjections - ясно, правильно, делает неправильную работу.
В processProjections ставляешь в стек пару: координата по X и высота.
Потом для каждого последующего элемента вычисляется область по формуле
На человеческом языке: высота ячейки находящийся на вершине стека умножается
на растояние между двумя ячейками, если высота текущей ячейки меньше высоты ячейки,
находящегося на вершине стека.
Вместо
явно нужен
или что-то другое. Нужно бы исправить. После этого я бы посмотрел,
что из-за того, что стек раскрывается в конце, не вычисляется ли площадь
для таких ячеек, между которыми черные ячейки. И по правде говоря stack.pop_back(); в rollbackStack мне тоже не нравится.
Конечно, благодаря тебе, код стал таким красивым, что глаза радует.
А если его стилистику видел бы Цицерон, то от зависти наверно покончил бы с собой.
Respect.
Двух маленьких замечаний.
1. Двойной цикл, с 1 по 9 в обоих циклах.
матрица имеет вид
Код:
int sourceField[10][10] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
Я не проверял на компе, но исходя из исходного кода
думаю, что твоя прога вернет, что в матрице нет белых
прямоугольников.
Не сможешь это проверить? И мимоходом и мою прогу.
Если моя выдает правильный результат, а твоя нет, то сможем
сделать заключение, что ты испортил даже то, что работало. :)
Второе замечание. Вроде требовалась эффективная программа.
Но в твоей проге, для ячейки в любом случае вызывается ф-ия,
и уже внутри ф-ии определяется, нужен был ли этот вызов.
Потом всюду индексы (x,y). У меня указатель. Переход от текущей
ячейки к любой соседней, это одна операция. А у тебя, вызов ф-ии,
и по x и y находится конкретный элемент вектора. Сколько это требует
операций в STL, не знаю. Но во всяком случае, намного больше операций,
чем непосредственный доступ к элементам памяти.
Мы так по разному определяем сложность алгоритма, что лучше я напишу
как я определяю сложность. Может это я ошибаюсь.
Если есть матрица N*N, тогда сложность алгоритма просто перебирающего
все его элементы равна N^2. Допустим входе перебора, для конкретного элемента в
зависимости от его значения выпоняется 5 или 10 или 20 операций. Эти операции не
зависят от значения N. Тогда наихудшая сложность такого алгоритма равно 20*N^2.
Ты определил для конкретного случая N^3. Т.е. Было выполнено 1000 условных операций,
в среднем 10 операций при каждой итерации, значит сложность = 10*N^2.
А теперь твой шедевр.
Constructor - ясен
calcProjections - тоже ясна.
rollBackStack - мда...
processProjections - ясно, правильно, делает неправильную работу.
В processProjections ставляешь в стек пару: координата по X и высота.
Потом для каждого последующего элемента вычисляется область по формуле
Код:
while(height < stack.back().height)
{
int area = stack.back().height * (x - stack.back().x);
...
}
{
int area = stack.back().height * (x - stack.back().x);
...
}
На человеческом языке: высота ячейки находящийся на вершине стека умножается
на растояние между двумя ячейками, если высота текущей ячейки меньше высоты ячейки,
находящегося на вершине стека.
Вместо
Код:
while(height < stack.back().height)
{
int area = stack.back().height * (x - stack.back().x);
...
}
{
int area = stack.back().height * (x - stack.back().x);
...
}
Код:
while(height <[color=red]=[/color] stack.back().height)
{
int area = height * (x - stack.back().x + 1);
...
}
{
int area = height * (x - stack.back().x + 1);
...
}
что из-за того, что стек раскрывается в конце, не вычисляется ли площадь
для таких ячеек, между которыми черные ячейки. И по правде говоря stack.pop_back(); в rollbackStack мне тоже не нравится.
Цитата:
Originally posted by Mоngооsе
Сперва о менее важном. Об усовершенствованной версии моей программы.
Конечно, благодаря тебе, код стал таким красивым, что глаза радует.
А если его стилистику видел бы Цицерон, то от зависти наверно покончил бы с собой.
Respect.
Сперва о менее важном. Об усовершенствованной версии моей программы.
Конечно, благодаря тебе, код стал таким красивым, что глаза радует.
А если его стилистику видел бы Цицерон, то от зависти наверно покончил бы с собой.
Respect.
Спасибо, за лестный отзыв. :)
Цитата:
Originally posted by Mоngооsе
Я не проверял на компе, но исходя из исходного кода
думаю, что твоя прога вернет, что в матрице нет белых
прямоугольников.
Не сможешь это проверить?
Я не проверял на компе, но исходя из исходного кода
думаю, что твоя прога вернет, что в матрице нет белых
прямоугольников.
Не сможешь это проверить?
Мой вариант твоего алгоритма вернул все правильно.
Думаю, свой вариант ты можешь проверить сам.
Цитата:
Originally posted by Mоngооsе
Если моя выдает правильный результат, а твоя нет, то сможем
сделать заключение, что ты испортил даже то, что работало. :)
Если моя выдает правильный результат, а твоя нет, то сможем
сделать заключение, что ты испортил даже то, что работало. :)
Ты обладаешь сокровенным знанием о TDD и рефакторинге?
Видимо, нет. Иначе ты бы знал, что перед началом рефакторинга пишутся тесты, которые запускаются на каждом шаге рефакторинга.
Единственное, что мне пришлось изменить индексы возвращаемые твоей прогой, т.к. ты неправильно их вычисляешь, в результате чего есть к примеру индекс 11 в строке из 10 элементов.
Цитата:
Originally posted by Mоngооsе
Второе замечание. Вроде требовалась эффективная программа.
Но в твоей проге, для ячейки в любом случае вызывается ф-ия,
и уже внутри ф-ии определяется, нужен был ли этот вызов.
Потом всюду индексы (x,y). У меня указатель. Переход от текущей
ячейки к любой соседней, это одна операция. А у тебя, вызов ф-ии,
и по x и y находится конкретный элемент вектора. Сколько это требует
операций в STL, не знаю. Но во всяком случае, намного больше операций,
чем непосредственный доступ к элементам памяти.
Второе замечание. Вроде требовалась эффективная программа.
Но в твоей проге, для ячейки в любом случае вызывается ф-ия,
и уже внутри ф-ии определяется, нужен был ли этот вызов.
Потом всюду индексы (x,y). У меня указатель. Переход от текущей
ячейки к любой соседней, это одна операция. А у тебя, вызов ф-ии,
и по x и y находится конкретный элемент вектора. Сколько это требует
операций в STL, не знаю. Но во всяком случае, намного больше операций,
чем непосредственный доступ к элементам памяти.
Во-первых, требовался оптимальный по сложности (скорости) АЛГОРИТМ, о реализации пока речи не было.
Во-вторых, ты имеещь представление об XP ? Видимо, нет, иначе ты бы знал, что вначале пишется алгоритм, дающий верный результат, а потом уже он оптимизируется. Твой алгоритм пока не дает результата вовсе. Если помнишь результатом должно было быть максимальная площадь.
В-третьих, по поводу проверки ячейки и вызова метода. Это свернутая, развернутая вначале тобой, рекурсия. Если сможешь её реализовать без проверки внутри, то продемонстрируй (без раскручивания рекурсии). Кроме того, особого выигрыша в скорости это не дает, т.к. компилятор и сам может эту структуру раскрутить.
В-четвертых, вектора введены лишь для простоты реализации, чтоб не отвлекаться на заведение массивов. При этом не используется специфичная для векторов функциональность (reasize и т.п.), т.о. вектора пи необходимости могут быть легко заменены массивами, а индексная адрессация, адресацией через указатели, но это не будет иметь значения, т.к. в простейших циклах (как видишь я преобразовал все к простейшим циклам) компилятор будет использовать приращение указателей.
Но это всё оптимизация, а она имеет место после получения рабочего алгоритма, профилирования и выяснения необходимости оптимизации конкретных мест реализации.
Цитата:
Originally posted by Mоngооsе
в среднем 10 операций при каждой итерации, значит сложность = 10*N^2.
в среднем 10 операций при каждой итерации, значит сложность = 10*N^2.
Хорошо, пусть будет N^2, это все равно ничего не меняет, т.к. действия твоего алгоритма в большинстве случаев бессмыслены в контексте решения поставленной задачи. Ну нашел ты область белого прямоугольника, это ничего не дало. Например, весь квадрат был белым, ты нашел всю белую область, но это не сколько не приблизило тебя к нахождению его площади. Ты сможешь это оспорить, только тогда, когда приведешь следующую часть алгоритма, которая собственно находит площадь.
Цитата:
Originally posted by Mоngооsе
Вместо
явно нужен
или что-то другое. Нужно бы исправить. После этого я бы посмотрел,
Вместо
Код:
while(height < stack.back().height)
{
int area = stack.back().height * (x - stack.back().x);
...
}
{
int area = stack.back().height * (x - stack.back().x);
...
}
Код:
while(height < stack.back().height)
{
int area = height * (x - stack.back().x + 1);
...
}
{
int area = height * (x - stack.back().x + 1);
...
}
А ты бы посмотрел сначала...
Код написан правильно. Вся проблема в том, что ты так и не понял алгоритма.
Цитата:
Originally posted by Mоngооsе
что из-за того, что стек раскрывается в конце, не вычисляется ли площадь
для таких ячеек, между которыми черные ячейки.
что из-за того, что стек раскрывается в конце, не вычисляется ли площадь
для таких ячеек, между которыми черные ячейки.
Представь себе нет.
Запусти программу и убедись сам.
Цитата:
Originally posted by Mоngооsе
И по правде говоря stack.pop_back(); в rollbackStack мне тоже не нравится.
И по правде говоря stack.pop_back(); в rollbackStack мне тоже не нравится.
Это чем же он тебе не нравится :)
Пришлесь проверить твою прогу. Не заметил, что рабочая матрица содержит окаймляющие 0-ые столбцы и строки по бокам, как и у меня, поэтому его размерность 12. Поэтому цикл с 1 по 10. А не с 1 по 9.
Ok.
А теперь твой алгоритм.
Есть матрица
1, 0,
1, 1,
1, 1,
1, 1
После calcProjection
1, 0,
2, 1,
3, 2,
4, 3
Итерация для последней строки
стек: (0, 0)
стек: (0, 0) : (0, 4)
для (1,3) вычисляется area
area = 4 * (1 - 0) = 4
убирается (0, 4) ставится (1, 3)
так называемое раскрытие стека элементом (2, 0)
area = 3 * (2 - 1) = 3.
Это я на бумаге. Может комп. найдет правильную величину.
Ok.
А теперь твой алгоритм.
Есть матрица
1, 0,
1, 1,
1, 1,
1, 1
После calcProjection
1, 0,
2, 1,
3, 2,
4, 3
Итерация для последней строки
стек: (0, 0)
стек: (0, 0) : (0, 4)
для (1,3) вычисляется area
area = 4 * (1 - 0) = 4
убирается (0, 4) ставится (1, 3)
так называемое раскрытие стека элементом (2, 0)
area = 3 * (2 - 1) = 3.
Это я на бумаге. Может комп. найдет правильную величину.
Цитата:
Originally posted by Mоngооsе
А теперь твой алгоритм.
Есть матрица
1, 0,
1, 1,
1, 1,
1, 1
После calcProjection
1, 0,
2, 1,
3, 2,
4, 3
Итерация для последней строки
стек: (0, 0)
стек: (0, 0) : (0, 4)
для (1,3) вычисляется area
area = 4 * (1 - 0) = 4
убирается (0, 4) ставится (1, 3)
так называемое раскрытие стека элементом (2, 0)
area = 3 * (2 - 1) = 3.
Это я на бумаге. Может комп. найдет правильную величину.
А теперь твой алгоритм.
Есть матрица
1, 0,
1, 1,
1, 1,
1, 1
После calcProjection
1, 0,
2, 1,
3, 2,
4, 3
Итерация для последней строки
стек: (0, 0)
стек: (0, 0) : (0, 4)
для (1,3) вычисляется area
area = 4 * (1 - 0) = 4
убирается (0, 4) ставится (1, 3)
так называемое раскрытие стека элементом (2, 0)
area = 3 * (2 - 1) = 3.
Это я на бумаге. Может комп. найдет правильную величину.
Согласен, это баг, проявляющийся при убывающих функциях.
Начало белой области должно оставаться неизменным при раскрутке стека.
Исправил:
Код:
int Algorithm::rollbackStack(int x, int height)
{
int actualX = x;
while(height < stack.back().height)
{
actualX = stack.back().x;
int area = stack.back().height * (x - actualX);
stack.pop_back();
if(area > maxArea) maxArea = area;
}
return actualX;
}
void Algorithm::processProjections()
{
for(int y=0; y<field[0].size(); ++y)
{
stack.clear();
stack.push_back( StackElement(0,0) );
for(int x=0; x<field.size(); ++x)
{
int height = field[x][y];
stack.push_back( StackElement(rollbackStack(x, height), height) );
}
rollbackStack(field.size(), 0);
}
}
{
int actualX = x;
while(height < stack.back().height)
{
actualX = stack.back().x;
int area = stack.back().height * (x - actualX);
stack.pop_back();
if(area > maxArea) maxArea = area;
}
return actualX;
}
void Algorithm::processProjections()
{
for(int y=0; y<field[0].size(); ++y)
{
stack.clear();
stack.push_back( StackElement(0,0) );
for(int x=0; x<field.size(); ++x)
{
int height = field[x][y];
stack.push_back( StackElement(rollbackStack(x, height), height) );
}
rollbackStack(field.size(), 0);
}
}
Ok. Принимаю наслово(но вечером проверю). Тогда можно посмотреть на stack.pop_back(); в rollbackStack.
Из-за того, что она так безапеляционно выталкивает элементы, мне кажется, что прога
неправильно вычисляет макс. область для
0, 1, 0
1, 1, 1
И мне не верится, что этот алгоритм можно закодировать таким образом, чтоб она правильно вычисляла область для
1, 0, 1
1, 1, 1
Из-за того, что она так безапеляционно выталкивает элементы, мне кажется, что прога
неправильно вычисляет макс. область для
0, 1, 0
1, 1, 1
И мне не верится, что этот алгоритм можно закодировать таким образом, чтоб она правильно вычисляла область для
1, 0, 1
1, 1, 1
Цитата:
Originally posted by Mоngооsе
Ok. Принимаю наслово(но вечером проверю).
Ok. Принимаю наслово(но вечером проверю).
Скрестил пальцы до вечера... :D
Хотя сам я себе наслово не поверил и всё уже проверил.
Цитата:
Originally posted by Mоngооsе
Тогда можно посмотреть на stack.pop_back(); в rollbackStack.
Из-за того, что она так безапеляционно выталкивает элементы, мне кажется, что прога
неправильно вычисляет макс. область для
0, 1, 0
1, 1, 1
И мне не верится, что этот алгоритм можно закодировать таким образом, чтоб она правильно вычисляла область для
1, 0, 1
1, 1, 1
Тогда можно посмотреть на stack.pop_back(); в rollbackStack.
Из-за того, что она так безапеляционно выталкивает элементы, мне кажется, что прога
неправильно вычисляет макс. область для
0, 1, 0
1, 1, 1
И мне не верится, что этот алгоритм можно закодировать таким образом, чтоб она правильно вычисляла область для
1, 0, 1
1, 1, 1
Можешь не верить в это ЧУДО, но прога правильно вычисляет площади для обоих случаев.
Когда мы будем обсуждать твой алгоритм?
Точнее, когда ты представишь нам заключительную часть твоего алгоритма?
Цитата:
Originally posted by Mоngооsе
Sorry. Пример для rollbackStack привел неправильный
1, 0, 0,
1, 1, 1,
1, 1, 1,
Sorry. Пример для rollbackStack привел неправильный
1, 0, 0,
1, 1, 1,
1, 1, 1,
Да ничего-ничего, и это работает.
Цитата:
Originally posted by Green
Да ничего-ничего, и это работает.
Да ничего-ничего, и это работает.
Угу. И в предыдущей версии она работала? :)
Я предполагал, что ты так исправишь код, как я советовал. Даже толком не посмотрел. Только теперь заметил изменение в processProjections:
stack.push_back( StackElement(rollbackStack(x, height), height) );
Но правильно площадь вычисляетя, только при конечном раскрытии. Очень подозрительно.
0, 1, 1, 0
0, 1, 1, 0
0, 1, 1, 0
1, 1, 1, 1
1, 1, 1, 1
Твоя прога какой результат возвращает?
А мой алгоритм обсуждать не будем. Наперед знаю твое мнение: "Этот алгоритм, полная халтура, в ней нет композиции, структуры. И в ней нарушаются принципы Аристотеля" ((C) Adams Family).
На счет
0, 1, 1, 0
0, 1, 1, 0
0, 1, 1, 0
1, 1, 1, 1
1, 1, 1, 1
вопрос снят. stack.push_back( StackElement(rollbackStack(x, height), height) );
исправляет все два бага.
0, 1, 1, 0
0, 1, 1, 0
0, 1, 1, 0
1, 1, 1, 1
1, 1, 1, 1
вопрос снят. stack.push_back( StackElement(rollbackStack(x, height), height) );
исправляет все два бага.
Цитата:
Originally posted by Mоngооsе
Угу. И в предыдущей версии она работала? :)
Угу. И в предыдущей версии она работала? :)
Ну я же признал, что допустил баг, который быстро исправил.
Цитата:
Originally posted by Mоngооsе
Я предполагал, что ты так исправишь код, как я советовал.
Я предполагал, что ты так исправишь код, как я советовал.
Наверное трудно советовать изменить реализацию алгоритма, который не понимаешь? ;)
Цитата:
Originally posted by Mоngооsе
Твоя прога какой результат возвращает?
Твоя прога какой результат возвращает?
Правильный, т.е. 10.
Цитата:
Originally posted by Mоngооsе
А мой алгоритм обсуждать не будем. Наперед знаю твое мнение: "Этот алгоритм, полная халтура, в ней нет композиции, структуры. И в ней нарушаются принципы Аристотеля" ((C) Adams Family).
А мой алгоритм обсуждать не будем. Наперед знаю твое мнение: "Этот алгоритм, полная халтура, в ней нет композиции, структуры. И в ней нарушаются принципы Аристотеля" ((C) Adams Family).
А вот это зря. Сдаешься без боя. А вдруг ты действительно нашел более оптимальное (по сложности) решение.
Мы же алгоритм будем обсуждать, а не реализацию.
Кроме того, получается что у предложенного мной алгоритма нет опонентов...
Победил из-за отсутствия соперника...
Грустно...
Цитата:
Originally posted by Green
Мы же алгоритм будем обсуждать, а не реализацию.Кроме того, получается что у предложенного мной алгоритма нет опонентов...
Победил из-за отсутствия соперника...
Грустно...
Мы же алгоритм будем обсуждать, а не реализацию.Кроме того, получается что у предложенного мной алгоритма нет опонентов...
Победил из-за отсутствия соперника...
Грустно...
Green, в данный момент у меня открыто 4 проекта в Visual C (2 windows service, 1 dll вызываемый из FoxPro программы, и одна нормальная прога оформлена ala OutLook Express) и 2 проекта Visual FoxPro (нормальная прога и Com Server). Все эти программы довольно тесно с друг другом взаимодействуют.
Ты ломаешь над этой прогой голову уже более 2 недели. И в первом посту ни о каком турнире речи не шло. Там вроде ставился вопрос, кто может мне помочь? На счет помощи я откликнулся, но если шла бы речь о том, что "ану посоревнуемся, кто выдумает лучший алгоритм," (или как ты любишь выражатся более вульгарно, "ану померяемся..." :)) то я бы промолчал, так как кроме этой основной работы, есть и другие (напр. вчера по просьбе трудящихся, дописал код к одной своей старой проге), да еще кое-что нужно выучить.
Я бы то же мог ехидничать, что ты бил себе грудь, что прога правильна, пока я не указал тебе контр. пример.
Но если хочешь лучший алгоритм, чем твой, тогда лови:
Код:
class Algorithm
{
public:
static int findMaxArea(int* source, int sizeX, int sizeY);
private:
struct StackElement
{
int x;
int height;
StackElement(int x, int height) : x(x), height(height) {}
};
Algorithm(int* source, int sizeX, int sizeY);
void calcProjections();
void rollbackStack(int x, int height);
void processProjections();
vector< vector<int> > field;
vector<StackElement> stack;
int maxArea;
int curHeight;
};
--------------------------------------------------------------------------------
code:--------------------------------------------------------------------------------
// Реализация
Algorithm::Algorithm(int* source, int sizeX, int sizeY)
: field(sizeX, vector<int>(sizeY, 0)), maxArea(0)
{
for(int y=0; y<sizeY; ++y)
{
for(int x=0; x<sizeX; ++x)
{
field[x][y] = *source;
++source;
}
}
}
void Algorithm::calcProjections()
{
for(int x=0; x<field.size(); ++x)
{
for(int y=1; y<field[0].size(); ++y)
{
if(field[x][y]) {
field[x][y] = field[x][y-1]+1;
}
}
}
}
int Algorithm::rollbackStack(int x, int height)
{
int actualX = x;
while(height < stack.back().height)
{
actualX = stack.back().x;
int area = stack.back().height * (x - actualX);
stack.pop_back();
if(area > maxArea) maxArea = area;
}
return actualX;
}
void Algorithm::processProjections()
{
for(int y=0; y<field[0].size(); ++y)
{
stack.clear();
curHeight = 0;
stack.push_back( StackElement(0,0) );
for(int x=0; x<field.size(); ++x)
{
int height = field[x][y];
if(height!=curHeight)
{
stack.push_back( StackElement(rollbackStack(x, height), height) );
curHeight = height;
}
}
rollbackStack(field.size(), 0);
}
}
int Algorithm::findMaxArea(int* source, int sizeX, int sizeY)
{
Algorithm alg(source, sizeX, sizeY);
alg.calcProjections(); // first step
alg.processProjections(); // second step
return alg.maxArea;
}
{
public:
static int findMaxArea(int* source, int sizeX, int sizeY);
private:
struct StackElement
{
int x;
int height;
StackElement(int x, int height) : x(x), height(height) {}
};
Algorithm(int* source, int sizeX, int sizeY);
void calcProjections();
void rollbackStack(int x, int height);
void processProjections();
vector< vector<int> > field;
vector<StackElement> stack;
int maxArea;
int curHeight;
};
--------------------------------------------------------------------------------
code:--------------------------------------------------------------------------------
// Реализация
Algorithm::Algorithm(int* source, int sizeX, int sizeY)
: field(sizeX, vector<int>(sizeY, 0)), maxArea(0)
{
for(int y=0; y<sizeY; ++y)
{
for(int x=0; x<sizeX; ++x)
{
field[x][y] = *source;
++source;
}
}
}
void Algorithm::calcProjections()
{
for(int x=0; x<field.size(); ++x)
{
for(int y=1; y<field[0].size(); ++y)
{
if(field[x][y]) {
field[x][y] = field[x][y-1]+1;
}
}
}
}
int Algorithm::rollbackStack(int x, int height)
{
int actualX = x;
while(height < stack.back().height)
{
actualX = stack.back().x;
int area = stack.back().height * (x - actualX);
stack.pop_back();
if(area > maxArea) maxArea = area;
}
return actualX;
}
void Algorithm::processProjections()
{
for(int y=0; y<field[0].size(); ++y)
{
stack.clear();
curHeight = 0;
stack.push_back( StackElement(0,0) );
for(int x=0; x<field.size(); ++x)
{
int height = field[x][y];
if(height!=curHeight)
{
stack.push_back( StackElement(rollbackStack(x, height), height) );
curHeight = height;
}
}
rollbackStack(field.size(), 0);
}
}
int Algorithm::findMaxArea(int* source, int sizeX, int sizeY)
{
Algorithm alg(source, sizeX, sizeY);
alg.calcProjections(); // first step
alg.processProjections(); // second step
return alg.maxArea;
}
На счет своего алгоритма, я еще подумаю, как буду иметь время и сообщу. Хорошо было бы знать средний размер и среднюю заполненность матрицы.
Цитата:
Originally posted by Mоngооsе
Green, в данный момент у меня открыто 4 проекта в Visual C (2 windows service, 1 dll вызываемый из FoxPro программы, и одна нормальная прога оформлена ala OutLook Express) и 2 проекта Visual FoxPro (нормальная прога и Com Server). Все эти программы довольно тесно с друг другом взаимодействуют.
Green, в данный момент у меня открыто 4 проекта в Visual C (2 windows service, 1 dll вызываемый из FoxPro программы, и одна нормальная прога оформлена ala OutLook Express) и 2 проекта Visual FoxPro (нормальная прога и Com Server). Все эти программы довольно тесно с друг другом взаимодействуют.
А... а я булыжники сушу...
Что-то до того, как я предложил доработать твой нерабочий алгоритм (рабочий, но не в том направлении), я что-то твоей крайней занятости не наблюдал.
Цитата:
Originally posted by Mоngооsе
Ты ломаешь над этой прогой голову уже более 2 недели. И в первом посту ни о каком турнире речи не шло. Там вроде ставился вопрос, кто может мне помочь?
Ты ломаешь над этой прогой голову уже более 2 недели. И в первом посту ни о каком турнире речи не шло. Там вроде ставился вопрос, кто может мне помочь?
Да?
А ты перечитай мой первый пост.
Особенно вот эта фраза "P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли." и последующее подталкивание к решению?явно что не помощи я просил, а интересную задачу предлагал.
Цитата:
Originally posted by Mоngооsе
На счет помощи я откликнулся, но если шла бы речь о том, что "ану посоревнуемся, кто выдумает лучший алгоритм," (или как ты любишь выражатся более вульгарно, "ану померяемся..." :)) то я бы промолчал, так как кроме этой основной работы, есть и другие (напр. вчера по просьбе трудящихся, дописал код к одной своей старой проге), да еще кое-что нужно выучить.
На счет помощи я откликнулся, но если шла бы речь о том, что "ану посоревнуемся, кто выдумает лучший алгоритм," (или как ты любишь выражатся более вульгарно, "ану померяемся..." :)) то я бы промолчал, так как кроме этой основной работы, есть и другие (напр. вчера по просьбе трудящихся, дописал код к одной своей старой проге), да еще кое-что нужно выучить.
А ну спасибо...
Слив засчитан.
Цитата:
Originally posted by Mоngооsе
Я бы то же мог ехидничать, что ты бил себе грудь, что прога правильна, пока я не указал тебе контр. пример.
Я бы то же мог ехидничать, что ты бил себе грудь, что прога правильна, пока я не указал тебе контр. пример.
За контр пример спасибо, я его учел.
Сути алгоритма это не поменяло.
Поехидничать можешь рискнуть.
Цитата:
Originally posted by Mоngооsе
Но если хочешь лучший алгоритм, чем твой, тогда лови:
<skip>
Это не на 100% мой алгоритм, меня только подтолкнули к его написанию.
Но если хочешь лучший алгоритм, чем твой, тогда лови:
<skip>
Это не на 100% мой алгоритм, меня только подтолкнули к его написанию.
а... я знаю, это типа шутка...
Очень смешно, с ошибками и ненужной оптимизацией, которая только замедляет программу в большинстве случаев.
Цитата:
Originally posted by Mоngооsе
На счет своего алгоритма, я еще подумаю, как буду иметь время и сообщу. Хорошо было бы знать средний размер и среднюю заполненность матрицы.
На счет своего алгоритма, я еще подумаю, как буду иметь время и сообщу. Хорошо было бы знать средний размер и среднюю заполненность матрицы.
Отлично, жду.
Нет среднего размера и средней заполненности.
Всё абсолютно произвольно.
Кроме того, ты немного изменил условие, но я с этим согласился, так что теперь исходная матрица не квадратная, а прямоугольная.
Цитата:
Originally posted by Green
А ты перечитай мой первый пост.
Особенно вот эта фраза "P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли." и последующее подталкивание к решению?явно что не помощи я просил, а интересную задачу предлагал.
А ты перечитай мой первый пост.
Особенно вот эта фраза "P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли." и последующее подталкивание к решению?явно что не помощи я просил, а интересную задачу предлагал.
Во всяком случае речи о соревновании не шло. И никто не предположил бы читая твои посты в начале, что в конце напишешь, блин какой я умный, вообще без соперника. Если б я предложил эту задачу, как интересную, и ты мимодом решил бы вместо меня, кто днями на нем сидел, тогда я бы тебя понял.
Цитата:
а... я знаю, это типа шутка...
Очень смешно, с ошибками и ненужной оптимизацией, которая только замедляет программу в большинстве случаев.
Очень смешно, с ошибками и ненужной оптимизацией, которая только замедляет программу в большинстве случаев.
Какие ошибки, и какая не нужная оптимизация? Вот матрица
0, 0, 0, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 1
0, 0, 0, 1, 1
Твоя прога поместит мин. 30 элементов в стек (и потом уберет).
Моя 7. Чувтствуешь разницу?
Цитата:
Нет среднего размера и средней заполненности.
Я вижу ты делаешь первые шаги в области определения сложности алгоритмов.
Напр. один алгоритм имеет сложность C*N^2, а другой D*N^3. C и D это среднее число операций на каждой итерации. Алгоритмы решают одну и ту же задачу. Если D=20, а С=1000 тогда для N от 1 до 50, алгоритм с N^3 будет лучше.
В твоем алгоритме 1 шаг оптимальный, второй не очень.
В моем наоборот. Если есть например непрерывная белая область 100*100, тогда определение макс. площади для этой области у тебя 10000 итераций. У меня может быть 20-30. Но чтоб на втором шаге было так мало операций, на первом нужно сделать довольно большую работу. Нужно подумать, ведь без моей оптимизации, твой алгоритм и не такой уж хороший. :)
Цитата:
Originally posted by Mоngооsе
Во всяком случае речи о соревновании не шло. И никто не предположил бы читая твои посты в начале, что в конце напишешь, блин какой я умный, вообще без соперника.
Во всяком случае речи о соревновании не шло. И никто не предположил бы читая твои посты в начале, что в конце напишешь, блин какой я умный, вообще без соперника.
Да именно шло.
По себя я ничего не писал.
Я отстаивал предложенный мной алгоритм, как оптимальный, и пока единственный, к сожалению.
Ты же начал утверждать что твой алгоритм, который НЕ РЕШАЕТ ЗАДАЧИ более оптимальный, а мой вообще не рабочий.
Цитата:
Originally posted by Mоngооsе
Какие ошибки, и какая не нужная оптимизация?
Какие ошибки, и какая не нужная оптимизация?
Ошибочка маленькая, но есть. Попробуй скомпилировать свой вариант.
Оптимизация спорная, т.к. на каждом шаге выполняется ещё одна проверка и все зависит от входных данных.
Цитата:
Originally posted by Mоngооsе
Твоя прога поместит мин. 30 элементов в стек (и потом уберет).
Моя 7. Чувтствуешь разницу?
Твоя прога поместит мин. 30 элементов в стек (и потом уберет).
Моя 7. Чувтствуешь разницу?
А сколько лишних проверок будет в твоем варианте ри такой матрице:
0, 0, 0, 0, 0
0, 0, 0, 0, 0
0, 0, 1, 0, 0
0, 1, 1, 1, 0
1, 1, 1, 1, 1
Цитата:
Originally posted by Mоngооsе
Я вижу ты делаешь первые шаги в области определения сложности алгоритмов.
Напр. один алгоритм имеет сложность C*N^2, а другой D*N^3. C и D это среднее число операций на каждой итерации. Алгоритмы решают одну и ту же задачу. Если D=20, а С=1000 тогда для N от 1 до 50, алгоритм с N^3 будет лучше.
Я вижу ты делаешь первые шаги в области определения сложности алгоритмов.
Напр. один алгоритм имеет сложность C*N^2, а другой D*N^3. C и D это среднее число операций на каждой итерации. Алгоритмы решают одну и ту же задачу. Если D=20, а С=1000 тогда для N от 1 до 50, алгоритм с N^3 будет лучше.
Я вижу ты делаешь последний и опять же неверный шаг.
Что значит "лучше"?
Кроме того, посмотри топик (какой же ты невнимательный), там говорилось о сложности, а не о "лучше".
Цитата:
Originally posted by Mоngооsе
В твоем алгоритме 1 шаг оптимальный, второй не очень.
В моем наоборот.
В твоем алгоритме 1 шаг оптимальный, второй не очень.
В моем наоборот.
Ага, в твоём алгоритме пока вообще второго шага нет, а первый совершенно бессмысленный, тем более для абсолютно белой области.
Цитата:
Originally posted by Mоngооsе
Нужно подумать, ведь без моей оптимизации, твой алгоритм и не такой уж хороший. :)
Нужно подумать, ведь без моей оптимизации, твой алгоритм и не такой уж хороший. :)
Твоя оптимизация - это проверка на равенство двух рядом стоящих значений: :D
Как ты думаешь, я бы смог сам догадаться до ТАКОГО?
Видимо, нет, иначе я бы не стал делать эту проверку по вышеописанным причинам. :D
Давай, не будем ругаться.
Приводи свой второй шаг алгоритма. Обсудим.
Приводи свой второй шаг алгоритма. Обсудим.
Цитата:
Originally posted by Green
Давай, не будем ругаться.
Приводи свой второй шаг алгоритма. Обсудим.
Давай, не будем ругаться.
Приводи свой второй шаг алгоритма. Обсудим.
Алгоритм я до конца не обдумал, но мне кажется что первый шаг требует очень много операций. Идея в том, что
1. прямоугольника однозначно определяют верхняя-левая и нижняя правые вершины.
2. стороны макс. прямоугольника должны лежать вдоль окаймляющих прямых.
Например. прилагаю скриншот. Там определяется площадь для двоек вершин
(A1) (A3)
(B1)
(D1) (D3)
(C1) (C2)
(E1) (E2) (E3) (E4)
Т.е 12 вычислений площади для матрицы 8*8.
А для реальных прямоугольников только одно вычисление.
Второй рисунок на скриншоте, это хаотически заполненная матрица.
Использование стека - это интересно. Несколько запоздало, но и мое решение было основано именно на нем, только, как мне кажется (я не утверждаю), несколько иначе. Я использовал стек, содержащий значения высот и счетчик для каждой из них соответственно. Кроме того, у меня не было матрицы высот, а использовался массив размера N, и рассмотрение рисунка я начинал сверху. Текущие высоты измерялись способом, аналогичным формированию матрицы, только выходило это, так сказать, "налету". Сам алгоритм:
В общем, это не совсем стек получается. Кроме того используется на одну итерацию больше при просмотре для столбцов: мне кажется, что так проще, чем делать проверку конца строки добавочно к остальным условиям. Соответственно, стек размера N+1. Так вот... Может, это и не "эстетический" подход, но решение укладывается в N^2.
Простите за несловесную реализацию: получилось бы еще хуже, наверное. В общем, в решения остальных я не вникал особо, нет времени; уж звиняйте, если где повторился.
Код:
for(y=0;y<n;y++)
{
s[0][0]=0;
s[0][1]=0;
i=0;
c=0;
for(x=0;x<=n;x++)
{
if(x==n) h=0; else
{
if(matrix[y][x]==1) m[x]++; else m[x]=0;
h=m[x];
}
if(h<s[0])
{
while(h<s[0])
{
...max s[0]*(s[1]+c)
c+=s[1];
i--;
}
}
if(h==s[0]) if(h!=0) s[1]+=(c+1);
if(h>s[0])
{
i++;
s[0]=h;
s[1]=c+1;
};
c=0;
};
};
{
s[0][0]=0;
s[0][1]=0;
i=0;
c=0;
for(x=0;x<=n;x++)
{
if(x==n) h=0; else
{
if(matrix[y][x]==1) m[x]++; else m[x]=0;
h=m[x];
}
if(h<s[0])
{
while(h<s[0])
{
...max s[0]*(s[1]+c)
c+=s[1];
i--;
}
}
if(h==s[0]) if(h!=0) s[1]+=(c+1);
if(h>s[0])
{
i++;
s[0]=h;
s[1]=c+1;
};
c=0;
};
};
В общем, это не совсем стек получается. Кроме того используется на одну итерацию больше при просмотре для столбцов: мне кажется, что так проще, чем делать проверку конца строки добавочно к остальным условиям. Соответственно, стек размера N+1. Так вот... Может, это и не "эстетический" подход, но решение укладывается в N^2.
Простите за несловесную реализацию: получилось бы еще хуже, наверное. В общем, в решения остальных я не вникал особо, нет времени; уж звиняйте, если где повторился.
Цитата:
Originally posted by REmindER
Может, это и не "эстетический" подход, но решение укладывается в N^2.
Может, это и не "эстетический" подход, но решение укладывается в N^2.
Похоже на то, но я не совсем понял, что делается в алгоритме.
Как понял я, твой алгоритм работает так же, как и предложенный мной. За одним исключением, что я делаю двумя шагами два цикла по x и y, а ты свел их в один. Так?
s[][0] - это стек высот?
s[][1] - это их позиции?
что такое i,c и h ?
Это аналог моего первого шага, т.е. построение проекций:
Код:
if(matrix[y][x]==1)
m[x]++;
else
m[x]=0;
h=m[x];
m[x]++;
else
m[x]=0;
h=m[x];
Итерация x==n введена для раскрутки стека. Так?
Собственно раскрутка:
Код:
while(h<s[0])
{
...max s[0]*(s[1]+c)
c+=s[1];
i--;
}
{
...max s[0]*(s[1]+c)
c+=s[1];
i--;
}
Не понятен вот этот участок:
Код:
if(h==s[0])
if(h!=0)
s[1]+=(c+1);
if(h!=0)
s[1]+=(c+1);
Это помещение нового элемента в стек:
Код:
if(h>s[0])
{
i++;
s[0]=h;
s[1]=c+1;
};
{
i++;
s[0]=h;
s[1]=c+1;
};
Т.е. принцип наших алгоритмов аналогичен. В защиту своей реализации могу сказать, что два цикла лучше одного (IMHO) тем, что внутри них меньше условных операций.
Цитата:
Originally posted by Mоngооsе
Алгоритм я до конца не обдумал, но мне кажется что первый шаг требует очень много операций. Идея в том, что
1. прямоугольника однозначно определяют верхняя-левая и нижняя правые вершины.
2. стороны макс. прямоугольника должны лежать вдоль окаймляющих прямых.
Алгоритм я до конца не обдумал, но мне кажется что первый шаг требует очень много операций. Идея в том, что
1. прямоугольника однозначно определяют верхняя-левая и нижняя правые вершины.
2. стороны макс. прямоугольника должны лежать вдоль окаймляющих прямых.
Чтоб не развивать опять наш минискандал, подождем устоявшегося алгоритма. :)