Dado un número entero N , la tarea es encontrar su raíz cuadrada perfecta solo mediante restas repetidas.
Ejemplos:
Entrada : N = 25
Salida : 5
Entrada : N = 841
Salida : 29
Método babilónico y enfoque de búsqueda binaria: Consulte la raíz cuadrada de un número entero para conocer los enfoques basados en el método babilónico y la búsqueda binaria .
Enfoque de resta repetida:
siga los pasos a continuación para resolver el problema:
- La suma de los primeros N números naturales impares es igual a N 2 .
- Basado en el hecho mencionado anteriormente, se debe realizar la resta repetitiva de números impares a partir de 1, hasta que N se convierta en 0 .
- El conteo de números impares, usado en este proceso, dará la raíz cuadrada del número N.
Ilustración:
N = 81
Paso 1: 81-1=80
Paso 2: 80-3=77
Paso 3: 77-5=72
Paso 4: 72-7=65
Paso 5: 65-9=56
Paso 6: 56- 11=45
Paso 7: 45-13=32
Paso 8: 32-15=17
Paso 9: 17-17=0
Dado que se usaron 9 números impares, la raíz cuadrada de 81 es 9.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of // the above approach #include <bits/stdc++.h> using namespace std; // Function to return the square // root of the given number int SquareRoot(int num) { int count = 0; for (int n = 1; n <= num; n += 2) { // Subtract n-th odd number num = num - n; count += 1; if (num == 0) break; } // Return the result return count; } // Driver Code int main() { int N = 81; cout << SquareRoot(N); }
Java
// Java implementation of // the above approach class GFG{ // Function to return the square // root of the given number public static int SquareRoot(int num) { int count = 0; for(int n = 1; n <= num; n += 2) { // Subtract n-th odd number num = num - n; count += 1; if (num == 0) break; } // Return the result return count; } // Driver code public static void main(String[] args) { int N = 81; System.out.println(SquareRoot(N)); } } // This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation of the # above approach # Function to return the square # root of the given number def SquareRoot(num): count = 0 for n in range(1, num + 1, 2): # Subtract n-th odd number num = num - n count = count + 1 if (num == 0): break # Return the result return count # Driver Code N = 81 print(SquareRoot(N)) # This code is contributed by Sanjit_Prasad
C#
// C# implementation of // the above approach using System; class GFG{ // Function to return the square // root of the given number public static int SquareRoot(int num) { int count = 0; for(int n = 1; n <= num; n += 2) { // Subtract n-th odd number num = num - n; count += 1; if (num == 0) break; } // Return the result return count; } // Driver code public static void Main() { int N = 81; Console.Write(SquareRoot(N)); } } // This code is contributed by chitranayal
Javascript
<script> // Javascript implementation of // the above approach // Function to return the square // root of the given number function SquareRoot(num) { let count = 0; for (let n = 1; n <= num; n += 2) { // Subtract n-th odd number num = num - n; count += 1; if (num == 0) break; } // Return the result return count; } // Driver Code let N = 81; document.write(SquareRoot(N)); // This code is contributed by Mayank Tyagi </script>
9
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vanshgaur14866 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA