Ajuda com algoritmo de caixa eletronico em python

[Carlos Eduardo Castro]

'''*************************
Faça um algoritmo para ler um valor a ser sacado em um caixa, desprezando os centavos.
Supondo que o CAIXA possua apenas notas 10 notas de  50, 10 notas de 20,10 notas de 10 e 10 notas de 5


*************************

Pessoal, consegui fazer boa parte do algoritmo, está funcionando.

Mas não consigo racionar como fazer o seguinte.

Se o valor de saque for 550, o programa deve me retornar a quantidade de notas que foram sacadas : 10 notas de 50, 2 notas de 20 e 1 nota de 10, pois o caixa não possui 11 notas de 50.

Alguem me da uma luz como coloco esse limite nas notas, sendo que tenho 10 notas de cada valor ?

/*************************


Algoritmo


qtinicial50 = 10
qtinicial20 = 10
qtinicial10 = 10
qtinicial5 = 10
qt50 = 500
qt20 = 200
qt10 = 100
qt5 = 50

totalcaixa = qt50 + qt20 + qt10 + qt5

notasrestantes50 = 10
notasrestantes20 = 10
notasrestantes10 = 10
notasrestantes5 = 10

while True:
    val = input("Digite o valor para saque: ")
    if type (val) is float: #verifica se o conteudo de val é float
        print "Não aceito valores com centavos"
        continue

    if val > totalcaixa:
        print "O caixa eletronico não possui este valor"
        continue

    if val % 5 > 0 or val <= 0: # o caixa nao possui notas de 1 e 2, este if limita valores como 51 por exemplo ou 52
        print "erro"
        continue # retorna o programa para o inicio do while
   
    not50 = val / 50
    val   = val % 50
    not20 = val / 20
    val   = val % 20
    not10 = val / 10
    val   = val % 10
    not5  = val / 5
    val   = val % 5


    print "Este valor corresponde a: "
    if not50 > 0: print not50," notas de R$ 50,00"
    if not20 > 0: print not20," notas de R$ 20,00"
    if not10 > 0:print not10," notas de R$ 10,00"
    if not5 > 0:print not5," notas de R$ 5,00"

[Marcos Thomaz]

Avalie o máximo disponível e parta para a próxima nota (valor disponível).

--
--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo quot;Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

--

Marcos Thomaz da Silva

Analista de Tecnologia da Informação

[Rodolfo Neug]

Carlos, bom dia

Trabalhei em uma empresa que fazia administração dessas máquinas para alguns bancos.
Fabricavam as máquinas e vendiam todo o conjunto de programas internos e outros da periferia.
Eu não estava envolvido diretamente com os aplicativos que rodavam nos ATMs.
Lembro que tinham diversos cuidados:
Os programas são parametrizados em função do valor de face de cada cassete do ATM.
Quando o pessoal do carro forte abastece tem que colocar as notas nos cassetes corretos e informar numa interface gráfica o valor abastecido.
O programa do pagamento do saque precisa fazer "balanceamento de cassetes": pagar evitando ficar sem um dos valores de face disponíveis.
O modo de pagar também é parametrizado conforme pedido do cliente banco.

Eu trabalhava num aplicativo que fazia a conciliação de saldos, programação de abastecimento, etc.

Se puder contribuir em mais alguma coisa, avisem.

[Carlos Eduardo Castro]

Tentei assim

not50 = val / 50
    val   = val % 50

    if not50 > qtinicial50:

        not20 = val / 20
        val   = val % 20

        if not20 > qtinicial20:

            not10 = val / 10
            val   = val % 10

            if not10 > qtinicial10:

                not5  = val / 5
                val   = val % 5

Mas não funcionou, estou no caminho certo ?

[Linux - Junior Polegato]

Em 29-03-2014 11:52, Carlos Eduardo Castro escreveu:

'''*************************
Faça um algoritmo para ler um valor a ser sacado em um caixa, desprezando os centavos.
Supondo que o CAIXA possua apenas notas 10 notas de  50, 10 notas de 20,10 notas de 10 e 10 notas de 5


