Sé Sé que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.
Así que si no puedes reproducir mis resultados (del mismo modo que yo no puedo reproducir los tuyos ni los de la otra persona que respondió), puede ser porque después de cierto punto las iteraciones hacen que los valores crezcan tanto que el lenguaje de programación que utilizaste comienza a comportarse de esta manerainesperadamente. También es posible queEn mi código esté incorrecto (posiblemente porque programe a la ligera), peroopinion la respuesta a esta cuestiónque busca el reclutador no radica en el código en sí, sino en el enfoque que se le debe dar.
En ese ordenEditado
Gracias a una respuesta de ideasun usuario, como datome percate de interés, lo que voy a compartir es el código de una posible implementación en Python con la librería NumPy. La probé con algunos valores bajos ysolucion numerica al problema se comporta según lo deseado, pero como mencioné antes, puede encontrar evitando que con valores grandes sea necesario hacer ajusteslos numeros crescan sin control aplicando el %
modulo internamente en lugares donde no afectan el resultado final.
import numpy as np
mod = 10000000000
# A y B son matrices, no son var_A ni var_B
def matrix_mult(A, B):
return np.dot(A, B) % mod
def matrix_pow(mat, exp):
result = np.eye(len(mat), dtype='object')
base = mat.copy()
while exp > 0:
if exp % 2 == 1:
result = matrix_mult(result, base)
base = matrix_mult(base, base)
exp //= 2
return result
def solucionar_rompecabezas(N):
mod = 10000000000
T = np.array([[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[1, 4, 1, 3]], dtype='object')
initial_state = np.array([1, 1, 1, 1], dtype='object')
T_N = matrix_pow(T, N)
final_state = matrix_mult(T_N, initial_state) % mod
return final_state[3]
print(solucionar_rompecabezas(10))
print(solucionar_rompecabezas(100))
print(solucionar_rompecabezas(pow(2023, 100)))
Editado Al ejecutarlo, notarán que para n=10n=10, el bucle while se repite 4 veces; para n=100n=100, se repite 7 veces; y para n=pot(2023,100)n=pot(2023,100) después de cambiar el dtype en NumPy de int a object, me di cuenta de que no se puede llegar (aunque sea mas eficiente el algoritmo el numero sigue siendo muy grande). Sin embargo, con valores de N=1000000 ya se puede evidenciar la diferencia en rendimiento entre esta solución y la solución trivial.
resultados: N=10 902441 N=100 8042318513Finalmente tras varias ediciones el codigo propuesto permite encontrar las soluciones numericas para los tres valores de N dados.
resultados:
N=10 902441
N=100 8042318513
N=23^100 3548910009