Atribuições para compilar algoritmos

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, temB_dir);

total = total_dir + total_esq;

se sobrouA_esq AND temB_dir então total++;

temB = temB_esq;

sobrouA = sobrouA_dir;

retorne

Solução Simples (vale 1) (um automato muito simples reconhece as cadeias...)

- total = 0

- Enquanto não chegar ao final do array {

- Continuar percorrendo o array da esquerda para direita até o final ou até encontrar um A;

- Se não encontrou A retorne total;

- Tendo encontrado um A, continuar percorrendo o array até o final ou até encontrar um B;

- Se não encontrou B retorne total senão total = total + 1

}

outra solução simples...

Para i = 1 até n faça

se Array[ i ] == A A_inicial = TRUE

senão se Array[ i ] == B então

se A_inicial então {

A_inicial = FALSE;

total++

}

}

1) Problema das cores da bandeira da França.

Seja um array com n elementos. Cada elemento possui uma tonalidade de uma das seguintes cores: branco, azul ou vermelho. Exemplo: VVBAABABVVVBVBVAABBBAABBBV .

Escreva um algoritmo para "transformar" o array deixando todos os As à esquerda, os Bs no meio e os Vs à direita.

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 fazer o "merge das duas bandeiras" deixando todos os As do lado esquerdo, os Bs no meio e os Vs à direita. Se vc souber onde termina o A o B e o V de cada lado fica muito fácil fazer o tal merge com poucas trocas (como pode acontecer de não ter uma ou duas das três cores, o que devemos saber é em que posição entraria um novo elemento de uma das cores).