Troco do caixa

Elabore um algoritmo para determinar as cédulas do saque em um terminal de autoatendimento bancário. O algoritmo receberá o valor de deve ser entregue, seguido dos tipos de cédula. O terminal deve entregar o menor número de cédulas possível, mas com pelo menos uma cédula de cada tipo solicitado. Considere que o sempre existirá uma solução possível.

Por exemplo, se o valor for de R$ 100,00 e forem solicitadas cédulas de R$ 20,00 e R$ 10,00, o caixa deverá entregar 4 cédulas de R$ 20,00 e 2 cédulas de R$ 10,00. Nunca seriam solicitadas as cédulas de R$ 50,00 e R$ 20,00 pois não existiria solução possível com as restrições apresentadas.

Código em Python

Uma primeira proposta de solução é mostrada no código a seguir. Ele funciona para uma entrada como R$ 110,00 de saque com notas de R$ 50,00 e R$ 10,00, mas não funcionará para todos os casos.

total = int(input()) #total a ser sacada
nota1 = int(input()) #primeiro tipo de nota
nota2 = int(input()) #segundo tipo de nota

#int() pega apenas a parte inteira da divisão
notas1 = int(total / nota1)
#desconta o que já foi dado em notas de 100
total = total - (notas1 * nota1) 
#faz o mesmo para a outra nota
notas2 = int(total / nota2)

print "Notas de ", nota1, ": ", notas1
print "Notas de ", nota2, ": ", notas2

Teste o código: http://www.codeskulptor.org/#user43_Zo0wEeOtyz_0.py

Embora a solução entregue o menor número de cédulas, ela não atende a consideração de que “pelo menos uma cédula de cada tipo solicitado” deve ser entregue. Para isso, as linhas 13, 14 e 15 são necessárias, forçando o uso do segundo tipo de nota.

total = int(input()) #total a ser sacada
nota1 = int(input()) #primeiro tipo de nota
nota2 = int(input()) #segundo tipo de nota

#int() pega apenas a parte inteira da divisão
notas1 = int(total / nota1)
#desconta o que já foi dado em notas de 100
total = total - (notas1 * nota1) 
#faz o mesmo para a outra nota
notas2 = int(total / nota2)

if notas2 == 0:
    notas1 = notas1-1
    notas2 = int(nota1 / nota2)

print "Notas de ", nota1, ": ", notas1
print "Notas de ", nota2, ": ", notas2

Teste o código: https://py2.codeskulptor.org/#user51_Zo0wEeOtyz_2.py

A solução foi melhorada, mas ainda não é suficiente. Ela funciona se a ordem informada das notas for a maior e depois a menor. Se a entrada for 150 50 10 a saída será correta, mas caso a entrada seja 150 10 50, ela não será adequada. Para isso, são adicionadas as linhas 5-8, garantindo as notas em ordem decrescente.

total = int(input()) #total a ser sacada
nota1 = int(input()) #primeiro tipo de nota
nota2 = int(input()) #segundo tipo de nota

if nota2 > nota1:
    aux = nota1
    nota1 = nota2
    nota2 = aux
    
#int() pega apenas a parte inteira da divisão
notas1 = int(total / nota1)
#desconta o que já foi dado em notas de 100
total = total - (notas1 * nota1) 
#faz o mesmo para a outra nota
notas2 = int(total / nota2)

if notas2 == 0:
    notas1 = notas1-1
    notas2 = int(nota1 / nota2)

print "Notas de ", nota1, ": ", notas1
print "Notas de ", nota2, ": ", notas2

As linhas 6-8 poderiam ser substituídas pelas linhas do código a seguir. O resultado é o mesmo, a operação é mais confusa, mas é evitada a utilização de uma variável (economiza uma variável).

    nota1 = nota1+nota2
    nota2 = nota1-nota2
    nota1 = nota1-nota2

Código em C/C++

Assim como mostrado em Python, o código a seguir é uma primeira tentativa.

#include <stdio.h>

int main(void) {
	int total, nota1, nota2, notas1, notas2;
	scanf("%i", &total); //total a ser sacado
	scanf("%i %i", &nota1, &nota2); //ler os dois tipos de nota
	
	//divisão de inteiro por inteiro resulta apenas a parte inteira da divisão
	//eu garanti com o casting (int) que converte um valor para inteiro
	notas1 = (int)total / nota1; 
	total = total - (notas1 * nota1); //desconta o que já foi dado em notas do primeiro tipo
	notas2 = (int)total / nota2; //faz o mesmo para a outra nota
	
	printf("Notas de %i: %i \n", nota1, notas1);
	printf("Notas de %i: %i", nota2, notas2);
	
	return 0;
}

Teste o código: http://ideone.com/a3WZWh

Para a solução completa, o código abaixo é proposto.

#include <stdio.h>

int main() {
    int total, nota1, nota2, notas1, notas2;

    // Entrada dos valores
    printf("Digite o valor total a ser sacado: ");
    scanf("%d", &total);
    printf("Digite o valor da primeira nota: ");
    scanf("%d", &nota1);
    printf("Digite o valor da segunda nota: ");
    scanf("%d", &nota2);

    // Troca os valores se nota2 for maior que nota1
    if (nota2 > nota1) {
        int aux = nota1;
        nota1 = nota2;
        nota2 = aux;
    }

    // Calcula a quantidade de notas de cada tipo
    notas1 = total / nota1;
    total = total - (notas1 * nota1);
    notas2 = total / nota2;

    // Ajusta a quantidade de notas se necessário
    if (notas2 == 0) {
        notas1 = notas1 - 1;
        notas2 = nota1 / nota2;
    }

    // Imprime o resultado
    printf("Notas de %d: %d\n", nota1, notas1);
    printf("Notas de %d: %d\n", nota2, notas2);

    return 0;
}

Teste o código: https://ideone.com/dPf1EQ