Primeira Lista de Exercícios

Introdução

Clone ou baixe o projeto da lista, importe ele na IDE Scala (IntelliJ IDEA), e implemente as funções correspondentes a cada questão do exercício. Depois envie apenas o arquivo lista1.scala com os fontes da sua implementação até 03/09, usando esse link.

Questão 1 - Triângulo de Pascal

O triângulo de Pascal é uma representação gráfica dos coeficientes dos binômios (x+y)^n. Cada linha do triângulo lista os coeficientes do seu respectivo binônio (contado a partir de 0).

Os números nos lados do triângulo são sempre 1, e cada número do interior do triângulo é a soma dos dois números acima dele. Implemente uma função em Scala que calcula coeficientes do triângulo de Pascal, dada sua posição no triângulo, contada a partir de 0:

def pascal(col: Int, lin: Int): Int = ???

Questão 2 - Parênteses Balanceados

Escreva uma função que verifica se os parênteses presentes em uma lista de caracteres estão balanceados. Note que não basta contar o número de ( e ), pois listas como List(')','(') e List('(',')',')','(') não são balanceadas.

def balanceado(l: List[Char]): Boolean = ???

Para facilitar o teste use a função toList de Scala, que converte uma string em uma lista de caracteres:

> balanceado("so (um (teste) (da funcao) ) ".toList)
res0: Boolean = true

Use recursão final na sua resposta.

Questão 3 - Quicksort

A ideia do algoritmo de ordenação quicksort é bem simples: escolhemos um elemento pivô de uma lista (o primeiro elemento, por exemplo), e particionamos a lista usando esse pivô em duas listas. A primeira lista tem todos os elementos menores ou iguais ao pivô, e a segunda lista todos os elementos maiores que o pivô. Então basta ordenar essas duas listas e concatenar o resultado.

Escreva a função particao que particiona uma lista dado um elemento pivô:

def particao(l: List[Int], pivo: Int): (List[Int], List[Int]) = ???

Escreva a função quicksort para ordenar uma lista, usando a função de partição que você escreveu:

def quicksort(l: List[Int]): List[Int] = ???

Questão 4 - CR acumulado

Podemos representar as notas de um aluno da UFRJ em dado semestre como uma lista de pares (nota,creditos):

> val sem1 = List((9.5,3),(7.3,4),(5.0,3),(4.0,4))
sem1: List[(Double, Int)] = List((9.5,3), (7.3,4), (5.0,3), (4.0,4))

O coeficiente de rendimento (CR) de um aluno em determinado semestre é a média ponderada de suas notas, com o peso de cada uma sendo o número de créditos da matéria.

Escreva a função crSemestre que recebe as notas do aluno no semestre e retorna seu CR para aquele semestre e o número de créditos que o aluno cursou:

def crSemestre(notas: List[(Double, Int)]): (Double, Int) = ???

As notas do aluno durante o curso podem ser representadas como uma lista de listas de notas para cada semestre. O CR acumulado de um aluno em determinado momento do curso é uma média ponderada dos CRs de cada semestre, com o peso sendo o número de créditos cursado naquele semestre.

Escreva a função crsAcumulados que recebe a lista de listas de notas para cada semestre e retorna uma lista com o CR acumulado para o aluno após cada semestre (o CR acumulado após o primero semestre é o CR do primeiro semestre), assim como o total de créditos cursados até aquele momento.

def crsAcumulados(semestres: List[List[(Double, Int)]]): (List[Double], Int) = ???

Questão 5 - Conjuntos usando funções de primeira classe

Uma representação para conjuntos é pela sua função característica, uma função que diz se um elemento pertence ao conjunto ou não. Em Scala, um conjunto de elementos de um tipo T pode ser então dado pelo tipo de funções de T para booleanos:

type Conjunto[T] = T => Boolean

Por exemplo, o conjunto dos inteiros pares pode ser dado por (x: Int) => x % 2 == 0. Dada essa definição para conjuntos, a definição de uma função que verifica se um conjunto contém ou não um elemento é trivial:

def contem[T](conj: Conjunto[T], elem: T) = conj(elem)

a) Defina uma função unitario que cria um conjunto unitário:

def unitario[T](elem: T): Conjunto[T] = ???

b) Defina as funções uniao, intesercao e diferenca, que fazem a união, interseção e diferença de dois conjuntos:

def uniao[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = ??? 	
def intersecao[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = ??? 	
def diferenca[T](c1: Conjunto[T], c2: Conjunto[T]): Conjunto[T] = ??? 

c) Defina a função filtro que retorna um conjunto contendo apenas os elementos do conjunto que passam pelo filtro:

def filtro[T](c: Conjunto[T], f: T => Boolean): Conjunto[T] = ???	

d) Defina a função map que transforma um conjunto de elementos de tipo T em um conjunto de elementos de tipo U, dada uma função de mapeamento U => T:

def map[T, U](c: Conjunto[T], f: U => T): Conjunto[U] = ???	

e) Por que a função de mapeamento para conjuntos tem os tipos trocados em relação à sua equivalente no map de listas? Responda em um comentário acima de sua implementação de map.

Questão 6 - Conjuntos como um tipo algébrico

Uma outra representação para conjuntos é como uma árvore binária de busca, que em Scala pode ser dada pelo tipo algébrico a seguir (para simplificar o problema, vamos tratar apenas de conjuntos de números inteiros):

trait ConjInt {
  def contem(x: Int): Boolean = ???
  def insere(x: Int): ConjInt = ???
  def uniao(outro: ConjInt): ConjInt = ???

  def filter(p: Int => Boolean): ConjInt = ???
  def map(f: Int => Int): ConjInt = ???
  def flatMap(f: Int => ConjInt): ConjInt = ???
}
case class ConjVazio() extends ConjInt
case class ConjCons(elem: Int, esq: ConjInt, dir: ConjInt) extends ConjInt

Implemente os métodos que estão definidos no tipo ConjInt. Dica: a maneira mais fácil de filtrar um conjunto é ir construindo um novo conjunto adicionando os elementos que passam pelo predicado um a um.

Com as funções filter, map e flatMap é possível usar a notação for com geradores do tipo ConjInt. Implemente a função intersecao(c1: ConjInt, c2: ConjInt): ConjInt usando a notação for para filtrar o produto cartesiano dos dois conjuntos.

---

Última Atualização: 2017-11-28 17:18