Algoritmusok¶

Információ

Az alábbi feladatokban különböző algoritmusokat kell elkészíteni. Minden algoritmushoz tartozik egy kiinduló Python kód, amely tartalmaz unittest teszteket is.

Idő -és memóriakorlátozások

A feladatok megoldásánál figyelj a megadott idő- és memóriakorlátozásokra!

Időlimit: 1.00 sec
Memória limit: 512 MB

Ajánlott előismeret

Unittest

Bevezető problémák¶

A bevezető problémák gyakran olyan feladatokat tartalmaz, amelyek bevezetnek az algoritmusok és programozási technikák világába. Ezek a problémák általában alapvető logikai gondolkodást, iterációkat, feltételeket, és néha egyszerű matematikai műveleteket követelnek meg. Itt van néhány példa az ilyen típusú problémákra és azok megoldásaira, Python nyelven.

Weird Algorithm¶

Egy algoritmust kell szimulálnod, amely egy pozitív egész számot \(n\) vesz bemenetként. Ha \(n\) páros, az algoritmus elosztja kettővel, és ha \(n\) páratlan, akkor megszorozza hárommal és hozzáad egyet. Az algoritmus addig ismétli ezt, amíg \(n\) egyenlő nem lesz eggyel.

Például, ha \(n = 3\), a sorozat így néz ki:

\[ 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \]

A feladat az algoritmus végrehajtásának szimulálása egy adott \(n\) értékre.

Bemenet: A bemenet egyetlen sora egy egész számot, \(n\)-t tartalmaz.

Kimenet: Nyomtass egy sort, amely tartalmazza az \(n\) értékeit az algoritmus futása során.

Feltételek

\(1 \leq n \leq 10^6\)

Példa

Bemenet

Kimenet

[3, 10, 5, 16, 8, 4, 2, 1]

Kiinduló Python kód

Az alábbi kódrészletben kizárólag a weird_algorithm függvény törzsét módosítsd!

import unittest

def weird_algorithm(n):
    return []


class TestStringMethods(unittest.TestCase):
    def test_first(self):
        self.assertEqual(weird_algorithm(3), [3, 10 ,5 ,16, 8, 4, 2, 1])

    def test_two(self):
        self.assertEqual(weird_algorithm(27), [27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1])


if __name__ == '__main__':
    unittest.main()

Megoldás

Az adott feladat egy egyszerű algoritmus szimulációját kéri, amely egy pozitív egész számmal dolgozik. A bemenetként megadott szám alapján egy sorozatot kell létrehozni, ahol a sorozat minden egyes elemét az alábbi szabályok alapján kell kiszámítani:

Ha a szám páros: Osszuk el kettővel.
Ha a szám páratlan: Szorozzuk meg hárommal, majd adjunk hozzá egyet.

Az algoritmus mindaddig folytatja a számításokat, amíg az aktuális szám értéke nem lesz egyenlő eggyel.

Példa

Amennyiben a bemeneti érték \(n = 3\), az algoritmus a következő lépéseket hajtja végre:

\(3\) páratlan, így \(3 \times 3 + 1 = 10\)
\(10\) páros, így \(10 / 2 = 5\)
\(5\) páratlan, így \(5 \times 3 + 1 = 16\)
\(16\) páros, így \(16 / 2 = 8\)
\(8\) páros, így \(8 / 2 = 4\)
\(4\) páros, így \(4 / 2 = 2\)
\(2\) páros, így \(2 / 2 = 1\)

A sorozat tehát így néz ki: 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Bemenet

A bemenet egyetlen sort tartalmaz, ami a kezdeti értéket adja meg: \(n\).

Kimenet

A kimenet egy sorban adja vissza az \(n\) értékeit az algoritmus végrehajtása során, egészen addig, amíg az 1-et nem kapjuk eredményül.

Feltételek

\(1 \leq n \leq 10^6\)

Algoritmus magyarázat

Az algoritmus a következőképpen épül fel:

Kezdjük a bemeneti \(n\) értékkel.
Amíg \(n\) nem egyenlő 1-gyel:
- Ha \(n\) páros, osszuk el 2-vel.
- Ha \(n\) páratlan, szorozzuk meg 3-mal, majd adjunk hozzá 1-et.
Minden egyes lépés után írjuk ki az \(n\) aktuális értékét.
A folyamat akkor ér véget, amikor \(n\) értéke 1 lesz, és ezt is kiírjuk.

Ez az algoritmus idő- és memóriahatékony, figyelembe véve, hogy a maximális érték \(n\) 1 millió lehet, és a számítási lépések száma meglehetősen gyorsan csökken, függetlenül a kezdeti \(n\) értékétől.

Lehetséges megoldás

