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()