Se quer manipular números e fazer cálculos, quase sempre é melhor usar matemática. Transformar os números em strings, como sugeriu a outra resposta, pode até "funcionar", mas não é o ideal (além de geralmente ser mais lento - claro que para programas pequenos a diferença será insignificante e imperceptível, mas ficar convertendo de número para string, para número, para string, etc, várias vezes, não só é mais lento como também mais propenso a erros, além de nesse caso ser desnecessário e na minha opinião mais complicado).
Enfim, como não precisamos nos preocupar com a quantidade total de notas existentes, basta ir fazendo divisões para saber a quantidade de notas necessárias, e depois ir descontando esse valor, até que ele chegue a zero. Mas vale lembrar que há outros casos a se tratar, pois nem sempre o algoritmo mais simples indicado abaixo pode funcionar. Mas vamos por partes, primeiro veremos o caso mais simples, e depois chegaremos aos mais complicados.
Caso Simples (ou "algoritmo ingênuo")
É o caso da pergunta, pois como tem notas de 1 sem limite de quantidade, sempre vai ser possível encontrar alguma combinação (no pior caso, basta usar várias notas de 1, já que os valores sempre são inteiros).
Enfim, o algoritmo básico é ir fazendo divisões e pegando o resto, até que o valor zere. Por exemplo, se o valor for 260, basta dividir por 100 (ignorando as casas decimais), que teremos a quantidade de notas de 100 (no caso, serão 2). No Python já existe um operador que faz a divisão inteira, que é o //
.
Depois, como já pegamos as notas de 100, posso considerar apenas o restante do valor, que no caso é o resto da divisão por 100 (no nosso exemplo, o resto da divisão de 260 por 100 é 60). Tendo o valor restante (60), posso fazer os mesmos passos com as notas de 50 (divide ignorando as casas decimais - dará 1 - pega o resto da divisão - que é 10 - e repete o procedimento para notas de 10, etc), e vou fazendo assim até o valor zerar. Para obter o resto da divisão, basta usar o operador %
.
Outro detalhe é que você não está verificando a faixa de valores que o exercício pede (entre 10 e 600). E se a ideia é só imprimir as quantidades de cada nota (no final veremos outra opção para armazenar essas quantidades), ficaria assim (omiti as mensagens de "bem vindo" etc para focar no algoritmo em si, mas claro que depois você pode adicioná-las conforme o desejado).:
while True: # enquanto não digitar um valor válido, pede que digite novamente
try:
valor = int(input('Digite o valor (entre 10 e 600):'))
if 10 <= valor <= 600:
break # valor válido, sai do while
# se não entrou no if acima, o valor é inválido
print('valor deve estar entre 10 e 600')
except ValueError: # não foi digitado um número
print('Digite um número válido')
# todas as notas possíveis
notas = [100, 50, 10, 5, 1]
for nota in notas:
if valor >= nota:
qtd = valor // nota # divisão exata (sem considerar casas decimais)
print(f'{qtd} notas de {nota}')
valor %= nota # valor recebe o resto da divisão de valor por nota
Só isso. Nada de transformar em string, ver o tamanho, pegar o primeiro, segundo índice, etc, nada disso. Apenas a boa e velha matemática, e com a vantagem de funcionar para quaisquer valores e qualquer conjunto de notas (na verdade não é exatamente qualquer conjunto, mais sobre isso abaixo na seção "Para funcionar com qualquer conjunto de notas").
Por exemplo, se eu quisesse incluir as notas de 20 e 200, bastaria mudar a lista notas
, lembrando de sempre colocar os valores maiores primeiro:
notas = [200, 100, 50, 20, 10, 5, 1]
Se eu quiser que aceite valores até 100 mil, bastaria mudar o if
para if 10 <= valor <= 100000
(e as respectivas mensagens). O resto do algoritmo permanece igual.
Agora tente mudar o algoritmo das outras respostas para aceitar esses casos. Tudo bem que neste caso específico não é tão complicado assim, mas vai ficar muito código repetitivo (faz basicamente as mesmas coisas com parâmetros diferentes, e por isso pode ser abstraído e simplificado para o loop acima). Percebeu como apesar do código da outra resposta "funcionar", não é o ideal?
E também é possível dar uma pequena otimizada:
for nota in notas:
if valor >= nota:
qtd = valor // nota
print(f'{qtd} notas de {nota}')
valor %= nota
if valor == 0:
break # se o valor zerou, sai do for
Se no meio do loop o valor for zero, não preciso mais verificar nenhuma nota, então posso interrompê-lo com break
.
Outra opção é usar divmod
, que já retorna o resultado da divisão e o resto de uma só vez:
for nota in notas:
if valor >= nota:
qtd, valor = divmod(valor, nota)
print(f'{qtd} nota{"" if qtd == 1 else "s"} de {nota}')
if valor == 0:
break # se o valor zerou, sai do for
Também coloquei um if
a mais para colocar ou não o "s" na palavra "nota", assim a mensagem fica "1 nota" caso a quantidade seja 1, e "X notas" para X maior que 1.
Por fim, vale lembrar que os códigos acima só imprimem as quantidades de cada nota. Mas se quiser também guardar essas quantidades, pode usar um dicionário:
quantidades = {} # guardar as quantidades de cada nota
for nota in notas:
if valor >= nota:
qtd, valor = divmod(valor, nota)
quantidades[nota] = qtd
if valor == 0:
break # se o valor zerou, sai do for
# imprimir as quantidades
for nota, qtd in quantidades.items():
print(f'{qtd} nota{"" if qtd == 1 else "s"} de {nota}')
No caso acima eu só imprimi as quantidades, mas uma vez que temos esses valores guardados no dicionário, podemos fazer o que quiser com eles. Eu acho melhor assim do que ter um monte de variáveis quantidadeNotasUm
, quantidadeNotasCinco
, etc. Não só por ser mais simples, mas também por ser mais genérico e funcionar com vários conjuntos de notas.
Para funcionar com qualquer conjunto de notas
Conforme dito acima, na verdade o algoritmo para funcionar com qualquer conjunto de notas seria um pouco mais complicado.
Por exemplo, se eu tiver apenas notas de 100, 50 e 20, e o valor for 60, o código acima dirá que precisa de uma nota de 50, o que está errado. Isso porque ainda faltam 10, mas as notas restantes não servem para completar este valor (pois a menor nota é de 20). O correto seria tentar novamente sem as notas de 50, pois a resposta neste caso é "3 notas de 20".
O mesmo acontece se for um valor que não é possível com nenhuma das combinações. No caso da pergunta sempre será possível porque a menor nota é 1, e como os valores sempre são números inteiros, então qualquer valor que sobre acabará sendo contemplado pelas notas de 1. Mas se as notas fossem apenas 100, 50 e 20, por exemplo, e o valor fosse 75, não seria possível com nenhuma das combinações.
Sendo assim, eu tenho que testar várias combinações de notas diferentes (primeiro com todas, se não der certo, tento sem a primeira nota, depois sem a segunda, e assim por diante, até que o valor tenha zerado, ou que nenhuma das combinações tenha funcionado).
Para gerar essas combinações, podemos usar o módulo itertools
, que na seção de "Recipes" mostra como gerá-las (eu adaptei para limitar o tamanho mínimo, além de colocar a combinação de todas as notas primeiro):
from itertools import chain, combinations
def powerset(iterable, size_limit=0):
"""
powerset([100, 50, 20]) --> (100, 50, 20) (100, 50) (100, 20) (50, 20) (100,) (50,) (20,) ()
powerset([100, 50, 20], 2) --> (100, 50, 20) (100, 50) (100, 20) (50, 20)
"""
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1, size_limit - 1, -1))
Ou seja, primeiro eu tento com todas as notas, depois removendo uma delas, depois removendo outra, e assim por diante. E assim que eu encontrar uma combinação que sirva, eu paro. Mas tem outro detalhe, eu não posso simplesmente pegar a maior quantidade possível da maior nota, pra depois ir para a próxima. Por exemplo, se o valor for 210 e só tiver notas de 50 e 20, não basta dividir 210 por 50, pois dará 4 notas de 50 e não será possível concluir com as notas de 20. Neste caso teria que pegar alguma das combinações possíveis (como 3 de 50 e 3 de 20, ou 1 de 50 e 8 de 20, etc).
Então eu crio uma função para gerar essas possibilidades, e pego a primeira delas:
from collections import Counter
def subsets(notas, valor, c = []):
if sum(c) == valor:
yield c
else:
for i in notas:
if sum(c + [i]) <= valor:
yield from subsets(notas, valor, c + [i])
def calcular_qtd_notas(valor_total, todas_notas):
for notas in powerset(todas_notas, 2):
# tenta encontrar um subset cuja soma seja o total
try:
return dict(Counter(next(subsets(notas, valor_total))))
except StopIteration:
pass # se não tem, tenta com a próxima combinação de notas
return None # se tentou todas as combinações e chegou aqui, é porque não é possível
Eu poderia usar a função subsets
para mostrar mais de uma possibilidade, mas no caso optei por pegar apenas a primeira (fica a seu critério o que fazer). A vantagem é que ela não gera todas as possibilidades de uma vez, já que esta função é um generator, ou seja, só gera sob demanda (apesar de não estar otimizada, pois ela gera a mesma combinação várias vezes - por exemplo, 20, 20, 50
e 20, 50, 20
- fica como exercício para o leitor eliminar essas repetições).
Eu limito às combinações de duas notas, porque não é necessário testar as que só tem uma nota. Por exemplo, para notas = [100, 50, 20]
. Se o valor é múltiplo de 100
, ele irá funcionar com este conjunto de notas, não sendo necessário testar para o conjunto que tem apenas a nota de 100. O mesmo vale para as demais, por isso vou até o limite de duas notas.
Testando:
def test(valor, notas):
print(f'Sacar ${valor} para {notas}')
quantidades = calcular_qtd_notas(valor, notas)
if quantidades is None:
print(f' - Não foi possível')
else:
for nota, qtd in quantidades.items():
print(f' - {qtd} nota{"" if qtd == 1 else "s"} de {nota}')
test(210, [50, 20]) # 3 notas de 50 e 3 notas de 20
test(60, [100, 50, 20]) # 3 notas de 20
test(60, [100, 50, 10]) # 1 nota de 50 e 1 nota de 10
test(75, [100, 50, 20]) # Não foi possível
test(360, [100, 50, 20]) # 3 notas de 100 e 3 notas de 20
Saída:
Sacar $210 para [50, 20]
- 3 notas de 50
- 3 notas de 20
Sacar $60 para [100, 50, 20]
- 3 notas de 20
Sacar $60 para [100, 50, 10]
- 1 nota de 50
- 1 nota de 10
Sacar $75 para [100, 50, 20]
- Não foi possível
Sacar $360 para [100, 50, 20]
- 3 notas de 100
- 3 notas de 20