Az alábbiakban egy egyszerű Python megvalósítás látható:

def weird_algorithm(n):
    solution = list()
    while n != 1:
        solution.append(n)
        if n % 2 == 0:
            n //= 2
        else:
            n = n * 3 + 1
    solution.append(1)
    return solution

Chessboard and Queens¶

A feladatod az, hogy helyezz el nyolc vezért egy sakktáblán úgy, hogy egyik sem támadja a másikat. További kihívásként minden mező vagy szabad (.), vagy foglalt (*). Csak a szabad mezőkre helyezheted a vezéreket, azonban a foglalt mezők nem akadályozzák meg a vezéreket abban, hogy támadják egymást.

Hány lehetséges mód van a vezérek elhelyezésére?

Bemenet:
- A bemenet nyolc sort tartalmaz, mindegyik sor nyolc karakter hosszú.
- Minden mező vagy szabad (.), vagy foglalt (*).
Kimenet:
- Egy egész számot kell kiírni: a lehetséges elhelyezések számát.

Példa

Bemenet

........
........
..*.....
........
........
.....**.
...*....
........

Kimenet

Kiinduló Python kód

import unittest


def count_queen_placements(board):
    return 0


class TestQueenPlacements(unittest.TestCase):
    def test_example_case(self):
        board = ["........", "........", "..*.....", "........", "........", ".....**.", "...*....", "........",]
        board = [list(row) for row in board]
        self.assertEqual(count_queen_placements(board), 65)

    def test_free_board(self):
        board = [
            "........", "........", "........", "........", "........", "........", "........", "........"]
        board = [list(row) for row in board]
        self.assertEqual(count_queen_placements(board), 92)

    def test_single_blocked(self):
        board = [ "........", "........", "........", "........", "........", "........", "........", "....*..."]
        board = [list(row) for row in board]
        self.assertEqual(count_queen_placements(board), 74)

    def test_complex_blocked(self):
        board = ["....**.*", "...*.*..", ".*..***.", ".*.**...", ".**.*.*.", "..***...", ".......*", "....*.**"]
        board = [list(row) for row in board]
        self.assertEqual(count_queen_placements(board), 2)

    def test_new_complex_case(self):
        board = ["***.*..*", ".***..*.", "..**....", "..*****.", "...*...*", ".****.**", ".....*.*", "*....***"]
        board = [list(row) for row in board]
        self.assertEqual(count_queen_placements(board), 1)


if __name__ == "__main__":
    unittest.main()

Megoldás

A feladat célja az, hogy elhelyezzünk 8 vezért egy 8x8-as sakktáblán úgy, hogy azok ne támadhassák meg egymást. Ez azt jelenti, hogy a vezérek nem lehetnek ugyanabban a sorban, oszlopban, vagy átlón.

Az algoritmus lépései a következők:

Sorozatos próbálkozás: Minden sorban megpróbálunk egy vezért elhelyezni egy olyan oszlopban, ahol az nem támadható más vezérek által.
Biztonsági ellenőrzés: Minden vezér elhelyezése előtt ellenőrizzük, hogy az adott pozíció biztonságos-e. Azaz, az adott vezért sem vízszintesen, sem függőlegesen, sem átlósan nem fenyegeti más vezér.
Visszalépés: Ha egy sorban nem lehet biztonságosan elhelyezni egy vezért, visszalépünk az előző sorba, és új pozícióval próbálkozunk.
Megoldás megtalálása: Az algoritmus addig folytatja az elhelyezéseket, amíg sikeresen el nem helyez 8 vezért a táblán. Minden ilyen elrendezés egy megoldásnak számít.

Az algoritmus a megoldások számát adja vissza.

Bemenet

A bemenet egy 8x8-as sakktábla, ahol a foglalt mezőket a * jelöli, a szabad mezőket pedig a ..

Kimenet

Az algoritmus visszaadja az összes érvényes vezérelhelyezés számát. A fenti példában ez a szám 1.

Feltételek

A sakktábla 8x8-as méretű.
Minden mező vagy szabad, vagy foglalt lehet.
Csak olyan mezőre helyezhetünk vezért, ami szabad, és ahol nem támadja más vezér.

Algoritmus magyarázat

Az algoritmus minden sorban megpróbál egy vezért elhelyezni egy biztonságos pozícióban, miközben figyelembe veszi az előző sorokban elhelyezett vezérek pozícióit. Ha nem talál megfelelő helyet, visszalép az előző sorba, és másik pozícióval próbálkozik.

Az algoritmus addig folytatja a próbálkozásokat, amíg minden sorban sikeresen el nem helyez egy vezért, vagy minden lehetséges kombinációt meg nem vizsgál.

Lehetséges megoldás

