1 of 56

Oszd meg és uralkodj�2023.09.27

2 of 56

Ismétlés

3 of 56

Időigény

  • NAGY ÖTLET: ¨ Nézzük csak azt, hogy milyen gyorsan nő a T(n), ha n → ∞.

​

4 of 56

Időigény

  • NAGY ÖTLET: ¨ Nézzük csak azt, hogy milyen gyorsan nő a T(n), ha n → ∞.

​

5 of 56

2. gyakorlat

Egy adott (rendezetlen) tömbben elem megtalálása

​

int linearSearch(int arr[], int n, int x)

{

int i;

for (i = 0; i < n; i++)

if (arr[i] == x)

return i;

return -1;

}

6 of 56

2. gyakorlat

Egy adott (rendezetlen) tömbben elem megtalálása

​

  • A: O(n)
  • B: O(1)
  • C: O(log n)
  • D: O(n2)

7 of 56

2. gyakorlat

n elemű rendezett vektorban egy elem megkeresése rekurzívan

​

int binarySearch(int arr[], int l, int r, int x)

{

if (r >= l) {

int mid = l + (r - l) / 2;

if (arr[mid] == x)

return mid;

if (arr[mid] > x)

return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);

}

return -1;

}

​

​

​

​

8 of 56

2. gyakorlat

n elemű rendezett vektorban egy elem megkeresése?

​

  • A: O(n)
  • B: O(1)
  • C: O(log n)
  • D: O(n2)

9 of 56

Oszd meg és uralkodj

10 of 56

Buborékos rendezés

  • Egymás melletti elemek cseréje

​

11 of 56

Buborékos rendezés

  • Egymás melletti elemek cseréje

