provaPAA

3) Resolva a seguinte relação de recorrência (vale 1)

x(n) = x(n-1) + n p/ n>0 e x(0) = 1

= x(n-2) + (n-1) + n

= x(n-3) + (n-2) + (n-1) + n

= x(n-4) + (n-3) + (n-2) + (n-1) + n

.

.

.

= x(0) + 1 + 2 + 3 + . . . + (n-1) + n

= 1 + Somatório( i, i=1 até n) = 1 + (n/2).(n+1)

}

2) Escreva um algoritmo para identificar quantas strings disjuntas começando com A e terminando com B existem em um array unidimensional ( de 1 a n) com n caracteres.

Divisão e Conquista (vale 2)

- A idéia é ir dividindo o array em duas partes recursivamente e resolvendo o problema (recursivamente) para essas partes menores, até que o tamanho do problema (tamanho da parte do array a ser processada) chegue a 1.

- Após o retorno do processamento de duas metades o programa deve somar a quantidade de strings encontrada na parte esquerda com a quantidade encontrada na parte direita. Deve ainda acrescentar mais uma unidade a essa soma caso o retorno da parte esquerda informe que sobrou um A à direita da última string contabilizada nessa parte e o retorno da parte direita informe que tem um B antes da primeira string contabilizada nesse lado.

- Assim, o procedimento recursivo deve retornar três resultados: total de strings encontradas; se sobrou ou não pelo menos um A à direita da última (pode ser nenhuma) string contabilizada; se tem ou não pelo menos um B antes da primeira (pode ser nenhuma) string contabilizada.

StringsAB( Array, inic, fim, total, sobrouA, temB)

total = 0;

sobrouA = FALSE;

temB = FALSE;

se inic == fim {

se Array[inic] == A sobrouA = TRUE

senão se Array[inic] == B temB = TRUE;

retorne

}

meio = divisãointeira(inic, fim); /*Calcula o meio do subarray */

StringsAB( Array, inic, meio, total_esq, sobrouA_esq, temB_esq);

StringsAB( Array, meio+1, fim, total_dir, sobrouA_dir,