*************************

Pessoal, consegui fazer boa parte do algoritmo, está funcionando.

Mas não consigo racionar como fazer o seguinte.

Se o valor de saque for 550, o programa deve me retornar a quantidade de notas que foram sacadas : 10 notas de 50, 2 notas de 20 e 1 nota de 10, pois o caixa não possui 11 notas de 50.

Alguem me da uma luz como coloco esse limite nas notas, sendo que tenho 10 notas de cada valor ?

[...]

Olá!

        Que bom que tentou! :)

        Vou tentar desenvolver contigo:

1. Tendo uma lista com o valor das notas e suas quantidades, vamos colocar isso num dicionário para ficar visualmente agradável
2. Vamos transformar em lista e ordenar do maior para o menor, para ficar usável e visualmente agradável
3. Montar uma função recursiva que pegue o maior número de notas da primeira nota da lista, calcular o restante, tirar essa nota da lista e chamar a função recursivamente até zerar o resto, contudo se não zerar o resto e acabar as notas, não há caixa para este valor.
4. Para explorar mais possibilidades, vamos remontar o caixa reduzindo a quantidade da primeira nota utilizada na possibilidade anterior, retirando esta do caixa se a quantidade for zero.
5. Podemos também explorar os possíveis arranjos das notas, assim passaremos por todas as possíveis combinações.
6. Ordenar cada combinação encontrada do maior para o menor e retirar as que são iguais
7. Imprimir o resultado de forma visualmente agradável

Executando:

1. caixa = {50: 10, 20: 10, 10: 10, 5: 10}

2. notas = sorted(caixa.items(), reverse = True)

3.
def quais_notas(caixa, valor):
    # se zerar retorna uma lista vazia
    if not valor:
        return []
    # se acabar o caixa retorna uma exceção
    if not caixa:
        raise SemCaixa
    # duplicar a lista
    notas_restantes = caixa[:]
    # primeira nota e quantidade disponível
    nota, qtd = notas_restantes.pop(0)
    # cômputo da nota a cima a ser utilizada
    utilizadas = min(int(valor / nota), qtd)
    # se não utilizou, chama novamente sem essa nota e mesmo valor
    if not utilizadas:
        return quais_notas(notas_restantes, valor)
    # se utilizou, calcula o resto
    resto = valor - nota * utilizadas
    # retorna lista com essa nota e quantidade utilizada mais
    # retorno do calculo das notas restantes com o valor restante
    return [(nota, utilizadas)] + quais_notas(notas_restantes, resto)

4.
possibilidades = []
while True:
    notas = sorted(caixa.items(), reverse = True)
    try:
        possibilidade = quais_notas(notas, valor)
    except SemCaixa:
        break
    possibilidades.append(possibilidade)
    # pegando primeira nota e sua quantidade
    nota1, qtd1 = possibilidade[0]
    # se a quantidade utilizada antes foi de 1, tira do caixa
    if qtd1 == 1:
        del caixa[nota1]
    # senão atualiza a quantidade desta no caixa menos 1
    else:
        caixa[nota1] = qtd1 - 1

5.
possibilidades = set() # set para evitar duplicidade
caixas = arranjos(sorted([x for x in caixa.items() if x[0] <= valor],
                                                        reverse = True))
for caixa in caixas:
    # duplica o caixa de tuplas para listas para permitir alterações
    caixa = [list(x) for x in caixa]
    while True:
        try:
            possibilidade = quais_notas(caixa, valor)
        except SemCaixa:
            break
        # adiciona a possibilidade ordenada e como tupla para o set
        possibilidades.add(tuple(sorted(possibilidade, reverse = True)))
        nota1, qtd1 = possibilidade[0]
        for n, (nota, qtd) in enumerate(caixa):
            if nota == nota1:
                break
        if qtd1 == 1:
            del caixa[n]
        else:
            caixa[n][1] = qtd1 - 1