def is_safe(queens, row, col):
    # Ellenőrzi, hogy biztonságos-e a vezért elhelyezni az adott (row, col) pozícióban
    for i in range(row):
        if queens[i] == col or abs(queens[i] - col) == abs(i - row):
            return False
    return True


def place_queens(board, queens, row):
    if row == 8:
        return 1  # Ha sikerült minden vezért elhelyezni
    count = 0
    for col in range(8):
        # Csak akkor próbáljuk meg elhelyezni a vezért, ha a mező nem foglalt
        if board[row][col] == "." and is_safe(queens, row, col):
            queens[row] = col  # Elhelyezzük a vezért a sorban
            count += place_queens(board, queens, row + 1)
            queens[row] = -1  # Visszalépés, hogy másik lehetőséget is próbáljunk
    return count


def count_queen_placements(board):
    queens = [-1] * 8  # Itt tároljuk, melyik sorban melyik oszlopba helyezzük a vezért
    return place_queens(board, queens, 0)

Rendezés és keresés¶

Buborékrendezés (Bubble Sort)¶

Feladatod az, hogy implementáld a buborékrendezés algoritmusát, amely egy egyszerű rendezési módszer. Az algoritmus ismételten végigmegy a listán, és egymás melletti elemeket hasonlít össze, cseréli őket, ha nincsenek megfelelő sorrendben. Ezt addig folytatja, amíg a lista teljesen rendezett nem lesz.

Bemenet
- Az első sor tartalmazza az elemek számát, \(n\)-et.
- A második sor tartalmazza az \(n\) egész számot, amelyeket rendezni kell.
Kimenet
- Írd ki a rendezett elemeket növekvő sorrendben, szóközzel elválasztva.

Miért hívják buborékrendezésnek ezt az algoritmust?

A buborékrendezés elnevezés onnan származik, hogy az algoritmus során a kisebb elemek fokozatosan "felúsznak" a lista elejére, hasonlóan ahhoz, ahogy a buborékok emelkednek a folyadék felszínére. Minden iteráció során a nagyobb elemek "lesüllyednek" a lista végére, miközben a kisebb elemek előre kerülnek.

Egymás melletti elemek összehasonlítása: Az algoritmus minden lépésben egymás melletti elemeket hasonlít össze, és ha az első elem nagyobb, mint a második, akkor cseréli őket. Ez biztosítja, hogy a nagyobb elemek fokozatosan hátrébb kerüljenek.
Többszöri áttekintés: Az algoritmus többször végigmegy a listán, hogy minden elem a megfelelő helyére kerüljön. Minden teljes áttekintés után a következő legnagyobb elem is a helyére kerül.
Egyszerűség és vizualizáció: A buborékrendezés könnyen megérthető és egyszerűen implementálható, ami különösen hasznossá teszi oktatási célokra. A "buborék" analógia segít vizualizálni az elemek mozgását a listában.

Példa

Tegyük fel, hogy a bemenet a következő:

Bemenet

5
64 34 25 12 22

A rendezett kimenet pedig:

Kimenet

12 22 25 34 64

Kiinduló Python kód

import unittest


def bubble_sort(arr):
    pass


class TestBubbleSort(unittest.TestCase):
    def test_bubble_sort_case1(self):
        self.assertEqual(bubble_sort([64, 34, 25, 12, 22, 11, 90]), [11, 12, 22, 25, 34, 64, 90], "1. teszt")

    def test_bubble_sort_case2(self):
        self.assertEqual(bubble_sort([5, 1, 4, 2, 8]), [1, 2, 4, 5, 8], "2. teszt")

    def test_bubble_sort_case3(self):
        self.assertEqual(bubble_sort([]), [], "3. teszt")

    def test_bubble_sort_case4(self):
        self.assertEqual(bubble_sort([1]), [1], "4. teszt")

    def test_bubble_sort_case5(self):
        self.assertEqual(bubble_sort([2, 1]), [1, 2], "5. teszt")


if __name__ == "__main__":
    unittest.main()

Megoldás

Bemenet

A feladatban egy egész számot kapunk első sorban, amely megadja a rendezendő elemek számát (\(n\)). A második sorban pedig \(n\) darab egész számot, amelyeket rendezni kell növekvő sorrendbe.

Kimenet

A kimenetben a rendezett elemeket kell kiírni növekvő sorrendben, az elemeket szóközzel elválasztva.

Algoritmus magyarázat

A buborékrendezés egy egyszerű rendezési algoritmus, amely az alábbi lépéseket követi:

