Zápočtový test 6. 1. 2023 - Šefl

Zadání:
Na vstupu máme na jednom řádku číslo K představující počet stavítek a na dalším číslo L představující počet možných poloh stavítka.
Máme vypsat počet kombinací, jak je možné otevřít zámek s K stavítky, každé s L možnými polohami, přičemž polohy každých dvou sousedních stavítek se mohou lišit maximálně o 1. Úloha se má řešit rekurzivně.

Např. K = 2, L = 3:
Možnosti jsou:
1 1
1 2
2 1
2 2
2 3
3 2
3 3
Takže celkem 7.
Např. 1 3 ne, protože to se liší o 2

Pro K = 2, L = 4:
1 1
1 2
2 1
2 2
2 3
3 2
3 3
3 4
4 3
4 4
Takže 10.

Jedno z funkčních řešení podle ReCodExu

k = int(input())  # number of pins
l = int(input())  # max height

# generate combinations recursively

keys = []

def is_valid_sequence(prev, cur):
    return (cur + 1 == prev) or (cur - 1 == prev) or (cur == prev)

def get_key_count(k, l, key=[]):
    prev_element = None
    if len(key) > 0:
        prev_element = key[-1]
    if len(key) == k:
        keys.append(key)
        return
    for lvl in range(1, l+1):
        if prev_element is not None:
            if not is_valid_sequence(prev_element, lvl):
                continue
        new_key = list(key)
        new_key.append(lvl)
        get_key_count(k, l, new_key)
    return len(keys)

print(get_key_count(k, l))

Moc podobný algoritmus lze také nalézt v přednášce z algoritmizace o rekurzivním generování (viz příloha, slidy 21-24)

# Vypsat všechna K-ciferná čísla v poziční soustavě o základu n
def k_numbers(k, r=10, n=[]):for i in range(r):n.append(i)if len(n) < k:k_numbers(k, r, n)else:print(n)n.pop()

Attachments:

• A6.pdf