Resoluções de atividades

1)A sequência de Pell começa com 0 e 1, e cada número de Pell é a soma
de duas vezes o número de Pell anterior e o número de Pell antes do anterior.
Os primeiros termos dessa sequência são: 0,1,2,5,12,29,70,...
Defina a função pell :: Int -> (Int, Int) tal que  pell n devolve a seguinte par ( P(n-1), P(n)). A
função pell está difinida para todo n >= 1.

2)Defina a função tribonacci :: Int -> (Int,Int,Int) tal que tribonacci n devolve a seguinte tripla ( f(n-2), f(n-1), f(n) ). A função tribonacci está definida para todo n >= 2.

3)[Recursão]binário: Escreva a definição da função binario :: Int -> [Int] que calcula a representação de um inteiro positivo em algarismos binários (0 ou 1). A lista resultado deve estar ordenada do algarismo menos significativo para o mais significativo.
Exemplo:
binario 6 = [0, 1, 1]

4)[Recursao, Listas]subidas: Escrever uma definição da função subidas :: [Float] -> Int que calcula quantas vezes a temperatura subiu (isto é, a temperatura do dia anterior foi estritamente inferior à do dia atual). No caso de a lista de temperaturas ter menos de dois valores, o resultado deverá ser zero. Exemplos:
subidas [19,20,21,22] = 3
subidas [19,20,20,22] = 2
subidas [20,19,18,19] = 1

5)[Recursao]fracaoContinua: Defina uma função fracaoContinua :: Fracao -> [Int] tal que fracaoContinua f devolve uma lista de inteiros representando os quocientes parciais da fração f.

Main> fracaoContinua (F 10 7)
[1,2,3]
*Main> fracaoContinua (F 137 33)
[4,6,1,1,2]
*Main> fracaoContinua (F 81 35)
[2,3,5,2]


6)[Recursão]caminho:  Escreva uma função caminho :: [(Int,Int)] -> [Int] -> Bool tal que caminho g xs é True se xs é uma lista de vértices que representa um caminho no grafo (isto é, se cada dois vérties consecutivos correspondem a uma aresta) e False caso contrário. Exemplos:
caminho [(1, 2),(2, 1),(2, 3)] [] = True
caminho [(1, 2),(2, 1),(2, 3)] [1] = True
caminho [(1, 2),(2, 1),(2, 3)] [1, 2, 1, 2, 3] = True
caminho [(1, 2),(2, 1),(2, 3)] [1, 2, 1, 3] = False

7)[Tipo Arvore]kMaior:  Considere a seguinte definição de árvore binária:

data Arv a = Vazia | No a ( Arv a ) ( Arv a ) deriving (Eq , Show)

Escreva a função kMaior :: Ord a => Int -> Arv a -> a tal que (kMaior k arv ) devolve o k-ésimo maior numa árvore de pesquisa ordenada arv com tamanho pelo menos k tal que os valores menores ou iguais ao elemento raiz estão na subárvore da esquerda e os valores maiores estão na subárvore da direita.
Por exemplo,
kMaior 3 (No 10 (No 4 (No 2 Vazia Vazia) Vazia) (No 20 (No 15 Vazia Vazia) (No 40 Vazia Vazia))) == 15
kMaior 6  (No 1 Vazia (No 4 (No 2 Vazia Vazia) (No 7 (No 5 Vazia Vazia) (No 9 Vazia Vazia)))) == 1
Entrada:  k = 3

            10

          /    \

        4      20

        /      /  \

      2    15    40
Saída : 15

8)[Tipo Arvore]isHeap: Considere a seguinte definição de árvore biária:

data Arvore a = Vazia | No a (Arvore a) (Arvore a) deriving (Show)
Para uma árvore binária precisa cumprir uma condição para ser um heap:
O valor de cada nó deve ser maior ou igual ao seu nó filho (considerando o heap máximo).

Defina uma função isHeap :: Arvore a -> Bool tal que (isHeap arv) verifica se a árvore binária satisfaz a propriedade heap ou não.

Entrada:

      97

      /  \

    46  37

    / \  / \

  12  3 7 31

Saída:True
Entrada:

      97

      /  \

    46  37

    / \  / \

  12  3 7 38

Saída:False
Exemplo:
isHeap ( No 25 (No 12 Vazia (No 6 Vazia Vazia)) (No 15 Vazia (No 4 Vazia Vazia)) ) == True

Dica: Use a função getValue :: Arvore a -> a que devolve o valor do nó.

GetValue (No x esq dir) = x

9) [Tipo Arvore]minMax:
Considere a seguinte definição de árvore binária:
data Arv a = Vazia | No a ( Arv a ) ( Arv a ) deriving (Eq , Show)
Escreva a função minMax :: Ord a => Arv a -> (a,a) tal que (minMax arv) devolve o menor e o maior elemento numa árvore de pesquisa ordenada arv não vazia tal que os valores menores ou iguais ao elemento raiz estão na subárvore da esquerda e os valores maiores estão na subárvore da direita.
minMax (No 4 (No 1 Vazia (No 3 Vazia Vazia)) (No 7 Vazia Vazia)) == (1,7)
minMax (No 4 (No 2 (No 1 Vazia Vazia) Vazia) (No 17 (No 10 (No 9 (No 5 Vazia Vazia) Vazia) Vazia) Vazia)) == (1,17)

PS: Não vale fazer o pecurso em ordem na árvore