Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a modul kezdőlapjáraUgrás a tananyag előző oldaláraUgrás a tananyag következő oldaláraFogalom megjelenítés (nem elérhető funckió)Fogalmak listája (nem elérhető funkció)Oldal nyomtatása (nem elérhető funkció)Oldaltérkép megtekintéseSúgó megtekintése

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 két kombinatorikus algoritmust vizsgálunk: az egyikben megadjuk, hogy valamely kombinatorikus jellemzőből hány darab van (K-Fibonacci szám), a másikban pedig egy adott sorszámút keresünk (i-edik permutáció).

Követelmény

Önállóan megoldható feladatok

Kombinatorikus algoritmusok

K-Fibonacci számok

Feladat

Az iskola bejáratánál N lépcsőfok van. Egyszerre maximum K fokot tudunk lépni, ugrani fölfele. Minden nap egyszer megyünk be az iskolába. Készítsük el a Lépcső függvényt, amely megadja, hogy hány napig tudunk más és más módon feljutni a lépcsőkön!

Az N-edik lépcsőfokra úgy tudunk lépni, hogy előtte vagy az N-1-edik, vagy az N-2-edik, … , vagy az N-K-adik lépcsőfokon voltunk, azaz L(N)=L(N-1)+L(N-2)+…+L(N-K). Kezdetben a 0. lépcsőfokon egyféleképpen állunk. Tehát olyan Fibonacci számokról van szó, amelyek az előző K szám összegeként számolhatunk ki (ha van előző K tag). Azaz a sorozatszámítás tételt alkalmazhatjuk:

Lépcső(N):
L[0]:=1
Ciklus i=1-től K-ig
L[i]:=0
Ciklus j=0-től i-1-ig
L[i]:=L[i]+L[j]
Ciklus vége
Ciklus vége

Ciklus i=K+1-től N-ig
L[i]:=0
Ciklus j=i-K-tól i-1-ig
L[i]:=L[i]+L[j]
Ciklus vége
Ciklus vége

Lépcső:=L(N)
Függvény vége.

Vegyük észre a következőt:

L(N)=L(N-1)+L(N-2)+…+L(N-K)

L(N-1)=L(N-2)+L(N-3)+…+L(N-K-1)

azaz

L(N)=2*L(N-1)-L(N-K-1)

Így ez már a másolás-függvényszámítás tétel, azzal a specialitással, hogy a be- és kimenő sorozat ugyanaz a tömb, majd a tömb utolsó eleme a feladat megoldása:

Lépcső(N):
L[0]:=1; L[1]:=1
Ciklus i=2-től K-ig
L[i]:=2*L[i-1]
Ciklus vége
Ciklus
i=K+1-től N-ig
L[i]:=2*L[i-1]-L[N-K-1]
Ciklus vége
Lépcső:=L(N)
Függvény vége.

Vissza a tartalomjegyzékhez

I-edik permutáció

Feladat

Rendeljünk valamilyen elv szerint sorszámot N elem permutációihoz (0 és N!-1 közötti szám), majd adjuk meg az ebben a sorrendben i-edik permutációt

Vegyünk egy rendező módszert (a minimumkiválasztásos rendezést), amelynek kiinduló adata egy adott permutáció! Rendezés közben tároljuk azt, hogy milyen távolságra kellett az egyes elemeket cserélni!

Rendezés(X,N,TÁV):
Ciklus i=1-től N-1-ig
min:=i
Ciklus j=i+1-től N-ig
Ha X[j]<X[i] akkor min:=i
Ciklus vége
Csere(X[i],X[min]); TÁV[i]:=min-i
Ciklus vége
Eljárás vége.

A TÁV vektor egyértelmű leírása a kiinduló permutációnak, mert az (1,2,…,N) sorozatból az alábbi algoritmussal egyértelműen előállítható:

Permutáció(X,N,TÁV):
Ciklus j=N-1-től 1-ig -1-esével
Csere(X[j],X[j+TÁV[j]])
Ciklus vége
Eljárás vége.

A TÁV vektor elemei:

TÁV[N-1]∈(0,1), TÁV[N-2]∈(0,1,2), TÁV[N-3]∈(0,1,2,3), TÁV[1]∈(0,1,…,N-1)

Ez egy olyan szám, ahol az utolsó helyiértéket kettes számrendszerben írjuk fel, az utolsó előttit hármas számrendszerben, az előzőt négyes számrendszerben, …, azaz egy ún. faktoriális számrendszerben felírt szám.

Az i. permutáció előállítása ezután úgy történik, hogy az i-t felírjuk faktoriális számrendszerben, és erre alkalmazzuk a fenti eljárást:

Permutáció(X,N,i):
K:=2
Ciklus j=N-1-től 1-ig -1-esével
t:=i mod K; i:=i div K; Csere(X[j],X[j+t])
K:=K+1
Ciklus vége
Eljárás vége.

Tehát az i-edik permutáció előállítása egy rendező módszer átalakítását jelentette.

Tekintse meg az alábbi animációt, amelyben összefoglaljuk a lecke lényegét, sőt némi további ismereteket is adunk!

Az animáció a Kombinatorika című előadáson vezet végig.

Flash lejátszó letöltése

Kombinatorika.

Vissza a tartalomjegyzékhez

Fel a lap tetejére
Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.