Jump to content

Problema da troco mínimo de moedas (Algoritmo Guloso)


crislanio_macedo
 Share

Recommended Posts

crislanio_macedo
troco n b soma a = if soma /= n then troco (n- (soma *maximum a) ) ( b ++ maximum [a]) (soma+1) a else soma

Olá pessoal, para ter o troco mínimo de um valor eu tenho que sempre escolher a moeda de maior valor e diminuir o valor de n, nesse caso o algoritmo está em loog infinito.

troco 71 [] 0 [25,10,5,1]

A ideia era que a saída fosse o valor mínimo de moedas utilizadas no troco.

Link to comment
Share on other sites

Seria suposto a função troco funcionar nestes moldes?

Prelude> troco 71 [20,10,5,1]
[20,20,20,10,1]

Não entendi o que tentaste fazer nessa função.

Não precisas de passar esses argumentos todos - basta o valor em numerário e as moedas disponíveis.

Além disso, nada te impede de, no decorrer da função, "destruires" elementos da lista de moedas disponíveis: por exemplo, se sobram 15 cêntimos, podes eliminar a moeda de 20 da lista.

Precisas de uma função recursiva e não a estás a construir. Explica qual é o algoritmo que tentaste aplicar.

Cumprimentos.

Knowledge is free!

Link to comment
Share on other sites

crislanio_macedo

Tenho que ter uma função que retorne o mínimo de troco para moedas de 25, 10, 5,1

Ex: para 71 a solução seria 2*25, 2*10, 1*1

 troco n (x:xs) = if n<=x then troco (n-x) xs else troco n xs

Por exemplo, algo assim resolveria, diminuindo o valor de N da maior moeda tal que Valor Maior Moeda < N, e o ideal seria retornar também a frequência que cada moeda era usada para compor o valor.

Link to comment
Share on other sites

Essa função em particular não resolveria.

Portanto, querias algo assim:

Prelude> troco 71 [25,10,5,1]
[(2,25),(2,10),(1,1)]

Para tal precisas de uma função com esta declaração:

troco :: Int -> [int] -> [(Int, Int)]

O mais fácil será criar o resultado como uma lista de todos os valores sem contagem, ou seja:

[25,25,10,10,1]

A esta lista aplicas uma função que junte os elementos em tuplos:

[(2,25),(2,10),(1,1)]

Esta será a estratégia inicial. Tens então dois problemas a resolver em separado (os quais juntas no final facilmente):

  1. Criar a função que gera o troco numa lista simples;
  2. Criar uma função que agrupe os elementos repetidos consecutivos.

Para o ponto 2 deixo como dica o uso da função group (é necessário importar da Data.List).

Para o ponto 1 deixo três dicas:

  1. Não tentar escrever tudo numa só linha - é pouco elegante;
  2. Utilizar pattern matching e guards será uma óptima estratégia.
  3. Um esboço do código que estou a propor 😉
    -- "ft" = Função Troco
    -- Ao resultado desta função será aplicada a função de agrupamento referida anteriormente no ponto 2.
    ft 0 _ = []
    ft p m@(x:xs) | -- a preencher
                 | otherwise = -- a preencher
    


Cumprimentos.

Knowledge is free!

Link to comment
Share on other sites

crislanio_macedo
ft 0 _ = []
ft p [] = []
ft p m@(x:xs) | p >= x = x:ft (p-x) m
             | otherwise = ft p xs

Para a função group como contabilizar os valores iguais e colocar na função de saída?

import Data.List 
troco c1 l1@(x:xs) = group (ft c1 l1)) ...
Edited by thoga31
Correção das tags
Link to comment
Share on other sites

A função group junta valores iguais consecutivos numa lista, originando uma lista de listas. Exemplo:

Prelude> group [1,1,1,2,2,3,4,4]
[[1,1,1],[2,2],[3],[4,4]]

Portanto, tudo o que precisas é de uma função map que transforme estas listas em tuplos:

