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.
Para su solución se requiere el uso de Matemáticas (lo que es importante, ya que a veces olvidamos lo necesarias que son).
Se busca la solución a un problema algorítmicamente ineficiente o imposible de resolver para valores grandes (del enunciado se entiende que la pregunta fue propuesta cuando los procesadores no tenían la capacidad para ejecutar dicha función con valores muy grandes, algo así como la función factorial de la calculadora de Windows hace unos 15 años).
teniendo en cuenta que el dispositivo dispone de los recursos necesarios para finalizar su ejecución
Introducción:
Hay muchas funciones, como por ejemplo la función sumatoria, que se pueden resolver con un simple for:
El código Python sería algo así:
def sumatoria(n):
result = 0
for i in range(1,n+1):
result += i
return result
print(sumatoria(10))
Y aunque válido, no es una implementación eficiente porque hace n iteraciones con al menos una operación en cada iteración.
Para mejorar la eficiencia de la función, podemos intentar hacer un análisis matemático y llegar a que la función sumatoria no es más que un polinomio de grado dos:
Y su código Python es algo así:
def sumatoria(n):
return n * (n + 1) // 2
Mucho más eficiente ahora, ¿no? No importa qué tan grande sea n, ahora la sumatoria se calcula con un número fijo (además muy bajo) de operaciones aritméticas.
Ahora, entrando en cuestión, la pregunta publicada aquí tiene ese tinte. Quien pregunta quiere saber las habilidades que tiene el desarrollador para abordar este tipo de situaciones. En mi opinión personal, la vacante debe ser para un cargo muy específico (ya que no todos los programadores saben matemáticas, desafortunadamente), o el entrevistador es muy troll poniendo ese tipo de preguntas...
Solución
IMPORTANTE: Tener en cuenta que con valores muy grandes, los lenguajes de programación pueden comenzar a producir resultados erroneos. Por ejemplo, JavaScript tiene esta joyita:
var x = 9007199254740992
var y = -x
(x == (x + 1)) // true !
(y == (y - 1)) // also true !
Así que si no puedes reproducir mis resultados, 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 inesperadamente. En mi opinion la respuesta que busca el reclutador no radica en el código en sí, sino en el enfoque que se le debe dar.
TEMA: Exponenciacion de matrices:
Inicialmente tenemos esto
resultado=A+4B+C+3D
que hablando en terminos de iteraciones es algo asi:
resultado(i)=A(i-1)+4B(i-1)+C(i-1)+3D(i-1)
y algo asi como esto:
A0=1
B0=1
C0=1
D0=1
# y
Ai=Bi-1
Bi=Ci-1
Ci=Di-1
Di=resultado(i)=A(i-1)+4B(i-1)+C(i-1)+3D(i-1)
Como A en la iteración i es igual a B en la iteración i-1, podemos hacer una representación matricial de A:
| Ai-1|
Ai = |0, 1, 0, 0| x | Bi-1|
| Ci-1|
| Di-1|
y repetir esto para B y C:
|Ai| |0, 1, 0, 0| | Ai-1|
|Bi| = |0, 0, 1, 0| x| Bi-1|
|Ci| |0, 1, 0, 1| | Ci-1|
| Di-1|
Y como Di es igual a la función resultado en la iteración i menos 1, que está en función de A, B, C y D, nuestra representación final es la siguiente::
|Ai| |0, 1, 0, 0| | Ai-1|
|Bi| = |0, 0, 1, 0| x| Bi-1|
|Ci| |0, 1, 0, 1| | Ci-1|
|Di| |1, 4, 1, 3| | Di-1|
Esto es lo mismo que:
|An+1| |0, 1, 0, 0| | An|
|Bn+1| = |0, 0, 1, 0| x| Bn|
|Cn+1| |0, 1, 0, 1| | Cn|
|Dn+1| |1, 4, 1, 3| | Dn|
Y si se fijan bien, la matriz del lado derecho es lo que queremos calcular (en realidad, solo queremos Dn)..
Por otro lado, podemos representar dicha matriz como sigue, donde Tn es una matriz con exponente n, que si lo despejamos encontramos la solución al problema.
|An| | 1|
|Bn| = Tn x| 1|
|Cn| | 1|
|Dn| | 1|
Con estas dos representaciones, como reclutador estaría contento y asumiría que se entiende el propósito del ejercicio.
La resolución de la matriz, matemáticamente hablando, sería absurdo ponerla aquí, porque además de ser bastante complejo el asunto, la pregunta se alargaría mucho y hay bastantes libros al respecto.
Editado
Gracias a una respuesta de un usuario, me percate de que la solucion numerica al problema se puede encontrar evitando que los 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):
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
Finalmente 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
dato de interes:
>print(2023 ** 100)
>3977299330281882403306574735225337717599631172062412445045578274405450110120677174505186273779312535365746310019472644285894036169695910906506233118452300676652476856018828588020899113867978825566482076357081191135854217234411796915745355130981797659740171549912770735205485217369751214708750973368807626092441067706281896347276001
Fin edicion
8042318513
te confirmo que ese resultado es correcto