MO417 - QUESTÃO PARA A PROVA ORAL

Número:

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[n] = 1
            else:
                x=R(X,n-1)+R(X,n-2)
            X[n] = x
            return x

e B(n) o seguinte algoritmo:

    B(n):
        if i<=2:
            return 1
        X[0]
        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 algoritmos levam O(n) passos no pior caso.

B) O algoritmo A é a 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 algoritmos retornam o número de Fibonacci para qualquer número natural n.

E) NDA

Ideia original de: Félix Carvalho Rodrigues