n > 0 valores inteiros, em uma lista
L, e um inteiro x, testa se
x pertence à lista.
Solução 1:
Solução por busca exaustiva percorrendo a lista (busca sequencial).
def pertence(x, L):
n = len(L)
i = 0
while i < n:
if L[i] == x:
return True
i += 1
return False
O vídeo abaixo apresenta uma análise da complexidade computacional do algoritmo de busca sequencial acima, demonstrando suas limitações.
Solução 2:
Essa solução
adiciona na posição seguinte a do último elemento
o valor de x, conseguindo com isso a
simplificação do laço que passa agora a realizar
uma única comparação para cada iteração.
Essa técnica de busca é
conhecida como busca com sentinela.
# busca com sentinela
def pertence(x, L):
n = len(L)
i = 0
L.append(x) #adiciona x no final da lista
while L[i] != x:
i += 1
L.pop() #remove x do final da lista
if i == n:
return False
else:
return True
Solução 3:
Essa terceira solução se aplica somente a listas previamente ordenadas. A cada iteração, o valor procurado é comparado com o elemento na posição central da lista, eliminando metade do intervalo de busca. Essa solução é conhecida como algoritmo de busca binária.
# Busca binária:
def pertence(x, L):
n = len(L)
inic = 0
fim = n-1
while inic <= fim:
meio = (inic+fim)//2
if x == L[meio]:
return True
elif x > L[meio]:
inic = meio+1
else:
fim = meio-1
return False
Solução 4:
Essa solução apresenta o algoritmo de busca binária de modo recursivo.
# Busca binária recursiva:
def pertence_aux(x, L, inic, fim):
meio = (inic+fim)//2
if inic > fim:
return False
elif x == L[meio]:
return True
elif x > L[meio]:
return pertence_aux(x, L, meio+1, fim)
else:
return pertence_aux(x, L, inic, meio-1)
def pertence(x, L):
n = len(L)
inic = 0
fim = n-1
return pertence_aux(x, L, inic, fim)
L com n > 0 números inteiros no intervalo de 0 a 255
(isto é, 0 <= L[i] <= 255 para i = 0,.., n-1),
faça uma função para ordenar os seus elementos em ordem crescente.
Solução 1:
Explorando o fato de que os valores estão em um intervalo limitado de 0 a 255, podemo usar o algoritmo de ordenação do Counting Sort. Para isso vamos usar uma lista de contadores para cada valor de 0 a 255. Portanto, o algoritmo necessita de memória auxiliar.
def ordenacao_por_contagem(L):
n = len(L)
C = [0]*256 #Lista de contadores
for i in range(0,n):
C[L[i]] += 1
#Agora C[k] contém o número de elementos iguais a k.
i = 0
for k in range(0,256):
for c in range(0,C[k]):
L[i] = k
i += 1
Solução 1:
Dividimos ao meio a lista e ordenamos as duas metades via duas chamadas recursivas. A ordenação final é então obtida via intercalação dos valores das duas metades ordenadas.
def mergeSortAux(L, inic, fim):
if fim - inic + 1 <= 1:
return
m = (inic + fim)//2
mergeSortAux(L, inic, m)
mergeSortAux(L, m+1, fim)
A = []
i = inic
j = m+1
while i <= m or j <= fim:
if i > m:
A.append(L[j])
j += 1
elif j > fim:
A.append(L[i])
i += 1
elif L[i] < L[j]:
A.append(L[i])
i += 1
else:
A.append(L[j])
j += 1
for k in range(inic, fim+1):
L[k] = A[k-inic]
def mergeSort(L):
n = len(L)
mergeSortAux(L, 0, n-1)
Exemplo de função principal que chama as
funções anteriores.
def main():
L = [6,3,9,2,7,1,0,4,8,5]
mergeSort(L)
for i in range(0,n):
print(L[i], end=" ")
print()
x = int(input("Digite x: "))
if pertence(x, L):
print("Sim")
else:
print("Não")
main()