crislanio_macedo Posted November 13, 2015 at 02:36 AM Report Share #589645 Posted November 13, 2015 at 02:36 AM 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 More sharing options...
thoga31 Posted November 13, 2015 at 05:15 PM Report Share #589669 Posted November 13, 2015 at 05:15 PM 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 More sharing options...
crislanio_macedo Posted November 13, 2015 at 07:33 PM Author Report Share #589673 Posted November 13, 2015 at 07:33 PM 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 More sharing options...
thoga31 Posted November 13, 2015 at 09:28 PM Report Share #589674 Posted November 13, 2015 at 09:28 PM 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): Criar a função que gera o troco numa lista simples; 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: Não tentar escrever tudo numa só linha - é pouco elegante; Utilizar pattern matching e guards será uma óptima estratégia. 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 More sharing options...
crislanio_macedo Posted November 14, 2015 at 08:28 PM Author Report Share #589710 Posted November 14, 2015 at 08:28 PM (edited) 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 Link to comment Share on other sites More sharing options...
thoga31 Posted November 14, 2015 at 09:14 PM Report Share #589713 Posted November 14, 2015 at 09:14 PM 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 More sharing options...
crislanio_macedo Posted November 14, 2015 at 10:56 PM Author Report Share #589718 Posted November 14, 2015 at 10:56 PM (edited) 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 Link to comment Share on other sites More sharing options...
thoga31 Posted November 14, 2015 at 10:59 PM Report Share #589719 Posted November 14, 2015 at 10:59 PM What is that? Não entendo a ideia por detrás desse código, esquecendo o facto de nem sequer funcionar. Knowledge is free! Link to comment Share on other sites More sharing options...
crislanio_macedo Posted November 14, 2015 at 11:16 PM Author Report Share #589721 Posted November 14, 2015 at 11:16 PM 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 More sharing options...
thoga31 Posted November 14, 2015 at 11:23 PM Report Share #589722 Posted November 14, 2015 at 11:23 PM 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 More sharing options...
crislanio_macedo Posted November 14, 2015 at 11:34 PM Author Report Share #589723 Posted November 14, 2015 at 11:34 PM 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 More sharing options...
thoga31 Posted November 14, 2015 at 11:38 PM Report Share #589724 Posted November 14, 2015 at 11:38 PM O caso é que em a e b são o 1° e 2° elementos de uma lista que está em f What? Knowledge is free! Link to comment Share on other sites More sharing options...
crislanio_macedo Posted November 14, 2015 at 11:42 PM Author Report Share #589725 Posted November 14, 2015 at 11:42 PM (edited) Eu sei o que é, só não to conseguindo enxergar como faz. Edited November 14, 2015 at 11:42 PM by crislanio_macedo Link to comment Share on other sites More sharing options...
thoga31 Posted November 14, 2015 at 11:52 PM Report Share #589726 Posted November 14, 2015 at 11:52 PM (edited) 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 Knowledge is free! Link to comment Share on other sites More sharing options...
crislanio_macedo Posted November 14, 2015 at 11:55 PM Author Report Share #589727 Posted November 14, 2015 at 11:55 PM (edited) 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 Link to comment Share on other sites More sharing options...
thoga31 Posted November 15, 2015 at 12:03 AM Report Share #589728 Posted November 15, 2015 at 12:03 AM 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 More sharing options...
crislanio_macedo Posted November 15, 2015 at 12:07 AM Author Report Share #589729 Posted November 15, 2015 at 12:07 AM (edited) 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 Link to comment Share on other sites More sharing options...
thoga31 Posted November 15, 2015 at 12:09 AM Report Share #589730 Posted November 15, 2015 at 12:09 AM Por favor, estuda lambda functions: http://learnyouahaskell.com/higher-order-functions#lambdas É absolutamente essencial perceber este conceito em Haskell, entre outros. Knowledge is free! Link to comment Share on other sites More sharing options...
crislanio_macedo Posted November 15, 2015 at 12:43 AM Author Report Share #589731 Posted November 15, 2015 at 12:43 AM 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 Link to comment Share on other sites More sharing options...
thoga31 Posted November 15, 2015 at 01:14 AM Report Share #589732 Posted November 15, 2015 at 01:14 AM 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 More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now