Analise de DNA Alienigena - Relatorio Cientifico e Algoritmo de Mutacao

O DNA DNA Depois de analisar cuidadosamente o disco voador que caiu no meio do parque da Redenção os cientistas chegaram a algumas conclusões sobre os seres que o ocupavam e que fugiram em uma cápsula de resgate Os cientistas descobriram que o DNA dos alienígenas é feito com 3 bases em vez das 4 bases do DNA terrestre Ironicamente eles batizaram as 3 bases de D N e A Eles também descobriram que o DNA alienígena sofre mutações que o deterioram com o tempo duas bases diferentes que estão uma ao lado da outra podem se fundir produzindo a terceira base e criando uma cadeia de DNA um pouco menor Isto acontece de uma forma muito organizada Em uma cadeia de DNA a fusão de bases acontece sempre na dupla de bases diferentes mais à esquerda A nova base criada com a fusão vai ser agregada ao final da cadeia de DNA Por exemplo a pequena cadeia DNA sofre uma deterioração em DN e acaba gerando AA Já uma cadeia maior como DNANDANDANDANADNDDDAN acaba virando simplesmente N Os cientistas agora perguntam dada uma cadeia de DNA qual o tamanho e qual cadeia podem ser obtidos depois de todas as mutações possíveis Você deve escrever um algoritmo capaz de ler as cadeias que os cientistas colocaram em vários arquivos de teste e depois informe o tamanho da menor cadeia que pode ser obtida em cada caso Ao final você deve apresentar um relatório descrevendo Qual o problema sendo resolvido Como o problema foi modelado Como é o processo de solução apresentando exemplos e algoritmos Os resultados dos casos de teste Conclusões