[![introducir la descripción de la imagen aquí][1]][1] 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:
[![introducir la descripción de la imagen aquí][2]][2]
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:
[![introducir la descripción de la imagen aquí][3]][3]
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 (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 manera. También es posible que mi código esté incorrecto (posiblemente porque programe a la ligera), pero la respuesta a esta cuestión 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.
En ese orden de ideas, como dato 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 y se comporta según lo deseado, pero como mencioné antes, puede que con valores grandes sea necesario hacer ajustes.
import numpy as np
# A y B son matrices, no son var_A ni var_B
def matrix_mult(A, B):
return np.dot(A, B)
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 8042318513
dato de interes:
>print(2023 ** 100)
>3977299330281882403306574735225337717599631172062412445045578274405450110120677174505186273779312535365746310019472644285894036169695910906506233118452300676652476856018828588020899113867978825566482076357081191135854217234411796915745355130981797659740171549912770735205485217369751214708750973368807626092441067706281896347276001
**Fin edicion**
[1]: https://i.sstatic.net/fzNM3Og6.png
[2]: https://i.sstatic.net/xV6Voaxi.png
[3]: https://i.sstatic.net/9ntF8gbK.png