2. heti jegyzet (2014.10.09.)

Órai anyag:

A Fibonacci sorozat n. elemének számítása rekurzívan:
Fibo(n)
| if (n==0)
| | return 0
| if (n==1)
| | return 1
| return Fibo(n-1)+Fibo(n-2)

A Fibonacci sorozat első n elemének számítása dinamikusan:
t[0]:=0
t[1]:=1
for i:=2..n-1
| t[i]:=t[i-1]+t[i-2]

Komplexitás, O() jelölés informális tárgyalása.

Egy n szintes ház szintjeit akarjuk befesteni, feketére vagy fehérre.
Hányféleképpen tehetjük ezt meg, ha nem festhetünk feketére két egymást követő szintet?
Megoldás: Fibo(n)

Feltöltöttünk egy mátrixot a Pascal háromszög elemeivel.
Megnéztük, hogyan használható fel "n alatt a k" kiszámítására.

Beszúró rendezés (helyben), rekordokon, az x mező szerint:
for j:=2..n
| kulcs:=A[j] // most 1-től indexeljük a tömböt
| i:=j-1
| while (i>0 && A[i].x>kulcs.x)
| | A[i+1]:=A[i]
| | i--
| A[i+1]:=kulcs

Gráfelmélet alapjai.

Széltében keresés a k csúcsból indítva:
for i:=0..n-1
| v[i]:=-1 // a v ("volt") tömbben jegyezzük fel a távolságokat, illetve a -1-gyel jelezzük, ha még nem vettük fel a listára
v[k]:=0 // a kezdő csúcs önmagától vett távolsága 0
l[0]:=k // a "lista" tömbben jegyezzük fel a feldolgozandó csúcsokat
akt:=0 // akt: a lista tömbben hol tartunk a csúcsok feldolgozásával
kov:=1 // kov: a lista tömbben hol van a következő üres hely
while akt<kov
| foreach sz eleme szomszédok(l[akt])
| | if v[sz]==-1
| | | l[kov]:=sz
| | | kov++
| | | v[sz]:=v[l[akt]]+1
| | | hon[sz]:=l[akt] // a hon tömbben feljegyezhetjük, honnan jöttünk
| akt++


Házi:

Be szeretnénk költözni egy utcába, ahol már n db ismerősünk él. A t tömbben a pozícióik vannak felsorolva (rendezetlenül).
Hová költözzünk, ha minimalizálni szeretnénk az ismerőseinktől vett távolságunk összegét? Írjunk pszeudokódot, mely O(n^2) idő alatt megadja ezt!
A könnyebbség kedvéért ismerőshöz is beköltözhetünk.
Több minimumhely esetén bármelyik megadható.