Exercícios sobre Listas, Árvores, Grafos e Recursão Generativa
Fundamentos de Algoritmos – INF05008
Esta lista não é para entrega, mas sim para aferir o preparo individual do aluno para a
última prova; dúvidas poderão ser discutidas na aula do dia 7/12
ATENÇÃO: DEFINIÇÕES DE DADOS, CONTRATOS E EXEMPLOS FAZEM PARTE DAS
SOLUÇÕES
1. Desenvolva um programa que ordena, em ordem crescente, lista de mensagens (emails) pela data (dia
apenas) deste email. Considere que:
uma estrutura email é definida da seguinte forma:
(define-struct email (remetente dia texto))
um email é uma estrutura
(make-email remetente dia texto)
onde remetente e texto são strings e dia é um número.
Defina o(s) outro(s) tipo(s) de dado(s) antes de apresentar a função.
2. Seguindo o enunciado do exercício anterior, modifique o programa para que ordene os emails pelo remetente. (Dica: use string<?).
3. Ainda considerando a questão de ordenação dos emails, desenvolva uma função de alta ordem para
ordenar emails pela data que receba como argumento também a forma de ordenação (crescente ou decrescente, através de funções apropriadas).
4. Considere a função search que determina se um número ocorre ou não em uma lista de números. Como
pode ser observado, esta função tem que percorrer toda a lista para determinar isto.
;; search : number list-of-numbers -> boolean
(define (search n alon)
(cond
[(empty? alon) false]
[else (or (= (first alon) n) (search n (rest alon)))]))
Desenvolva uma função search-sorted que determina a mesma coisa, mas que se aproveita do fato
de que a lista está ordenada.
5. Simule manualmente as chamadas e confirme que (ancestral-olhos-azuis? empty) retorna
false. Faça o mesmo para (ancestral-olhos-azuis? Gustav) (não é necessário realizar todas as
chamadas; concentre-se nas principais). Obs.: para este e outros exemplos sobre árvores, consideraremos
a árvore usada no exemplo visto em aula.
6. Desenvolva a função conta-pessoas que consome uma árvore cujos nodos são membros de uma
família, e produz o número de pessas na família.
7. Desenvolva a função idade-média que consome uma árvore cujos nodos são membros de uma família,
e produz a idade média das pessoas na família.
8. Desenvolva a função cores-dos-olhos que consome uma árvore cujos nodos são membros de uma
família, e produz uma lista de todas as cores de olhos que ocorrem na família. Uma cor de olhos pode
ocorrer mais de uma vez na lista.
Dica: use a operação append que consome 2 listas e produz a concatenação delas.
9. Desenvolva a função contem-ab? que consome um número n e uma árvore binária cujos nodos são
números. Se a árvore contiver o número em algum dos nodos, retornar true, senão false.
1
10. Desenvolva a função pesquisar-ab que consome um número e uma árvore binária cujos nodos contém
estruturas que armazenam dados sobre um determinado contribuinte. As informações relevantes sobre
contribuintes são: seu CPF e seu nome; além disto os nodos precisam apontar para os nodos anterior
(esquerda) e posterior (direita). Esta função produz o nome do contribuinte caso o número exista na
árvore e false em caso contrário.
11. Desenvolva a função na-ordem que consome uma árvore binária referente a contribuintes e produz uma
lista de todos os CPF’s destes contribuintes. Tal lista deve conter os números na ordem em que aparecem
na árvore da esquerda para a direita.
Dica: use a operação append que concatena 2 ou mais listas.
12. Desenvolva a função pesquisar-abp que consome um número n e uma ABP (árvore binária de pesquisa).
Se a árvore contiver um nodo cuja estrutura tem o CPF igual a n, a função retorna o nome do contribuinte.
Caso contrario, produz false. Compare com o resultado produzido pela função pesquisar-ab (ver exercício nesta lista).
13. Desenvolva a função insere-nó. A função recebe uma ABP B, um número n e um símbolo s. A função
cria uma nova ABP igual a anterior mas com a adição do nó com valores n e s.
14. Desenvolva a função constrói-ABP a partir de uma lista-de-números. Use as listas exemplos apresentadas na página 204 do livro.
• Uma lista-de-números é:
– empty
– (cons (list id nome) lnum) onde id é um número, nome é um símbolo, e lnum é uma lista de
números
15. Uma página web é:
(a) empty, ou
(b) (cons s wp), onde s é um símbolo e wp é uma página web, ou
(c) (cons ewp wp), onde ewp e wp são páginas web
A partir dessa definição de dados, desenvolva a função troca. A função recebe dois símbolos, novo e
velho, e uma página web wp. A função produz uma página com a mesma estrutura de wp, mas com
todas as ocorrências de velho trocadas por novo.
16. Muitos usuários não gostam de navegar em páginas web que têm muitos sub-níveis até que se atinja a
informação necessária. Por isso, um web designer quer medir qual a profundidade (número de níveis)
de uma página. Se uma página contem apenas símbolos, então sua profundidade é zero. Uma página
que remete a uma sub-página tem a profundidade desta mais um. Se uma página remete a diversas
páginas, a profundidade dela é a máxima profundidade entre as páginas para as quais ela remete, mais
um. Desenvolva a função profundidade que consome uma página web e calcula sua profundidade.
17. Simule manualmente (descendente-olhos-azuis?
(descendente-olhos-azuis? Bettina).
Eva), bem como
18. Desenvolva a função quão-longe que determina quão longe, na árvore, está um dado parent de um
de seus descendentes de olhos azuis, caso haja algum. Se um dado parent tem olhos azuis, a distância é
zero. Em caso contrário, se pelo menos um de seus filhos tem olhos azuis, a distância é um, e assim por
diante. Se nenhum descendente tiver olhos azuis, então a função deve retornar false.
19. Desenvolver a função conta-descendentes que consome um nodo do tipo parent e conta o número
de seus descendentes, incluindo a si mesmo. Modifique o exercício e crie a função
conta-descendentes-exclusivo que realiza o mesmo porém exclui a si mesmo.
20. Desenvolver a função cor-dos-olhos que consome um parent e produz uma lista com todas as cores
de olhos em sua árvore genealógica (seus descendentes). Uma cor pode ocorrer mais de uma vez na lista.
21. Desenvolver a função tamanho-página que consome uma página web (como definida) e produz o
número de símbolos (palavras que ela contem).
2
22. Desenvolva a função ocorre-símbolo? que consome um símbolo e uma página web e determina se
tal símbolo ocorre em algum lugar da página, incluindo suas sub-páginas.
23. Desenvolva a função encontra-símbolo. Ela produz false se um dado símbolo não ocorre em uma
dada página ou em alguma de suas sub-páginas. Se o símbolo ocorre pelo menos uma vez, a função
deve produzir uma lista dos cabeçalhos das páginas percorridas. Considere que uma estrutura webpage contem um cabeçalho (um símbolo) e um corpo (uma lista de símbolos).
Dica: defina uma função auxiliar similar mas que produza apenas true quando uma web-page contem o
símbolo desejado.
24. Explique porque cada uma das expressões abaixo é sintaticamente incorreta:
1. (local ((define x 10)
(y (+ x x)))
y)
2. (local ((define (f x) (+ (* x x) (* 3 x) 15))
(define x 100)
(define f@100 (f x)))
f@100 x)
3. (local ((define (f x) (+ (* x x) (* 3 x) 14))
(define x 100)
(define f (f x)))
f)
25. Determine quais das seguinte expressões são legais e quais não são, e explique porque.
1. (define A-CONSTANT
(not
(local ((define (odd an)
(cond
[(= an 0) false]
[else (even (- an 1))]))
(define (even an)
(cond
[(= an 0) true]
[else (odd (- an 1))])))
(even a-nat-num))))
2. (+ (local ((define (f x) (+ (* x x) (* 3 x) 15))
(define x 100)
(define f@100 (f x)))
f@100)
1000)
3. (local ((define CONST 100)
(define f x (+ x CONST)))
(define (g x y z) (f (+ x (* y z)))))
26. Avalie manualmente as seguintes expressões:
1. (local ((define (x y) (* 3 y)))
(* (x 2) 5))
2. (local ((define (f c) (+ (* 9/5 c) 32)))
(- (f 0) (f 10)))
3
3. (local ((define (odd? n)
(cond
[(zero? n) false]
[else (even? (sub1 n))]))
(define (even? n)
(cond
[(zero? n) true]
[else (odd? (sub1 n))])))
(even? 1))
4. (+ (local ((define (f x) (g (+ x 1) 22))
(define (g x y) (+ x y)))
(f 10))
555)
5. (define (h n)
(cond
[(= n 0) empty]
[else (local ((define r (* n n)))
(cons r (h (- n 1))))]))
(h 2)
27. Use uma expressão local para organizar a função para encontrar descendentes de olhos azuis vista
anteriormente.
28. Considere a seguinte definição de função:
;; maxi : non-empty-lon -> number
;; to determine the largest number on alon
(define (maxi alon)
(cond
[(empty? (rest alon)) (first alon)]
[else (cond
[(> (first alon) (maxi (rest alon))) (first alon)]
[else (maxi (rest alon))])]))
Notar que ambas as cláusulas da expressão cond computam (maxi (rest an-inv)). Logo, esta
é uma candidata natural a uma expressão local. Reformule a função dada usando a expressão local
e teste ambas as versões com (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20). Qual o efeito? Explique.
29. Considere a seguinte definição de função e considere inventário conforme definido anteriormente neste
curso:
;; extract1 : inventário -> inventário
;; cria um inventário a partir de an-inv para
;; todos os itens que custam menos de $1
(define (extract1 an-inv)
(cond
[(empty? an-inv) empty]
[else (cond
[(<= (ir-price (first an-inv)) 1.00)
(cons (first an-inv) (extract1 (rest an-inv)))]
[else (extract1 (rest an-inv))])]))
Já que ambas as cláusulas da expressão cond extraem o primeiro ítem de um inventário, reformule o
exemplo usando a expressão local.
30. Descreva as seguintes classes de funções:
4
1.
2.
3.
4.
5.
(number -> boolean)
(boolean symbol -> boolean)
(number number number -> number)
(number -> (listof number))
((listof number) -> boolean)
31. Escreva o contrato da função filter1 conforme definida abaixo:
(define (filter1 rel-op alon t)
(cond
[(empty? alon) empty]
[else (cond
[(rel-op (first alon) t)
(cons (first alon)
(filter1 rel-op (rest alon) t))]
[else
(filter1 rel-op (rest alon) t)])]))
32. Abstraia as 2 funções seguintes em uma única função chamada extremo:
;; mini : nelon -> number
;; to determine the smallest number
;; on alon
(define (mini alon)
(cond
[(empty? (rest alon)) (first alon)]
[else (cond
[(< (first alon)
(mini (rest alon)))
(first alon)]
[else
(mini (rest alon))])]))
;; maxi : nelon -> number
;; to determine the largest number
;; on alon
(define (maxi alon)
(cond
[(empty? (rest alon)) (first alon)]
[else (cond
[(> (first alon)
(maxi (rest alon)))
(first alon)]
[else
(maxi (rest alon))])]))
Ambas consomem listas não vazias (nelon) e produzem um único número. A função da esquerda produz
o menor número da lista, enquanto que a da direita produz o maior.
Posteriormente, defina as funções mini1 e maxi1 em termos da função extremo. Teste cada uma das
versões com as seguintes listas:
(a) (list 3 7 6 2 9 8)
(b) (list 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)
(c) (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
33. Formule contratos para as seguintes funções:
(a) sort: consome uma lista de números e uma função que consome 2 números (da lista dada) e produz
um booleano; sort produz então uma lista de números
(b) map que produz uma lista de números e consome uma função de número para número e uma lista
de números
(c) project que produz uma lista de símbolos e consome uma lista de lista de símbolos e uma função
de lista de símbolos para símbolo
34. Use filter1 para desenvolver uma função que consome uma lista de símbolos e extrai todos os símbolos que não são iguais a ’car. Escreva o contrato de filter1.
35. Desenvolva a função mesmo-resultado?, a qual determina se duas funções (ambas consomem três
números e produzem um número), produzem o mesmo resultado para 1.2, 3, −5.7.
36. Modifique as definições de ordena e insere para que elas passem a ser funções de alta ordem onde o
critério de ordenação é definido como parâmetro. Denomine-as ordena-criterio e insere-criterio.
5
37. Simulte todos os passos até a solução usando a função quick-sort quando aplicada a
(list 11 9 2 18 12 14 4 1).
38. O que acontece se usarmos quick-sort com a lista (list 11 8 7 8 14 7))? Modifique quick-sort
para que nos devolva uma lista com o mesmo tamanho da lista passada como argumento.
39. Desenvolva e teste as funções mdc-e e mdc-g com os números 101135853 e 45014640. Use (time
(mdc-e ...)) e (time (mdc-g ...)) e compare os tempos de execução. Explique a razão da
diferença.
40. A função quick-sort reduz o tamanho do problema em muitos casos, mas ela é muito lenta quando
se trata de problemas pequenos. Desta forma, em geral se usa quick-sort para reduzir o tamanho
do problema, aliada à função ordena (vista na aula sobre o cap. 12) para tratar os sub-problemas.
Desenvolva uma versão da quick-sort que usa a função ordena se o tamanho da lista está abaixo de
um limiar (dado como argumento).
41. Teste as funções quick-sort e ordena com o auxílio de (time (...)), para diversos tamanhos de
listas e constate que ordena é mais rápida para listas de até um certo tamanho. Determine que tamanho
é este.
42. Desenvolva a função concatena-strings, que recebe uma lista não-vazia do tipo lista-de-strings
e retorna a concatenação de todas as strings da lista. Por exemplo:
(concatena-strings (cons "Fundamentos de Algoritmos "
(cons "é uma disciplina "
(cons "muito legal!" empty))))
===>
"Fundamentos de Algoritmos é uma disciplina muito legal!"
Use a função string-append :
ficas.
string string -> string para concatenar duas strings especí-
43. Um cozinheiro deve preparar uma receita. Antes de começar, ele precisa ter certeza de que possui todos os ingredientes necessários. Para ajudar esse cozinheiro, apresente a definição de dados do tipo
lista-de-ingredientes e crie um programa que, a partir da lista de ingredientes em estoque e da
lista de ingredientes da receita, retorne "OK" se todos os ingredientes estiverem disponíveis. Caso contrário, o programa deve informar quais ingredientes estão faltando.
44. Um ônibus percorre uma determinada linha, passando por diversas paradas. Apresente a definição de
dados para lista-de-paradas e crie um programa que indique se é possível utilizar este ônibus para
um deslocamento de uma parada inicial até uma parada final. Assuma que o percurso de volta é o
inverso do percurso de ida.
45. Dadas três listas l1, l2 e l3 do tipo lista-de-números, definido abaixo, crie um programa que diga
qual das três listas possui mais números dentro de um intervalo fechado entre dois números ini-int e
fim-int.
;;
;;
;;
;;
;;
Uma lista-de-números é ou
- empty, ou
- (cons n ldn), onde
n : number
ldn : lista-de-números
46. Desafio (exercício 12.4 do livro). Desenvolva a função permuta que, dada uma palavra (representada
como uma lista de símbolos), retorna uma lista de todas as suas possíveis permutações. Por exemplo:
6
(permuta (list ’o ’l ’a))
====> (list (list
(list
(list
(list
(list
(list
’o
’o
’l
’l
’a
’a
’l
’a
’o
’a
’a
’l
’a)
’l)
’a)
’o)
’l)
’o) )
Dica 1. É necessário o uso de funções auxiliares.
Dica 2. Para iniciar, pode-se usar a estratégia da função ordena: separar os itens da lista, passando-os para
uma auxiliar.
Dica 3. Cuidado com os tipos de retorno das funções: este exemplo ressalta a importância do contrato no
desenvolvimento de funções complexas.
47. Considere a seguinte definição de dados:
(define-struct nó (val esq dir))
Uma AB (árvore binária) é ou
- false, ou
- (make-nó val esq dir),
onde val é número, esq e dir são AB
Defina a função valores-AB que, dada uma árvore binária de entrada, retorna uma lista com os valores
de todos os nós da árvore (em qualquer ordem).
48. Escreva uma função acha-maior-AB que encontre o maior valor armazenado em uma árvore binária.
49. Apresente um programa converte-árvores, o qual, dada uma AB, converte esta estrutura em uma
ABP.
50. Além do insertion sort e do quick sort, vistos em aula, outro método de ordenação famoso é o merge
sort. Neste método, a lista de números a serem ordenados é dividida em pares de números (listas de
dois números consecutivos na lista original). Cada lista de pares é ordenada. Após isso, listas de pares
ordenados consecutivos são ordenados, formando listas ordenadas de 4 números. Em seguida, as listas
de 4 números ordenados são usadas para formar listas com oito números, e assim por diante.
Apresente um programa que implemente este método de ordenação. Assuma que o tamanho da lista de
entrada é sempre uma potência de 2 maior ou igual a 4.
51. Considere um conjunto de cidades de uma região. Cada cidade possui um conjunto de estradas que a
ligam a outras cidades da mesma região, sendo que todas as estradas possuem mão dupla.
Crie um programa que, dada uma lista de cidades e suas conexões, ache o menor caminho entre uma
cidade de origem e uma cidade de destino. O comprimento do caminho a ser considerado é o número
de estradas a serem percorridas entre cidades; i.e., o menor caminho possível entre duas cidades seria
uma estrada que ligue as duas diretamente. No entanto, não deve ser assumido que sempre existe uma
ligação direta entre todas as cidades.
52. Escreva a função move-bolas que, dada uma lista de bolas, move cada uma até que todas estejam fora
do limite da mesa (uma única mesa)
7