IPython Notebook

MAC2166 - Introdução à Computação

29/04/2014 - Aula 9

Copiando listas

Quando fazemos uma de atribuição de uma variável do tipo list para uma outra variável, precisamos ter cuidado. A operação de atribuição nesse caso não faz uma cópia da lista na nova variável, ela apenas cria uma outra referência para a mesma lista. Veja o exemplo a seguir:

In [3]:
 
lista1 = [20, 40, 30, 10]
print("Lista 1:", lista1)
lista2 = lista1
print("Lista 2:", lista2)
print("Atribuindo um novo valor à primeira posição da Lista 1...")
lista1[0] = 50       # modifica primeira posição de lista1
print("Lista 1:", lista1)
print("Lista 2:", lista2)
print("Inclindo um novo elemento na Lista 2...")
lista2.append(60)
print("Lista 1:", lista1)
print("Lista 2:", lista2)
 
Lista 1: [20, 40, 30, 10]
Lista 2: [20, 40, 30, 10]
Atribuindo um novo valor à primeira posição da Lista 1...
Lista 1: [50, 40, 30, 10]
Lista 2: [50, 40, 30, 10]
Inclindo um novo elemento na Lista 2...
Lista 1: [50, 40, 30, 10, 60]
Lista 2: [50, 40, 30, 10, 60]

Pelo exemplo acima, é possível ver que uma modificação em lista1 é refletida também em lista2 e vice-versa. Na verdade, as variáveis lista1 e lista2 são apenas dois nomes diferentes para uma mesma lista.

Esse tipo de comportamento não acontece com variáveis dos tipos int e float. Veja o exemplo a seguir:

In [4]:
 
num1 = 20
num2 = num1
print(num1, num2)
num1 = 30
print(num1, num2)
num2 = 50
print(num1, num2)
20 20
30 20
30 50

Diante do exposto acima, qual é a forma correta de se copiar uma lista (ou seja, criar uma nova lista com os mesmos elementos de uma lista já existente)? A função clone() criada no Problema 18 exemplifica uma forma de se fazer isso.

Problema 18 (Jogo Senha)

Faça um programa que sorteie aleatoriamente um número inteiro (a senha) e depois ajude o usuário a adivinhar qual é o valor da senha. O seu programa deve:

(1) Receber um número inteiro semente que será a semente do gerador de números aleatórios (veja mais sobre a geração de números aleatórios mais a frente, nesta mesma página).

(2) Sortear um número aleatório, maior ou igual a zero, de no máximo 5 dígitos, que será a senha.

(3) Receber um número inteiro chute, maior ou igual a zero, de no máximo 5 dígitos que será uma tentativa de adivinhar a senha.

(4) Imprimir na tela:

  • número de dígitos em posições certas e
  • número de dígitos certos da tentativa.

Por exemplo, se senha = 74894 e chute = 45897, os dígitos 8 e 9 do chute estão nas posições corretas, e os dígitos 4 e 7 do chute estão corretos mas em posições incorretas. Portanto, para o chute 45897 há 4 dígitos certos e 2 deles em posições certas.

Embora os números sejam digitados sempre com 5 ou menos dígitos, todos os dígitos à esquerda, até completar 5 dígitos, são sempre considerados zeros. Por exemplo, se o número sorteado é 10 e o número chutado é 1, considera-se que o número sorteado é 00010 e o número chutado é 00001. Com isso, o número de dígitos certos é 5 e o número de dígitos na posição certa é 3, que são os 3 zeros à esquerda.

(5) Repetir os passos 3 e 4 enquanto a senha não for descoberta e o número de tentativas não ultrapassar 10.

Obs.: Este problema é parte do EP2 das outras turmas de MAC2166, que por sua vez foi inspirado pelo jogo Mastermind, chamado no Brasil de Senha. Você pode ver soluções para esse EP que não envolvem o uso de listas aqui.

In [ ]:
 
"""
Jogo Senha (Mastermind)
"""
 
import random
 
## definição de alguma constantes
MAX_TENTATIVAS = 10
NUM_DIGITOS    = 5
MAX_NUMERO     = 99999
MODO_DEBUG     = True
 
##############################################################################
 
