Märgi järgnevatest kõik funktsioonid, mis prindivad positiivse täisarvu n kahendesituse.

Mis ülesannet lahendab järgnev funktsioon?

def f(a, b):
    if b == 0:
        return a
    return 1 + f(a, b-1)

Mille prindib järgmine funktsioon sisendil "INFORMATSIOON"?

def tag_a(sõne):
    if len(sõne) == 0:
        return
    print(sõne[0], end=' ')
    tag_b(sõne[1:])
def tag_b(sõne):
    if len(sõne) == 0:
        return
    tag_a(sõne[1:])
    print(sõne[0], end=' ')

Esimesena kutsutakse välja funktsioon

Olgu antud järgmised funktsioonid naturaalarvude paarsuse arvutamiseks:

def paaris(n):
    if n == 0:
        return True
    return not paaritu(n-1)
def paaritu(n):
    if n == 1: 
        return True
    return not paaris(n-1)

Milline järgnevatest väidetest on tõene?

Olgu antud järgnev rekursiivne funktsioon, mis peaks leidma arvu kahega jagamisel tekkiva jäägi. Kas see funktsioon peatub iga positiivse paaritu sisendi korral?

def mod2(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return mod2(n-2)

Mille leiab järgmine funktsioon, kus funktsiooni parameetriks on teatav sõne s?

public static String leia(String s) {
    if (s.length() > 1) {
        return leia(s.substring(1));
    }
    return s;
}

Millised järgnevatest sorteerimismeetoditest on parima juhu ajalise keerukusega Θ(n)? Eeldada, et meetodid on realiseeritud leheküljel http://www.sorting-algorithms.com toodud algoritmidega (kiirmeetodist kolmeharuline variant).

Märgi kõik sobivad vastused.

Läbides massiivi A mõõtmetega n × n, töötleb algoritm iga elementi A[i, j] ajaga Θ(i+j).

Milline on kogu tabeli töötlemise algoritmi ajaline keerukus kujul Θ(f(n))?

Definitsioon.

Olgu f ja g naturaalarvuliste argumentidega

funktsioonid. Siis f on O(g), kui leiduvad c > 0 ja N > 0 nii, et |f(n)| <

c|g(n)| iga n > N korral.

Olgu

• f(n) = 2n² + 6n - 4
• g(n) = n

Kas nende funktsioonide puhul kehtib lause „f on O(g)”?

Vali kõik

sobivad variandid.