a) Escreva uma função que, dados como parâmetro uma lista L e um número real x, devolve a posição em que x ocorre na lista ou None caso x não esteja na lista.
b) Usando a função do interior, escreva um programa que lê uma sequência de números reais e depois imprime a sequência eliminando os elementos repetidos.
def acha(lista, x):
''' (list, float) -> int
Retorna a posição em que x ocorre na lista, ou None caso contrário.
'''
i = 0
while i < len(lista) and lista[i] != x:
i += 1
if i == len(lista): # chegou ao final da lista sem encontrar x
return None
else:
return i
def main():
n = int(input("Digite o número de elementos da sequência de números reais: "))
seq = []
for i in range(1,n+1):
numero = float(input("Digite o %dº número da sequência: " %i))
if acha(seq, numero) == None: # Se o número lido ainda não está na sequência,
seq.append(numero) # inclui o número na sequência
print("A sequência sem repetições fica: ", seq)
##################################
main()
O algoritmo usado para implementar a função acha(lista,x) acima é chamado de Busca Sequencial. Observe que, nesse algoritmo, toda a sequência precisa ser varrida quando o x procurado não está em lista.
Mas é possível deixar esse algoritmo mais eficiente quando os elementos da lista na qual se quer buscar um valor estão ordenados. O código abaixo mostra uma nova versão da função -- a acha2(lista_ordenada,x); nessa nova versão, a função pode detectar que um elemento não está na lista ordenada mesmo antes de chegar ao seu final:
def acha2(lista_ordenada, x):
''' (list, float) -> int
A função recebe uma lista ordenada e um valor x e retorna a posição em que x
ocorre na lista ordenada, ou None caso contrário.
'''
i = 0
while i < len(lista_ordenada) and lista_ordenada[i] < x:
# avança i enquanto ainda não foi encontrado em i um valor igual ou maior que x
i += 1
if i < len(lista_ordenada) and lista_ordenada[i] == x: # encontrou x na posição i da lista
return i
else:
return None
##################################
# Testando a função
seq_ordenada = [1.2, 2.5, 3.14, 8.75]
x_buscado = 3.14
print("A posição de", x_buscado, "na sequência", seq_ordenada, "é:", acha2(seq_ordenada,x_buscado))
Quando a sequência está ordenada, a busca pode ser ainda mais eficiente do que a implementada na função acha2 acima. Para isso, usamos uma estratégia parecida com a forma como buscamos palavras em um dicionário ou nomes em um catálogo de telefones ou endereços em papel. Nesse caso, ao invés de testar um elemento de cada vez sequencialmente, podemos aplicar o seguinte algoritmo:
Observe que nesse algoritmo, a cada vez que executamos os passos 3 ou 4, metade da sequência é eliminada da busca. É por isso que o algoritmo é chamado de Busca Binária.
Para "enxergar" melhor quão mais eficiente a Busca Binária é em relação à Busca Sequencial, considere o seguinte exemplo: procuramos um dado x em uma sequência ordenada com 512 elementos, mas x não está nesta sequência. Antes de indicar que x não está na sequência, o algoritmo de Busca Sequencial precisa testar todos os 512 elementos da sequência. No caso da Busca Binária, o primeiro teste elimina 256 elementos, o segundo 128, o terceiro 64, e depois 32, 16, 8, 4, 2, até que a lista contenha apenas 1 elemento. Dessa forma, ao invés de 512, apenas 9 elementos (ou log(len(sequencia))) precisam ser testados.
Escreva uma função que implemente o algoritmo da Busca Binária. A sua função deve receber como parâmetro uma lista ordenada e um número real x e devolver a posição em que x ocorre na lista ou None caso x não esteja na lista.
def busca_binaria(seq, x):
''' (list, float) -> bool
retorna a posição em que x ocorre na lista ordenada,
ou None caso contrário, usando o algoritmo de busca binária.
'''
n = len(seq)
inicio = 0
fim = n-1
while inicio <= fim:
meio = (inicio + fim) // 2
if x == seq[meio]: # achou x
return meio
elif x < seq[meio]: # x pode estar na primeira metade da sequência
fim = meio - 1
else:
inicio = meio + 1 # x pode estar na segunda metade da sequência
return None
##########################################
# Alguns testes da função busca_binaria
seq = [4, 10, 80, 90, 91, 99, 100, 101]
testes = [80, 50]
print("A sequência usada para testes é: ", seq)
for t in testes:
pos = busca_binaria(seq, t)
if pos is None:
print("Nao achei ", t)
else:
print("Achei %d na posição %d" %(t, pos))
def busca_binaria_recursiva(seq, x, inicio, fim):
''' (list, float, inicio, fim) -> bool
retorna a posição em que x ocorre na sublista entre as posições inicio e fim
(ou seja, em {seq[inicio], seq[inicio+1],...,seq[fim-1],seq[fim]} )
ou None caso contrário, usando o algoritmo de busca binária.
'''
meio = (inicio + fim) // 2
if inicio > fim: # caso base (subsequencia vazia)
return None
elif x == seq[meio]: # achou x
return meio
elif x < seq[meio]: # x pode estar na primeira metade da sequência
return busca_binaria_recursiva(seq, x, inicio, meio - 1)
else: # x pode estar na segunda metade da sequência
return busca_binaria_recursiva(seq, x, meio + 1, fim)
def busca_binaria2(seq,x):
''' (list, float) -> bool
retorna a posição em que x ocorre na lista ordenada,
ou None caso contrário, usando o algoritmo de busca binária.
'''
n = len(seq)
inicio = 0
fim = n - 1
return busca_binaria_recursiva(seq, x, inicio, fim)
##########################################
# Alguns testes da função busca_binaria
seq = [4, 10, 80, 90, 91, 99, 100, 101]
testes = [80, 50]
print("A sequência usada para testes é: ", seq)
for t in testes:
pos = busca_binaria2(seq, t)
if pos is None:
print("Nao achei ", t)
else:
print("Achei %d na posição %d" %(t, pos))