Lista de exercícios para a turma do básico.

[Imre Simon <is@ime.usp.br>]

Estes exercícios não precisam ser entregues, porém a sua resolução
deverá tornar a prova da semana que vem mais amena.

Bom trabalho,

Imre Simon


=====

Exercício D.1

Escreva uma função recursiva com protótipo 

        void mergesort(int a[], int l, int r);

que rearrange o vetor  a[l..r-1]  em ordem decrescente. 

O código da rotina de intercalação (merge) deve estar embutido na
função mergesort. Essa rotina de intercalação deve começar com
a[l..m-1]  e  a[m..r-1]  decrescentes e terminar com  a[l..r-1]
decrescente.  

Sua função pode usar um vetor auxiliar (alocado
dinâmicamente). Inspire-se no programa 8.2 do Sedgewick.



Exercício X.1

Refaça o exercício anterior, mas trabalhe com listas ligadas em vez de
vetores. Você consegue evitar o uso de vetores adicionais agora?


Exercício Y.1

Um cadeado eletrônico de bicicleta é formado por N chaves
que podem estar abertas ou fechadas (0/1). Faça um
procedimento recursivo que imprime todas as possibilidades a
serem testadas para se abrir o cadeado.

Simule a execução do seu procedimento para N=3.



Exercício Y.2

Seja v[1..n] um vetor de inteiros distintos em ordem
crescente.

Por exemplo,

i        1    2   3   4   5   6   7   8   9  10
v[i]   -12  -06  00  03  05  06  07  09  10  12

Escreva um programa que descobre, em tempo proporcional a 
log n, o maior valor i tal que v[i]=i, caso haja algum i
nestas condições. Explique o método usado e justifique
sucintamente porque ele funciona e qual a sua comlexidade.




Exercício Y.3

Dada uma lista ligada de inteiros escreva um algoritmo que separa os
elementos pares dos ímpares, i.e. rearranja as células da lista em
duas outras listas ligadas de modo que todos os elementos pares
estejam na primeira lista e todos os ímpares na segunda.

Faça o algoritmo mais eficiente possível. Qual a
complexidade do seu algoritmo? Justifique.




Exercício Y.4

Escreva um programa que inverte as letras de cada palavra de
um texto dado, preservando a ordem das palavras. Por
exemplo, dado o texto

      tancredo neves ganhou mas morreu
      
a saída do seu programa deve ser:      

      odercnat seven uohnag sam uerrom

Escreva um programa que usa pilhas e outro que não as usa.

Resolva este problema com vetores e também com listas ligadas.




Exercício Y.5

Uma companhia que vende software precisa acomodar n
arquivos, de tamanhos t=(t[1],t[2],...,t[n]), em disquetes
de capacidade C, sendo que t[i]<=C para cada i.

Faça um programa que aloca os arquivos no menor número
possível de disquetes.

Exemplo:    C=360

arquivo     1   2   3   4    5    6    7    8    9
tamanho    40  80  80  80  100  100  100  240  240
disquete    1   1   2   2    2    2    3    1    3 

No caso, precisa de 3 disquetes para acomodar os 9 arquivos.



Exercício Y.6

Uma permutação é tão mais econômica quanto menos
comparações o Heapsort do livro executar para ordená-la.
Encontre a permutação mais econômica que conseguir para N=32. Quantas
comparações são feitas? Explique como encontrou a permutação.



Exercícios do livro texto:


5.17, página 207

5.40, página 214

5.41, página 215

5.55, página 216

3.27, página 96

3.33, página 96

3.35, página 105

3.47, página 108

3.49, página 108



Bom trabalho,

Imre Simon