Armenian Knowledge Base  

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

Reply
 
LinkBack Thread Tools
Old 08.12.2005, 15:27   #31
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

PHP Code:
import string

def Calx
(str):

    
operators = {
        
'+' lambda ab,
        
'-' lambda ab,
        
'*' lambda ab,
        
'/' lambda ab
    
}

    
def tonum(tok):
        try: return 
string.atof(tok)
        
except: return tok

    def CalcExpr
(toks):
        
rv toks[:]
        for 
op in ['*''/''+''-']:
            while 
op in rv:
                
rv.index(op)
                
rv [2] = [operators[op](rv[1], rv[1])]

        return 
rv[0]

    for 
sign in ['('')'] + operators.keys():
        
str str.replace(sign' %s ' sign)      

    
toks map(tonumstr.split())

    
startend =  len(toks) - 10  

    
while  '(' in toks:

        while 
toks[start] != '(':
            
start -= 1

        end 
start

        
while toks[end] != ')':
            
end += 1

        toks
[start end 1] = [CalcExpr(toks[start end])]
        

    return 
CalcExpr(toks
Rabotaet na floatax, nalichie probelov mezhdu chislami, operatorami i skobkami, a takzhe skobok vokrug vsego vyrazhenia ne trebuetsa.
Reply With Quote
Old 08.12.2005, 20:10   #32
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Мое решение.
Ограничения: корректность строки не проверяется, не должно быть пробелов, из чисел только неотрицательные целые,
число с точностью unsigned int, всё выражение с точностью double, деление на ноль не отслеживается.

Code:
double eval(char *str, unsigned int end, unsigned int start=0){
    unsigned int v=0, brk=0, hi=0, i;
    for(i=start; i<end; i++){
        if(str[i]=='('){brk++;}
        else if(str[i]==')'){if(i==end-1 && !hi){return eval(str, --end, ++start);}brk--;}
        else if(!brk && (((str[i]=='*' || str[i]=='/') && (str[hi]!='+' && str[hi]!='-')) || (str[i]=='+' || str[i]=='-'))){hi=i;}
        else v=v*10+str[i]-'0';
    }
    if(!hi){return v;}
    double l=eval(str, hi, start), r=eval(str, end, hi+1);
    return str[hi]=='+' ? l+r : str[hi]=='-' ? l-r : str[hi]=='*' ? l*r : l/r;
}
Для (12*3+6-73/3)*23+(21)/3+3*(12+1)+12+((1+1)*(2+4)) ответ 476.333(~). Вроде, верно.

Cамый короткий вариант - javascript:eval(str);

========

Quote:
Originally Posted by Ablertus
А давайте я задачку задам. Как посчитать дистанцию Марчевского-Стеинхауса, задействовав минимальный обьем памяти? Для тех кто не знает речь идет о доле симметричного комплемента в обьединении: d = |(A/B) U (B/A)| / |A U B|.
Если множества заданы как массивы и их нельзя изменять, и заданы:
функиция, нумерующая элементы множества (от 0 по ++),
количество всевозвожных элементов n,
и уменьшить нужно ТОЛЬКО расход памяти, то элементарно и грубо решается в среднем
расходуя n*sizeof(bool) (может лучше использовать char) плюс 3-4 инта.
Можно даже меньше в несколько раз, если использовать массив битов. Тогда код возрастет.

Что-то вроде этого... но, опять таки, решение в лоб...
Code:
template<class T, unsigned int n, unsigned int (*nE)(T)> double dist(T *A, unsigned int nA, T *B, unsigned int nB){
    unsigned int nU=0, nD=0, i; bool b[n];
    for(i=0; i<n; b[i++]=0);
    for(i=0; i<nA; b[nE(A[i++])]^=1);
    for(i=0; i<nB; b[nE(B[i++])]^=1);
    for(i=0; i<n; nD+=b[i++]);        //можно(?) включить в два предыдущих
    for(i=0; i<nA; b[nE(A[i++])]=1);
    for(i=0; i<nB; b[nE(B[i++])]=1);
    for(i=0; i<n; nU+=b[i++]);        //можно(?) включить в два предыдущих
    return (double)nD/nU;
}
Quote:
Originally Posted by Ablertus
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
Old 09.12.2005, 12:09   #33
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by knightmare
...
Interesno, chto ya i sam v svoe vremya reshil etu zadachu na C++ recursivno. I tolko Python spodvig menya na vozmozhno menee effectivnoe (s tochki zrenia skorosti), no gorazdo bolee legko realizuemoe iterativnoe reshenie. Okazyvaetsa, vozmozhnosti jazyka inogda podskazyvajut samu logiku reshenia Kod knightmare vrode kak bolee kompakten, zato moy gorazdo bolee chitabelen (po moemu) i napisan byl na sutki bystree, tak chto Python rulez!
__________________
Она нахмурила свой узенький лобок...
Reply With Quote
Old 09.12.2005, 20:33   #34
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

2Ablertus: Всё то, о чем ты говоришь, безусловно верно, и к этому приходят опытные программисты...
и потом, иногда, в свободные минуты, с ностальгией пишут программы, соответствующие названию темы,
чисто для эстетического наслаждения. А написав, быстро удаляют код, не соответствующий
никаким правилам "хорошего тона", правилам переносимости и разным другим ограничением мира...
(о.. как загнул!)

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

Кстати, о задаче про дистанцию...
Кокого это решение? Чисто исходя из практики?
2*(n+An+Bn) обычно бывает больше nA*nB (плюс расход на сравнение при прямом решении)?
И всегда ли можно легко реализовать быструю/маленькую нумерующую функцию?
Если, конечно, кто-либо вообще сталкивался с этим на практике...
Reply With Quote
Old 10.12.2005, 10:06   #36
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by knightmare
Кстати, о задаче про дистанцию...
Кокого это решение? Чисто исходя из практики?
2*(n+An+Bn) обычно бывает больше nA*nB (плюс расход на сравнение при прямом решении)?
И всегда ли можно легко реализовать быструю/маленькую нумерующую функцию?
Если, конечно, кто-либо вообще сталкивался с этим на практике...
Chestno govorya, sam ne ponyal tvoe reshenie (mozhet, nachinayu zabyvat C? ) Ty sozdaesh massiv bitov dopolnitelno k uzhe sushestvujushim v pamjati massivam mnozhestv? Zachem?
Reply With Quote
Old 10.12.2005, 10:37   #37
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

b[i]=1 если i-ый элемент присутствует и т.д. (при XOR - исключается двойное вхождение, в оба массива), ну а потом просто считаем 1-ы.
Это всё оправданно, если тип T ооочень большой + элементы дорого сравнивать + но легко индексировать.
Reply With Quote
Old 10.12.2005, 12:00   #38
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Ponjatno, znachit vse taki imela mesto optimizacija s maksimizaciej skorosti. Ladno, togda chto nibud sam predlozhi
Reply With Quote
Old 10.12.2005, 20:33   #39
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Если нельзя изменять массивы, то этот вариант не только быстрее, но и меньше памяти расходует... см. требования.
Кстати я чуть-чуть ошибся в их определении: возможность индексации решает проблему сравнивания.
Reply With Quote
Old 11.12.2005, 18:58   #40
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Quote:
Originally Posted by knightmare
Если нельзя изменять массивы, то этот вариант не только быстрее, но и меньше памяти расходует... см. требования.
Кстати я чуть-чуть ошибся в их определении: возможность индексации решает проблему сравнивания.
nu obyasni mne, bud dobr. v moem variante v pamyati (vo vsyakom sluchae explicitly) voobshe ne sozdaetsa nichego novogo krome dvux integerov.
Reply With Quote
Old 11.12.2005, 20:53   #41
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Ну ладно, понятно с памятью всё уже... я просто про скорость не забывал...

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

ladno, ya ne xotel sporit, prosto bylo interesno net, ya sam zhdu
Reply With Quote
Old 20.12.2005, 19:13   #43
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

Вот проблема (лучше что-нибудь, чем ничего).
Дан двумерный массив NxM с булев. значениями.
Нужно выбрать случайный элемент со значением true - выбрать пару (x, y).
С оптимизацией во все стороны.

Доступна rand(), ну или что там еще бывает.
Reply With Quote
Old 21.12.2005, 21:07   #44
The splendid
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Pure thoughts
Age: 36
Posts: 3,408
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default Re: Минимальные, оптимальные, красивые решения простых задач :)

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

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

...или я чего-то не понял?

Т. е. создавать еще один массив пар координат элементов, значения которых в главном массиве true? А лучше?
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.