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

[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.

[thoga31]

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.

[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.

[thoga31]

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.

[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 November 14, 2015 at 09:11 PM by thoga31
Correção das tags

[thoga31]

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.

[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 November 14, 2015 at 10:57 PM by thoga31
Tags code + GeSHi

[thoga31]

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

[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

[thoga31]

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.

[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) ) )

[thoga31]

O caso é que em a e b são o 1° e 2° elementos de uma lista que está em f

What?

[crislanio_macedo]

Eu sei o que é, só não to conseguindo enxergar como faz.

Edited November 14, 2015 at 11:42 PM by crislanio_macedo

[thoga31]

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 November 14, 2015 at 11:54 PM by thoga31

[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 November 15, 2015 at 12:02 AM by thoga31
Tags code + GeSHi

[thoga31]

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?

[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 November 15, 2015 at 12:07 AM by crislanio_macedo

[thoga31]

Por favor, estuda lambda functions: http://learnyouahaskell.com/higher-order-functions#lambdas

É absolutamente essencial perceber este conceito em Haskell, entre outros.

[crislanio_macedo]

troco t = map (\xs -> ( head xs, length xs)) . group $ ft s@(x:xs)

thoga31, seria algo do tipo acima? qual seria o argumento de ft

[thoga31]

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.