Introducción
Como hace un día espléndido, no te apetece nada pasar una hora en un aula.
De mal humor, entras en clase y te fijas en una forma triangular extrañamente satisfactoria en la pizarra.
Mientras esperas a que llegue tu profesor de matemáticas, no puedes evitar fijarte en algunos patrones del triángulo: los valores exteriores son todos unos, cada fila tiene un valor más que la anterior y el triángulo es simétrico.
¡Qué raro!
No mucho después de que te sientes, entra tu profesor y explica que ese triángulo es el famoso triángulo de Pascal.
Durante la hora siguiente, tu profesor te desvela algunas cosas asombrosas que se esconden en este triángulo:
- Sirve para calcular de cuántas formas puedes elegir K elementos de entre N valores.
- Contiene la sucesión de Fibonacci.
- Si coloreas los números pares e impares de forma distinta, obtienes un bonito patrón llamado triángulo de Sierpiński.
El profesor te pide a ti y a tus compañeros que busquéis otros usos, ¡y os asegura que hay muchísimos más!
En ese momento suena el timbre del colegio.
Te das cuenta de que durante la última hora has estado completamente absorto aprendiendo sobre el triángulo de Pascal.
Coges rápidamente el portátil de la mochila y sales fuera, dispuesto a disfrutar tanto del sol como de las maravillas del triángulo de Pascal.
Instrucciones
Tu tarea es generar las primeras N filas del triángulo de Pascal.
El triángulo de Pascal es un array triangular de números enteros positivos.
En el triángulo de Pascal, el número de valores de una fila es igual al número de esa fila (que empieza en uno).
Por lo tanto, la primera fila tiene un valor, la segunda fila tiene dos valores, y así sucesivamente.
La primera fila (la más alta) tiene un único valor: 1.
Los valores de las filas siguientes se calculan sumando los números que están directamente a la derecha y a la izquierda de la posición actual en la fila anterior.
Si la fila anterior no tiene un valor a la izquierda o a la derecha de la posición actual (lo que solo ocurre en las posiciones más a la izquierda y más a la derecha), trata el valor de esa posición como cero (lo que equivale a «ignorarlo» en la suma).
Ejemplo
Vamos a ver las primeras 5 filas del triángulo de Pascal:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
La fila más alta tiene un valor, que es 1.
Los valores más a la izquierda y más a la derecha solo tienen una posición precedente que considerar, que es la posición a su derecha y a su izquierda, respectivamente.
Como el valor más alto es 1, se deduce que todos los valores más a la izquierda y más a la derecha también son 1.
Los demás valores tienen dos posiciones que considerar.
Por ejemplo, el valor central de la quinta fila (1 4 6 4 1) es 6, ya que los valores a su izquierda y a su derecha en la fila anterior son 3 y 3:
Cómo se implementa este ejercicio en Python: recursión
Este ejercicio está pensado para completarse usando recursion, en lugar de bucles.
Una función recursiva es una función que se llama a sí misma, lo cual es útil para resolver problemas que se definen en términos de sí mismos.
Para evitar la recursión infinita (o, más concretamente, para evitar desbordar la pila), se usa algo llamado «caso base».
Cuando se alcanza el caso base, se devuelve un valor no recursivo, lo que permite que la llamada anterior a la función se resuelva y devuelva su valor, y así sucesivamente, propagándose hacia atrás por la pila hasta que la primera llamada a la función devuelve la respuesta.
Podríamos escribir una función recursiva que halle la respuesta de 5! (es decir, 5 * 4 * 3 * 2 * 1) así:
def factorial(number):
if number <= 1: # base case
return 1
return number * factorial(number - 1) # recursive case
print(factorial(5)) # returns 120
Por último, cabe señalar que Python limita el número de veces que se pueden hacer llamadas recursivas (1000 por defecto) y no optimiza la recursión de cola.
Mensajes de excepción
A veces es necesario lanzar una excepción.
Cuando lo hagas, siempre debes incluir un mensaje de error significativo que indique cuál es el origen del error.
Esto hace que tu código sea más legible y ayuda enormemente con la depuración.
En situaciones en las que sabes que el origen del error va a ser de un tipo concreto, puedes optar por lanzar uno de los tipos de error integrados, pero aun así debes incluir un mensaje significativo.
Este ejercicio en concreto requiere que uses la instrucción raise para "lanzar" varios ValueErrors si se pasa un número negativo a la función rows().
Las pruebas solo pasarán si lanzas la exception con raise y además incluyes un mensaje con ella.
Para lanzar un ValueError con un mensaje, escribe el mensaje como argumento del tipo exception:
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
