EP1: Comentários

EP1: Comentários

by José Coelho de Pina -
Number of replies: 2

Salve,

O que vocês acham da função indice() a seguir?
Alguém propõe uma versão recursiva dessa função?
O comentário na linha do return faz sentido?

#-----------------------------------------------
def indice(item, lista):
    '''(objeto,list) -> int ou None

    Recebe um objeto 'item' e uma lista 'lista' e retorna o
    indice da posicao em que item ocorre na lista.
    Caso item nao ocorra na lista a funcao retorna None.

    Exemplos:
    >>> indice(1,[-2,13,1,14])
    2
    >>> indice(1,[1,-2,13,14])
    0
    >>> indice(1,[2,13,14,1])
    3
    >>> indice(1,[2,13,14,-1])
    >>> indice(1.3,[2,13,14,1.3])
    3
    ''' 
    n = len(lista) 
    for i in range(n):
        if lista[i] == item:
            return i
    return None  # supérfluo
In reply to José Coelho de Pina

Re: EP1: Comentários

by Willian Akira Mizutani -

Ela funciona bem. Na pior das hipóteses, ela demora n.

Uma possível versão recursiva seria perguntar se apenas o primeiro elemento é igual a <item>. Se sim, retorna 0. Se não, retorna o resultado de <indice(item,lista[1:n]) + 1>

E sim, o comentário faz sentido.

 

In reply to José Coelho de Pina

Re: EP1: Comentários

by José Coelho de Pina -

Ela funciona bem. Na pior das hipóteses, ela demora n.

Legal!
No pior caso o consumo de tempo é proporcional a n.
Nesses casos, como veremos nas próximas aulas, também é comum dizermos que o consumo de tempo é ONo.

Agora, o que vocês acham da seguinte função recursiva.
Está correta? Consumo de tempo?

#-----------------------------------------------
def indice(item, lista):
    '''(objeto,list) -> int ou None

    Recebe um objeto 'item' e uma lista 'lista' e retorna o
    menor índice de uma posição em que item ocorre na lista.
    Caso item não ocorra na lista a função retorna None.

    Pré-condição: supõe n >= 0.

    Exemplos:
    >>> indice(1,[-2,13,1,14])
    2
    >>> indice(1,[1,-2,13,14])
    0
    >>> indice(1,[2,13,14,1])
    3
    >>> indice(1,[2,13,14,-1])
    >>> indice(1.3,[2,13,14,1.3])
    3
    '''
    if item == lista[0]: return 0
    return 1 + indice(item, lista[1:]) # equivalente a: return 1 + indice(item,lista[1:n])