![](https://forum.armkb.com/images/enlighten/misc/cat_top_ls.gif) |
Минимальные, оптимальные, красивые решения простых задач :) |
![](https://forum.armkb.com/images/enlighten/misc/cat_top_rs.gif) |
25.11.2005, 04:59
|
#1
|
(vagabond)
Join Date: 12 2004
Location: Himalayas
Posts: 823
Rep Power: 0
|
Минимальные, оптимальные, красивые решения простых задач :)
Навеяно соседним топиком "Шедевры". Но здесь пишем только свои задачи и решения
Так вот. Кто-то задает конкретную задачу. Предлагаем и обсуждаем свои решения. Выбираем наилучшее, целуем победителя в лоб, и переходим к следующей задаче.
Начну я сам. В тот день, после поста про незакрытые скобки, я задумался как можно оптимально (быстро и/или с минимальным кодом)
реализовать функцию проверки балланса различных скобок (фигурных, круглых, и т.п.) в заданной строке текста.
У кого какие предложения? У меня есть одно довольно короткое и быстрое решение, выложу потом после ваших версий.
Last edited by Gypsy; 25.11.2005 at 05:54.
|
|
|
25.11.2005, 06:09
|
#2
|
Грустно...
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 42
Posts: 21,717
Rep Power: 9
|
проходим по строке и кладем в стэк открывающую скобку, когда встречаем закрывающаю берем элемент со стэка, если его нет или он не соответствует закрывающей - то баланс нарушен.
|
|
|
25.11.2005, 06:37
|
#3
|
(vagabond)
Join Date: 12 2004
Location: Himalayas
Posts: 823
Rep Power: 0
|
Ну да. А без стека?
Задача в том чтобы реализовать функцию в минимальном количестве строк кода и в минимальной памяти. Можно ставить ограничения на строку (скажем определить максимальную глубину скобок).
Хотя конечно задача не супер. Если есть более интересные задачи, милости просим...
|
|
|
25.11.2005, 08:26
|
#4
|
the mochinger
Join Date: 02 2002
Location: Paranoid Android, @10:50
Age: 45
Posts: 1,894
Rep Power: 5
|
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 '('
|
|
|
25.11.2005, 12:00
|
#5
|
Грустно...
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 42
Posts: 21,717
Rep Power: 9
|
Ганс, читаем внимательнее вместе:
реализовать функцию проверки балланса различных скобок (фигурных, круглых, и т.п.) в заданной строке текста
Если скобка одного типа тогда да - как ты сказал - это элементарно. Я дико обрадуюсь если вы найдете решение лучше моего, которое проверит баланс скобок разных типов.
|
|
|
25.11.2005, 12:17
|
#6
|
the mochinger
Join Date: 02 2002
Location: Paranoid Android, @10:50
Age: 45
Posts: 1,894
Rep Power: 5
|
oh, my bad ![Big Grin](https://forum.armkb.com/images/smilies/biggrin.gif) i am fusking asleep
|
|
|
25.11.2005, 20:08
|
#7
|
Banned
Join Date: 10 2001
Location: ...осень колибри
Age: 44
Posts: 7,487
Rep Power: 0
|
А последовательность учитыается? В смысле, ты считаешь последовательность ошибочной?
Code:
abcd(efg{hijk)lmnop}
А эту считаешь верной?
Code:
abcd(efg{hijk}lmnop)
Или без разницы?
|
|
|
25.11.2005, 20:41
|
#8
|
Какое небо, *, Багдад!
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Rep Power: 4
|
По-моему, тут всё упирается в стек LIFO (c)Agregat
Можно и по-другому, но будет далеко не красиво ![Smilie](https://forum.armkb.com/images/smilies/smile.gif) и, в принципе, тот же LIFO + рудименты.
хотя надо подумать...
|
|
|
25.11.2005, 21:09
|
#9
|
Какое небо, *, Багдад!
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Rep Power: 4
|
Вот еще одна простая задача: случайным образом преремешать символы в строке (доступна только radn()).
|
|
|
26.11.2005, 10:01
|
#10
|
ЙЦУКЕН
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 54
Posts: 3,118
Rep Power: 0
|
насчет скобок:
есть быстрое решение, которое предложил агрегат - но оно требует в максимуме столько же память, сколько занимает проверяемая строка (ерсли учитывать, что скобок у нас всего 4 разных типов -- то их можно паковать в 2 бита , что в 4 раза уменьшит используюмую память)
вполне возможно, что есть решение дле фиксированного размера памяти - хранить указатель только на открывающую скобку, и при нахождении парной данной скобки делать скан по строке обратно от сохраненной позиции. но его нужно обдумать, чтоб корректно обрабатывать вложенные скобки -- правда придется платить призводительностью за фиксированный размер памяти.
|
|
|
26.11.2005, 10:38
|
#11
|
Грустно...
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 42
Posts: 21,717
Rep Power: 9
|
можно красиво спрятать стэк - заменив его на рекурсию.
|
|
|
27.11.2005, 11:22
|
#12
|
Ego coder
Join Date: 07 2004
Location: Yerevan, Armenia
Age: 43
Posts: 3,738
Rep Power: 4
|
красивое 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]);
Last edited by AvDav; 27.11.2005 at 12:19.
|
|
|
![](https://forum.armkb.com/images/enlighten/misc/cat_top_ls.gif) |
Re: Минимальные, оптимальные, красивые решения простых задач :) |
![](https://forum.armkb.com/images/enlighten/misc/cat_top_rs.gif) |
01.12.2005, 23:12
|
#13
|
Какое небо, *, Багдад!
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Rep Power: 4
|
Re: Минимальные, оптимальные, красивые решения простых задач :)
ООП и скорость компиляции/выполнения по-моему имеют мало общего...
|
|
|
![](https://forum.armkb.com/images/enlighten/misc/cat_top_ls.gif) |
Re: Минимальные, оптимальные, красивые решения простых задач :) |
![](https://forum.armkb.com/images/enlighten/misc/cat_top_rs.gif) |
02.12.2005, 09:16
|
#14
|
(vagabond)
Join Date: 12 2004
Location: Himalayas
Posts: 823
Rep Power: 0
|
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);
}
Такие дела. Я думаю можно найти и более интересные решения...
Last edited by Gypsy; 02.12.2005 at 09:54.
|
|
|
![](https://forum.armkb.com/images/enlighten/misc/trans.gif) |
![](https://forum.armkb.com/images/enlighten/misc/cat_top_ls.gif) |
Re: Минимальные, оптимальные, красивые решения простых задач :) |
![](https://forum.armkb.com/images/enlighten/misc/cat_top_rs.gif) |
02.12.2005, 09:42
|
#15
|
(vagabond)
Join Date: 12 2004
Location: Himalayas
Posts: 823
Rep Power: 0
|
Re: Минимальные, оптимальные, красивые решения простых задач :)
Quote:
Originally Posted by knightmare
Вот еще одна простая задача: случайным образом преремешать символы в строке.
|
Можно просто пройтись по строке делая случайные swap-ы (как уже предлагалось). Пусть будет не compile-time если не хочешь, эффект тот же
Просто тут дело в том, что зная random seed перед генерацией случайной строки, можно ее собрать обратно (применив те же swap-ы в обратном порядке).
Если ты хочешь чтоб перемешивание было односторонней функцией, тут одним только rand-ом вряд ли обойдешься.
|
|
|
All times are GMT. The time now is 12:18. |
|
|