Külső ciklus: Ismételten végigmegyünk a lista elemein, összesen \(n\) alkalommal, ahol \(n\) a lista hossza.
Belső ciklus: Minden iterációban egymás melletti elemeket hasonlítunk össze.
Csere: Ha egy elem nagyobb, mint a következő, akkor kicseréljük őket.
Optimalizáció: Ha egy teljes iteráció során nem történt csere, az azt jelenti, hogy a lista rendezett, és az algoritmus befejezhető.
Hatékonyság: Bár a buborékrendezés könnyen megérthető és implementálható, nagy adathalmazok esetén nem hatékony, mivel az időkomplexitása \(O(n^2)\).

Lehetséges megoldás

import unittest


def bubble_sort(arr):  # (1)
    n = len(arr)  # (2)
    for i in range(n):  # (3)
        swapped = False  # (4)
        for j in range(0, n - i - 1):  # (5)
            if arr[j] > arr[j + 1]:  # (6)
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # (7)
                swapped = True  # (8)
        if not swapped:  # (9)
            break  # (10)
    return arr  # (11)


class TestBubbleSort(unittest.TestCase):
    def test_bubble_sort_case1(self):
        self.assertEqual(bubble_sort([64, 34, 25, 12, 22, 11, 90]), [11, 12, 22, 25, 34, 64, 90], "1. teszt")

    def test_bubble_sort_case2(self):
        self.assertEqual(bubble_sort([5, 1, 4, 2, 8]), [1, 2, 4, 5, 8], "2. teszt")

    def test_bubble_sort_case3(self):
        self.assertEqual(bubble_sort([]), [], "3. teszt")

    def test_bubble_sort_case4(self):
        self.assertEqual(bubble_sort([1]), [1], "4. teszt")

    def test_bubble_sort_case5(self):
        self.assertEqual(bubble_sort([2, 1]), [1, 2], "5. teszt")


if __name__ == "__main__":
    unittest.main()

bubble_sort függvény: Meghatározzuk a buborékrendezés algoritmusát egy függvényben.
Lista hossza: Meghatározzuk az arr lista hosszát az n változóban.
Külső ciklus: Végigmegyünk a lista elemein, összesen n alkalommal, hogy minden elem a helyére kerüljön.
swapped változó: Bevezetünk egy swapped logikai változót, amely nyomon követi, történt-e csere az adott iterációban.
Belső ciklus: Minden iterációban összehasonlítjuk az egymás melletti elemeket a lista végéig, amelyet a n - i - 1 határoz meg (mivel a végén lévő elemek már rendezettek).
Összehasonlítás: Ellenőrizzük, hogy az aktuális elem nagyobb-e, mint a következő.
Csere: Ha igen, akkor kicseréljük az elemeket.
Csere jelzése: Ha történt csere, a swapped változót True-ra állítjuk.
Optimalizáció: Ha egy teljes iteráció során nem történt csere (swapped marad False), az azt jelenti, hogy a lista már rendezett.
Ciklus megszakítása: Ha a lista rendezett, kilépünk a külső ciklusból, hogy elkerüljük a felesleges iterációkat.
Visszatérés: A függvény visszaadja a rendezett listát.

Megjegyzés: A buborékrendezés nem a leghatékonyabb rendezési algoritmus, de oktatási célokra kiválóan alkalmas az algoritmikus gondolkodás fejlesztésére és az alapvető programozási fogalmak gyakorlására.

Különböző számok (Distinct Numbers)¶

Adott egy \(n\) hosszúságú számokból álló lista, a feladatod, hogy kiszámold a különböző értékek számát a listában.

Bemenet:
- Az első sor tartalmazza az \(n\) egész számot, ami a lista hosszát jelzi. (unittest esetén nem szükséges)
- A második sor \(n\) egész számot tartalmaz \(x_1, x_2, ..., x_n\).
Kimenet:
- Egy egész számot kell kiírnod, ami a különböző értékek száma a listában.

Feltételek

\(1 \leq n \leq 2 \times 10^5\)
\(1 \leq x_i \leq 10^9\)

Példa

Bemenet

2 2 2 3 3

Kimenet

Kiinduló Python kód

import unittest


def count_distinct_numbers(nums):
    pass


class TestDistinctNumbers(unittest.TestCase):
    def test_example_case(self): # (1)
        nums = [2, 2, 2, 3, 3]
        self.assertEqual(count_distinct_numbers(nums), 2)

    def test_all_distinct(self): # (2)
        nums = [1, 2, 3, 4, 5]
        self.assertEqual(count_distinct_numbers(nums), 5)

    def test_all_same(self): # (3)
        nums = [7, 7, 7, 7, 7]
        self.assertEqual(count_distinct_numbers(nums), 1)

    def test_large_input(self): # (4)
        nums = list(range(1, 200001)) # 1-től 200000-ig minden szám különböző
        self.assertEqual(count_distinct_numbers(nums), 200000)

    def test_single_number(self): # (5)
        nums = [1]
        self.assertEqual(count_distinct_numbers(nums), 1)

