Прости броеви

Пак математика :) Овде ставам два алгоритми за генерирање на прости броеви.

Првиот алгоритам генерира табела од која брзо може да се види дали некој број е прост.

int i,j;
int N = 100;

boolean isprime[] = new boolean[N+1];

for (i=2;i<=N;i++) {
  isprime[i]=true;
}

for (i=2;i<=N;i++) {
  if (isprime[i]==true) {
      for (j=2*i;j<=N;j+=i) {
          isprime[j]=false;
      }
  }
}

Вториот алгоритам генерира низа во која се чуваат простите проеви.

int i,j;
int prime[] = new int[1000];
int numofprimes=1;
boolean pom;
prime[0]=2;

for (i=3;i<1000;i++) {
   // we check if i is a prime number
   pom=true;
   for (j=0;j<numofprimes;j++) {
       if (prime[j]<=Math.sqrt((double)i)) {
           if (i%prime[j]==0) {
               pom=false;
               break;
           }
       } else {
           break;
       }   
   }
   if (pom==true) {
       prime[numofprimes]=i;
       numofprimes++;
   }
}

Пресметување на комбинации

In combinatorial mathematics, a combination is an un-ordered collection of distinct elements, usually of a prescribed size and taken from a given set.

Овде ќе зборувам за алгоритам за пресметување на комбинации. Според основната дефиниција може да се направи една функција, но како што може да се забележи е многу неефикасна во смисла на тоа што n! тешко може да се смести во променлива, поради големината. На пример 15! = 1,307,674,368,000. Ова не го собира во long, а да не зборуваме за int. Ова не е единствениот недостаток на овој алгоритам, има премногу пресметки па дури и да го поправиме овој алгоритам. Има уште една работа освен комплексноста за која нема да зборувам овде. Еднаш при решавање на задача, го решив најголемиот дел на задачата, и кога дојде она "најлесното", пресметување на комбинациите го оптимизирав овој алгоритам и цело време ми паѓаше на време, се додека не ми текна на нешто што го знаев од часовите по математика. Потоа направив брз алгоритам, но ми беше криво што порано не сум се сетил на тоа :) Но од грешките се учи, па тоа ми беше една добра лекција, доколку некој алгоритам е точен, но паѓа на време, размисли дали проблемот може да се реши со друг алгоритам.

Решението на нашиот проблем лежи во Паскаловиот триаголник. Колку просто :)



Нема да објаснувам многу за ова, повеќе можете да прочитате на wikipedia.

Еве една инплементација на пресметување на комбинации со помош на Паскалов триаголник.

long N=20;
int i,j;
long comb[][] = new long[N][N];

for (j=0;j<N;j++) {
  comb[0][j]=1;
  comb[j][j]=1;
  for (i=1;i<j;i++) {
       comb[i][j]=comb[i-1][j-1]+comb[i][j-1];
  }
}

Како што се гледа, комплексноста на алгоритмот е O(N), а кога ни се пресметани "претходните" комбинации, пресметувањето на една комбинација е во константно време O(1). За да пресметаме N "последователни" комбинации ни треба O(N). Нема да навлегувам во понатамошни анализи :)

Теорија на веројатност

Една од математичките дисциплини кои често се предмет на проучување од страна на програмерите е Теоријата на веројатност. Една од примените е кај проблемите од типот, колкави ми се шансите да фатам на лото :)

Во математиката, веројатноста да се случи еден настан А се претставува како реален број во опсегот од 0 до 1 и се запишува како P(A). Невозможен настан има веројатност 0, и сигурен настан име веројатност 1.

Спротивно или комплемент на настанот A е настанот [not A] (ова е, настанот A не се случил). Неговата веројатност се означува со P(not A) = 1 - P(A)> На пример, шансата да не ти се падне шестка при фрлање на коцка е 1 - (шансата да ти се падне шест) = 1 - (1/6) = (5/6).



Ако двата настани А и B се случат во исто време додека се врши експериментот, ова се нарекува "joint probability" на A и B.
Ако двата настани А и В се независни, тогаш "joint probability" е:

P(A and B) = P(A) * P(B)

пример: ако две монети се фрлени, шансата да се погоди "глава" и кај двете е (1/2) * (1/2) = (1/4).



Ако се случи настанот А или настанот В, или пак се случат и двата настани истовремено, ова се нарекува унија на настаните А и В.
Ако настаните А и В не можат да се случат истовремено т.е. тие се зависни, тогаш веројатноста да се случи еден од нив е:

P(A or B) = P(A) + P(B)

пример: шансата да ти се погоди 1 или 2 при фрлање на коцка е P(1 or 2) = P(1) + P(2) = (1/6 + (1/6) = (1/3)

Ако настаните А и В не се зависни еден од друг тогаш:

P(A or B) = P(A) + P(B) - P(A and B).

На пример, при извлекувањето на една карта по случајност од еден шпил од карти, шансата да добијам "срце" или карта во боја (J, Q, K) (или една што е и во срце и е карта во боја) е (13/52) + (12/52) - (3/52) = (22/26), затоа што од 52 карти, 13 се во "срце", 12 се карти во боја, и 3 се и двете: овде веројатноста вклучена во "3 што се и двете" се вклучени во секоја од "13 срца" и "12 карти во боја", но треба да бидат избројани само еднаш.



Условна веројатност е веројатноста да се случи некој настан А, при дадена веројатноста на друг настан B. Симболот погоре се чита "веројатност на А, при дадено В". Се дефинира како:

P(A | B) = P(A and B) / P(B)

На пример. Земаме два настани А и В. Две фрлања на коцки А и В.

A: Првата коцка паѓа на 3.
В: Вкупната сума на погодени броеви по фрлањето на втората коцка е 8.

Да претпоставиме дека ги фрламе двете коцки истовремено и ја покриваме втората коцка, па само ја гледаме коцката 1; и забележуваме дека коцката 1 паднала на 3. При дадена половична информација, веројатноста дека збирот на двете коцки ќе даде 8 не е 5/36 (2+6; 3+5, 4+4, 5+4, 6+3 од сите можни збирови на двете коцки кои се 6*6 на број) туку е 1/6, затоа што втората коцка мора да падне точно на 5 за да се постигне бараниот резултат.

Повеќе информации и примери за условна веројатност.

Најмал заеднички содржател

Евклидов алгоритам за најголем заеднички делител и најмал заеднички содржател. Може да послужи некогаш за натпревари по програмирање, па го постирам овде за да имам брз пристап до него и да го користам copy paste.

int nzd(int a, int b) {
   return ( b != 0 ? nzd(b, a % b) : a );
}

int nzs(int a, int b) {
   return (a*b)/nzd(a,b);
}