Здравейте,
За утрешните часове по практикум няма конкретно определена тема. Предлагам ако има някой, на който му е интересно да се обсъди нещо, да пише тук и може да направим един час. Ако няма такива ще отложим и утрешното занимание.
Доста неприятно е, че различните групи ще са свободни по различно време. Според мен би било най-добре да се наредят нещата по такъв начин, че да могат възможно най-много групи да бъдат едновременно. 4-та група можем да се освободим някъде към 4 и половина...
Ами втора група имаме май до 3, ОС. Даже до 2 и нещо.
Аз бих се радвала да напишем един mergeSort или някое динамично, или Крускал само с масиви, понеже всеки път го пиша с ArrayList-и и ползвам вградени неща и тва ме дразни
Дано някой има по-интересни предложения ;-)
Аз бих се радвала да напишем един mergeSort или някое динамично, или Крускал само с масиви, понеже всеки път го пиша с ArrayList-и и ползвам вградени неща и тва ме дразни
Дано някой има по-интересни предложения ;-)
Ами досега излиза, че най-рано 16:30 можете всички, така ли е?
Теми, които са предложени са да пишем mergesort, динамични и някои алгоритми без вградени неща от java.
Добре ще е обаче да се обадят повечко хора, че имат желание понеже няма смисъл иначе.
Теми, които са предложени са да пишем mergesort, динамични и някои алгоритми без вградени неща от java.
Добре ще е обаче да се обадят повечко хора, че имат желание понеже няма смисъл иначе.
Може да обсъдим и задачите от контролното вчера, защото бяха интересни. Например задача А сигурно доц. Манев като я е давал си е представял да бъде една от лесните, а то какво стана.
Има какво да се обсъжда, така че давайте да се разбираме кога и колко :)
Има какво да се обсъжда, така че давайте да се разбираме кога и колко :)
за задача А , мисля че е формула , но явно се оказа че не успях да я сметна
ако някой може да я каже самата формула. според мене тя беше следната
Ам = а* б^м-1 + [((б^м-1)*с - с) / (б-1)]
ако някъде бъркам в геометричната прогресия моля някой да ме поправи, или да каже къде бъркам в формулата
Сигурно има формула, обаче има и друго решение, което трябва да мине.
То се базира на това, че резултата от формулата е в интервала [0, 19999] ако не се лъжа. Също така поредния елемент се извежда от предния. Следователно ако една стойност се повтори ще започнат да се повтарят числата през някакъв интервал.
То се базира на това, че резултата от формулата е в интервала [0, 19999] ако не се лъжа. Също така поредния елемент се извежда от предния. Следователно ако една стойност се повтори ще започнат да се повтарят числата през някакъв интервал.
Ami moje i s formula i tq e
[[a*b^(m-1)](mod 20000) + [(c*(b^(m-1))/(b-1))](mod 20000)](mod 20000)
kato za vsqko povdigane na stepen trqbva da vzema6 ostatyka(mod 20000)
no za Hard testovete dava tl1.
:(
[[a*b^(m-1)](mod 20000) + [(c*(b^(m-1))/(b-1))](mod 20000)](mod 20000)
kato za vsqko povdigane na stepen trqbva da vzema6 ostatyka(mod 20000)
no za Hard testovete dava tl1.
:(
А за повдигането на степен използваш ли бързо повдигане на степен? Имам предвид, като имаш b^(m-1) дали умножаваш m-2 пъти или го правиш по-бързо.
Принципно като искаш да вдигнеш числото А на степен В тогава това става със сложност logB. Псевдокод за това горе долу изглежда така:
int pow(A, B)
{
if (B == 1)
return A;
int res = pow(A, B/2);
if (B & 1)
// ako B nechetno
return res * res * A;
else
// ako B chetno
return res*res;
}
Принципно като искаш да вдигнеш числото А на степен В тогава това става със сложност logB. Псевдокод за това горе долу изглежда така:
int pow(A, B)
{
if (B == 1)
return A;
int res = pow(A, B/2);
if (B & 1)
// ako B nechetno
return res * res * A;
else
// ako B chetno
return res*res;
}
Според мен търсенето решение е това, което каза Тони по-горе :). Едно по-добро решение е:
Нека f(x) = (a * x + b) % 20000.
Търсим an = fn(a0) = f(f(f(f...f(f(а0))...)))) - функцията приложена n-пъти. Но
f2*k (x) = fk (fk (x)) следователно можем да сметнем всичко директно с бързо повдигане на степен. Сложността е O(log(n)), където n е търсения елемент.
Поздрави,
Пресли
Нека f(x) = (a * x + b) % 20000.
Търсим an = fn(a0) = f(f(f(f...f(f(а0))...)))) - функцията приложена n-пъти. Но
f2*k (x) = fk (fk (x)) следователно можем да сметнем всичко директно с бързо повдигане на степен. Сложността е O(log(n)), където n е търсения елемент.
Поздрави,
Пресли
Утре, 27-ми май, ще има ли практикум?