Jump to content

Dúvidas com algumas questões de Haskell


Guest 1505338889
 Share

Recommended Posts

Guest 1505338889

Alguém poderia me ajudar a resolver essas questões?

1- Escreva uma função em Haskell para determinar o MDC de dois números inteiros positivos pela utilização do algoritmo de Euclides.

2- Escreva uma função em Haskell para determinar se um número inteiro positivo e ou não primo. Utilize para isto o algoritmo de Eratostenes.

3- Escreva uma função em Haskell que dada uma lista de elementos e um inteiro, retorne uma lista com dois elementos cuja soma é a que mais se aproxima do inteiro recebido. Caso não seja encontrado tal par (ex.: a lista de entrada possui tamanho 1), a lista retornada deve ser vazia.

4- Escreva uma função em Haskell para determinar todas as permutações de uma lista de entrada cujos elementos armazenados sejam de um tipo desconhecido T. O retorno da função deve ser uma lista de listas.

Link to comment
Share on other sites

Guest Kylops

Quanto à questão 1:

mdc :: Integer -> Integer -> Integer
mdc a 0 = a
mdc a b = mdc b (a `mod` b)

Se conseguir posto aqui as outras também, mas como sou iniciante em Haskell não prometo nada 😛

Link to comment
Share on other sites

Guest 1505338889

Obrigado Kylops !  🙂

Essa 1 é a mais fácil mesmo, também sou iniciante, então ta osso de fazer.

mas to conseguindo algumas..

Olha essa aqui em baixo se você acha que ta certo:

*Implemente em Haskell o algoritmo de ordenação por inserção para ordenar uma lista de elementos do tipo Ord.

insere :: (Ord a) => a -> [a] -> [a]
insere e [] = [e]
insere e (a:x)
   | e <= a    = e : (a:x)
   | otherwise = a : insere e x
Link to comment
Share on other sites

Guest 1505338889

alguém me ajuda ver se isso ta certo???

2- Escreva uma função em Haskell para determinar se um número inteiro positivo e ou não primo. Utilize para isto o algoritmo de Eratostenes.

eratosthenes :: [int] -> [int]
eratosthenes []    = []
eratosthenes (h:t) = h : (eratosthenes (filter (\x -> mod x h /= 0) t))

-- conjunto dos primos menores ou iguais a 'x'
primos :: Int -> [int]
primos x = eratosthenes [2..x]
Link to comment
Share on other sites

Não tens nenhuma função que faça o que é pedido (determinar se o número é primo ou não).

Ainda precisas de uma função que verifique se x está no conjunto de primos entre 2 e x.

Na questão da ordenação, acho que tens um problema semelhante. Implementaste uma função que faz a inserção ordenada numa lista, mas não tens nenhuma função de ordenação.

Link to comment
Share on other sites

Guest 1505338889

Rui, conseguir fazer dessa forma. Em que a função fatores retorna cada um dos fatores de um número e depois a utilizei para verificar se o número é primo.

fatores n = [i | i<-[1..n], n `mod` i == 0]
primo n = if (fatores n) == [1,n]   then True
					     else False

Porém tenho uma dúvida: agora a função determina se o número é ou não primo, mas parece q não utilizei para isto o algoritmo de Eratostenes. aff.. nao sei oq eh esse algoritmo de erastotenes direito.. oq acha ? ta errado ne?

Link to comment
Share on other sites

Esse código está correcto. O problema é que esse código é terrivelmente ineficiente.

Daí o exercício pedir para se usar o algoritmo de Eratóstenes.

Podes ler sobre o algoritmo em http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Link to comment
Share on other sites

Guest 1505338889

Então Betovsky, eu já li sobre o agoritmo de Erastóstenes.

Porém eu conseguir fazer isso:

eratosthenes :: [int] -> [int]
eratosthenes []    = []
eratosthenes (h:t) = h : (eratosthenes (filter (\x -> mod x h /= 0) t))

-- conjunto dos primos menores ou iguais a 'x'
primos :: Int -> [int]
primos x = eratosthenes [2..x]

Mas o fato é que preciso escrever uma função em Haskell para determinar se um número inteiro positivo é ou não primo a partir desse algoritmo de erastostenes. E não consigo! vc tem alguma idéia de como posso fazer isso a partir desse código que te mandei?

Não consigo fazer a partir disso uma função que gera true se for primo e false se não for.

Link to comment
Share on other sites

Em 22/06/2010 às 14:03, Convidado disse:

Mas o fato é que preciso escrever uma função em Haskell para determinar se um número inteiro positivo é ou não primo a partir desse algoritmo de erastostenes. E não consigo! vc tem alguma idéia de como posso fazer isso a partir desse código que te mandei?

Não consigo fazer a partir disso uma função que gera true se for primo e false se não for.

Podes usar a função primos em que passas o 'x' com o valor do primo que queres saber se é primo ou não. Depois verificas se o último número na lista gerada é esse 'x', se for é primo, senão não é primo.

"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Link to comment
Share on other sites

Guest 1505338889

Acho que conseguii!!!

Olhem para mim por favor se é isso:

erastotenes [] = []
erastotenes (x:xs) = 
x : erastotenes [y | y <- xs, rem y x /=0]

primos = erastotenes [2..]

ehMembroDaLista (x:xs) n
| x < n = ehMembroDaLista xs n
| x == n = True
| otherwise = False

ehPrimo n = ehMembroDaLista primos n
Link to comment
Share on other sites

Guest 1505338889

O Rui tinha comentando que: "Implementaste uma função que faz a inserção ordenada numa lista, mas não tens nenhuma função de ordenação."

Tentei fazer de outra maneira, será que alguém pode dar uma olhada pra ver se agora está certo?

-- Ordena uma lista de elementos do tipo Ord através do algoritmo de ordenação por inserção.
insere :: (Ord a) => a -> [a] -> [a]
insere x [] = [ x ]
insere x (y:ys)
  | x <= y = x:y:ys
  | otherwise = y : (insere x ys)

insertsort :: Ord a => [a] -> [a]
insertsort = foldr insere []

Agradeço desde já.

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.