Opgaver/Øvelser

Aflevering af opgaver

Send en mail til neinalways@gmail.com med:

  • Ordet grprog i emnelinjen.
  • Én vedlagt arkivfil i rar, jar, 7z, zip, eller tgz.format indeholdende jeres kildekode.
  • Alle relevante filer skal være i arkivfilen. Relevante filer er .py-filer.
  • Arkivfilen skal have lektionsnummer og initialer i filnavnet. Fx NMLlektion3.zip. INGEN MELLEMRUM i directory- eller filnavne, tak!

Opgave 6.1

Tegn et stack-diagram for følgende:

def b(z):
    prod = a(z, z)
    print(z, prod)
    return prod

def a(x, y):
    x = x + 1
    return x * y

def c(x, y, z):
    total = x + y + z
    square = b(total)**2
    return square

x = 1
y = x + 1
print(c(x, y+3, x+y))

Hvad printes? Ræsonner før du afprøver koden.

Opgave 6.2

Ackermann-functionen, A(m, n), defineres således:

A(m, n) = { n + 1 if m = 0
A(m−1, 1) if m > 0 ∧ n = 0
A(m−1, A(m, n−1)) if m > 0 ∧ n > 0

Læs om Ackermann funktionen her. Skriv nu en funktion ack, der evaluerer Ackermann funktionen. Test den i et program ass62.py. Test bl a ack(3, 4), der skulle give 125. Hvad sker der for større værdier af m og n?

Opgave 6.3

Et palindrom er et ord, der skrives ens forfra og bagfra. Eksempler på danske enkeltordspalindromer er "kajak," "rejer" og "regninger". På engelsk “noon” og “redivider”. Se https://da.wikipedia.org/wiki/Palindrom og/eller https://en.wikipedia.org/wiki/Palindrome. En rekursiv definition af palindrom:

Et palindrom er en streng (ord, tal), hvis første og sidste tegn er ens, og hvor det resterende (midten) er et palindrom.

Her følger tre funktioner, der returnerer henholdsvis første og sidste tegn samt midterste streng:

""" first returns first character of a word """
def first(word):
    return word[0]

""" last returns last character of a word """
def last(word):
    return word[-1]

""" middle returns middle string of a word
    ie new string without first and last chars
    of original string
    Uses slicing, re [Dow15] chapter 8
"""
def middle(word):
    return word[1:-1]

En af funktionerne anvender slicing, der gennemgås i [Dow15] kaitel 8.

  1. Tast funktionerne ind i en fil (modul) kaldet palindrome.py og test dem i et program ass631.py Programmet skal hjælpe med at besvare spørgsmål, som fx "hvad sker der, hvis middle kaldes med et argument på to tegn? Ét tegn? Eller endnu værre "hvad sker der, hvis middle kaldes med en tom streng?" En tom streng skrives som ''.
  2. Skriv en funktion isPalindrome, som tager ét argument, en streng, og returnerer værdien True hvis strengen er et palindrom, og ellers returnerer False.

    Hint: Husk at der findes en funktion (indbygget) len, der returnerer længden af en streng.

    Test funktionaliteten gennem ass632.py.

Opgave 6.4

Et tal, a, er en potens af b hvis det er deleligt med b og a/b er en potens af b. Skriv en funktion isPower, der tager to argumenter, a og b og returnerer True hvis a er en potens af b. Husk at overveje base case.

Opgave 6.5

Den største fællesnævner, gcd, Greatest Common Denominator, også kaldet Greatest Common Divisor, af to tal a og b er det største tal, der "går op i" begge tal.

En måde, hvorpå vi kan finde gcd, er baseret på, at hvis r er resten fra divisionen a/b, så er gcd(a, b) = gcd(b, r). Som grænsetilfælde er gcd(a, 0) = a.

Skriv funktionen gcd, der tager argumenterne a og b og returnerer deres største fællesnævner. Test den i programmet ass65.py.

Downey, [Dow15], krediterer et eksempel fra [Abl96] for denne opgave. Den er en implementering af verdens ældste ikke-trivielle algoritme, Euclids algoritme fra hans Elementer, bog 7, ca. 300 fvt.