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
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:
Download Executar código
Download Executar código
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:
Download Executar código
Download Executar código
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 🙂 |