​

  • (n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1

​

  • Sum = n(n-1)/2

​

  • = O(n2) - Legrosszabb idő
  • = O(n) – Legjobb idő
  • = O(n2) – Átlagos idő

​

12 of 56

Oszd meg és uralkodj

  • Divide & Conquer (,,Oszd meg és uralkodj”) paradigma

​

13 of 56

Oszd meg és uralkodj

Oszd-meg és uralkodj:

​

  • A feladatot több részfeladatra osztjuk, amelyek hasonlóak az eredeti feladathoz, de méretük kisebb

​

  • Rekurzív módon megoldjuk a részfeladatokat, majd összevonjuk ezeket a megoldásokat, hogy az eredeti feladatra megoldást adjanak.

​

14 of 56

Oszd meg és uralkodj

Felosztás: hogyan osztjuk a feladatot több részfeladatra

​

Uralkodás: a részfeladatokat rekurzív módon megoldjuk. Ha a részfeladatok mérete elég kicsi, akkor közvetlenül megoldja a részfeladatokat.

​

Összevonás: a részfeladatok megoldásait összevonjuk az eredeti feladat megoldásává

PL: vállalat adója ->részleg->munkások

​

15 of 56

Rekurzió

16 of 56

Rekurzió

A rekurzió olyan művelet, mely végrehajtáskor a saját maga által definiált műveletet, vagy műveletsort hajtja végre (általában a probléma egy kisebb példányára), ezáltal önmagát ismétli.

​

17 of 56

Rekurzió

  • Egy rekurzív algoritmusnak két része van:

​

    • Alapeset: a megoldást már előre tudjuk vagy könnyen kiszámítható (ekkor nincs rekurzív hívás)

​

    • Rekurzív eset: a megoldást úgy kapjuk, hogy a probléma más, általában kisebb példányainak megoldását használjuk fel.

​

Csináljunk belőle mindig kisebbet, amíg el nem érjük az alapesetet

18 of 56

Rekurzió

A rekurzív függvényhívás gondolata nagyon hasonló a matematikából ismert teljes indukciós bizonyítási módszerhez:

​

az állítást belátjuk 1-re, majd n-1 alapján n-re.

​

Az egyik legegyszerűbb rekurzív definíció a faktoriálisé:

1 faktoriálisa 1, n faktoriálisa n* (n-1)!

​

19 of 56

Rekurzió

Faktoriális számítás: n! = n· (n - 1) · … · 2 · 1

​

Rekurzív összefüggés: n! = n · (n - 1)!

​

Alapeset: n = 1

​

Rekurzív eset: n > 1: n · (n - 1)!

​

20 of 56

Rekurzió

A rekurzív függvények természetesen nem a végtelenségig hívják saját magukat, mindig van egy leállási feltétel, azaz a rekurzív függvényeknek szükséges kelléke a feltételes elágazás.

​

21 of 56

Bináris keresés

22 of 56

Bináris keresés

  • Az előző órán tárgyalt bináris keresés egy ilyen Oszd meg és uralkodj típusú algoritmus.

​

  • Mutassuk meg, hogy tényleg az és adjuk meg a rekurzív változatát!

​

23 of 56

Bináris keresés

24 of 56

Bináris keresés

Megoldás:

​

Az oszd meg és uralkodj paradigma 3 lépésének megvalósulása:

​

1. Feloszt: megnézzük a középső elemet, és az értékétől függően döntünk

2. Uralkodik: Az egyik résztömbben keresünk ugyanezzel a módszerrel

3. Kombinál: Nem szükséges.

​

25 of 56

Bináris keresés

Írjuk fel a lehetséges eseteket:

​

  • Alapeset: két alapesetünk van:

1. amikor megtaláljuk az elemet

2. és amikor nincs benne a keresett elem a tömbben

​

  • Rekurzív eset:

keressünk a megfelelő résztömbben rekurzívan.

​

26 of 56

Faktoriális

27 of 56

Faktoriális

Írjuk fel a lehetséges eseteket:

​

Alapeset: 1! = 1

​

Rekurzív eset: n!=n*(n-1)!

​

28 of 56

Faktoriális

Írjuk fel a lehetséges eseteket:

​

Alapeset: 1! = 1

​

Rekurzív eset: n!=n*(n-1)!

​

def fakt( n ) :

if ( n == 1 )

return 1

else

return n* fakt(n-1)

​

29 of 56

Faktoriális

https://visualgo.net/en/recursion

​

30 of 56

Fibonacci

31 of 56

Fibonacci

Keressük meg a Fibonacci sorozat (1, 1, 2, 3, 5, 8, 13...) N. elemét

​

Alapeset:

az első és a második elem értéke 1.

​

Rekurzív eset:

az N. elem az N-1 - edik és az N-2 - dik elemek összege.

​

32 of 56

Fibonacci

def fibo( n ) :

if (( n == 1 ) || (n == 0)):

return 1

else

return fibo(n-1) + fibo(n-2)

​

https://visualgo.net/en/recursion

​

33 of 56

Lépcső probléma

34 of 56

Lépcső

  • Adjunk rekurzív algoritmust, ami meghatározza, hogy hányféleképpen mehetünk fel egy n lépcsőfokból álló lépcsőn, ha egyszerre csak 1 vagy 2 lépcsőfokot léphetünk!

​

35 of 56

Lépcső

n=4

36 of 56

Lépcső

  • Jelölje P(n) azt, hogy n lépcsőfokon hányféleképpen mehetünk fel.

​

  • Ekkor a következő összefüggések állnak fent:

​

  • P(1) = 1 (ha egy lépcső van, egyféleképpen mehetünk)

​

​

  • P(2) = 2 (ha két lépcső van, vagy kétszer egyet lépünk, vagy egyszer kettőt)

​

37 of 56

Lépcső

  • P(n) = P(n − 1) + P(n − 2), ha n ≥ 3 (utolsó lépésként egyet vagy kettőt léphetünk)

​

38 of 56

Lépcső

  • P(n) = P(n − 1) + P(n − 2), ha n ≥ 3 (utolsó lépésként egyet vagy kettőt léphetünk)

​

def P( n ) :

if ( n == 1 )

return 1

elseif ( n == 2 )

return 2

else

return P( n−1) + P( n−2)

​

39 of 56

Sakk probléma

40 of 56

Sakk

  • Adjunk rekurzív algoritmust, amely meghatározza, hogy hányféleképpen juthatunk el egy k sorból és n oszlopból álló sakktábla bal alsó sarkából a jobb felső sarkába, ha csak a jobbra vagy a felfelé szomszédos mezőre léphetünk!

​

41 of 56

Sakk

n=k=3

42 of 56

Sakk

  • Jelölje R(n, k) azt a számot, ahányféleképpen eljuthatunk a bal alsó sarokból a jobb felső sarokba.

​

  • R(1, k) = 1 (csak felfelé mehetünk)

​

43 of 56

Sakk

  • R(n, 1) = 1 (csak jobbra mehetünk)

​

44 of 56

Sakk

  • R(n, k) = R(n−1, k)+R(n, k−1)

​

  • ha n, k ≥ 2 (az első lépés jobbra vagy felfelé történhet)

​

45 of 56

Sakk

def R( n , k ):

if ( ( n == 1 ) || ( k == 1 ) ):

return 1

else

return R( n−1, k ) + R( n , k−1)

​

46 of 56

Hatvány probléma

47 of 56

Hatvány

  • Hogyan tudnánk egy egész szám pozitív kitevős hatványát meghatározni rekurzívan?

​

​

  • Alapeset:

​

  • Rekurzív eset:

​

48 of 56

Hatvány

def hatvany(n,alap):

if ( n == 1 ):

return alap

return alap * hatvany(n-1,alap)

hatvany( 10,2 )

49 of 56

Partició probléma

50 of 56

Partíció

Olyan partíciók érdekelnek bennünket, amelyekben minden elem legfeljebb m.

​

Jelöljük P(n,m)-mel az n szám olyan partícióinak számát, amelyekben minden szám kisebb vagy egyenlő m-mel.

​

Például: P(5,2)=3,

​

a partíciók pedig:

2 + 2 + 1,

2+1+1+1

és 1+1+1+1+1.

51 of 56

Természetes számok partíciója

Egy természetes szám partícióján (felbontásán) természetes számok összegére bontását értjük. Például az 5 a következőképpen bontható fel természetes számok összegére.

​

5

4+1

3+2

3+1+1

2+2+1

2+1+1+1

1+1+1+1+1

​

Így az 5-nek összesen 7 különböző partíciója van. Egy partícióban nem számít az elemek sorrendje.

52 of 56

Partíció

P(n,m)-re könnyen találhatunk rekurzív képletet

​

​

Felosztjuk a partíciókat két csoportra:

​

- egyikbe tartoznak azok, amelyekben nincsenek m-mel egyenlő számok (ezek száma P(n,m−1))

​

- a másikba pedig azok, amelyekben van legalább egy m-el egyenlő

szám (ezek száma P(n−m,m)).

53 of 56

Partíció

Alapesetek:

​

N=0 ekkor 1 a visszaadott érték

N<0 ekkor 0 a visszaadott érték

M=0 ekkor 0 a visszaadott érték

​

​

A rekurzív képlet a következő:

​

P(n,m) = P(n−m,m) + P(n,m−1) , ahol n > m > 1

54 of 56

Partíció

def count_partitions(n, m):

if n == 0:

return 1

elif n < 0:

return 0

elif m == 0:

return 0

else:

return count_partitions(n-m, m) + count_partitions(n, m-1)

55 of 56

Ajánlott linkek

56 of 56

Ajánlott linkek

Videók

​

Linkek