Esta sección está orientada a resolver un problema algorítmico de teoría de números y revisa algunos conceptos básicos de la sintaxis y semática de Python. Hay dos soluciones al problema, una que explota características propias de la aritmética de precisión arbitraria implementada en Python. La otra, una solución que requiere algo de ingenio. Del lenguaje se abordan los conceptos de constante, variable, asignación, condicionales e iteración (con for y con while).
El problema se encuentra en la arena de programación competitiva UVa y es el siguiente:
Este problema puede ser formalizado de la siguiente manera:
n, con n impar y no divisible por 5m divisible por n y tal que m contiene únicamente el dígito 1Un número que tiene a 1 como su único dígito se llama (en inglés) repunit (de repetitive unit). Aunque el enunciado del problema no lo hace explícito, dadas las condiciones sobre n, hay un teorema que garantiza la existencia de m. Es decir, este es un problema de búsqueda con certeza.
Dado que el problema es una búsqueda con certeza y que Python tiene artimética de precisión arbitraria, este problema acepta una solución muy sencilla. La idea es la siguiente: iterativamente construir los números 1, 11, 111, 1111, etc. hasta que encontremos uno múltiplo de n (ese sería el testigo m por el cual pregunta el problema). Note que esta estrategia no es posible, en general, al usar un lenguaje de programación como C que tiene tipos numéricos de precisión limitada.
Con base en la estrategia anterior, es necesario conocer los siguientes elementos del lenguaje:
En esta sección usaremos documentación externa para revisar los elementos del lenguaje necesarios para resolver el problema. En particular, visitaremos parte de la sección 3 de The Python Tutorial y practicaremos con material para aprender Python del sitio After Hours Programming.
Adicionalmente hay que mencionar lo siguiente. Como se pudieron dar cuenta, Python ofrece asignaciones simultáneas, i.e., asignaciones en donde más de una variable puede ser afectada. Sin embargo, para aquellas personas que estamos acostumbradas a este tipo de funcionalidad es lenguajes algorítmicos, es importante resaltar que las asignaciones simultáneas en Python NO son asignaciones en paralelo. La semántica adoptada por Python para este tipo de asignaciones es una semántica de evaluación secuencial que en algunos casos difiere de una semántica pura de asignación en paralelo.
Para entender esta situación y su explicación pueden visitar:
La solución la presentamos en dos partes: (1) lectura de datos de entrada e impresión de datos de salida, y (2) solución algorítmica del problema.
Los datos se leen de la entrada estándar de la siguiente manera:
l (cada l es una cadena que representa un número entero)l se convierte a un número entero y se almcena en la variable entera nsolve con parámetro n (esta función será implementada por nosotros a continuación)El código de lectura, transformación de datos y de impresión hacen parte de una función main (esta función puede llamarse como uno quiera, no necesariamente main).
La estructura de la solución y la implementación de la función main se presentan a continuación:
from sys import stdindef solve(n): passdef main(): for l in stdin.readlines(): n = int(l) print(solve(n))main()Por favor cerciórese de entender la estructura del código y cómo interactúan sus principales componentes. Por favor consulte la documentación del comando pass.
La solución algorítmica del problema está implementada en la función solve y está basada en la estrategia descrita al inicio de la sesión: iterativamente construir los números 1, 11, 111, 1111, etc. hasta que encontremos uno múltiplo de n.
def solve(n): m,r = 1,1 while m%n!=0: m,r = m*10+1,r+1 return rLa variable m representa el testigo y r la cantidad de dígitos de m (invariante). Inicialmente m y r son asignadas el valor 1 (note que 0 es múltiplo de 2 y por ende no hace parte de la entrada del problema). El ciclo mantiene el invariante al aumentar m en un dígito y actualizando r con una unidad más. El ciclo termina cuando el resídulo al dividir m por n es 0, i.e., cuando m es múltiplo de n. El número de dígitos de m está almacenado en r, que corresponde al valor retornado por la función solve.
El código completo de la solución lo llamaremos ones_v1.py y es el siguiente:
from sys import stdindef solve(n): m,r = 1,1 while m%n!=0: m,r = m*10+1,r+1 return rdef main(): for l in stdin.readlines(): n = int(l) print(solve(n))main()Considere un archivo ones_test1.in con el siguiente contenido:
379901Al ejecutar la solución construída, se obtienen el siguiente resultado (el mismo del enunciado del problema).
$ python3 ones_v1.py < ones_test1.in3612La primera versión de la solución es cortesía de la implementación de aritmética arbitraria en Python. Sin embargo, también explicamos inicialmente, algunos lenguajes de programación no cuentan con esta funcionalidad (al menos, como parte de su distribución básica). La buena noticia es que, bajo los supuestos iniciales del problema, la primera versión de la solución puede ser modificada ligeramente, sin alterar su sencillez y elegancia, para obtener una equivalente que no usa aritmética de precisión arbitraria.
Considere la guarda del ciclo en la función solve: m no es divisible por n (i.e., m%n!=0). Fíjese que para hacer la comprobación basta con fijarse en el resíduo de dividir m por n; en particular no nos interesa el valor del cociente de dividir m por n. Entonces es suficiente con almacenar el resíduo de dividir m por n (i.e., m módulo n) y no el valor de m.
El código que implementa esta observación hace parte de la función solve y se presenta a continuación:
def solve(n): m,r = 1%n,1 while m!=0: m,r = m*10+1,r+1 m = m%n return rNote que el enunciado del problema indica que el varlor máximo de n es 10000. Por ende, esta versión 2 de la solución se puede implementar en un entero de 32 bits como (int en C y Java, por ejemplo) sin posibles efectos de desborde de tipo.
m, el valor de m. Siga el formato de impresión del archivo ones_test3.out que corresponde a la salida correcta para la entrada en ones_test3.in. Verifique que su implementación es correcta con respecto al archivo de entrada ones_test4.in y de salida ones_test4.out. Una forma conveniente de resolver el problema es con tuple.tiling_test1.in y tiling_test1.out.