Jump to content
explod1ng

Calcular menor troco

Recommended Posts

explod1ng

Boa noite.

Estou a desenvolver um programa que permite calcular o menor troco através de uma série de moedas disponíveis, por exemplo:

troco = 24

moedas = {20,12,1}

A solução devia ser 2 moedas de 12.

Numa primeira fase implementei uma solução que apenas verificava se era possível dar troco e que não calculava o menor número de moedas com que se podia fazer esse troco, para isso usei o seguinte código.

public static int [] calcula(int troco,int [] moedas){
        int i =0;
        int [] nmoedas =new int [moedas.length];
        
        while(moedas[i]!=0){
            
            if (troco >= moedas[i]){
                troco = troco - moedas[i];
                nmoedas[i]=nmoedas[i]+1;
            }
            else{
                if((moedas[i+1]==0) && (troco !=0))
                    nmoedas[i]++;
                i++;
            }
            
        }
        return nmoedas;
    }

Agora tenho que implementar uma solução usando recursividade e que já devolva a solução onde o número de moedas a dar como troco é menor, mas não estou a conseguir fazer.

Já vi o seguinte tópico  http://www.portugal-a-programar.pt/index.php?showtopic=17250 onde o problema é parecido com o meu mas continuo sem perceber muito bem uma vez que na solução que foi desenvolvida nesse tópico não percebo certas partes do código. Se alguém conseguir dar uma ajuda agradecia.

Cumprimentos.

Share this post


Link to post
Share on other sites
pedrotuga

O conjunto de moedas do enunciado é esquisito. 20 nem sequer duas vezes maior que 12 é. Eu diria que um sistema desses não faz sentido.

Eu estou a referir isto não é porque sou chato, é porque os valores das moedas reais são escolhidos de forma a simplificar ao máximo este tipo de problema. Mas com as moedas posíveis que enuncias, então o algoritmo fica muito mais complicado.

De resto, o exemplo que dás ilustra bem isso. 24, o troco com menos moedas são duas moedas de 12, mas com dinheiro normal, se puderes usar a maior moeda possível, isso nunca te vai fazer usar mais moedas no final de contas.

Não estou a ver se isso dá para resolver com recursividade simples, só com backtracking.

Até escrevia aqui o algoritmo, mas vou dormir :)

Não sei, se calhar o objectivo é mesmo complicar, isso é típico no ensíno português.

Share this post


Link to post
Share on other sites
explod1ng

Sim é mesmo para complicar, mas é o que é pedido.

Depois se puderes explicar como funciona o backtracking agradecia, estive agora a pesquisar mas não percebi muito bem.

Share this post


Link to post
Share on other sites
pedrotuga

Backtracking é um caso particular de recursividade que é utilizado para fazer pesquisas numa árvore.

Entras por um ramo, se esse ramo te levar a um beco sem saída voltas atrás e vais por outro ramo. Assim que chegas a outra bifurcação, aplicas o mesmo algoritmo.

O teu algoritmo seria então, uma coisa deste tipo.

Isto está uma mistura de pseudocódigo com código normal :s

function calculatroco(trocototal, array moedas[], array trocofinal[]){

     array trocofinal[];
     para cada moeda em arraymoedas[]{
         se moeda for maior que troco total devolve null;
         
         insere moeda no array trocofinal[]
         subtrai valor da moeda à variável trocototal;

         se troco total for zero: guarda o array troco final algures (num atributo da classe) mas só se o seu comprimento for menor que o que já lá está, caso já lá esteja alguma coisa. 
     
         caso contrario: chama claculatroco( trocototal, array moedas[], arraytrocofinal[])
}

}

Repara que quando chamas claculatroco() recursivamente, os parâmetros já foram modificados.

O array moedas[] aqui não precisa de andar sempre a ser passado porque nunca é alterado, mas para não meter scope de variáveis ao barulho, é capaz de ser a forma mais facil.

Share this post


Link to post
Share on other sites
explod1ng

Obrigado, só não estou a perceber o que faz o array trocofinal. Guarda quantas moedas de cada tipo vão existir?

Share this post


Link to post
Share on other sites
pedrotuga

Obrigado, só não estou a perceber o que faz o array trocofinal. Guarda quantas moedas de cada tipo vão existir?

Sim. É o array onde vais guardando as moedas que fazem parte do troco.

Isto com arrays simples não é nada prático.

Há estruturas de dados próprias para fazer isto, ArrayList por exemplo.

Se já falaram desse tipo de estruturas de dados, usa-as.

Share this post


Link to post
Share on other sites
explod1ng

Sim podemos usar ArrayLists, mas neste caso acho que com arrays simples é mais fácil, uma vez que isto tem que ser submetido no mooschak e com ArrayLists depois torna-se bem mais dificil fazer os outputs pedidos.

Share this post


Link to post
Share on other sites
pedrotuga

O array não tem nenhuma forma simples de adicionar elementos sequencialmente. Com um arraylist basta usar o método add(), e depois no fim podes converter parra array simplesmente chamando o método toArray().

Adicionalmente facilmente obtens o comprimento de um arraylist, enquanto que se usares um array tens que manter tu a contagem de quantos elementos lá inseriste.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.