Exercícios sobre Força Bruta
Questão 1
Dado um conjunto de números e um valor S, verificar se existe algum
subconjunto cuja soma seja igual a S.
Entrada: Um conjunto de números inteiros e um valor S, que representa a soma procurada.
Saída: Os elementos de um subconjunto cuja soma seja igual a S ou uma mensagem informando que não existe tal subconjunto.
Exemplo:
Exemplo 2:
Exemplo 3:
Entrada: Um conjunto de números inteiros e um valor S, que representa a soma procurada.
Saída: Os elementos de um subconjunto cuja soma seja igual a S ou uma mensagem informando que não existe tal subconjunto.
Exemplo:
Entrada:
2 4 7 10 15
17
Saída:
Subconjunto encontrado: 2 15
Exemplo 2:
Entrada:
3 5 8 12 20
16
Saída:
Subconjunto encontrado: 3 5 8
Exemplo 3:
Entrada:
2 4 6 9 11
20
Saída:
Subconjunto não encontrado.
Questão 2
Considere um cadeado que utiliza uma combinação de 4 dígitos, sendo que cada posição pode assumir um valor de 0 a 9.
O objetivo é desenvolver um algoritmo que utilize a técnica de força bruta (brute force) para descobrir a combinação correta do cadeado.
O algoritmo deve testar, de forma sistemática, todas as combinações possíveis, começando por 0000 e avançando até 9999, até encontrar a combinação que corresponde à senha definida. Por exemplo, se a combinação correta for 5732, o algoritmo deverá testar:
O algoritmo deve informar a combinação encontrada e a quantidade de tentativas realizadas até descobri-la.
O objetivo é desenvolver um algoritmo que utilize a técnica de força bruta (brute force) para descobrir a combinação correta do cadeado.
O algoritmo deve testar, de forma sistemática, todas as combinações possíveis, começando por 0000 e avançando até 9999, até encontrar a combinação que corresponde à senha definida. Por exemplo, se a combinação correta for 5732, o algoritmo deverá testar:
0000
0001
0002
...
5730
5731
5732 ← combinação encontrada
Questão 3
Considere uma sequência de DNA representada pelos caracteres A, C, G e T. Dada uma sequência de DNA maior e uma sequência menor, o objetivo é descobrir se a sequência menor aparece como uma substring dentro da sequência maior.
Por exemplo, considere a seguinte entrada:
A sequência TACG aparece dentro da sequência de DNA, começando na posição 4.
O algoritmo deve realizar a busca comparando a sequência procurada com cada possível posição da sequência de DNA. Caso encontre uma correspondência completa, deve informar a posição onde ela começa. Caso contrário, deve informar que a sequência não foi encontrada.
Entrada: Duas sequências de DNA, sendo a primeira a sequência onde será realizada a busca e a segunda a sequência que deve ser procurada.
Saída: A posição em que a sequência procurada foi encontrada ou uma mensagem informando que ela não existe na sequência.
Exemplo:
Sequência de DNA:
ACGTACGTTACGGAATCG
Sequência procurada:
TACG
O algoritmo deve realizar a busca comparando a sequência procurada com cada possível posição da sequência de DNA. Caso encontre uma correspondência completa, deve informar a posição onde ela começa. Caso contrário, deve informar que a sequência não foi encontrada.
Entrada: Duas sequências de DNA, sendo a primeira a sequência onde será realizada a busca e a segunda a sequência que deve ser procurada.
Saída: A posição em que a sequência procurada foi encontrada ou uma mensagem informando que ela não existe na sequência.
Exemplo:
Entrada:
ACGTACGTTACGGAATCG
TACG
Saída:
Sequência encontrada na posição 4.