Kihagyás

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.

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

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

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
3
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!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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:

  1. \(3\) páratlan, így \(3 \times 3 + 1 = 10\)
  2. \(10\) páros, így \(10 / 2 = 5\)
  3. \(5\) páratlan, így \(5 \times 3 + 1 = 16\)
  4. \(16\) páros, így \(16 / 2 = 8\)
  5. \(8\) páros, így \(8 / 2 = 4\)
  6. \(4\) páros, így \(4 / 2 = 2\)
  7. \(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:

  1. Kezdjük a bemeneti \(n\) értékkel.
  2. 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.
  3. Minden egyes lépés után írjuk ki az \(n\) aktuális értékét.
  4. 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ó:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
65
Kiinduló Python kód 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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:

  1. 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.
  2. 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.
  3. 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.
  4. 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 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

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
2
Kiinduló Python kód 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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()
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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)
  1. Alapellenőrzés: Ha a nums lista üres, azonnal visszatérünk 0-val, mert nincs egyetlen szám sem, amit számolni kellene.
  2. Üres lista kezelése: A 0 a visszatérési érték üres lista esetén.
  3. Rendezés: A nums.sort() rendezi a számokat növekvő sorrendbe. A rendezés időkomplexitása \(O(n \log n)\).
  4. 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.
  5. Végighaladás a listán: Egy for ciklus segítségével a második elemtől kezdve végighaladunk a listán.
  6. 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.
  7. 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.
  8. 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.

  1. 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.
  2. 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.
  3. 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
3
Kimenet
4
Kiinduló Python kód 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import unittest


def count_dice_combinations(n):
    return 0


class TestDiceCombinations(unittest.TestCase):
    def test_count_dice_combinations(self):
        self.assertEqual(count_dice_combinations(3), 4, "1. teszt")
        self.assertEqual(count_dice_combinations(1), 1, "2. teszt")
        self.assertEqual(count_dice_combinations(6), 32, "3. teszt")
        self.assertEqual(count_dice_combinations(8), 125, "4. teszt")
        self.assertEqual(count_dice_combinations(10), 492, "5. teszt")
        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 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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(self):
        self.assertEqual(count_dice_combinations(3), 4, "1. teszt")
        self.assertEqual(count_dice_combinations(1), 1, "2. teszt")
        self.assertEqual(count_dice_combinations(6), 32, "3. teszt")
        self.assertEqual(count_dice_combinations(8), 125, "4. teszt")
        self.assertEqual(count_dice_combinations(10), 492, "5. teszt")
        self.assertEqual(count_dice_combinations(50), 660641036, "6. teszt")

if __name__ == "__main__":
    unittest.main()
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. É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.
  8. 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.
  9. 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.