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

Základní kurs programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Obsahem kursu je programovací jazyk Pascal a Turbo Pascal, problematika návrhu algoritmů a tvorby programů.
Želvík
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 6. 1. 2023 11:20
Typ studia: Informatika Bc.

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

Příspěvek od Želvík »

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.
wildgreen
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 23. 1. 2023 23:13
Typ studia: Informatika Bc.

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

Příspěvek od wildgreen »

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

Kód: Vybrat vše

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)

Kód: Vybrat vše

# 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()
Přílohy
A6.pdf
(722.84 KiB) Staženo 51 x
Odpovědět

Zpět na „PRG030 Programování I“