1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

[algoritmo] menor troco

Discussão em 'Programação' iniciada por CyberOps, 28 de Fevereiro de 2008. (Respostas: 6; Visualizações: 2792)

  1. CyberOps

    CyberOps I'm cool cuz I Fold

    Boas,

    estou aqui com um problema para achar um algoritmo para achar o menor troco.
    ja fiz o codigo para determinar se o troco realmente existe mas caso ele n existe tenho q determinar um possivel troco com o menor numero de moedas. por exemplo

    exemplo sem troco possivel:
    troco = 11 %% com moedas dos tipos 10 e 5
    1 10
    1 5

    Código:
    int [] moedas = new int[]{25, 20, 13, 7, 5, 3}; /*tem que estar ordenado decrescentemente*/
    int [] nmoedas = new int[moedas.lenght]
    while(soma!=troco && i<moedas.length){				
    
    	if(troco>=moedas[i]){
    		j=i;
    		while(j<moedas.length){
    			System.out.println("adicionou: "+moedas[j]);
    			soma+=moedas[j];
    			nmoedas[j]+=1;
    
    			if(soma>troco){
    				System.out.println("retirou: "+moedas[j]);							
    				soma-=moedas[j];
    				System.out.println("soma: "+soma);
    				nmoedas[j]-=1;
    				j++;
    			}else if(soma==troco){
    				System.out.println("certo");
    				return nmoedas;
    			}						
    		}
    		soma-=moedas[i];
    		nmoedas[i]-=1;
    		i++;
    	}else
    		i++;
    
    se calhar tenho q arranjar outro forma de determinar o menor troco para ter sempre uma referencia para o melhor troco até ao final, nao?

    e se calhar tenho q fazer todas as combinaçoes possiveis, claro q retirando sempre as somas que excedem o troco

    cumps
     
  2. souto

    souto To fold or to FOLD?

    Pelo que vejo, só precisas de calcular o troco, e depois disso:

    Escolher a maior moeda disponível, somar a uma variável. Recalcular o troco que falta dar.
    Escolher novamente a maior moeda disponível. Recalcular...

    Isto duma forma muito básica. :) Não há nada para complicar aqui ;)
     
  3. CyberOps

    CyberOps I'm cool cuz I Fold

    não sei se percebi bem o que disseste
    calcular o troco como? ver se existe mesmo a quantia exacta?

    exacto, mas acho q ao dar o troco tem sempre que ser por excesso, caso n dê quantia exacta com as moedas disponiveis. se tiveres q dar troco de 11 com moedas de 10 e 5 tens q dar 3 * 5 moedas. pelo menos é assim q acho q deve ser. estou a espera da resposta do prof relativamente a esta minha duvida.

    cumps
     
  4. slack_guy

    slack_guy Power Member

  5. CyberOps

    CyberOps I'm cool cuz I Fold

    nao é bem igual. a parte de dar o troco certo ja tenho implementado.

    o problema é q isto tem sempre que cuspir troco caso a maquina não tenha troco certo para dar e é sempre o menor numero de moedas que excede o troco, ou seja

    troco = 11 %% com moedas dos tipos 10 e 5
    1 10
    1 5
     
  6. slack_guy

    slack_guy Power Member

    O problema ou está mal formulado, ou pressupõe uma impossibilidade ou eu estou todo maradinho! :-)

    Para poderes dar troco de 11, tens de ter moedas cujo valor te permita essa possibilidade. Repara que só podem existir preços cujo contra-valor possa ser expresso numa unidade de medida existente.

    Dito isto, de acordo com as moedas que tens definidas (25, 20, 13, 7, 5, 3), 11 (o teu exemplo), nunca poderia acontecer - nem como preço nem como troco.

    Neste caso, assumindo a impossibilidade, as moedas deveriam ser:
    1 x 7
    1 x 5
    Assim, a 'casa' ficava a perder apenas 1; enquanto que no teu exemplo a 'casa' ficava a perder 4.

    Outra solução: se o que interessa é, por esta ordem:
    1º menor número de moedas;
    2º menor 'prejuízo' para a casa.

    devolve-se apenas 1 x 13

    Assume-se a perda de 2, mas só se devolve uma moeda.

    Resumindo: mostra lá o enunciado completo, que parece-me que há aí alguma confusão.
     
  7. CyberOps

    CyberOps I'm cool cuz I Fold

    Foi pedido aos alunos de AED que desenvolvam um programa eficiente para, sabendo
    a soma a devolver ao cliente, fazer o cálculo das moedas a entregar. Os pressupostos
    são os seguintes:
    1. A máquina tem moedas de 25, 13 e 1 unidades, por exemplo. Pode ter outras.
    2. O número de moedas disponíveis de cada tipo não limita a composição do
    troco
    3. O programa deve permitir também ter uma zona de parametrização em que
    possamos indicar outro leque diverso de moedas.
    4. O objectivo é que o troco seja formado pelo menor número possível de
    moedas.

    exemplos:

    Exemplo de input
    11 %% com moedas dos tipos 10 e 5
    Exemplo de output
    1 10
    1 5
    2
    -1
    *************************
    Exemplo de input
    26 %% com moedas dos tipos 20 13 1
    __________________________
    Exemplo de output
    1 20 %% solução sôfrega
    0 13
    6 1
    7
    0
    _______________________
    0 20 %% solução recursiva ou c/ progr dinâmica
    2 13
    0 1
    2
    0

    é +- isso. é como tenho no exemplo acima. a maq tem q dar troco de 11 e so tem moedas de 10 e 5. Ou seja, a maquina vai dar uma de 10 e outra de 5. Tem q dar sempre por excesso no menor numero de moedas. nao pode por exemplo dar 10.
     
    Última edição: 28 de Fevereiro de 2008

Partilhar esta Página