Новинарски форум

Занимания утре - 20 май

Занимания утре - 20 май

by Anton Dimitrov -
Number of replies: 10
Здравейте,

За утрешните часове по практикум няма конкретно определена тема. Предлагам ако има някой, на който му е интересно да се обсъди нещо, да пише тук и може да направим един час. Ако няма такива ще отложим и утрешното занимание.
In reply to Anton Dimitrov

Re: Занимания утре - 20 май

by Михаил Георгиев -
Доста неприятно е, че различните групи ще са свободни по различно време. Според мен би било най-добре да се наредят нещата по такъв начин, че да могат възможно най-много групи да бъдат едновременно. 4-та група можем да се освободим някъде към 4 и половина...
In reply to Михаил Георгиев

Re: Занимания утре - 20 май

by Мария Матева -
Ами втора група имаме май до 3, ОС. Даже до 2 и нещо.
Аз бих се радвала да напишем един mergeSort или някое динамично, или Крускал само с масиви, понеже всеки път го пиша с ArrayList-и и ползвам  вградени неща  и тва ме дразни изплезен(а) Дано някой има по-интересни предложения ;-)

In reply to Мария Матева

Re: Занимания утре - 20 май

by Anton Dimitrov -
Ами досега излиза, че най-рано 16:30 можете всички, така ли е?

Теми, които са предложени са да пишем mergesort, динамични и някои алгоритми без вградени неща от java.

Добре ще е обаче да се обадят повечко хора, че имат желание понеже няма смисъл иначе.
In reply to Anton Dimitrov

Re: Занимания утре - 20 май

by Орлин Тенчев -
Може да обсъдим и задачите от контролното вчера, защото бяха интересни. Например задача А сигурно доц. Манев като я е давал си е представял да бъде една от лесните, а то какво стана.
Има какво да се обсъжда, така че давайте да се разбираме кога и колко :)
In reply to Орлин Тенчев

Re: Занимания утре - 20 май

by Николай Станоев -

за задача А , мисля че е формула , но явно се оказа че не успях да я сметна
ако някой може да я каже самата формула. според мене тя беше следната
Ам = а* б^м-1 + [((б^м-1)*с - с) / (б-1)]

ако някъде бъркам в геометричната прогресия моля някой да ме поправи, или да каже къде бъркам в формулата

In reply to Николай Станоев

Re: Занимания утре - 20 май

by Anton Dimitrov -
Сигурно има формула, обаче има и друго решение, което трябва да мине.

То се базира на това, че резултата от формулата е в интервала [0, 19999] ако не се лъжа. Също така поредния елемент се извежда от предния. Следователно ако една стойност се повтори ще започнат да се повтарят числата през някакъв интервал.
In reply to Николай Станоев

Re: Занимания утре - 20 май

by Атанас Боиклиев -
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.
:(
In reply to Атанас Боиклиев

Re: Занимания утре - 20 май

by Anton Dimitrov -
А за повдигането на степен използваш ли бързо повдигане на степен? Имам предвид, като имаш 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;
}
In reply to Anton Dimitrov

Re: Занимания утре - 20 май

by Преслав Ле -
Според мен търсенето решение е това, което каза Тони по-горе :). Едно по-добро решение е:

Нека 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 е търсения елемент.

Поздрави,
Пресли