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

<{ForumPost(poster="Želvík", timestamp=2023-01-06 12:20:07)}>
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.
<{/ForumPost}>

<{ForumPost(poster="wildgreen", timestamp=2023-01-24 00:02:03)}>
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](/Forum%20archiv/Attachments/7460_b09c41a7173bcf25fc892b52fc6468bf)*

<{/ForumPost}>