Oi pessoal...sou nova neste fórum e estou aprendendo sobre linguagem C...
tenho dúvidas em um exercício que preciso fazer....aqui vai o enunciado para que vocês possam entendê-lo:
Este exercício está baseado num problema que ocorre em Biologia Computacional.
Todos sabem sobre DNA. Um DNA pode ser resumido como um string nas letras ATCG. O DNA pode sofrer uma série de mutações, alguma das quais podem ser descritas como transformações algorítmicas no string. Uma delas é a reversão, e este problema consiste em simular uma série de reversões. Dada uma sequência de DNA inicial (descrita por uma sequência de N caracteres, com valor A, T, C ou G), uma reversão consiste em destacar um trecho contínuo desta sequência e recolocá-lo na ordem invertida, invertendo a sequência de caracteres deste trecho. A operação é descrita pelos índices da posição inicial e final do trecho (indexamento começando em 1).
O programa deve ler, da entrada padrão (stdin), uma sequência de DNA inicial e uma série de operações de inversão a serem realizadas em sequência e imprimir os 1000 primeiros caracteres (ou todos caso N < 1000) da sequência final, na saída padrão (stdout).
A entrada conterá 3 linhas. A primeira linha conterá um número, M, com a quantidade de operações a serem realizadas. A segunda linha conterá uma sequência de N caracteres representando o DNA inicial, cada caracter com valor A, T, C ou G. A terceira linha conterá M pares de números (ai e bi, respeitando 1 ≤ ai < bi ≤ N) representando o índice inicial e final de cada operação.
Restrições: 1 < N ≤ 10.000.000; 1 ≤ M ≤ 10.000.
Tempo de processamento: 10 seg.
Exemplo de entrada e saída:
3
ATATGCGA
3 6 4 8 3 4
ATACGATG
Veja o que aconteceu (em vermelho os trechos invertidos):
Sequência inicial: ATATGCGA
Operação 1: [3, 6]
Sequência 2: ATCGTAGA
Operação 2: [4, 8]
Sequência 3: ATCAGATG
Operação 3: [3, 4]
Sequência final: ATACGATG
A intenção deste exercício é testar a capacidade de adaptar estrutura de dados para aplicações específicas, otimizando o tempo de processamento, reduzindo a complexidade computacional temporal da solução.Uma solução intuitiva, realizando as operações de reversão em um vetor de modo direto, tem tempo de complexidade computacional O(M*N), N para cada operação. Para as restrições acima, isso corresponderia a uma ordem de 1012 operações, o que deve estourar o limite de 10 seg imposto.Para melhorar o tempo de processamento, o programa deve conter uma estrutura mais eficiente. Uma possibilidade é uma estrutura baseada em lista ligada, que não tenha que inverter os caracteres um por um a cada operação.
Alguém sabe como posso utilizar uma lista ligada para conseguir inverter a sequencia do DNA??? A lista ligada deve ser a seuqncia recebida pelo meu programa...tipo...cada gene deve ser uma célula da lista??
Minha idéia inicial era inverter os elementos da string com base no bubblesort...mas ira estourar o tempo de execução do programa.... Se alguém puder me ajudar ficarei muito agradecida....
Pergunta
aninha1988
Oi pessoal...sou nova neste fórum e estou aprendendo sobre linguagem C...
tenho dúvidas em um exercício que preciso fazer....aqui vai o enunciado para que vocês possam entendê-lo:
Este exercício está baseado num problema que ocorre em Biologia Computacional.
Todos sabem sobre DNA. Um DNA pode ser resumido como um string nas letras ATCG. O DNA pode sofrer uma série de mutações, alguma das quais podem ser descritas como transformações algorítmicas no string. Uma delas é a reversão, e este problema consiste em simular uma série de reversões. Dada uma sequência de DNA inicial (descrita por uma sequência de N caracteres, com valor A, T, C ou G), uma reversão consiste em destacar um trecho contínuo desta sequência e recolocá-lo na ordem invertida, invertendo a sequência de caracteres deste trecho. A operação é descrita pelos índices da posição inicial e final do trecho (indexamento começando em 1).
O programa deve ler, da entrada padrão (stdin), uma sequência de DNA inicial e uma série de operações de inversão a serem realizadas em sequência e imprimir os 1000 primeiros caracteres (ou todos caso N < 1000) da sequência final, na saída padrão (stdout).
A entrada conterá 3 linhas. A primeira linha conterá um número, M, com a quantidade de operações a serem realizadas. A segunda linha conterá uma sequência de N caracteres representando o DNA inicial, cada caracter com valor A, T, C ou G. A terceira linha conterá M pares de números (ai e bi, respeitando 1 ≤ ai < bi ≤ N) representando o índice inicial e final de cada operação.
Restrições: 1 < N ≤ 10.000.000; 1 ≤ M ≤ 10.000.
Tempo de processamento: 10 seg.
Exemplo de entrada e saída:
3
ATATGCGA
3 6 4 8 3 4
ATACGATG
Veja o que aconteceu (em vermelho os trechos invertidos):
Sequência inicial: ATATGCGA
Operação 1: [3, 6]
Sequência 2: ATCGTAGA
Operação 2: [4, 8]
Sequência 3: ATCAGATG
Operação 3: [3, 4]
Sequência final: ATACGATG
A intenção deste exercício é testar a capacidade de adaptar estrutura de dados para aplicações específicas, otimizando o tempo de processamento, reduzindo a complexidade computacional temporal da solução.Uma solução intuitiva, realizando as operações de reversão em um vetor de modo direto, tem tempo de complexidade computacional O(M*N), N para cada operação. Para as restrições acima, isso corresponderia a uma ordem de 1012 operações, o que deve estourar o limite de 10 seg imposto.Para melhorar o tempo de processamento, o programa deve conter uma estrutura mais eficiente. Uma possibilidade é uma estrutura baseada em lista ligada, que não tenha que inverter os caracteres um por um a cada operação.
Alguém sabe como posso utilizar uma lista ligada para conseguir inverter a sequencia do DNA??? A lista ligada deve ser a seuqncia recebida pelo meu programa...tipo...cada gene deve ser uma célula da lista??
Minha idéia inicial era inverter os elementos da string com base no bubblesort...mas ira estourar o tempo de execução do programa.... Se alguém puder me ajudar ficarei muito agradecida....
Link para o comentário
Compartilhar em outros sites
0 respostass a esta questão
Posts Recomendados
Participe da discussão
Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.