Prelude> map (funcao) . group $ [1,1,1,2,2,3,4,4]
[(3,1),(2,2),(1,3),(2,4)]

O que tens de fazer é determinar o que será "funcao".

Dica: é uma função lambda.

Knowledge is free!

Link to comment
Share on other sites

crislanio_macedo

Precisaria de um troco t, sendo igual a uma função map (frequencia head x ft) . group $ ft

frequencia x xs = [y | y<-xs, x==y]

troco t = map () . group $ ft t (x:xs) )

algo assim

Edited by thoga31
Tags code + GeSHi
Link to comment
Share on other sites

crislanio_macedo

What is that? Não entendo a ideia por detrás desse código, esquecendo o facto de nem sequer funcionar.

De fato não funciona, a frequencia conta o número de vezes que cada elemento ocorre numa lista, a função map teria que mapear com uma função que conta o número de vezes que um elemento ocorre numa lista, e agruparia em group em cada sublista a frequencia e o numero

Link to comment
Share on other sites

Estás a complicar aquilo que é simples. O Haskell tem uma panóplia de funções prontas-a-usar. Vejamos:

  • Para contar quantos elementos tem uma lista:
    length lista
    


  • Para mapear:
    map (\xs -> (a, b)) . group
    


Já te estou a dar a solução quase toda... só te falta preencher "a" e "b". Repara bem que "a" e "b" são, respecivamente, o primeiro e o segundo elemento do tuplo que será gerado.

Knowledge is free!

Link to comment
Share on other sites

crislanio_macedo

O caso é que em a e b são o 1° e 2° elementos de uma lista que está em f , então poderia fazer o head da lista e o 2° elemento dela?

A ideia seria algo assim

troco t = map (\xs -> (x,  )) . group $ ft t (x:xs) ) )
Link to comment
Share on other sites

Ao passar de [[1,1,1],[2,2],[3],[4,4]] para [(3,1),(2,2),(1,3),(2,4)], qual é a composição dos tuplos?

Exemplo: de [4,4] passámos a ter (2,4). 4 é o elemento que compõe a lista (pode ser dado pela função head) e 2 é o número de elementos da lista cuja função já indiquei).

Então, o que será "a" e "b" em (a, b)?

Não pode ser assim tão difícil - já te dei a estrutura da função que faz o mapeamento e já te dei as funções que constroem o tuplo.

Edited by thoga31

Knowledge is free!

Link to comment
Share on other sites

crislanio_macedo

Ok, poderia ficar algo assim:

troco t = map (\xs -> ( lenght ft, head ft ) . group $ ft t xs

mas xs não estaria no escopo de ft nesse caso em group

Edited by thoga31
Tags code + GeSHi
Link to comment
Share on other sites

Três coisas:

1) A função length está mal escrita;

2) Os parêntesis não estão correctamente fechados:

3) Que raio está o ft a fazer dentro do map? Sabes o que é o \xs?

Knowledge is free!

Link to comment
Share on other sites

crislanio_macedo

Três coisas:

1) A função length está mal escrita;

2) Os parêntesis não estão correctamente fechados:

3) Que raio está o ft a fazer dentro do map? Sabes o que é o \xs?

troco t = map (\xs -> ( head xs, length xs )) . group $ ft t ?

Não, é uma função anônima onde.

Edited by crislanio_macedo
Link to comment
Share on other sites

A notação s@(x:xs) não se usa nesse ponto dessa forma. Essa notação serve para identificar uma lista enquanto argumento de uma função e não para passar uma lista como argumento.

fn l@(x:xs) = -- whatever

Que argumentos recebe troco? E que argumentos recebe ft?

Os argumentos de ambos são os mesmos! A única questão é que troco faz o "empacotamento" dos dados brutos devolvidos por ft.

Portanto, se troco recebe dois argumentos, esses mesmos dois serão os passados a ft.

Tens de pensar e analisar aquilo que tens à tua frente e não estar apenas à espera que eu te diga as coisas.

Knowledge is free!

Link to comment
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
 Share

×
×
  • 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.