¿Qué es el Proyecto Euler?
Project Euler es una serie de problemas desafiantes que requieren habilidades matemáticas y de programación. Alguien que disfruta aprendiendo nuevas áreas de las matemáticas, el proyecto Euler será un viaje divertido.
¿Dónde están los problemas?
Los problemas están aquí en su archivo oficial .
Resolvamos un problema del archivo y comprendamos su complejidad. Al azar he elegido el Problema 116.
Problema 116: Baldosas rojas, verdes o azules
Enunciado del problema
Solución: [SE RECOMIENDA QUE PRUEBE USTED PRIMERO]
Una baldosa roja tiene una longitud de 2, una verde de 3 y una azul de 4.
Dado que necesitamos contar las formas totales para 50 unidades de mosaicos cuadrados de color negro, digamos k = 50 .
def E_116(i, k):
ways = [1] * i + [0] * (k-i+1)
for j in range(i, k+1):
ways[j] += ways[j - 1] + ways[j - i]
return ways[k] - 1
Aquí, estamos inicializando nuestra función E_116() que contiene la lógica de la solución al problema. La función E_116() tiene dos parámetros i = número de mosaicos cuadrados de color negro cubiertos por los nuevos mosaicos de color (rojo, verde o azul) y k = número total de mosaicos cuadrados de color negro.
en la función,
ways = [1] * i + [0] * (k-i+1)
Por lo tanto, las formas son una lista que contiene el número total de formas en que el bloque de longitud i puede cubrir 50 mosaicos cuadrados de color negro. Por ejemplo: en el ejemplo anterior, x = [1, 1, 1, 0, 0, 0], tiene 1 (x3) y 0 (x3), donde 1 representa el caso de solución posible y 0 representa el fracaso. Como podemos comparar para i = 3 y k = 5 de la pregunta, obtenemos un total de 3 formas posibles. Por lo tanto, hay 1 (x3 ) en la lista, formas.
for j in range(i, k+1):
ways[j] += ways[j - 1] + ways[j - i]
Usando el ciclo for estamos iterando de i a 50, hemos escrito k+1 ya que iterar en el ciclo a través de range() excluirá el último caso. Inways [j] +=ways[j – 1] +ways[j – i] , estamos actualizando el índice jth de las formas de la lista con la suma de (j-1) y (j+i) el valor del índice y también el valor del índice jth (Desde += ).
Estos son los posibles valores de j, para i=3 yk =5. Finalmente, devolvemos nuestra lista como formas de retorno [k] – 1. Entonces, para i = 3 y k = 5, esto da la solución (es decir, Ans = 3) Por último, en nuestro código,
print("Number of black tiles =", k, "units")
print("Number of ways to fill:", E_116(2, k) + E_116(3, k) + E_116(4, k))
Imprimimos nuestro resultado usando la función print(). La primera instrucción imprime Número de mosaicos negros = 50 y la segunda instrucción imprime Número de formas de llenar: 20492570929, que es la respuesta deseada al problema.
# Project Euler Problem 116
k = 50
def E_116(i, k):
ways = [1] * i + [0] * (k-i+1)
for j in range(i, k+1):
ways[j] += ways[j - 1] + ways[j - i]
return ways[k] - 1
print("Number of black tiles =", k, "units")
print("Number of ways to fill:", E_116(2, k) + E_116(3, k) + E_116(4, k))
Recursos:
Este artículo es una contribución de Amartya Ranjan Saikia . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA