Exercícios sobre Dividir para Conquistar
Questão 1
Dado um vetor de números ordenado v, verifique se existe o elemento alvo. Caso existir, retorne a posição do elemento. Caso contrário retorne -1. Implemente o algortimo de busca binária.
Exemplo:
Exemplo 2:
Exemplo:
Entrada:
v = [1 ,3 ,5 ,10, 15, 19, 89]
alvo = 3
Saída: 2
Exemplo 2:
Entrada:
v = [1 ,3 ,5 ,10, 15, 19, 89]
alvo = 7
Saída: -1
Questão 2
Dado um vetor de números v, realize a ordenação dos elementos em ordem crescente. Implemente o algortimo de ordenação quick-sort.
Exemplo:
Exemplo 2:
Exemplo:
Entrada:
v = [1 ,3 ,5 ,10, 15, 19, 89]
Saída: [1 ,3 ,5 ,10, 15, 19, 89]
Exemplo 2:
Entrada:
v = [8, 7, 9, -1, 19]
Saída: [-1, 8, 7, 9, 19]
Questão 3
Um terreno retangular possui largura L e altura A. Deseja-se dividir esse terreno em quadrados iguais, tão grandes quanto possível, sem que haja sobras. Implemente um algoritmo utilizando o paradigma Dividir para Conquistar para determinar o tamanho do lado desses quadrados.
Exemplo 1:
Exemplo 2:
Exemplo 1:
Entrada:
L = 168
A = 64
Saída: 8
Exemplo 2:
Entrada:
L = 24
A = 16
Saída: 8
Questão 4
Você possui 9 moedas visualmente idênticas, sendo que uma delas é falsa e pesa menos que as demais. As outras 8 moedas possuem exatamente o mesmo peso.
Você dispõe de uma balança de dois pratos, que permite comparar dois grupos de moedas e informar qual grupo é mais leve ou se ambos possuem o mesmo peso.
Implemente um algoritmo utilizando o paradigma Dividir para Conquistar para descobrir qual moeda é falsa, realizando o menor número possível de pesagens.
Considere que existe uma função `pesar(grupo1, grupo2)` que recebe dois grupos de moedas e retorna qual grupo é mais leve ou se ambos possuem o mesmo peso. Você pode utilizar essa função, mas não conhece previamente a moeda falsa.
Exemplo 1:
Exemplo 2:
Os exemplos representam execuções diferentes. A moeda falsa não é informada na entrada; ela deve ser descoberta pelo algoritmo por meio das pesagens.
Você dispõe de uma balança de dois pratos, que permite comparar dois grupos de moedas e informar qual grupo é mais leve ou se ambos possuem o mesmo peso.
Implemente um algoritmo utilizando o paradigma Dividir para Conquistar para descobrir qual moeda é falsa, realizando o menor número possível de pesagens.
Considere que existe uma função `pesar(grupo1, grupo2)` que recebe dois grupos de moedas e retorna qual grupo é mais leve ou se ambos possuem o mesmo peso. Você pode utilizar essa função, mas não conhece previamente a moeda falsa.
Exemplo 1:
Entrada:
moedas = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Saída:
Moeda falsa: 7
Número de pesagens: 2
Exemplo 2:
Entrada:
moedas = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Saída:
Moeda falsa: 3
Número de pesagens: 2