Armenian Knowledge Base  

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

Reply
 
LinkBack Thread Tools
Old 02.12.2005, 10:00   #16
(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
Вот еще одна простая задача: случайным образом преремешать символы в строке.
А еще можно просто отсортировать строку
Никаких тебе рандов, и никто обратно не соберет
Reply With Quote
Old 02.12.2005, 21:01   #17
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by Gypsy
Есть ограничения:
- максимальная глубина (вложенность) < 16.
- максимальная глубина отдельно взятого типа скобок <= 8
Не хочу оставить впечатление ****звона, но не слишком ли строгие ограничения? На коде, написанном на Lisp-е, не применишь...

Quote:
Originally Posted by Gypsy
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);
 }
У нас в Ереване газовые трубы проводят примерно в этом же стиле

Кстати, предложение shuffle было inspired by текстом, опубликованным в топике Исследование одного университета. (текстом, а не топиком - см. даты постов
).
Reply With Quote
Old 02.12.2005, 21:37   #18
(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
У нас в Ереване газовые трубы проводят примерно в этом же стиле
Это потому что я для них пишу и код и спецификации
Reply With Quote
Old 02.12.2005, 21:40   #19
(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
Не хочу оставить впечатление ****звона, но не слишком ли строгие ограничения? На коде, написанном на Lisp-е, не применишь...
Вообще-то собственный source эта функция запросто проверит (там глубина = 5 кажется).

Если серьезно, то ограничения можно тривиально расширить до любых констант. Использовать несколько int-ов вместо одного, к примеру, или просто 64-битные int-ы. Суть не в этом, а в самом алгоритме
Reply With Quote
Old 02.12.2005, 21:44   #20
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Вообщем идея хорошая - избавились от самой строки (хоть как нибудь)...
Reply With Quote
Old 03.12.2005, 15:56   #21
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

А давайте я задачку задам. Как посчитать дистанцию Марчевского-Стеинхауса, задействовав минимальный обьем памяти? Для тех кто не знает речь идет о доле симметричного комплемента в обьединении: d = |(A/B) U (B/A)| / |A U B|.
Reply With Quote
Old 04.12.2005, 15:23   #22
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

[QUOTE=Gypsy]Если A и B даны как массивы, и их можно модифицировать на месте,
то можно решить задачу используя постоянное количество памяти (всего несколько переменных).

OK, ya napishu svoe, ono gorazdo koroche, no prosto potomu chto na Pythone :

PHP Code:

def Dist
(AB):
     
unilensectlen len(A) + len(B), 0
     
     
for el in A:
          if 
el in B:
               
unilen -= 1
               sectlen 
+= 1

     
return - (float) sectlen unilen 
Reply With Quote
Old 04.12.2005, 20:19   #23
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by Ablertus
PHP Code:
if el in B
Не смешно...
Reply With Quote
Old 05.12.2005, 13:08   #24
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by knightmare
Не смешно...
A kto prosil smejatsja? Eto Python - i bezo vsjakih shutok. Vse kogda to byli arrogantnymi C-istami.
Reply With Quote
Old 05.12.2005, 16:32   #25
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

так ведь решение в лоб
Reply With Quote
Old 05.12.2005, 19:48   #26
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by Agregat
так ведь решение в лоб
Nu ladno, prosto zahotel prodemonstrirovat krasotu yazyka, a to ego tut vrode kak nedoocenivayut. Est reshenie luchshe? Esli net, poslozhnee zadachku vylozhu
Reply With Quote
Old 06.12.2005, 21:17   #27
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by Ablertus
A kto prosil smejatsja? Eto Python - i bezo vsjakih shutok. Vse kogda to byli arrogantnymi C-istami.
Не имею ничего против Python (даже наоборот - за), просто 80% задачи решились встроенными возможностями языка. Это как если задачу про перемешку строки решить на PHP так: <?php $shuffled=str_shuffle($str); ?>
Reply With Quote
Old 07.12.2005, 12:43   #28
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by knightmare
Не имею ничего против Python (даже наоборот - за), просто 80% задачи решились встроенными возможностями языка. Это как если задачу про перемешку строки решить на PHP так: <?php $shuffled=str_shuffle($str); ?>
A tut ya ne soglasen. Ved zadacha (gromko skazano - zadachka, zadachka!) byla ne o poiske identichnyh elementov v posledovatelnostyax, a o tom kak vychislit sootnoshenie komplementov k unionu. Python kak raz tem i xorosh, chto pozvolyaet skoncentrirovatsa na sobstvenno celi, ne tratya vremeni na rutinnye i nabivshie oskominu kuski koda. Mozhete predlozhit druguyu zadachu, poslozhnee, i my sravnim reshenie, skazhem, na C, na Jave i na Pythone.
__________________
Она нахмурила свой узенький лобок...
Reply With Quote
Old 07.12.2005, 18:15   #29
(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 Ablertus
Mozhete predlozhit druguyu zadachu, poslozhnee, i my sravnim reshenie, skazhem, na C, na Jave i na Pythone.
Хорошая идея. Допустим такая задача:

Найти значение арифметического выражения
(только положительные числа, скобки, и +-*/)


Скажем: (5 + 3) * (5 + 4 - 1) --> 64

Тут главная цель - написать минимальный код, который решает эту задачу, скорость/общность/и т.п. не при чем. Просто хочется потом сравнить эти минимальные решения в разных языках.
Reply With Quote
Old 08.12.2005, 14:54   #30
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Ya tolko otmechu, chto samoe glavnie vse taki ne kompaktnost koda, a skorost raboty programmista. Naprimer, kod na Jave izvestna svoej mnogoslovnostyu, mozhet zanimat gorazdo bolshe mesta, chem na C, no pisat na ney vse taki poluchaetsa bystree.
Reply With Quote
Sponsored Links
Reply

Thread Tools


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

All times are GMT. The time now is 15:03.


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