if __name__ == "__main__":
    unittest.main()

Ez a teszt a feladat alapértelmezett példáját használja. A bemenet egy lista: [2, 2, 2, 3, 3]. A teszt az assertEqual metódust használja annak ellenőrzésére, hogy a count_distinct_numbers függvény eredménye 2 lesz, mivel a listában két különböző szám található: 2 és 3.
Ebben a tesztben minden szám különböző: [1, 2, 3, 4, 5]. A függvénynek 5-öt kell visszaadnia, mivel minden elem egyedi. Az assertEqual ellenőrzi, hogy a függvény eredménye megegyezik a várt kimenettel.
Ez a teszt egy olyan listát használ, amelyben minden szám azonos: [7, 7, 7, 7, 7]. Ilyenkor a különböző számok száma 1 lesz, mivel a listában csak a 7-es szerepel. A teszt ellenőrzi, hogy a függvény eredménye 1.
Ez a teszt nagy méretű bemenetet ad a függvénynek, egy 200,000 elemű listát, amely 1-től 200,000-ig minden számot tartalmaz. Mivel minden szám különböző, a függvénynek 200,000-et kell visszaadnia. Ez a teszt segít annak ellenőrzésében, hogy a függvény megfelelően működik nagy bemenetek esetén is.
Ez a teszt egyetlen számot tartalmazó listát használ: [1]. Mivel csak egy szám van, a függvénynek 1-et kell visszaadnia. Ez a teszt ellenőrzi, hogy a függvény helyesen működik nagyon kis bemenetek esetén is.

Megoldás

A feladat az, hogy egy listában lévő különböző számokat megszámoljuk, majd ennek a számnak az értékét visszaadjuk. A kód egységteszteket (unittest) is tartalmaz, amelyek különböző esetekben ellenőrzik a függvény helyes működését.

Bemenet

A bemenet egy számokból álló lista, amely tartalmazza az összes elemet, amelyeket megvizsgálunk.

Kimenet

A kimenet egyetlen egész szám, amely a különböző számok számát adja meg.

Feltételek

Lista mérete (\(n\)):
- A bemeneti lista hossza \(n\), ahol: \(1 \leq n \leq 200000\)
Lista elemei (nums):
- Minden listaelem \(x_i\) egy egész szám, ahol: \(1 \leq x_i \leq 10^9\)
További feltételek:
- A bemenet mindig érvényes, tehát az adott számok mindig illeszkednek a fenti feltételekhez.
- Az eredmény mindig egy egész szám lesz, ami a különböző elemek számát adja vissza.

Algoritmus magyarázat

Input:
- A nums lista tartalmazza a számokat, amelyeket megvizsgálunk.
- Célunk az, hogy megszámoljuk, hány különböző elem található ebben a listában.
Függvény Megvalósítása: A függvény logikája három fő lépésből áll:
- Rendezés: A számokat először rendezzük, hogy egymás mellé kerüljenek a duplikált értékek. Ez egyszerűbbé teszi a különböző elemek számolását.
- Különböző számok megszámlálása: Végigmegyünk a listán, és ha egy elem eltér az előzőtől, növeljük a különböző számok számlálóját. Az első szám mindig különbözőnek tekintendő, így alapértelmezetten 1-ről indulunk.
- Eredmény visszaadása: A függvény visszaadja a különböző számok számát, amit a distinct_count változó tárol.

Lehetséges megoldás

Az alábbiakban egy lehetséges megoldás látható. Ez a megközelítés hatékony és könnyen követhető, mivel az egyedi elemek számlálása a rendezés után lineáris időben történik \(O(n)\).

def count_distinct_numbers(nums):
    if not nums:  # (1)
        return 0  # (2)

    # A számok rendezése
    nums.sort()  # (3)

    distinct_count = 1  # (4)
    for i in range(1, len(nums)):  # (5)
        if nums[i] != nums[i - 1]:  # (6)
            distinct_count += 1  # (7)

    return distinct_count  # (8)

Alapellenőrzés: Ha a nums lista üres, azonnal visszatérünk 0-val, mert nincs egyetlen szám sem, amit számolni kellene.
Üres lista kezelése: A 0 a visszatérési érték üres lista esetén.
Rendezés: A nums.sort() rendezi a számokat növekvő sorrendbe. A rendezés időkomplexitása \(O(n \log n)\).
Számláló indítása: Az első szám mindig különbözőnek számít, ezért a számláló kezdeti értéke 1.
Végighaladás a listán: Egy for ciklus segítségével a második elemtől kezdve végighaladunk a listán.
Egyedi számok keresése: Minden iteráció során összehasonlítjuk az aktuális elemet az előzővel. Ha eltérnek, az azt jelenti, hogy egy új különböző számot találtunk.
Számláló növelése: Ha egy különböző számot találunk, növeljük a distinct_count értékét.
Visszatérési érték: Végül visszaadjuk a különböző számok megszámolt értékét.

