2

Estoy intentando resolver el siguiente algoritmo para una propuesta laboral, y consigo tener el resultado que solicitan en las 10 primeras iteraciones, pero luego al querer aplicarlo para 100 iteraciones y sacar el valor de la variable D modulo 10000000000 (ultimos 10 digitos) el resultado ya me arroja otro resultado completamente distinto: Dejo el acertijo a continuacion para saber si alguien resolvio algo similar alguna vez:

¿Cuál sería el resultado de ejecutar el siguiente pseudocódigo? teniendo en cuenta que el dispositivo dispone de los recursos necesarios para finalizar su ejecución. Los puntos a continuación son para indentación.

función solucionarRompecabezas(N) {
.var_A = 1
.var_B = 1
.var_C = 1
.var_D = 1

.para i en el rango de 1 a N {
..resultado = 3 * var_D + 1 * var_C + 4 * var_B + 1 * var_A
..var_A = var_B
..var_B = var_C
..var_C = var_D
..var_D = resultado
.}

.devolver var_D % 10000000000 // últimos 10 dígitos de var_D
}

mostrar solucionarRompecabezas(10)
mostrar solucionarRompecabezas(100)
mostrar solucionarRompecabezas(pot(2023, 100)) // 2023 elevado a la 100

Salida 902441 8042318513 ??

6
  • Mira Cómo preguntar para que tu pregunta sea mejor recibida. También, aprovecha y haz el recorrido de bienvenida para entender mejor cómo funcionamos y de paso obtener tu primera medalla! No entiendo siquiera como resolves eso o sea cual es el problema??? quien te dice que tu resultado esta mal?? como lo ejecutas???
    – gbianchi
    Commented el 30 jun. a las 23:29
  • 8042318513 te confirmo que ese resultado es correcto
    – Yussef
    Commented el 1 jul. a las 1:31
  • Hola Emanuel, bienvenido... 2023 elevado a la 100... puede que este muy dormido, pero no creo que tengas una computadora capaz de manejar ese número. Commented el 1 jul. a las 17:20
  • 1
    Tu comentario aca no sirve para absolutamente nada... nadie lo va a leer... esto no es una red social, aprende a usar el sitio...
    – gbianchi
    Commented el 2 jul. a las 17:12
  • 1
    Yo puedo aprender a utilizar el sitio. Estoy dando mis primeros pasos y probablemente lo haga. Por tu parte dudo que aprendas de empatía, a cómo responder y tratar a la gente. Saludos Commented el 3 jul. a las 21:49

3 respuestas 3

5

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í

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í

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

6
  • Muchas gracias por tu respuesta, valoro enormemente que te hayas tomado el tiempo en darme esta explicacion , que a mi entender, termino viendo que no era tan sencillo, estaba intentando resolverlo para una prueba tecnica, en la cual me solicitaban lograr que el valor adquirido para var_D % 1000000000 fuese los resultados esperados, al intentar resolverlo con PSeInt en Pseudocodigo lograba hallar el primer valor, pero luego ya en el segundo, el codigo me arrojaba otro valor completamente distinto. Muchas gracias por tu respuesta y me sirvio de mucho! Commented el 2 jul. a las 1:41
  • 1
    @EmanuelMuises si es pseint no es psudocodigo.. es pseint.. es un lenguaje con una estructura.. si hubieras peusto que era en pseint, era otra cosa totalmente diferente....
    – gbianchi
    Commented el 2 jul. a las 13:24
  • 1
    No.. la respuesta es todo... la respuesta debe ser correcta.. toda la parte matematica es muy bonita, pero este sitio es sobre programacion.. es mas.. tu respuesta deberia estar estructurada al reves.. este es el codigo, y esta es la explicacion teorica... y el codigo si debe resolver el problema.. y el cartel esta muy de mas.. y si no lo sacas vos, lo voy a sacar yo. Es puro ruido...
    – gbianchi
    Commented el 2 jul. a las 17:10
  • no voy a dejar que borres una buena respuesta.. pero si la vamos a dejar mas bonita...
    – gbianchi
    Commented el 2 jul. a las 17:35
  • 1
    Retiro mis comentarios anteriores ahora que das los resultados correctos. Estoy impresionado. No te pierdas del sitio.
    – Candid Moe
    Commented el 2 jul. a las 23:19
1

Traducido a Python:

def solucionarRompecabezas(N):
    var_A = 1
    var_B = 1
    var_C = 1
    var_D = 1

    for i in range(1, N + 1):
        resultado = 3 * var_D + 1 * var_C + 4 * var_B + 1 * var_A
        var_A = var_B
        var_B = var_C
        var_C = var_D
        var_D = resultado


    return var_D % 10000000000


print(solucionarRompecabezas(10))
print(solucionarRompecabezas(100))
#print(solucionarRompecabezas(2023 ** 100))

Observaciones:

  1. El rango del for. En Python, range(1, N) produce 1, 2, ... N - 1. Si quieres llegar hasta N, tienes que sumarle 1 al límite superior: range(1, N + 1). Siempre hay que revisar si el rango incluye o no el valor final, según que lenguaje o pseudolenguaje estás usando.

  2. 2023 ** 100 es un número bien grande y ahí el programa se va a quedar pegado un largooooo tiempo.

El código produce resultados

902441
8042318513
1
  • Muchas gracias por tu respuesta! Commented el 2 jul. a las 1:42
1

Me parece que tu problema se produce al estar utilizando números excesivamente grandes.

Debes recordar que lo importante son los 10 últimos números, por lo que desde el digito 11 hacia la izquierda no son relevantes y lo puedes truncar. Esto gracias a que todas las operaciones que realizas son sumas y multiplicaciones.

Por ejemplo: Para simplificar diremos que nos interesa el último número de la operación (12312 + 47456) * 18

El resultado de la operación es 1075824

En realidad, solo debemos preocuparnos del primer digito (el más de la derecha)

(2+6) * 8 = 64

El último digito es 4


Para tu caso son los 10 últimos números, entonces realizas la operación modulo en cada iteración:

función solucionarRompecabezas(N) {
.var_A = 1
.var_B = 1
.var_C = 1
.var_D = 1

.para i en el rango de 1 a N {
..resultado = 3 * var_D + 1 * var_C + 4 * var_B + 1 * var_A
..var_A = var_B
..var_B = var_C
..var_C = var_D
..var_D = resultado  % 10000000000 // Aquí recortamos el número
.}

.devolver var_D % 10000000000 // últimos 10 dígitos de var_D
}

mostrar solucionarRompecabezas(10)
mostrar solucionarRompecabezas(100)
mostrar solucionarRompecabezas(pot(2023, 100)) // 2023 elevado a la 100
0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.