.. -- coding: utf-8 -- .. Copyright (C) Coelho e Hitoshi Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with Invariant Sections being Forward, Prefaces, and Contributor List, no Front-Cover Texts, and no Back-Cover Texts. .. shortname:: EP4 .. description:: exercício acha troco recursivo Exercício Programa 4: Câmbio Automático - Parte B ================================================= Descrição ......... Na parte B, você deve desenvolver uma função ``menor_troca()`` que recebe um valor a ser trocado e um *dicionário* contendo os valores e quantidades de notas no caixa. Caso seja possível trocar o valor, a função retorna um troco para o valor com o menor número de notas possível de acordo com o estado do estoque de notas. Caso não seja possível trocar as notas a função imprime uma mensagem de aviso e retorna ``None``. Sua função deve utilizar a função ``lista_trocos()`` feita na parte A (EP3) ou a que será fornecida depois do dia 27/08. **Parte B:** entrega até 03/09 ------------------------------ Nesta parte B, você deve escrever a função ``menor_troca`` que será utilizada na máquina de câmbio automático. Objetivos ......... - Treinar o uso de *dicionários* em Python (classe ``dict``) Leitura Recomendada ................... - `Como Pensar Como um Cientista da Computação: Dicionários `__ Dicionários ........... Para essa parte, vamos representar o estoque de notas (e depois também o estoque de moedas) usando um `dicionário `__. Um dicionário é um conjunto de objetos (itens) cada um dotado de uma *chave* (``key``) e de um valor (``value``). As chaves podem ser números inteiros ou strings ou outros tipos de dados. Um dicionário está sujeito a dois tipos de operações: - *inserção*: consiste em introduzir um objeto no dicionário; e - *busca*: consiste em encontrar um elemento que tenha uma dada chave. Python possui dicionários como um tipo nativo (classe ``dict``). Uma maneira de criar um dicionário é começar com o dicionário vazio e adicionar pares chave:valor. O dicionário vazio é denotado ``{}``: .. sourcecode:: python >>> naipes = {} # dicionário vazio >>> type(naipes) # tipo da variável dicio >>> len(naipes) # número de pares chave:valor no dicionário 0 Como listas, podemos também criar um dicionário com alguns pares chave:valor. Po exemplo, para se criar um dicionário com a chave ``'cavalos'`` com o valor 2 e a chave ``'galinhas'`` com o valor 15, podemos escrever: .. sourcecode:: python >>> estoque_animais = {'cavalos':2, 'galinhas':15} >>> estoque_animais {'galinhas': 15, 'cavalos': 2} >>> len(estoque_animais) 2 >>> No exemplo acima as chaves são strings (classe ``str``) e os valores são inteiros (classe ``int``) Note que a chave é separada do seu valor pelo símbolo ``:``. Para *inserir* ou *atualizar* um par chave:valor em um dicionário escrevemos ``dicio[chave] = valor``. .. sourcecode:: python >>> estoque_animais['patos'] = 25 >>> estoque_animais['bois'] = 7 >>> estoque_animais {'patos': 25, 'galinhas': 15, 'bois': 7, 'cavalos': 2} >>> len(estoque_animais) 4 >>> >>> naipes['♡'] = 'copas' >>> naipes['♣'] = 'paus' >>> naipes['♢'] = 'ouros' >>> naipes['♠'] = 'espadas' >>> naipes {'♡': 'copas', '♠': 'espadas', '♢': 'ouros', '♣': 'paus'} >>> len(naipes) 4 >>> Note que diferente de uma lista, onde os índices são inteiros sequencias, uma chave pode ser qualquer objeto *imutável*, como um número inteiro, um string, ou um *tuple*, e o valor associado a cada chave pode ser um número, ou lista, ou string, etc. .. sourcecode:: python >>> estoque_animais['patos'] 25 >>> estoque_animais['cavalos'] 2 >>> estoque_animais['bois'] 7 >>> estoque_animais['bois'] += 5 >>> estoque_animais {'cavalos': 2, 'patos': 25, 'galinhas': 15, 'bois': 12} >>> >>> estoque_animais['patos'] = 3 >>> estoque_animais {'cavalos': 2, 'patos': 3, 'galinhas': 15, 'bois': 12} >>> >>> valor_carta = {'A':14, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9, 'D':10, 'J':11, 'Q':12, 'K':13} >>> valor_carta {'J': 11, 'K': 13, 'Q': 12, '6': 6, '5': 5, 'D': 10, '7': 7, '8': 8, '3': 3, '2': 2, '4': 4, 'A': 14, '9': 9} >>> valor_carta['K'] 13 >>> Vejamos mais um exemplo de como criar e manipular um estoque de notas. Desta vez o exemplo será um *script* (= programa) e não no Python Shell. .. sourcecode:: python # Vamos ver algumas formas de criar um dicionario estoque_notas = {} # cria um dicionário vazio estoque_notas[50] = 0 # cria a chave 50 (nota de 50) com quantidade 0 estoque_notas[20] = 0 estoque_notas[10] = 0 estoque_notas[5] = 0 estoque_notas[2] = 0 print("Agora tenho o seguinte dicionário de notas: ") print(estoque_notas) print() # seria também possível criar o dicionário com zeros usando # estoque_notas = {50:0, 20:0, 10:0, 5:0, 2:0} # experimente! # varrer o dicionário para colocar 36 notas de cada tipo chaves = list( estoque_notas.keys() ) for c in chaves: print("Coloquei 36 notas de ", c) estoque_notas[c] = 36 # seria também possível criar o dicionário diretamente usando # estoque_notas = {50:36, 20:36, 10:36, 5:36, 2:36} # agora vamos retirar notas do estoque fim = False while not fim: print () print ("Estoque de notas: ", estoque_notas) print ("Digite 't' para terminar") print ("Ou 2 inteiros (nota e quantidade) como: 50 2") print (" para retirar 2 notas de 50") opcao = input(">>> digite sua opcao: ") print() if opcao == 't': fim = True else: opcao = opcao.split() nota, qtd = int(opcao[0]), int(opcao[1]) if nota in estoque_notas: if estoque_notas[nota] >= qtd: print("Você recebeu %d notas de %d"%(qtd, nota)) estoque_notas[nota] -= qtd else: print("O estoque de notas de ", nota, "é insuficiente") else: print("A nota de valor", nota, "não existe no dicionário") print("Fim!") Copie o código em um arquivo Python. Utilizando, por exemplo, o idle, execute o script, modifique-o, brinque com ele para experimentar outras formas de criar e manipular o dicionário. O que você deve fazer ..................... Nesse exercício, você deverá implementar a função ``menor_troca()`` como especificado a seguir. .. sourcecode:: python def menor_troca (v, estoque): ''' (int, dict) -> list Recebe um valor v e um dicionário estoque. As chaves do dicionário são valores de notas. O valor no dicionário correspondente a cada nota é a quantidade de notas que a máquina câmbio possui daquele valor. A função retorna um troco para o valor v com o menor número de notas possível de acordo com o estado do estoque de notas da máquina. Caso não seja possível trocar o valor a função imprime uma mensagem de aviso e retorna None. ''' A função **NÃO** deve alterar o estoque (aguarde pelos próximos eps). Estude os exemplos abaixo antes de implementar a função. Exemplos ........ .. sourcecode:: python >>> menor_troca(4, {1:0, 2:1}) Não dá para trocar 4 com o estoque {1:0, 2:1} >>> menor_troca(4, {5:4, 3:4}) Não dá para trocar 4 com notas de [3, 5] >>> menor_troca(4, {1:4, 2:4}) [2, 2] >>> menor_troca(4, {1:4, 2:0}) [1, 1, 1, 1] >>> menor_troca(4, {2:1, 1:4}) [2, 1, 1] O que você precisa entregar ........................... Neste exercício programa você deverá depositar na página de MAC0122 no paca um arquivo contendo as seguintes funções: - ``menor_troca(v, estoque)``: como descrita nesse enunciado - ``lista_trocos(v, valores)``: como entregue no EP3, mas você pode alterar a função. - ``main()``: com testes que você fez com a função menor_troca e outras - outras funções que desejar, como por exemplo: - uma função que ordena uma lista de listas em ordem crescente do comprimento das listas, ou seja, que transforme uma lista [[1,1,1], [1,2]] em [[1,2], [1,1,1]] - uma função que verifica se um estoque permite trocar uma certa combinação de notas - etc