Dinamikus programozás¶

Kocka kombinációk (Dice Combinations)¶

Feladatod az, hogy megszámold, hányféleképpen lehet egy \(n\) összegű számot előállítani kockadobással, ahol egy vagy több dobást hajtasz végre. Minden dobás eredménye 1 és 6 között van.

Bemenet
- Az egyetlen bemeneti sor egy egész számot tartalmaz, \(n\)-t.
Kimenet
- Add meg, hányféleképpen lehet előállítani az \(n\) összeget, az eredményt a következő modulo értékkel kell megadni: \(10^9+7\)

Miért \(10^9+7\) moduloval kell megadni az értéket?

A modulo művelet szükséges ahhoz, hogy a nagy számokkal végzett számítások kezelhetőek maradjanak, elkerüljük a túlcsordulást, és biztosítsuk a program gyors és stabil működését nagy inputokra is. A \(10^9+7\) használata pedig egy elterjedt szabvány a versenyprogramozás világában.

Túl nagy számok kezelése: A kockadobásos probléma során a lehetséges kombinációk száma gyorsan nagyon nagyra nő, különösen akkor, ha n értéke nagy (például 1 millió). A modern számítógépek és programozási nyelvek képesek nagy számokat kezelni, de a teljesítményromlás és túlcsordulás problémái előjöhetnek, ha a számok túl nagyok lesznek. Ezért gyakran használunk modulo műveletet a nagy számok kezelésére. A modulo egyfajta maradékosztás, amely megakadályozza, hogy a számok nagyobbak legyenek, mint a \(10^9+7\), így a számok kezelhetőek maradnak.
Matematikai előnyök: A \(10^9+7\) egy nagy prímszám, ami matematikailag kedvező tulajdonságokat biztosít. A prímszámok előnyösek a számelméleti és kombinatorikai problémákban, mert a modulo művelet tulajdonságai egyszerűbbek és egyértelműbbek prímekkel. Például megkönnyíti a számok kezelésekor fellépő esetleges egyenlőségeket vagy inverz számításokat.
Versenyprogramozás szabvány: \(10^9+7\) egy szabvány a versenyprogramozásban. A legtöbb online programozási verseny és algoritmusprobléma ezt a számot használja a nagyméretű kimenetek kezelése érdekében. Így biztosítják, hogy a kimenetek sose lépjék túl a memóriakorlátokat, és optimalizált legyen a teljesítmény.

Példa a működésre

Tegyük fel, hogy egy algoritmus valamilyen kombinációk számát 1 000 000 050-nek számolja ki, ami túl nagy ahhoz, hogy hatékonyan kezeljük. Ha ezt az értéket modulo \(10^9+7\)-tel számítjuk, akkor: \(1000000050 \mod 1000000007 = 43\) Így a kimenet sokkal kisebb lesz, és ezzel biztosíthatjuk, hogy a számítások hatékonyak maradjanak anélkül, hogy túlcsordulás történne.

Feltételek

\(1 \leq n \leq 10^6\)

Példa

Például, ha \(n = 3\), 4 különböző lehetőség van:

\(1 + 1 + 1\)
\(1 + 2\)
\(2 + 1\)
\(3\)

Bemenet

Kimenet

Kiinduló Python kód

import unittest


def count_dice_combinations(n):
    return 0


class TestDiceCombinations(unittest.TestCase):

    def test_count_dice_combinations_1(self):
        self.assertEqual(count_dice_combinations(3), 4, "1. teszt")

    def test_count_dice_combinations_2(self):
        self.assertEqual(count_dice_combinations(1), 1, "2. teszt")

    def test_count_dice_combinations_3(self):
        self.assertEqual(count_dice_combinations(6), 32, "3. teszt")

    def test_count_dice_combinations_4(self):
        self.assertEqual(count_dice_combinations(8), 125, "4. teszt")

    def test_count_dice_combinations_5(self):
        self.assertEqual(count_dice_combinations(10), 492, "5. teszt")

    def test_count_dice_combinations_6(self):
        self.assertEqual(count_dice_combinations(50), 660641036, "6. teszt")


if __name__ == "__main__":
    unittest.main()

Megoldás

Bemenet

A feladatban egy egész számot kapunk bemenetként, amelyet \(n\)-nel jelölünk. Ez az érték jelenti azt az összeget, amelyet el kell érnünk kockadobásokkal. Minden kockadobás eredménye 1 és 6 közötti szám lehet. A bemenet tehát egy egész szám, amely egyetlen sorban szerepel.

