MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-034

Enunciado: Seja A(n) o seguinte algoritmo:

    A(n):
        for i in 1..n:
            X[i] = -1
        return R(X,n)
    R(X,n):
        if X[n] >= 0:
            return X[n]
        else:
            if n <= 2:
                x = 1
            else:
                x = R(X,n-1)+R(X,n-2)
            X[n] = x
            return x

e B(n) o seguinte algoritmo:

    B(n):
        for i in 1..n:
            if i<=2:
                X[i] = 1
            else:
                X[i] = X[i-1] + X[i-2]
        return X[n]

Qual afirmação NÃO é verdadeira?

A) Ambos os algoritmos levam O(n) passos no pior caso.

B) O algoritmo A é uma versão memoizada do algoritmo recursivo de Fibonacci.

C) O algoritmo B é uma versão do algoritmo de Fibonacci que utiliza programação dinâmica.

D) Ambos os algoritmos retornam o n-ésimo número de Fibonacci para qualquer natural n.

E) NDA

 Ideia original de: Félix Carvalho Rodrigues