División euclídea
Cuando en la escuela nos enseñan a dividir, nos explican qué son el dividendo, el divisor, el cociente y el resto. Intuitivamente aprendemos que la división sirve para repartir un número determinado de cosas (dividendo) entre una serie de personas (divisor). El resultado de la operación nos indica a cuántas cosas tocan cada uno (cociente) y cuántas sobran (resto).
Esa es la que se llama división euclídea (o entera) de números naturales, es decir números no negativos. Enseguida aprendemos, además, que no tiene sentido repartir algo entre cero personas y por lo tanto el divisor no puede ser nulo.
Formalmente, la división euclídea entre dos números enteros a y b (siendo b un número distinto de cero) calcula un cociente q y un resto r asociados a esos a y b, que cumplen que a = b × q + r, y donde el resto r es siempre un entero no negativo, 0 ≤ r < |b|.
Aunque la definición es fácil de entender y aplicar cuando trabajamos con números positivos, hay que pensarlo con un poco más de cuidado antes de contestar cuál es el resultado de la división cuando el dividendo o el divisor son negativos.
Entrada
La entrada comienza con un número indicando la cantidad de casos de prueba que deberán procesarse. Cada caso de prueba aparece en una línea independiente y está compuesto por dos números enteros, primero el dividendo y luego el divisor. Ninguno será mayor que 10.000 en valor absoluto.
Salida
Para cada caso de prueba, el programa escribirá en una línea el cociente y el resto de la división euclídea separados por un espacio. En el caso de que el divisor sea 0 se escribirá únicamente DIV0.
Entrada de ejemplo
5
7 3
7 -3
-7 3
-7 -3
7 0
Salida de ejemplo
2 1
-2 1
-3 2
3 2
DIV0
Solución propuesta
python
if __name__ == '__main__':
respuestas = []
casos = int(input())
for i in range(casos):
dividendo, divisor = [int(x) for x in input().split( ' ')]
if divisor == 0:
respuestas.append('DIV0')
elif dividendo > 0:
cociente = 0
resto = dividendo
abs_divisor = abs(divisor)
while resto > abs_divisor:
resto -= abs_divisor
cociente += 1
if divisor < 0:
cociente *= -1
respuestas.append('%d %d' % (cociente, resto))
else:
cociente = 0
resto = dividendo
abs_divisor = abs(divisor)
while abs(resto) > abs_divisor:
resto += abs_divisor
cociente += 1
if divisor > 0:
cociente *= -1
respuestas.append('%d %d' % (cociente, resto))
for respuesta in respuestas:
print(respuesta)El que solo dependa
El que solo dependa
En el código de hoy, hay que tener en cuenta que hay cuatro casos posibles según la combinación de signos del dividendo y del divisor. Hay que recordar que el cociente puede ser negativo si los signos del dividendo y el divisor no son el mismo, de ahí el primer if, que solo depende del dividendo.
El while, lo que controla es que el resto sea mayor que el divisor, como en cualquier división, sin embargo, la peculiaridad en el caso de que el dividendo sea negativo es que el mismo signo va a tener el resto, con lo que lo que hemos de buscar es que llegue a ser positivo, como pide la fórmula.
Creo que este algoritmo es relativamente sencillo si se consiguen solventar el problema de los signos, el resto es aplicar la forma de calcular la división tal y como nos enseñaron de pequeños en el colegio.