Kimenet

A feladat kimenete annak a lehetőségek számának megadása, amely segítségével elérhetjük az \(n\) összeget. Az eredményt modulo \(10^9+7\)-tel kell megadni, hogy elkerüljük a túl nagy számokat.

Feltételek

A bemenetként adott \(n\) értéke \(1\) és \(10^6\) között van: \(1 \leq n \leq 10^6\)
A válasz nagyságrendje miatt a kimenetet modulo \(10^9+7\) kell megadni.

Algoritmus magyarázat

A feladat megoldása dinamikus programozással történik. A dinamikus programozás lényege, hogy felbontjuk a problémát kisebb részekre, és az eredményeket elmentjük egy táblázatban, hogy később újra felhasználhassuk őket.

Hozzunk létre egy dp nevű tömböt, ahol dp[i] az i érték elérésének összes lehetséges módját tárolja.
Kiinduláskéntdp[0] = 1, mivel egyetlen módja van annak, hogy nulla értéket érjünk el: nem dobunk kockát.
Minden i értéknél (1-től n-ig), végignézzük az összes lehetséges dobást (1-től 6-ig), és hozzáadjuk a korábbi értékek kombinációit a jelenlegi értékhez.
Az összes számítás során az eredményt modulo \(10^9+7\)-tel számoljuk, hogy elkerüljük a túlcsordulást.

Lehetséges megoldás

import unittest

MOD = 10**9 + 7  # (1)

def count_dice_combinations(n):  # (2)
    dp = [0] * (n + 1)  # (3)
    dp[0] = 1  # (4)

    for i in range(1, n + 1):  # (5)
        for j in range(1, 7):  # (6)
            if i - j >= 0:  # (7)
                dp[i] = (dp[i] + dp[i - j]) % MOD  # (8)

    return dp[n]  # (9)

class TestDiceCombinations(unittest.TestCase):

    def test_count_dice_combinations_1(self):
        self.assertEqual(count_dice_combinations(3), 4, "1. teszt")

    def test_count_dice_combinations_2(self):
        self.assertEqual(count_dice_combinations(1), 1, "2. teszt")

    def test_count_dice_combinations_3(self):
        self.assertEqual(count_dice_combinations(6), 32, "3. teszt")

    def test_count_dice_combinations_4(self):
        self.assertEqual(count_dice_combinations(8), 125, "4. teszt")

    def test_count_dice_combinations_5(self):
        self.assertEqual(count_dice_combinations(10), 492, "5. teszt")

    def test_count_dice_combinations_6(self):
        self.assertEqual(count_dice_combinations(50), 660641036, "6. teszt")


if __name__ == "__main__":
    unittest.main()

MOD változó: Egy konstans, amelyet a kimenet modulo értékeként használunk, \(10^9+7\). Ez biztosítja, hogy az eredmények ne legyenek túl nagyok.
count_dice_combinations függvény: Ez a fő függvény, amely kiszámítja, hányféleképpen lehet elérni a bemenetként kapott n összeget kockadobásokkal.
DP tömb inicializálása: Létrehozunk egy dp nevű tömböt, amelyben az összes lehetséges n értékhez tároljuk a kombinációk számát. A tömb mérete n+1, mert 0-tól n-ig kell értékeket tárolnunk.
Kezdeti érték beállítása: A kiindulópont az, hogy a 0 összeget egyféleképpen érhetjük el (nem dobunk semmit), ezért dp[0] = 1.
Fő ciklus: Az i ciklus végigmegy az összes lehetséges értéken 1-től n-ig, hogy kiszámítsuk, hányféleképpen érhetjük el az adott összeget.
Dobások ciklusa: A belső ciklus az összes lehetséges kockadobáson (1-től 6-ig) megy végig, hogy megnézzük, hogyan tudjuk az i összeget elérni az előző összegek alapján.
Érvényességi ellenőrzés: Itt ellenőrizzük, hogy az i - j érték nem negatív, mivel csak pozitív vagy nulla indexű értékekkel dolgozhatunk a dp tömbben.
DP tömb frissítése: Az aktuális i értékhez hozzáadjuk az előző i - j értékhez tartozó kombinációkat, mivel ebből a dobásokkal elérhetjük az i összeget.
Visszatérési érték: A függvény végül visszaadja az n értékhez tartozó kombinációk számát a dinamikus programozás tömbből.

Fák, gráfok¶

Bináris fa maximális mélysége¶

Feladatod az, hogy meghatározd egy bináris fa maximális mélységét.

