Tanulási útmutató
Összefoglalás
A tananyag vége felé közeledve kitekintünk a továbblépési lehetőségekre. Olyan feladatokat nézünk át, amelyek alapvetően más tantárgyak témakörébe tartoznak, de a Programozási alapismeretek tantárgy eszközkészletével tökéletesen megoldhatóak.
Ebben a leckében a véletlent vezetjük be az algoritmusok világába.
Követelmény
Önállóan megoldható feladatok
Véletlen algoritmus
Számos véletlenhez kötődő algoritmus ismert. Ezek közül ízelítőül eggyel ismerkedünk meg, amely a „keverés” feladatát oldja meg sajátosan.
K-Fibonacci számok
Van N elemünk (1,2,…,N), keverjük össze őket véletlenszerűen!
Mit jelent a keverés? Az N elem összes lehetséges sorrendje egyenlő eséllyel álljon elő a keverésnél: (1,2,…,N) → (X1, X2,…, XN).
Induljunk ki egy tetszőleges rendező módszerből, például a minimumkiválasztásos rendezésből!
Minimumkiválasztásos rendezés(N,X):
Ciklus i=1-től N-1-ig
min:=i
Ciklus j=i+1-től N-ig
Ha X[j]<X[min] akkor min:=j
Ciklus vége
Csere(X[i],X[min])
Ciklus vége
Eljárás vége.
Ebben a rendezésben az adott elemhalmazból mindig a legkisebbet választottuk, majd cseréltük meg az aktuális elsővel.
A keverés megoldásának elve: Válasszunk az N elem közül egyet véletlenszerűen, és cseréljük meg az elsővel! Így az első helyre egyenlő (1/N) eséllyel kerül bármely elem. A maradék N-1-ből újra válasszunk véletlenszerűen egyet, s cseréljük meg a másodikkal! És így tovább.
Be kellene látnunk, hogy így jó megoldást kapunk! Nem bizonyítás, csak gondolatok: Nézzük meg, hogy mi annak az esélye, hogy az I kerül a második helyre! Ez úgy történhet, hogy az első helyre nem az I került (esélye (N-1)/N), a másodikra pedig igen (esélye 1/(N-1)). Tehát annak az esélye, hogy az I kerül a második helyre: (N-1)/N*1/(N-1)=1/N!
Véletlen permutáció(N,X): [minimumkiválasztásos rendezésre építve]
Ciklus i=1-től N-1-ig
j:=véletlen(i..N); Csere(X[i],X[j])
Ciklus vége
Eljárás vége.
A véletlen(A..B) függvény A és B közötti egészek közül állít elő egyet egyenletesen véletlenül.
Tekintse meg az alábbi animációt, amelyben összefoglaljuk a lecke lényegét!