6. morreu fazendo "possibilidades = set()" e "possibilidades.add(tuple(sorted(possibilidade, reverse = True)))" no item 5 acima

7.
if not possibilidades:
    print "Não há caixa para este valor!"
else:
    for p, notas in enumerate(sorted(possibilidades, reverse = True)):
        notas = ["%2i x %3i" % n[::-1] for n in notas]
        print 'Possibilidade %4i: %s' % (p, ' + '.join(notas))


Código completo em:

https://gist.github.com/JuniorPolegato/9897730

--

[]'s

Junior Polegato

[Juan Lopes]

Bem, já que estamos discutindo esse problema, ele é bastante famoso, é uma versão do problema da mochila. Mochila é NP-completo (e pseudo-polinomial, em específico).

Essa versão que você está resolvendo (com notas de 5, 10, 20 e 50) tem solução gulosa (que é a que você está tentando), mas ela não funcionaria caso o conjunto de notas fosse outro. Por exemplo, dado que eu tenha notas de 2 e 3, para dar 10 reais, a resposta é 10 = 3 + 3 + 2 + 2, mas a abordagem gulosa iria escolher 3 notas de 3 incorretamente. Há uma solução geral para o problema usando programação dinâmica. Um esboço de solução (ligeiramente funcional) em Python 3.2:

import functools, sys

def caixa(notas):

    def cat(a, b): 

        return None if a is None or b is None else a+b

    @functools.lru_cache(maxsize=1000)

    def fn(n, m=0, k=0):

        if n==0: return []

        if n<0 or m>=len(notas): return None

        if k>=notas[m][1]: return fn(n, m+1, 0)

        return min(fn(n, m+1), 

                   cat(fn(n-notas[m][0], m, k+1), [notas[m][0]]),

                   key = lambda x: len(x) if x else sys.maxsize)

    return fn

notas = (5, 10), (10, 10), (20, 10), (50, 10)

print(caixa(notas)(550))

--

--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo quot;Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

--

https://github.com/juanplopes

[Jéssica Gonzatti]

Juan, chegaste no ponto em que tenho dúvida!

Desenvolvi esse algoritmo:

qntd100=0

qntd50=0

qntd20=0

qntd10=0

qntd05=0

qntd02=0

valor = int(input("Quanto você quer sacar? "))

while(valor  > 0 and valor != 1 and valor !=3):

    if (valor >=100 and( valor !=101 and valor != 103)):

        qntd100=valor//100

        valor=valor-(qntd100*100)

    if (valor >=50  and( valor !=51 and valor != 53)):

        qntd50=valor//50

        valor=valor-(qntd50*50)

    if (valor >=20 and (valor !=21 and valor != 23)):

        qntd20=valor//20

        valor=valor-(qntd20*20)

    if (valor >=10 and( valor !=11 and valor != 13) ):

        qntd10=valor//10

        valor=valor-(qntd10*10)

    if (valor >=5 and (valor !=6 and valor !=8) ):

        qntd05=valor//5

        valor=valor-(qntd05*5)

    if (valor >=2):

        qntd02=valor//2

        valor=valor-(qntd02*2)

    print ("Foram utilizadas",qntd100,"notas de R$100,00")

    print ("Foram utilizadas",qntd50,"notas de R$50,00")

    print ("Foram utilizadas",qntd20,"notas de R$20,00")

    print ("Foram utilizadas",qntd10,"notas de R$10,00")

    print ("Foram utilizadas",qntd05,"notas de R$5,00")

    print ("Foram utilizadas",qntd02,"notas de R$2,00")

Porém estou com problemas para sacar R$23 ou R$21, por exemplo.

O que tenho que fazer?

[Lucas de Biaggi Januário]

Jéssica,

              Da uma olhada neste tópico aqui https://groups.google.com/forum/#!topic/python-brasil/dh1oC-HJKEI

              Acredito que vai te dar a luz que esteja procurando.

Abraços

python-brasil+unsubscribe@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasil+unsubscribe@googlegroups.com.