Algoritmos Iterativos
listas é um tipo de dados muito versátil e útil para modelar uma vasta gama de problemas. Como veremos logo mais, em Python listas possuem um grande numero de funções "incorporadas" que facilitam muito sua manipulação.Nos exemplos de pseudo código vamos assumir que existem duas funções para manipular listas:
juntar(lista, objeto qualquer) Esta função pega uma lista e acrescenta o objeto no final da lista, retornando a lista aumentada.
inserir(lista, objeto, indice) Esta função pega a lista e insere o objeto na posição de indice dado, retornando a lista aumentada.
Por exemplo:
lst = [1, 2, 3]
L1 = juntar(lst, 789)
L2 = inserir(lst, 'Eva', 2)
imprima(L1) # [1, 2, 3, 789]
imprima(L2) # [1, 2, 'Eva', 3]
Vejamos um exemplo de algoritmo iterativo onde listas são utilizadas.
Em muitos jogos de cartas os jogadores recebem uma quantidade delas viradas para baixo no início da partida e formam uma "mão" pegando-as uma por uma e colocando-as em ordem crescente.
Neste problema vamos construir um algoritmo para fazer esta ordenação de cartas. Em inglês o algorítmo é conhecido como Insertion Sort e segue nosso padrão de algorítmo iterativo.
As cartas recebidas serão representadas por números no intervalo de 1 a 56, pois são 14 cartas em cada um dos quatro naipes.
Representaremos as cartas recebidas pelo jogador como uma lista de N números do intervalo, onde N depende do jogo. Por exemplo:
cartas recebidas = [ 3, 5, 10, 1, 2, 14, 7, 9, 8, 13]
A saida do nosso algoritmo deverá ser:
mão = [1, 2, 3, 5, 7, 8, 9, 10, 13, 14]
Vejamos como isto se enquadra no padrão iterativo. O conjunto de objetos a percorrer é o conteudo da primeira lista.
O procedimento para cada número desta lista é inserir ele na segunda lista de forma que a segunda lista fique ordenada.
E como fazer esta inserção de forma ordenada? Bem, para quem gosta de jogar cartas isto é familiar: assuma que as cartas já na sua mão estão ordenadas e você puxou uma carta nova para inserir. Percorra as cartas na mão começando com a maior e indo para a menor, comparando a carta nova com as cartas da mão até achar na mão uma carta menor do que a nova carta, ou então até que não reste nenhuma carta na mão para comparar. Insira a nova carta neste ponto.
Vejamos passo a passo como fica nosso exemplo com este algoritmo. Aqui a coluna na esquerda são as cartas dadas e a coluna da direita é a mão do jogador em cada passo do algoritmo:
[ 3, 5, 10, 1, 2, 14, 7, 9, 8, 13] []
[5, 10, 1, 2, 14, 7, 9, 8, 13] [3]
[10, 1, 2, 14, 7, 9, 8, 13] [3, 5]
[1, 2, 14, 7, 9, 8, 13] [3, 5, 10]
[2, 14, 7, 9, 8, 13] [1, 3, 5, 10]
[14, 7, 9, 8, 13] [1, 2, 3, 5, 10]
[7, 9, 8, 13] [1, 2, 3, 5, 10, 14]
[9, 8, 13] [1, 2, 3, 5, 7, 10, 14]
[8, 13] [1, 2, 3, 5, 7, 9, 10, 14]
[13] [1, 2, 3, 5, 7, 8, 9, 10, 14]
[] [1, 2, 3, 5, 7, 8, 9, 10, 13, 14]
Simples, não é mesmo? Agora vamos criar o algoritmo em pseudo código.
Na entrada temos duas listas, uma com N cartas aleatórias e a outra é uma lista vazia.
Vamos percorrer as cartas dadas na entrada inserindo cada uma na outra lista de forma ordenada.
# assumo dada uma lista cartas[] com N cartas aleatórias.
# cria lista vazia de saida
mao = []
indice = -1 # ultima carta inserida na mao
para cada carta C em cartas:
se indice == -1:
mao[0] = C
indice = 0
senão:
para cada j de indice até 0:
se mao[j] > C:
se j == 0:
mao = insere(mao, C, 0)
break
senão:
j = j - 1
senão:
mao = insere(mao, C, j + 1)
break
indice = indice + 1
imprime(mao)
Vejamos como funciona o procedimento:
Inicialmente temos uma lista cartas com cartas em ordem aleatória.
O algoritmo inicia com:
mao = []
indice = -1
Criamos uma lista vazia mao onde colocaremos as cartas em ordem crescente. A variável indice guarda o indice da ultima carta presente na lista mao.
O algoritmo segue o padrão iterativo já conhecido: percorremos o conjunto de cartas da lista cartas e processamos cada uma delas por sua vez:
para cada carta C em cartas:
.............
............
.....
Observe que cada vez que uma carta for inserida em mao a variável indice deve ser devidamente incrementada, porque mao passa a ter uma carta a mais.
Inicialmente mao está vazia e a primeira carta C das cartas é simplesmente adicionada em mao.Para saber se estamos neste caso especial pode-se testar a variável indice:
se indice == -1:
mao[0] = C
indice = 0
Para as cartas restantes faremos a inserção propriamente dita. Lembre-se da idéia: as cartas em mao já foram ordenadas e a nova carta vai sendo comparada com elas até achar uma carta menor. Neste ponto inserimos a carta nova. A cada passo a variável indice diz onde está a última e maior carta em mao, então as comparações começam ali e vai-se descendo até achar a posição para inserir:
para cada j de indice até 0:
se mao[j] > C:
.....
.....
j = j - 1
senão:
mao = insere(mao, C, j + 1)
...
indice = indice + 1
Temos um caso especial quando todas as comparações falham, ou seja, a carta nova é menor do que qualquer carta na mao. A diferença é que não há uma carta menor em mao antes da qual iriamos inserir a carta nova.
Para tratar este caso testamos se as comparações pararam porque encontrou uma carta menor em mao ou porque esgotamos todas cartas em mao. Este teste é feito examinando a variável j:
se j == 0:
mao = insere(mao, C, 0)
......
senão:
j = j - 1
Observe que usamos o comando break para interromper loops de repetição quando necessário.
Existem outros algoritmos para resolver este problema? Com certeza!
Por exemplo podemos simplificar o algorítmo usando uma função que dá o comprimento de uma lista:
len(L) Esta função retorna o comprimento da lista L.
Nesta implementação eliminamos os casos especiais, tornando mais simples o algoritmo:
mao = []
para cada C em cartas:
# percorre todas cartas na mao procurando uma menor do que C
indx = 0
para cada j no intervalo(len(mao) - 1, 0):
se mao[j] > C:
j = j - 1
senao:
indx = j + 1
break
# indx é o indice onde inserir C
mao = insere(mao, C, indx)
imprime(mao)
E é isto aí. Mais tarde você vai codificar este algoritmo em Python e ver ele funcionando, ao vivo!
Python icon by kaelan
No comments:
Post a Comment