Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 25.11.2005, 04:59   #1
(vagabond)
 
Gypsy's Avatar
 
Join Date: 12 2004
Location: Himalayas
Posts: 823
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Минимальные, оптимальные, красивые решения простых задач :)

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

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

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

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

Last edited by Gypsy; 25.11.2005 at 05:54.
Reply With Quote
Old 25.11.2005, 06:09   #2
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 8
Default

проходим по строке и кладем в стэк открывающую скобку, когда встречаем закрывающаю берем элемент со стэка, если его нет или он не соответствует закрывающей - то баланс нарушен.
Reply With Quote
Old 25.11.2005, 06:37   #3
(vagabond)
 
Gypsy's Avatar
 
Join Date: 12 2004
Location: Himalayas
Posts: 823
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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

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

Хотя конечно задача не супер. Если есть более интересные задачи, милости просим...
Reply With Quote
Old 25.11.2005, 08:26   #4
the mochinger
 
Hans Andersen's Avatar
 
Join Date: 02 2002
Location: Paranoid Android, @10:50
Age: 38
Posts: 1,894
Downloads: 2
Uploads: 0
Reputation: 204 | 4
Default

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 '('
Reply With Quote
Old 25.11.2005, 12:00   #5
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 8
Default

Ганс, читаем внимательнее вместе:
реализовать функцию проверки балланса различных скобок (фигурных, круглых, и т.п.) в заданной строке текста
Если скобка одного типа тогда да - как ты сказал - это элементарно. Я дико обрадуюсь если вы найдете решение лучше моего, которое проверит баланс скобок разных типов.
Reply With Quote
Old 25.11.2005, 12:17   #6
the mochinger
 
Hans Andersen's Avatar
 
Join Date: 02 2002
Location: Paranoid Android, @10:50
Age: 38
Posts: 1,894
Downloads: 2
Uploads: 0
Reputation: 204 | 4
Default

oh, my bad i am fusking asleep
Reply With Quote
Old 25.11.2005, 20:08   #7
Banned
 
Forever Child's Avatar
 
Join Date: 10 2001
Location: ...осень колибри
Age: 37
Posts: 7,487
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

А последовательность учитыается? В смысле, ты считаешь последовательность ошибочной?
Code:
abcd(efg{hijk)lmnop}
А эту считаешь верной?
Code:
abcd(efg{hijk}lmnop)
Или без разницы?
Reply With Quote
Old 25.11.2005, 20:41   #8
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default

По-моему, тут всё упирается в стек LIFO (c)Agregat
Можно и по-другому, но будет далеко не красиво и, в принципе, тот же LIFO + рудименты.
хотя надо подумать...
Reply With Quote
Old 25.11.2005, 21:09   #9
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default

Вот еще одна простая задача: случайным образом преремешать символы в строке (доступна только radn()).
Reply With Quote
Old 26.11.2005, 10:01   #10
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

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

вполне возможно, что есть решение дле фиксированного размера памяти - хранить указатель только на открывающую скобку, и при нахождении парной данной скобки делать скан по строке обратно от сохраненной позиции. но его нужно обдумать, чтоб корректно обрабатывать вложенные скобки -- правда придется платить призводительностью за фиксированный размер памяти.
Reply With Quote
Old 26.11.2005, 10:38   #11
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 8
Default

можно красиво спрятать стэк - заменив его на рекурсию.
Reply With Quote
Old 27.11.2005, 11:22   #12
The splendid
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Universe
Age: 36
Posts: 3,413
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default

красивое 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.
Reply With Quote
Old 01.12.2005, 23:12   #13
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

ООП и скорость компиляции/выполнения по-моему имеют мало общего...
Reply With Quote
Old 02.12.2005, 09:16   #14
(vagabond)
 
Gypsy's Avatar
 
Join Date: 12 2004
Location: Himalayas
Posts: 823
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default 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.
Reply With Quote
Old 02.12.2005, 09:42   #15
(vagabond)
 
Gypsy's Avatar
 
Join Date: 12 2004
Location: Himalayas
Posts: 823
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by knightmare
Вот еще одна простая задача: случайным образом преремешать символы в строке.
Можно просто пройтись по строке делая случайные swap-ы (как уже предлагалось). Пусть будет не compile-time если не хочешь, эффект тот же

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

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

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 13:58.


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