Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais
Dado um número positivo, retorne a raiz quadrada dele. Se o número não for um quadrado perfeito, retorne o piso de sua raiz quadrada. Por exemplo,
Input: x = 12
Input: x = 16
Output: 3
Output: 4
Pratique este problema
Uma solução ingênua é considerar todos os números positivos a partir de 1 e encontre o primeiro número i para qual i2 é maior que o número dado x. Então i-1 seria o piso da raiz quadrada de x.
A seguir está o programa C, Java e Python que o demonstra:
// Função para encontrar o piso da raiz quadrada de `x` // encontre o primeiro número positivo `i` tal que `i×i` seja maior que `x` for (int i = 0; i <= 16; i++) { printf("sqrt(%d) = %d\n", i, findSqrt(i)); |
Download Executar código
// Função para encontrar o piso da raiz quadrada de `x` public static int sqrt(int x) // encontre o primeiro número positivo `i` tal que `i×i` seja maior que `x` public static void main(String[] args) for (int i = 0; i <= 16; i++) { System.out.printf("sqrt(%d) = %d\n", i, sqrt(i)); |
Download Executar código
# Função para encontrar o piso da raiz quadrada de `x` # encontre o primeiro número positivo `i` tal que `i×i` seja maior que `x` if __name__ == '__main__': print(f'sqrt({i}) = {sqrt(i)}') |
Download Executar código
Output: sqrt(0) = 0 sqrt(1) = 1 sqrt(2) = 1 sqrt(3) = 1 sqrt(4) = 2 sqrt(5) = 2 sqrt(6) = 2 sqrt(7) = 2 sqrt(8) = 2 sqrt(9) = 3 sqrt(10) = 3 sqrt(11) = 3 sqrt(12) = 3 sqrt(13) = 3 sqrt(14) = 3 sqrt(15) = 3
sqrt(16) = 4
A complexidade de tempo da solução acima é O(√x) e não requer nenhum espaço extra. Podemos melhorar a complexidade de tempo para O(log(x)) com a ajuda do algoritmo de busca binária. O algoritmo pode ser implementado da seguinte forma em C, Java e Python:
// Função para encontrar a raiz quadrada de `x` usando o algoritmo de busca binária. // Se `x` não for um quadrado perfeito, retorna o piso da raiz quadrada // para armazenar o andar de `sqrt(x)` // a raiz quadrada de `x` não pode ser maior que `x/2` para `x > 1` // encontra o elemento do meio int mid = (start + end) / 2; // retorna `mid` se `x` for um quadrado perfeito // se `mid×mid` for menor que `x` // descarta o espaço de pesquisa esquerdo // atualiza o resultado, pois precisamos de um piso // se `mid×mid` for maior que `x` // descarta o espaço de busca correto for (int i = 0; i <= 16; i++) { printf("sqrt(%d) = %d\n", i, findSqrt(i)); |
Download Executar código
// Função para encontrar a raiz quadrada de `x` usando o algoritmo de busca binária. // Se `x` não for um quadrado perfeito, retorna o piso da raiz quadrada public static int sqrt(int x) // para armazenar o andar de `sqrt(x)` // a raiz quadrada de `x` não pode ser maior que `x/2` para `x > 1` // encontra o elemento do meio int mid = (start + end) / 2; // retorna `mid` se `x` for um quadrado perfeito // se `mid×mid` for menor que `x` // descarta o espaço de pesquisa esquerdo // atualiza o resultado, pois precisamos de um piso // se `mid×mid` for maior que `x` // descarta o espaço de busca correto public static void main(String[] args) for (int i = 0; i <= 16; i++) { System.out.printf("sqrt(%d) = %d\n", i, sqrt(i)); |
Download Executar código
# Função para encontrar a raiz quadrada de `x` usando o algoritmo de busca binária. # Se `x` não for um quadrado perfeito, retorne o piso da raiz quadrada # para armazenar piso de `sqrt(x)` # a raiz quadrada de `x` não pode ser maior que x/2 para `x` > 1 # encontre o elemento do meio # retorna `mid` se `x` for um quadrado perfeito # se `mid×mid` for menor que `x` # descarta o espaço de pesquisa esquerdo # Resultado da atualização #, pois precisamos de um piso # se `mid×mid` for maior que `x` # descarta o espaço de busca correto if __name__ == '__main__': print(f'sqrt({i}) = {sqrt(i)}') |
Download Executar código
Output: sqrt(0) = 0 sqrt(1) = 1 sqrt(2) = 1 sqrt(3) = 1 sqrt(4) = 2 sqrt(5) = 2 sqrt(6) = 2 sqrt(7) = 2 sqrt(8) = 2 sqrt(9) = 3 sqrt(10) = 3 sqrt(11) = 3 sqrt(12) = 3 sqrt(13) = 3 sqrt(14) = 3 sqrt(15) = 3
sqrt(16) = 4
Obrigado por ler.
Por favor, use nosso compilador online para postar código em comentários usando C, C++, Java, Python, JavaScript, C#, PHP e muitas outras linguagens de programação populares.
Como nós? Indique-nos aos seus amigos e ajude-nos a crescer. Codificação feliz 🙂