Armenian Knowledge Base

Armenian Knowledge Base (http://forum.armkb.com/)
-   Algorithms (http://forum.armkb.com/algorithms/)
-   -   Минимальные, оптимальные, красивые решения простых задач :) (http://forum.armkb.com/algorithms/20785-minimalnye-optimalnye-krasivye-resheniya-prostyx-zadach.html)

Gypsy 25.11.2005 04:59

Минимальные, оптимальные, красивые решения простых задач :)
 
Навеяно соседним топиком "Шедевры". Но здесь пишем только свои задачи и решения :)

Так вот. Кто-то задает конкретную задачу. Предлагаем и обсуждаем свои решения. Выбираем наилучшее, целуем победителя в лоб, и переходим к следующей задаче.

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

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

Agregat 25.11.2005 06:09

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

Gypsy 25.11.2005 06:37

Ну да. А без стека?

Задача в том чтобы реализовать функцию в минимальном количестве строк кода и в минимальной памяти. Можно ставить ограничения на строку (скажем определить максимальную глубину скобок).

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

Hans Andersen 25.11.2005 08:26

stek eto chereschur,
int cntopenbraces;
++ delaem pri '('
-- pri ')'
isli kogda nit' cnt < 0, to imba, more )
v konze,
esli cnt == 0 ok
otherwise imba, more '('

Agregat 25.11.2005 12:00

Ганс, читаем внимательнее вместе:
реализовать функцию проверки балланса различных скобок (фигурных, круглых, и т.п.) в заданной строке текста
Если скобка одного типа тогда да - как ты сказал - это элементарно. Я дико обрадуюсь если вы найдете решение лучше моего, которое проверит баланс скобок разных типов.

Hans Andersen 25.11.2005 12:17

oh, my bad :D i am fusking asleep :)

Forever Child 25.11.2005 20:08

А последовательность учитыается? В смысле, ты считаешь последовательность ошибочной?
Code:

abcd(efg{hijk)lmnop}
А эту считаешь верной?
Code:

abcd(efg{hijk}lmnop)
Или без разницы?

knightmare 25.11.2005 20:41

По-моему, тут всё упирается в стек LIFO (c)Agregat
Можно и по-другому, но будет далеко не красиво:) и, в принципе, тот же LIFO + рудименты.
хотя надо подумать...

knightmare 25.11.2005 21:09

Вот еще одна простая задача: случайным образом преремешать символы в строке (доступна только radn()).

nm 26.11.2005 10:01

насчет скобок:
есть быстрое решение, которое предложил агрегат - но оно требует в максимуме столько же память, сколько занимает проверяемая строка (ерсли учитывать, что скобок у нас всего 4 разных типов -- то их можно паковать в 2 бита , что в 4 раза уменьшит используюмую память)

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

Agregat 26.11.2005 10:38

можно красиво спрятать стэк - заменив его на рекурсию.

AvDav 27.11.2005 11:22

красивое compile-time решение перемешивания:)
Code:

template <int iter, typename T> struct Random {
        static void Shuffle(T* ptr) {
                        size_t i=iter-1, j=i*rand()/(RAND_MAX+1);
                        ptr[i]^=ptr[j]^=ptr[i]^=ptr[j];
                        Random<iter-1, T>::Shuffle(ptr);
        }
};
template <typename T> struct Random<1, T>{static void Shuffle(T*) {}};
.
.
char s[]="abcdefg";
Random<7, char>::Shuffle(&s[0]);


knightmare 01.12.2005 23:12

Re: Минимальные, оптимальные, красивые решения простых задач :)
 
ООП и скорость компиляции/выполнения по-моему имеют мало общего...

Gypsy 02.12.2005 09:16

Re: Минимальные, оптимальные, красивые решения простых задач :)
 
Quote:

Originally Posted by Gypsy
Можно ставить ограничения на строку (скажем определить максимальную глубину скобок).

Quote:

Originally Posted by Agregat
можно красиво спрятать стэк

Короче у меня такое решение. Тоже разновидность идеи стека, но используется всего (N+5) int-ов, где N - количество видов скобок. То есть используемая память не зависит от длины строки.

Если считать количество видов скобок постоянной величиной, то решение линейное. Всего один проход по строке, и для каждого символа N тестов плюс немного арифметики.

Есть ограничения:
- максимальная глубина (вложенность) < 16.
- максимальная глубина отдельно взятого типа скобок <= 8

Создаем массив из N int-ov, изначально все нулевые.
Сканируем строку слева направо.

- При каждой открытой скобке вносим текущий уровень глубины в соответсвующий элемент массива (с помощью побитового сдвига). Увеличиваем уровень глубины.

Скажем встретили '(' на нулевой глубине, в первом элементе пишем 1, потом встретили '{', во втором элементе пишем 2, потом опять '(', в первом элементе уже получается (1 3).

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

Код я постарался сделать как можно короче, просто ради интереса :)

Допустим даны следующие определения.
Типов скобок может быть сколько угодно (но >1), алгоритм от этого не пострадает. В принципе это и есть основное преимущество данного решения.

Code:

char pOC[] = "{([})]";
#define NUM_BRACKETS (sizeof(pOC)>>1)

Функция проверки баланса:
Code:

int CheckBalance(char* p)
{
        int i, c, b = 1, m = 0, n[NUM_BRACKETS], s = NUM_BRACKETS;
        while (i=0, (c=*p++) && b)
            while ((pOC[i]==c) && ((n[i]<<=4)|=++m),
                  (pOC[s+i]==c) && (b=((n[i]&0xF)==m--), n[i]>>=4), ++i-s);

        return b && (m==0);
}

Такие дела. Я думаю можно найти и более интересные решения...

Gypsy 02.12.2005 09:42

Re: Минимальные, оптимальные, красивые решения простых задач :)
 
Quote:

Originally Posted by knightmare
Вот еще одна простая задача: случайным образом преремешать символы в строке.

Можно просто пройтись по строке делая случайные swap-ы (как уже предлагалось). Пусть будет не compile-time если не хочешь, эффект тот же :)

Просто тут дело в том, что зная random seed перед генерацией случайной строки, можно ее собрать обратно (применив те же swap-ы в обратном порядке).

Если ты хочешь чтоб перемешивание было односторонней функцией, тут одним только rand-ом вряд ли обойдешься.


All times are GMT. The time now is 20:43.

Powered by vBulletin® Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.