def main():
    '''
    Função que implementa o jogo Senha (ou Mastermind)
    '''
    # entrada dos dados
    print("=========================================================================")
    semente = int(input("Digite a semente para inicializar o gerador de números aleatórios: "))
    random.seed(semente)   
  
    # gera aleatoriamente a senha, um número entre 0 e MAX_NUMERO
    senha = random.randint(0, MAX_NUMERO)   
    # cria uma lista contendo os dígitos da senha
    senha_lista = para_lista(senha, NUM_DIGITOS)
 
    # mensagens
    print("=========================================================================")
    print("Bem-vindo ao jogo! Qual é a senha?")
    print("=========================================================================")
 
    if MODO_DEBUG: ### MUDE A CONSTANTE MODO_DEBUG PARA True OU False
        print("MODO_DEBUG: o número senha foi %d"%(senha))
  
    ##############################################################################
    # malha principal do Mastermind
    tentativa = 0
    acertou = False
 
    while tentativa < MAX_TENTATIVAS and not acertou:
        tentativa += 1
        chute = int(input("Tentativa   %d   .....: "%tentativa))
        chute_lista = para_lista(chute, NUM_DIGITOS)
        
        emparelhados = posicoes_certas(chute_lista, senha_lista)
        certos = digitos_certos(chute_lista, senha_lista)
 
        print("Número de dígitos em posições certas:  ", emparelhados)
        print("Número de dígitos certos:  ", certos)
        acertou = emparelhados == NUM_DIGITOS
 
    ###########################################################################
    # FINALIZANDO
 
    print("=========================================================================")
 
    if acertou:
        print("Parabéns, você acertou em %d tentativas!"%(tentativa))
    else:
        print("Que pena, você errou.")
        
    print("=========================================================================")
 
 
###########################################################################
# Função para_lista
 
def para_lista_inv(num, n):
    """ (int, int) --> list
    para_lista recebe inteiros num e n, e cria e retorna uma lista com
    seus n dígitos menos significativos.
    Essa versão retorna uma lista com os dígitos invertidos (eles aparecem
    invertidos usando print).
    """
    lista = []
    for i in range(n):
        lista.append(num % 10)
        num //= 10
    return lista
 
def para_lista(num, n):
    """ (int, int) --> list
    essa versão retorna os dígitos na mesma ordem.
    """
    lista = [0] * n
    for i in range(n):
        lista[n -1 -i] = num % 10
        num //= 10
    return lista
 
###########################################################################
# Função posicoes_certas
 
def posicoes_certas(num1, num2):
    """(list, list) --> int
    recebe duas listas e retorna o número dígitos em "posições certas".
    Exemplos:
    >>> posicoes_certas([1, 2, 3, 2, 1],[0, 1, 2, 2, 1])
    2
    >>> posicoes_certas([1, 2, 3, 2, 1],[2, 1, 2, 1, 3])
    0
    """
    cont = 0
    for i in range(len(num1)):
        if num1[i] == num2[i]:
            cont += 1
 
    return cont
 
###########################################################################
# Função digitos_certos
 
def digitos_certos_versao_errada(num1, num2):
    """ (list, list) --> int
    recebe duas lista e retorna o número de "dígitos certos"
    Essa versao funciona para a 1a tentativa apenas, pois destroi num2.
 
    """    
    cont = 0
    for i in range(len(num1)):
        j = 0
        achei = False
        while j<len(num2) and not achei:
            if num1[i] == num2[j]:
                cont+=1
                num2[j] = -1
                achei = True
            j+=1
    return cont
 
def digitos_certos(num1, num2):
    """ (list, list) --> int
    recebe duas lista e retorna o número de "dígitos certos"
    versao com clone e destroi o clone
    """
    copia_num2 = clone(num2)
    
    cont = 0
    for i in range(len(num1)):
        j = 0
        achei = False
        while j<len(copia_num2) and not achei:
            if num1[i] == copia_num2[j]:
                cont+=1
                copia_num2[j] = -1
                achei = True
            j+=1
    return cont
 
def digitos_certos_com_flags(num1, num2):
    """ (list, list) --> int
    recebe duas listas e retorna o número de "dígitos certos"
    versao com flags
    """
    marcado = [False] * len(num2)
    
    cont = 0
    for i in range(len(num1)):
        j = 0
        achei = False
        while j<len(num2) and not achei:
            if not marcado[j] and num1[i] == num2[j]:
                cont+=1
                marcado[j] = True
                achei = True
            j+=1
    return cont
 
 
###########################################################################
 
def clone(lista):
    """ (list) --> list
    recebe uma lista e cria e retorna um clone
    Dá para fazer return lista[:] (esse slice cria uma copia da lista inteira)
    """
    clone = []
    for i in range(len(lista)):
        clone.append(lista[i])
    return clone
 
    
###########################################################################
 
main()

No solução acima, temos uma função chamada main(), que contém todo o código do programa principal. A função só foi chamada no final do código (mais precisamente, na última linha). Note que a função main(), dentro dela, chama outras funções que só são definidas mais para baixo no código, e isso não é um problema!

Assim, ao criar uma função main() e colocar dentro dela todo o código do programa principal, não precisamos nos preocupar em colocar a definição das funções chamadas no programa principal antes dele no código, precisamos apenas fazer a chamada à função main() depois das definições das funções usadas nela.

Sobre a geração de números (pseudo-)aleatórios

[Texto extraído do enunciado do EP2]

Para gerar números aleatórios, precisamos usar algumas funções prontas no Python. Para usar essas funções, é necessário carregar o módulo random onde elas estão implementadas. Para isso, a linha abaixo deve ser incluída no início do seu código:

import random

