![]() |
![]() | #31 |
Дошкольник Join Date: 08 2004 Location: Oxford Age: 40
Posts: 141
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]() PHP Code: |
![]() |
![]() | #32 | ||
Какое небо, *, Багдад! Join Date: 10 2005 Location: Ереван
Posts: 1,682
Downloads: 16 Uploads: 0
Reputation: 99 | 3 | ![]()
Мое решение. Ограничения: корректность строки не проверяется, не должно быть пробелов, из чисел только неотрицательные целые, число с точностью 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; } Cамый короткий вариант - javascript:eval(str); ![]() ======== Quote:
функиция, нумерующая элементы множества (от 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:
...Но иногда хочется расслабиться ![]() | ||
![]() |
![]() | #33 | |
Дошкольник Join Date: 08 2004 Location: Oxford Age: 40
Posts: 141
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]() Quote:
![]() ![]()
__________________ Она нахмурила свой узенький лобок... | |
![]() |
![]() | #34 |
Какое небо, *, Багдад! Join Date: 10 2005 Location: Ереван
Posts: 1,682
Downloads: 16 Uploads: 0
Reputation: 99 | 3 | ![]()
2Ablertus: Всё то, о чем ты говоришь, безусловно верно, и к этому приходят опытные программисты... и потом, иногда, в свободные минуты, с ностальгией пишут программы, соответствующие названию темы ![]() чисто для эстетического наслаждения. А написав, быстро удаляют код, не соответствующий никаким правилам "хорошего тона", правилам переносимости и разным другим ограничением мира... (о.. как загнул!) ...Ждем новых задач! ![]() |
![]() |
![]() | #35 |
Какое небо, *, Багдад! Join Date: 10 2005 Location: Ереван
Posts: 1,682
Downloads: 16 Uploads: 0
Reputation: 99 | 3 | ![]()
Кстати, о задаче про дистанцию... Кокого это решение? Чисто исходя из практики? 2*(n+An+Bn) обычно бывает больше nA*nB (плюс расход на сравнение при прямом решении)? И всегда ли можно легко реализовать быструю/маленькую нумерующую функцию? Если, конечно, кто-либо вообще сталкивался с этим на практике... |
![]() |
![]() | #36 | |
Дошкольник Join Date: 08 2004 Location: Oxford Age: 40
Posts: 141
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]() Quote:
![]() | |
![]() |
![]() | #37 |
Какое небо, *, Багдад! Join Date: 10 2005 Location: Ереван
Posts: 1,682
Downloads: 16 Uploads: 0
Reputation: 99 | 3 | ![]()
b[i]=1 если i-ый элемент присутствует и т.д. (при XOR - исключается двойное вхождение, в оба массива), ну а потом просто считаем 1-ы. Это всё оправданно, если тип T ооочень большой + элементы дорого сравнивать + но легко индексировать. |
![]() |
![]() | #38 |
Дошкольник Join Date: 08 2004 Location: Oxford Age: 40
Posts: 141
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
Ponjatno, znachit vse taki imela mesto optimizacija s maksimizaciej skorosti. Ladno, togda chto nibud sam predlozhi ![]() |
![]() |
![]() | #39 |
Какое небо, *, Багдад! Join Date: 10 2005 Location: Ереван
Posts: 1,682
Downloads: 16 Uploads: 0
Reputation: 99 | 3 | ![]()
Если нельзя изменять массивы, то этот вариант не только быстрее, но и меньше памяти расходует... см. требования. Кстати я чуть-чуть ошибся в их определении: возможность индексации решает проблему сравнивания ![]() |
![]() |
![]() | #40 | |
Дошкольник Join Date: 08 2004 Location: Oxford Age: 40
Posts: 141
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]() Quote:
| |
![]() |
![]() | #41 |
Какое небо, *, Багдад! Join Date: 10 2005 Location: Ереван
Posts: 1,682
Downloads: 16 Uploads: 0
Reputation: 99 | 3 | ![]()
Ну ладно, понятно с памятью всё уже... я просто про скорость не забывал... Есть еще задачи??? |
![]() |
![]() | #43 |
Какое небо, *, Багдад! Join Date: 10 2005 Location: Ереван
Posts: 1,682
Downloads: 16 Uploads: 0
Reputation: 99 | 3 | ![]()
Вот проблема (лучше что-нибудь, чем ничего). Дан двумерный массив NxM с булев. значениями. Нужно выбрать случайный элемент со значением true - выбрать пару (x, y). С оптимизацией во все стороны. ![]() Доступна rand(), ну или что там еще бывает. ![]() |
![]() |
![]() | #45 | |
Какое небо, *, Багдад! Join Date: 10 2005 Location: Ереван
Posts: 1,682
Downloads: 16 Uploads: 0
Reputation: 99 | 3 | ![]() Quote:
...или я чего-то не понял? Т. е. создавать еще один массив пар координат элементов, значения которых в главном массиве true? А лучше? | |
![]() |
Sponsored Links |