Bemenet
- Egy bináris fa beágyazott listák formájában.
Kimenet
- Egy egész szám, amely a fa maximális mélységét jelenti.

Hogyan ábrázoljuk a bináris fát beágyazott listákkal?

A bináris fa beágyazott listákkal való ábrázolása során minden csomópontot egy három elemű listával reprezentálunk:

Első elem: A csomópont értéke.
Második elem: A bal gyermek, amely lehet None vagy egy másik csomópont (lista).
Harmadik elem: A jobb gyermek, amely szintén lehet None vagy egy másik csomópont (lista).

Ez a struktúra rekurzív, mivel a gyermekek is ugyanolyan formátumú listák lehetnek.

Példa

Tekintsük a következő bináris fát:

graph TD;
    1((1))
    1 --> 2((2))
    1 --> 3((3))
    2 --> 4((4))

Ezt a fát beágyazott listákkal így ábrázolhatjuk:

[1, [2, [4, None, None], None], [3, None, None]]

Ennek a fának a maximális mélysége \(3\), mivel a leghosszabb út a gyökértől a levélig: \(1 \rightarrow 2 \rightarrow 4\).

Bemenet

[1, [2, [4, None, None], None], [3, None, None]]

Kimenet

Kiinduló Python kód

import unittest


def max_depth(root):
    pass


class TestMaxDepth(unittest.TestCase):
    def test_max_depth_case1(self):
        root = [1, [2, [4, None, None], None], [3, None, None]]
        self.assertEqual(max_depth(root), 3, "Egyszerűbb fa")

    def test_max_depth_case2(self):
        root2 = [1, None, None]
        self.assertEqual(max_depth(root2), 1, "Egyetlen csomópontból álló fa")

    def test_max_depth_case3(self):
        self.assertEqual(max_depth(None), 0, "Üres fa")

    def test_max_depth_case4(self):
        root3 = [1, [2, [3, [4, None, None], None], None], None]
        self.assertEqual(max_depth(root3), 4, "Egy mélyebb fa")


if __name__ == "__main__":
    unittest.main()

Megoldás

Bemenet

A bemenet egy bináris fa, amely beágyazott listákkal van ábrázolva. Minden csomópont egy listából áll: [érték, bal_oldal, jobb_oldal], ahol bal_oldal és jobb_oldal lehet None vagy egy másik csomópont ugyanebben a formátumban.

Kimenet

A kimenet egy egész szám, amely a bináris fa maximális mélységét jelenti.

Algoritmus magyarázat

A maximális mélység meghatározása rekurzív módon történik, hasonlóan az osztályos megoldáshoz, de itt listákat használunk.

Alapeset: Ha a jelenlegi csomópont None, akkor a mélység 0.
Rekurzív lépés: Meghívjuk a max_depth függvényt a bal és a jobb gyermekre.
Maximális mélység meghatározása: A bal és jobb mélységek közül kiválasztjuk a nagyobbat, és hozzáadunk 1-et a jelenlegi csomópont miatt.

Lehetséges megoldás

import unittest


def max_depth(root):  # (1)
    if root is None:  # (2)
        return 0
    else:
        left_depth = max_depth(root[1])  # (3)
        right_depth = max_depth(root[2])  # (4)
        return max(left_depth, right_depth) + 1  # (5)


class TestMaxDepth(unittest.TestCase):
    def test_max_depth_case1(self):
        root = [1, [2, [4, None, None], None], [3, None, None]]
        self.assertEqual(max_depth(root), 3, "Egyszerűbb fa")

    def test_max_depth_case2(self):
        root2 = [1, None, None]
        self.assertEqual(max_depth(root2), 1, "Egyetlen csomópontból álló fa")

    def test_max_depth_case3(self):
        self.assertEqual(max_depth(None), 0, "Üres fa")

    def test_max_depth_case4(self):
        root3 = [1, [2, [3, [4, None, None], None], None], None]
        self.assertEqual(max_depth(root3), 4, "Egy mélyebb fa")


if __name__ == "__main__":
    unittest.main()

max_depth függvény: Meghatározzuk a maximális mélységet a gyökércsomóponttól kiindulva.
Alapeset ellenőrzése: Ha a jelenlegi csomópont None, akkor visszatérünk 0-val, mivel nincs további mélység.
Bal mélység meghatározása: Rekurzívan meghívjuk a max_depth függvényt a bal gyermekre, amely a lista második eleme (root[1]).
Jobb mélység meghatározása: Rekurzívan meghívjuk a max_depth függvényt a jobb gyermekre, amely a lista harmadik eleme (root[2]).
Maximális mélység kiszámítása: A bal és jobb mélységek közül kiválasztjuk a nagyobbat, és hozzáadunk 1-et a jelenlegi csomópont miatt.