MAC122 - Lista 4 - Recursão e ordenação

1. Escreva uma função recursiva com cabeçalho

      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.
2. Escreva uma função recursiva com cabeçalho

     int maxmin (int v[], int n, int *max, int *min);
   

   que devolve o maior valor do vetor em *max e o menor em *min.
3. Escreva uma função recursiva busca_ternária com o seguinte cabeçalho:

      int busca_ternaria (int v, int ini, int fim, int x);
   

   Sua função deve devolver 1 se x aparece no vetor, 0 em 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. Procura recursivamente nesta parte.
4. Simule o algoritmo mergesort com o seguinte vetor de entrada:

      15  27  3  18  7  11  22  19  9  10  1  5  8  14
   

5. Encontre um vetor com 10 elementos que faz o mergesort fazer o maior número possível de trocas.
6. 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.
7. Simule a execução do 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 particiona. Quantas chamadas do particiona foram feitas neste caso? Quantas auto-chamadas o quicksort (recursivo) para o vetor acima geraria?
8. Escreva, sem olhar em nenhuma anotação nem nas notas de aula, a sua versão da função particiona (ou separa).
9. 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).
10. 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.