Antes de fazer estes exercícios, leia com atenção:

                                  - Textos sobre Comparação e Alinhamento de Seqüências e Backtracking

                                  - Os slides das aulas correspondentes.

1. Faça um programa para encontrar um alinhamento ótimo de duas cadeias de caracteres dadas.
O alinhamento pode ser local ou semi-global, sendo este um parâmetro de entrada.  

• Tipo de alinhamento desejado - Escolha entre Local  (1) e Semi-global (2)
• Cadeia s
• Cadeia t

PROCESSAMENTO

1. Alinhamento Local:

O alinhamento local consiste em construir a tabela M com algumas modificações:

      1.   Inicialização da primeira linha e da primeira coluna com zeros.

      2.   Uma quarta alternativa com valor 0 (zero) para cada computação de um entrada M[i, j] da tabela, i, j > 0,  e

      3.   Escolha da posição final do alinhamento com sendo a posição (ou uma das posições) de

            maior valor dentre todas as posições da tabela M.

           EX:    s: ---------------XXXXXXACCGTAGAGT--GAGAXXXXXXXXXX----

                       t: YYYYYYYYYYYYYYYYYYYYYYYACGGT-GAGTCAGAGAYYYYYYYYYYYYYYY

O alinhamento reportado deve usar como referência a posição final do trecho em vermelho,

que representa a posição de maior valor na tabela M, ou seja, o início e o final do alinhamento

serão definidos a partir daquela posição.

2. Alinhamento Semi-global:

O alinhamento semi-global vai rodar duas variações da construção da tabela M. Aquela que der um
escore maior será escolhida.   As duas tabelas serão construídas da seguinte forma.

   1. IGNORA INSERÇÕES NO INÍCIO E REMOÇÕES NO FIM DE s.
      s: ---------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
      t: YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY-------------------------------------------

      >  Inicializa a primeira linha com zeros.  (Ou seja, não cobra por inserções no início de s.)
      > Procura o máximo na  última coluna.    (Ou seja, ignora as remoções no final de s.)


  2.  IGNORA REMOÇÕES NO INÍCIO E INSERÇÕES NO FIM DE s
      s:  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---------------------------------------------------
      t:  -------------------------------------------YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY

      > Inicializa a primeira coluna  com zeros. (Ou seja, não cobra por remoções no início de s.)
      >  Procura o máximo na última linha.         (Ou seja, ignora as inserções no final de s.)

 

2. O problema das 8 Rainhas consiste em organizar 8 rainhas em um tabuleiro de Xadrez, de modo que nenhuma possa atacar a outra (ou seja, duas rainhas não podem estar na mesma linha, coluna ou diagonal).

Este problema consiste em generalizar o problema para N rainhas em um tabuleiro N x N (onde N < 12). Como podem haver várias soluções, é pedido que seja impressa apenas a K-ésima solução, se esta existir.

Sugestão: Para representar o tabuleiro eficientemente, aconselha-se o uso de um único array unidimensional, em que cada posição indica, para uma dada linha, em que coluna a rainha está.

Q . . .  [0]
. Q . .  [1]
. . Q .  [2]
. . . Q  [3]

. . Q .  [2]
. . Q .  [2]
. . Q .  [2]
Q . . .  [0]

. . . Q  [3]
. . Q .  [2]
. . . Q  [3]
. . Q .  [2]

. . Q .  [2]
. . Q .  [2]
. . Q .  [2]
. . Q .  [2]

. . . Q  [3]
. . Q .  [2]
. Q . .  [1]
Q . . .  [0]

A busca pela solução deve ser feita de cima para baixo, da esquerda para a direita, utilizando backtracking. Isto é, quando uma Rainha não puder ser colocada em nenhuma posição da linha (pois todas elas são atacadas por outra rainha) ou a solução desejada não foi encontrada, deve ser feito um retrocesso, para encontrar uma nova posição para a Rainha da linha anterior.

Dados N e K, faça um programa que encontre a K-ésima solução para um tabuleiro de tamanho N x N.