- Escreva uma função recursiva com protótipo
int maximo (int v[], int ini, int fim);
que devolve o maior valor do vetor entre as posições ini e fim.
Use uma estratégia como a do mergesort (divisão e conquista):
divida o vetor ao meio, chame a função recursivamente para cada
uma das metades, depois "junte" as respostas.
- Escreva uma função recursiva busca_ternária com o seguinte
protótipo
int busca_ternaria (int v, int ini, int fim, int x);
Sua função deve devolver 1 se x aparece no vetor, 0 caso contrário.
Inspire-se na busca binária. Na busca ternária, você
deve dividir o vetor em três (em vez de em dois), comparar o x com
os dois elementos separadores dessas três partes e, ou encontra x,
ou decide em qual das partes ele pode estar, procurando-o recursivamente nesta parte.
- Notação prefixa é definida de forma semelhante a notação posfixa.
Na notação prefixa, os operadores aparecem antes de seus operandos.
Assim, por exemplo, a expressão
A + B * C - ( D - E / F + G ) / H + I
em notação prefixa ficaria:
- + A * B C + / + - D / E F G H I
Escreva uma função recursiva que calcula o valor de uma expressão prefixa.
Suponha que exista uma função
int valor (char ch);
que, dada uma letra, devolve o valor da variável correspondente àquela letra.
- Simule os algoritmos mergesort, quicksort e heapsort
com o seguinte vetor de entrada:
15 27 3 18 7 11 22 19 9 10 1 5 8 14
- Encontre um vetor com 10 elementos que faz o mergesort fazer o maior número possível de trocas.
- Simule a execução do algoritmo quicksort no vetor abaixo:
17 10 7 23 15 3 1 20 8 4
Indique na sua simulação as comparações que estão
sendo feitas e o resultado de cada chamada do separa.
Quantas chamadas do separa foram feitas neste caso?
Quantas auto-chamadas o quicksort (recursivo) para o vetor acima geraria?
- Escreva uma versão recursiva do quicksort que consuma espaço no máximo logarítmico da pilha de execução.
Inspire-se na segunda versão interativa do quicksort que mostramos na aula!
- Escreva, sem olhar em nenhuma anotação nem nas notas de aula,
a sua versão da função intercala.
- Escreva, sem olhar em nenhuma anotação nem nas notas de aula,
a sua versão da função separa.
- Escreva, sem olhar em nenhuma anotação nem nas notas de aula,
a sua versão da função peneira e constroiHeap.
- Escreva uma função que recebe um vetor com n letras
As e Bs e, por meio de trocas, move todos os As para
o início do vetor. Sua função deve consumir tempo linear
(proporcional ao tamanho do vetor, ou seja, a n).
- Dê uma lista não ordenada de 10 elementos em que o quicksort
se dá o pior possível. Dê uma lista de 10 elementos onde o
quicksort se dá o melhor possível.
- Escreva uma função com protótipo
void alteraChave (int x, int i, int n, intv[]);
que recebe um heap em v[1..n] e altera a chave do elemento i para x,
rearranjando v para que continue um heap.
- Escreva uma função com protótipo
void removeHeap (int i, int *n, intv[]);
que recebe um heap em v[1..*n] e remove o elemento v[i] do heap,
rearranjando v para que continue um heap.