Com o módulo carregado, é necessário inicializar o gerador de números aleatórios com uma semente, que vai ser um dos valores que o usuário terá que passar como entrada no Problema 18. Supondo que a semente digitada pelo usuário seja armazenada na variável semente, a linha abaixo inicializa o gerador de números aleatórios com ela:

random.seed(semente)

O uso de semente permite que o programa seja executado sempre com o mesmo número pseudo-aleatório como senha, facilitando portanto o teste e correção do programa. Na prática, se você quisermos deixar a senha mais aleatória, basta não passar uma semente explicitamente pois o Python utilizá a hora do computador como semente. Como o instante em que o programa é executado é, de certa forma, aleatório, a senha se torna difícil de ser prevista.

Para entender melhor o que são e como números "aleatórios" (ou quase) são gerados no computador, leia esta página.

Uma vez inicializada a geração dos números aleatórios, o código abaixo mostra como sortear um número inteiro maior ou igual a 1 e menor ou igual a 99 e atribuir o resultado do sorteio à variável sorteio:

sorteio = random.randint(1,99)

Problema Extra 1

(a) Escreva uma função com protótipo

def insereSeNovo (x, lista):

que devolve a posição em que o real x ocorre em lista ou, caso x não estiver na lista, insere x no final da lista e devolve o índice dessa posição.

(b) Dada uma sequência de n números reais, escreva um programa (usando a função do item anterior) que conte quantas vezes cada número ocorre na sequência.

In [ ]:
 
###
# programa principal
###
def main()
    n = int(input("Digite n: "))
    cont = 0
    listaNum = []
    listaCont = []
    
    while cont < n:
        num = float(input("Digite um número: "))
        ind = insereSeNovo(num, listaNum)
        if ind > len(listaCont)-1:
            listaCont.append(1)
        else:
            listaCont[ind] += 1
        cont += 1
    
    cont = 0
    while cont < len(listaNum):
        print ("O num %f aparece %d vezes"%(listaNum[cont], listaCont[cont]))
        cont += 1
 
def insereSeNovo (x, lista):
    ind = -1
    cont = 0
    # procura 
    while cont < len(lista) and ind == -1:
        if (lista[cont] == x):
            ind = cont
        cont += 1
    # se não achei
    if ind == -1:
        lista.append(x)
        ind = len(lista) - 1
    return ind
        
def insereSeNovo1 (x, lista):
    if x not in lista:
        lista.append(x)
        return len(lista) - 1
    else:
        # eu sei que x está na lista
        ind = 0
        while lista[ind] != x:
            ind += 1
        return ind
 
def insereSeNovo2 (x, lista):
   for i in range(len(lista)):
      if x == lista[i]:
         return i
   lista.append(x)
   return len(lista)-1
 
def insereSeNovo3 (x, lista):
   if x not in lista:
      lista.append(x)
   i = 0
   while x != lista[i]:
      i += 1
   return i
 
def insereSeNovo4 (x, lista):   # melhor solucao estilo C
   ind = 0
   while ind < len(lista) and lista[ind] != x :
      ind += 1
   if ind == len(lista) :
      lista.append(x)
   return ind
 
def insereSeNovo5 (x, lista):  # solucao totalmente pythonica
   if not x in lista :
      lista.append(x)
   return lista.index(x)
 
 
####################
main()

Problema Extra 2

(a) Escreva uma função que recebe 2 inteiros ini e fim, e uma lista L, tal que 0 <= ini <= fim < len(L) e calcula a soma dos elementos L[i], para ini <= i <= fim.

(b) Usando a função anterior, escreva um programa que leia n>0 e uma sequência com n números reais, e determina um segmento de soma máxima.

Exemplo: Na sequência

5, 2, -2, -7, 3, 14, 10, -3, 9, -6, 4, 1 ,

a soma do segmento de soma máxima é 33.

In [ ]:
 
# Programa Principal
def main():
 
  # Lê a sequência de valores e armazena-os em uma lista
  n = int(input("Digite n: "))
  seq = []
  for i in range(n):
    num = float(input("Digite um número da sequência: "))
    seq.append(num)
 
  max = seq[0] # max não pode ser inicializada com 0,
               # porque a lista pode ser toda negativa
               
  ini = 0
  while ini < n:
      fim = ini
      while fim < n:
          s = soma(ini, fim, seq)
          # alternativa para a linha anterior:   s = sum(seq[ini:fim+1])
          if s > max:
              max = s
          fim += 1
      ini += 1
  print("A soma máxima de um segmento da sequência é %d." %max)
 
 
# Função soma (solução 1)
def soma(ini, fim, lst):
    s = lst[ini]
    while ini < fim:
        ini += 1
        s += lst[ini]
    return s
 
# Função soma (solução 2)
def soma1(ini, fim, lst):
    s = 0
    for x in lst[ini:fim+1]:
        s += x
    return s
 
##################################
 
main()

Tópicos vistos na Aula 9

  • Funções que recebem listas como parâmetros ou que devolvem listas

Referências e outros materiais para estudo