Dado un número entero X que es un cuadrado perfecto, la tarea es encontrar su raíz cuadrada usando el método de división larga .
Ejemplos:
Entrada: N = 484
Salida: 22
22 2 = 484Entrada: N = 144
Salida: 12
12 2 = 144
Enfoque:
La división larga es un método muy común para encontrar la raíz cuadrada de un número . La siguiente es la solución paso a paso para este método:
1. Divide los dígitos del número en pares de segmentos comenzando con el dígito en el lugar de las unidades. Identifiquemos cada par y el último dígito restante (en caso de que haya una cuenta impar de dígitos en el número) como un segmento.
Por ejemplo:
1225 is divided as (12 25)
2. Después de dividir los dígitos en segmentos, comience desde el segmento más a la izquierda. Se toma como divisor y también como cociente el mayor número cuyo cuadrado es igual o justo menor que el primer segmento (de manera que el producto es el cuadrado).
Por ejemplo:
9 is the closest perfect square to 12, the first segment 12
3. Resta el cuadrado del divisor del primer segmento y baja el siguiente segmento a la derecha del resto para obtener el nuevo dividendo.
Por ejemplo:
12 - 9 = 3 is concatenated with next segment 25. New dividend = 325
4. Ahora, el nuevo divisor se obtiene tomando dos veces el cociente anterior (que era 3 en el ejemplo anterior como 3 2 = 9) y concatenándolo con un dígito adecuado que también se toma como el siguiente dígito del cociente, elegido de tal manera que el producto del nuevo divisor y este dígito sea igual o menor que el nuevo dividendo.
Por ejemplo:
Two times quotient 3 is 6.
65 times 5 is 325 which is closest to the new dividend.
5. Repita los pasos (2), (3) y (4) hasta que se hayan recogido todos los segmentos. Ahora, el cociente así obtenido es la raíz cuadrada requerida del número dado.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find the square root of a
// number by using long division method
#include <bits/stdc++.h>
using namespace std;
#define INFINITY_ 9999999
// Function to find the square root of
// a number by using long division method
int sqrtByLongDivision(int n)
{
int i = 0, udigit, j; // Loop counters
int cur_divisor = 0;
int quotient_units_digit = 0;
int cur_quotient = 0;
int cur_dividend = 0;
int cur_remainder = 0;
int a[10] = { 0 };
// Dividing the number into segments
while (n > 0) {
a[i] = n % 100;
n = n / 100;
i++;
}
// Last index of the array of segments
i--;
// Start long division from the last segment(j=i)
for (j = i; j >= 0; j--) {
// Initialising the remainder to the maximum value
cur_remainder = INFINITY_;
// Including the next segment in new dividend
cur_dividend = cur_dividend * 100 + a[j];
// Loop to check for the perfect square
// closest to each segment
for (udigit = 0; udigit <= 9; udigit++) {
// This condition is to find the
// divisor after adding a digit
// in the range 0 to 9
if (cur_remainder >= cur_dividend
- ((cur_divisor * 10 + udigit)
* udigit)
&& cur_dividend
- ((cur_divisor * 10 + udigit) * udigit)
>= 0) {
// Calculating the remainder
cur_remainder = cur_dividend - ((cur_divisor * 10
+ udigit)
* udigit);
// Updating the units digit of the quotient
quotient_units_digit = udigit;
}
}
// Adding units digit to the quotient
cur_quotient = cur_quotient * 10
+ quotient_units_digit;
// New divisor is two times quotient
cur_divisor = cur_quotient * 2;
// Including the remainder in new dividend
cur_dividend = cur_remainder;
}
return cur_quotient;
}
// Driver code
int main()
{
int x = 1225;
cout << sqrtByLongDivision(x) << endl;
return 0;
}
Java
// Java program to find the square root of a
// number by using long division method
import java.util.*;
class GFG{
static final int INFINITY_ =9999999;
// Function to find the square root of
// a number by using long division method
static int sqrtByLongDivision(int n)
{
int i = 0, udigit, j; // Loop counters
int cur_divisor = 0;
int quotient_units_digit = 0;
int cur_quotient = 0;
int cur_dividend = 0;
int cur_remainder = 0;
int a[] = new int[10];
// Dividing the number into segments
while (n > 0) {
a[i] = n % 100;
n = n / 100;
i++;
}
// Last index of the array of segments
i--;
// Start long division from the last segment(j=i)
for (j = i; j >= 0; j--) {
// Initialising the remainder to the maximum value
cur_remainder = INFINITY_;
// Including the next segment in new dividend
cur_dividend = cur_dividend * 100 + a[j];
// Loop to check for the perfect square
// closest to each segment
for (udigit = 0; udigit <= 9; udigit++) {
// This condition is to find the
// divisor after adding a digit
// in the range 0 to 9
if (cur_remainder >= cur_dividend
- ((cur_divisor * 10 + udigit)
* udigit)
&& cur_dividend
- ((cur_divisor * 10 + udigit) * udigit)
>= 0) {
// Calculating the remainder
cur_remainder = cur_dividend - ((cur_divisor * 10
+ udigit)
* udigit);
// Updating the units digit of the quotient
quotient_units_digit = udigit;
}
}
// Adding units digit to the quotient
cur_quotient = cur_quotient * 10
+ quotient_units_digit;
// New divisor is two times quotient
cur_divisor = cur_quotient * 2;
// Including the remainder in new dividend
cur_dividend = cur_remainder;
}
return cur_quotient;
}
// Driver code
public static void main(String[] args)
{
int x = 1225;
System.out.print(sqrtByLongDivision(x) +"\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the square root of a # number by using long division method INFINITY_ = 9999999 # Function to find the square root of # a number by using long division method def sqrtByLongDivision(n): i = 0 udigit, j = 0, 0 # Loop counters cur_divisor = 0 quotient_units_digit = 0 cur_quotient = 0 cur_dividend = 0 cur_remainder = 0 a = [0]*10 # Dividing the number into segments while (n > 0): a[i] = n % 100 n = n // 100 i += 1 # Last index of the array of segments i -= 1 # Start long division from the last segment(j=i) for j in range(i, -1, -1): # Initialising the remainder to the maximum value cur_remainder = INFINITY_ # Including the next segment in new dividend cur_dividend = cur_dividend * 100 + a[j] # Loop to check for the perfect square # closest to each segment for udigit in range(10): # This condition is to find the # divisor after adding a digit # in the range 0 to 9 if (cur_remainder >= cur_dividend - ((cur_divisor * 10 + udigit) * udigit) and cur_dividend - ((cur_divisor * 10 + udigit) * udigit) >= 0): # Calculating the remainder cur_remainder = cur_dividend - ((cur_divisor * 10 + udigit) * udigit) # Updating the units digit of the quotient quotient_units_digit = udigit # Adding units digit to the quotient cur_quotient = cur_quotient * 10 + quotient_units_digit # New divisor is two times quotient cur_divisor = cur_quotient * 2 # Including the remainder in new dividend cur_dividend = cur_remainder return cur_quotient # Driver code x = 1225 print(sqrtByLongDivision(x)) # This code is contributed by mohit kumar 29
C#
// C# program to find the square root of a
// number by using long division method
using System;
class GFG
{
static readonly int INFINITY_ =9999999;
// Function to find the square root of
// a number by using long division method
static int sqrtBylongDivision(int n)
{
int i = 0, udigit, j; // Loop counters
int cur_divisor = 0;
int quotient_units_digit = 0;
int cur_quotient = 0;
int cur_dividend = 0;
int cur_remainder = 0;
int []a = new int[10];
// Dividing the number into segments
while (n > 0) {
a[i] = n % 100;
n = n / 100;
i++;
}
// Last index of the array of segments
i--;
// Start long division from the last segment(j=i)
for (j = i; j >= 0; j--) {
// Initialising the remainder to the maximum value
cur_remainder = INFINITY_;
// Including the next segment in new dividend
cur_dividend = cur_dividend * 100 + a[j];
// Loop to check for the perfect square
// closest to each segment
for (udigit = 0; udigit <= 9; udigit++) {
// This condition is to find the
// divisor after adding a digit
// in the range 0 to 9
if (cur_remainder >= cur_dividend
- ((cur_divisor * 10 + udigit)
* udigit)
&& cur_dividend
- ((cur_divisor * 10 + udigit) * udigit)
>= 0) {
// Calculating the remainder
cur_remainder = cur_dividend - ((cur_divisor * 10
+ udigit)
* udigit);
// Updating the units digit of the quotient
quotient_units_digit = udigit;
}
}
// Adding units digit to the quotient
cur_quotient = cur_quotient * 10
+ quotient_units_digit;
// New divisor is two times quotient
cur_divisor = cur_quotient * 2;
// Including the remainder in new dividend
cur_dividend = cur_remainder;
}
return cur_quotient;
}
// Driver code
public static void Main(String[] args)
{
int x = 1225;
Console.Write(sqrtBylongDivision(x) +"\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the square root of a
// number by using long division method
let INFINITY_ =9999999;
// Function to find the square root of
// a number by using long division method
function sqrtByLongDivision(n)
{
let i = 0, udigit, j; // Loop counters
let cur_divisor = 0;
let quotient_units_digit = 0;
let cur_quotient = 0;
let cur_dividend = 0;
let cur_remainder = 0;
let a = new Array(10);
// Dividing the number into segments
while (n > 0) {
a[i] = n % 100;
n = Math.floor(n / 100);
i++;
}
// Last index of the array of segments
i--;
// Start long division from the last segment(j=i)
for (j = i; j >= 0; j--) {
// Initialising the remainder to the maximum value
cur_remainder = INFINITY_;
// Including the next segment in new dividend
cur_dividend = cur_dividend * 100 + a[j];
// Loop to check for the perfect square
// closest to each segment
for (udigit = 0; udigit <= 9; udigit++) {
// This condition is to find the
// divisor after adding a digit
// in the range 0 to 9
if (cur_remainder >= cur_dividend
- ((cur_divisor * 10 + udigit)
* udigit)
&& cur_dividend
- ((cur_divisor * 10 + udigit) * udigit)
>= 0) {
// Calculating the remainder
cur_remainder = cur_dividend - ((cur_divisor * 10
+ udigit)
* udigit);
// Updating the units digit of the quotient
quotient_units_digit = udigit;
}
}
// Adding units digit to the quotient
cur_quotient = cur_quotient * 10
+ quotient_units_digit;
// New divisor is two times quotient
cur_divisor = cur_quotient * 2;
// Including the remainder in new dividend
cur_dividend = cur_remainder;
}
return cur_quotient;
}
// Driver code
let x = 1225;
document.write(sqrtByLongDivision(x) +"<br>");
// This code is contributed by unknown2108
</script>
Producción:
35
Complejidad de tiempo: O((log 100 n) 2 * 10)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shampa Sinha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA