Triangulo de pascales con recursion

De acuerdo, alguien puede decirme si mi código actual es posible. Tengo que crear triangularjs de pascales con una entrada SIN usar ningún bucle. Estoy obligado a la recursión.

He pasado 3 días en esto, y esta es la mejor salida que puedo hacer. me está volviendo loca

def pascal(curlvl,newlvl,tri): if curlvl == newlvl: return "" else: tri.append(tri[curlvl]) print(tri) return pascal(curlvl+1,newlvl,tri) def triLvl(): msg = "Please enter the number of levels to generate:" triheight = int(input(msg)) if triheight < 1: print("\n Sorry, the number MUST be positive\n Please try again.") return triLvl() else: return triheight def main(): triangle = [1] curlvl = 0 print("Welcome to the Pascal's triangle generator.") usrTri = triLvl() print(triangle) pascal(curlvl,usrTri,triangle) main() 

Podemos definir un pascal recursivo usando la función de ayuda, pairs

pascal devolverá [[Int]] (una matriz de matrices de Int) – por ejemplo, pascal(3) devolvería

 [ [1], [1, 1], [1, 2, 1] ] 

De acuerdo, te mostraré todo el código al principio, pero luego te explicaré algunos bits.

 def pairs (xs): if 2 > len(xs): return [] else: return [xs[0:2]] + pairs(xs[1:]) def pascal (n): def compute (prev): return [1] + [x + y for (x,y) in pairs(prev)] + [1] def aux (m, prev): if (m > n): return [] else: return [prev] + aux(m + 1, compute(prev)) return aux(1, [1]) [print(line) for line in pascal(5)] # [1] # [1, 1] # [1, 2, 1] # [1, 3, 3, 1] # [1, 4, 6, 4, 1] 

Explicación

Lo que realmente nos importa es la función de pascal : todo lo demás que hemos escrito nació de la forma en que escribimos pascal , así que empezaré por eso.

Una forma muy común de escribir funciones recursivas es usar una función auxiliar interna que realiza un seguimiento de los diversos estados de nuestros cálculos. Usaremos esta técnica como la base de nuestra función pascal .

 def my_recursive_func (  ): def aux (  ): if (  ): return  else return aux(  ) return aux(  ) 

Ya sabemos cómo completar algunos de estos textos para nuestra función de pascal .

  • parameters deben ser n , un entero, porque esperamos llamar a nuestra función como pascal(3) o pascal(5) , etc., no se deben aceptar otros argumentos.
  • state_parameters : solo sabemos dos cosas en este momento: 1) necesitaremos algún valor m que cuente hasta n , incrementando en 1 cada vez, y 2) algún valor que nos permita calcular la siguiente fila; lo llamaremos prev porque cada fila de pascal se calcula en base a la fila anterior
  • base_condition – cuando m == n sabemos que hemos generado todas las filas que necesitamos, esto es cuando queremos detener la repetición
  • base_value : este es el último valor devuelto, no estoy seguro de lo que debería ser todavía
  • updated_state : actualizaremos m utilizando m + 1 y actualizaremos las filas, presumiblemente, utilizando algún tipo de concatenación de matrices, sin estar seguros hasta que escribamos más código
  • initial_state – comenzaremos m en 1 y la primera fila de pascal es [1]

OK, vamos a completar lo que tenemos hasta ahora

 def pascal ( n ): def aux ( m , prev ): if ( m > n ): return ? else: return aux( m + 1 , ? ) return aux( 1 , [1] ) 

Lo que nos gustaría hacer es que pascal construya nuestro resultado algo como esto.

 [[1]] + [[1, 1]] + [[1, 2, 1]] + [[1, 3, 3, 1]], ...] # => [ [1], [1 ,1], [1, 2, 1], [1, 3, 3, 1], ... ] 

Entonces, para escribir el valor base_value y el estado actualizado de prev , debemos considerar este tipo de retorno. Queremos devolver [[Int]] , que es una lista, por lo que el valor base_value puede ser simplemente la lista vacía, [] .

Eso significa que en cada paso, realmente queremos tomar [prev] y concatenar ( + ) al resultado recursivo también …

 [prev] + aux(m + 1,  ) 

Nos estamos acercando mucho ahora, volvamos a actualizar pascal para ver qué tenemos que terminar

 def pascal (n): def aux (m, prev): if (m > n): return [] else: return [prev] + aux(m + 1,  ) return aux(1, [1]) 

Ok, aquí viene la parte difícil: calcular la siguiente fila, ¿verdad? Bueno, en realidad no está tan mal.

 # given [1,2,1] # the next row is [1, (1 + 2), (2 + 1), 1] 

U otro ejemplo

 # given [1, 4, 6, 4, 1] # the next row is [1, (1 + 4), (4 + 6), (6 + 4), (4 + 1), 1] 

Entonces, el patrón es algo como esto: cree una nueva matriz comenzando con 1 , luego para cada par de números en la fila anterior, sume los dos números juntos y agregue cada sum a la matriz, luego finalmente agregue otro 1 . Podríamos express que en python usar una lista de comprensión como esta

 [1] + [x + y for (x,y) in pairs(prev)] + [1] 

Ahora solo necesitamos descubrir que los pairs funcionan. pairs deben tener el siguiente contrato

 pairs([]) => [] pairs([a]) => [] pairs([a,b]) => [[a,b]] pairs([a,b,c]) => [[a,b],[b,c]] pairs([a,b,c,d]) => [[a,b],[b,c],[c,d]] 

Implementémoslo ahora y verifiquemos que nuestra implementación cumpla con el contrato. Tenga en cuenta que estoy implementando esta función fuera de pascal porque es una función genérica y útil por sí misma. Para calcular las filas de pascal, debemos agregar pares de números, pero agregar o cómo obtenemos esos pares o números no debe dejarse como una responsabilidad de la función de pascal sí.

 def pairs (xs): if 2 > len(xs): return [] else: return [xs[0:2]] + pairs(xs[1:]) print(pairs([])) # [] print(pairs([1])) # [] print(pairs([1,2])) # [[1,2]] print(pairs([1,2,3])) # [[1,2],[2,3]] print(pairs([1,2,3,4])) # [[1,2],[2,3],[3,4]] 

OK, eso nos está acercando mucho ahora. Vamos a actualizar la función de pascal nuevo para ver dónde estamos

 def pascal (n): def aux (m, prev): if (m > n): return [] else: return [prev] + aux(m + 1, [1] + [x + y for (x,y) in pairs(prev)] + [1] ) return aux(1, [1]) 

¡Santo fuma! Ya hemos terminado. Esa llamada aux con el cálculo en línea de la siguiente fila se ve un poco ocupada aunque. Agreguemos otro ayudante dentro de pascal llamado compute para limpiar las cosas. Ahora hemos terminado!

 def pascal (n): def compute (prev): return [1] + [x + y for (x,y) in pairs(prev)] + [1] def aux (m, prev): if (m > n): return [] else: return [prev] + aux(m + 1, compute(prev) ) return aux(1, [1]) 

Siendo minucioso

Si desea que aparezcan el texto y las indicaciones, puede escribir algo main como a continuación: Esto mantiene todas las E / S separadas de nuestras funciones de pascal y pairs . Es importante considerar esta separación de preocupaciones y el manejo de los efectos secundarios al principio de su progtwig porque es difícil reutilizar funciones que hacen más de lo que queremos.

 def main (): try: print("Pascal triangle generator") n = int(input("Pascal(x): x = ")) if n < 1: raise [print(line) for line in pascal(n)] except: print("enter a non-zero positive integer") main() # run program main() 

Continúa y ejecuta pascal(300) o algo para obtener resultados impresionantes.

No sé si esto es lo que estás buscando pero funciona bien:

 from operator import add def pascal(curlvl, newlvl, tri): if curlvl == newlvl: return "" elif curlvl == 0: tri.append(1) print (tri) return pascal(curlvl + 1, newlvl, tri) else: tmp = [1] rt = tri[:-1] rt.reverse() # print (map(add, rt, tri[:-1])) # In Python 3, map returns a generator. # Wrapping map in list makes this code compatible with # both Python 2 and 3 tt = list(map(add, rt, tri[:-1])) if (len(tt) > 0): tmp.extend(tt) tmp.append(1) tri = tmp print (tri) return pascal(curlvl + 1, newlvl, tri) def triLvl(): msg = "Please enter the number of levels to generate:" triheight = int(input(msg)) if triheight < 1: print("\n Sorry, the number MUST be positive\n Please try again.") return triLvl() else: return triheight def main(): triangle = [1] curlvl = 0 print("Welcome to the Pascal's triangle generator.") usrTri = triLvl() print(triangle) pascal(curlvl, usrTri, triangle) main() 

Triángulo de Pascal recursivo como una lista:

 P=lambda h:(lambda x:x+[[x+y for x,y in zip(x[-1]+[0],[0]+x[-1])]])(P(h-1))if h>1 else[[1]] print(P(10)) 

Espero que pueda ayudar, no sé si ‘zip’ y ‘map’ son considerados como bucles (ciertamente contienen bucles).