Programiranje 1 (22/23)

Matematične funkcije

Fakulteta

Fakulteto, n!, navadno računamo kot produkt n števil; 5! = 1*2*3*4*5. Lahko pa bi jo definirali tudi takole: fakulteta(n) je n-krat toliko kot fakulteta(n-1). Če jo lahko tako definiramo - pa jo tako še sprogramirajmo!

Da se stvar izteče pa se moram dogovoriti še, da je fakulteta 0 enaka 1.

def fakulteta(n):
    if n == 0:
        return 1
    return n * fakulteta(n - 1)

Vsota prvih n naravnih števil

Vsoto prvih n naravnih števil lahko izračunamo kot 1+2+3+4+5+...+n, lahko pa jo definiramo tudi z rekurzijo. Napišite funkcijo vsotan(n), ki bo s pomočjo rekurzije sešteva prvih n naravnih števil. Razmislite, kdaj se rekurzija zaključi.

def vsota(n):
    if n == 1:
        return 1
    return n + vsota(n - 1)

Fibonaccijevo zaporedje

Napišite funkcijo fibonacci(n), ki bo vrnila n-ti člen Fibonaccijevega zaporedja.

Namig: Najprej napiši funkcijo brez rekurzije, nato pa jo poskusi napisati še z rekurzijo.

def fibonacci(n):
    if (n == 0 or n == 1):
        return n
    return fibonacci(n-1) + fibonacci(n-2)
    

Največji skupni delitelj

Napiši funkcijo gcd(a, b), ki prejme dve števili in s pomočjo rekurzije vrne njun največji skupni delitelj. Pomagaj si z rešitvijo naloge s prvih vaj.

def gcd(a, b):
    if b == 0:
        return a
    return  gcd(b, a % b)

Vsota

Vsota elementov nekega seznama je enaka vsoti prvega elementa in vsota seznama od prvega elementa naprej. Znate to sprogramirati? Funkciji naj bo ime vsota, kot argument prejme seznam števil.

Spomnite se, kako smo na predavanjih ugotavljali, ali seznam vsebuje določen element.

def vsota(stevila):
    if stevila == []:
        return 0
    return stevila[0]+vsota(stevila[1:])

Koliko lihih števil je v seznamu?

Napišite funkcijo lihih(s), ki prebere seznam števil in z uporabo rekurzije prešteje, koliko je lihih.

def lihih(s):
    if len(s) == 0:
        return 0
    if s[0] % 2 == 1:
        return 1 + lihih(s[1:])
    return lihih(s[1:])

Seznam sodih števil

Napišite funkcijo soda(s), ki kot argument dobi seznam števil in soda števila prepiše v nov seznam. Uporabi rekurzijo.

def soda(s):
    if not s:
        return []
    if s[0] % 2 == 0:
        return [s[0]]+soda(s[1:])
    return soda(s[1:])

Pretvori v dvojiški sestav

Napišite funkcijo v_dvojiski(n), ki kot argument dobi desetiško število in z uporabo rekurzije vrne niz, ki predstavlja to število v dvojiškem številskem sestavu.

def v_dvojiski(n):
    if (n==0 or n==1):
        return str(n)
    return v_dvojiski(n // 2) + str(n % 2)

Iz dvojiškega v desetiško število

Napišite funkcijo iz dvojiskega(s), ki kot argument dobi niz, ki predstavlja zapis števila v dvojiškem številskem sestavu in vrne desetiško vrednost tega števila. Funkcija naj uporablja rekurzijo.

def iz_dvojiskega(s):
    if len(s) == 0:
        return 0
    return 2 * iz_dvojiskega(s[:-1]) + int(s[-1])

def iz_dvojiskega(s):
    if not s:
        return 0
    return int(s[0]) * 2**(len(s) - 1) + iz_dvojiskega(s[1:])