Generarlmente en programación los números tienen un espacio de memoria asignado, este espacio limita al número a un rango de valores validos, por ejemplo
- Un entero de 32 bits con signo:
[−2147483647, +2147483647]
- Un entero de 32 bits sin signo:
[0 , 4294967295]
El límite dependerá del tipo de número (int, long, double, float, etc), el lenguaje y la arquitectura.
Cuando te sales de los rangos válidos, suceden cosas extrañas (que también varían dependiendo del lenguaje) y ese esMe parece que tu problema. El algoritmo hace crecer rápidamente los números y te sales de rango.
Por ejemplo, tu código en javasript:
function solucionarRompecabezas(N) {
let var_A = 1;
let var_B = 1;
let var_C = 1;
let var_D = 1;
for (let i = 1; i <= N; i++){
let 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;
}
console.log( solucionarRompecabezas(10));
console.log( solucionarRompecabezas(100));
Como puedes apreciar no da el resultado esperado en el segundo caso, tal como te pasa a ti.
Pero si ahora cambiamos de tipo de datos a BigInt, podrás ver cómo funciona:
Notar el sufijo n
en los se produce al estar utilizando números que indicarán que son del tipo BigInt
function solucionarRompecabezas(N) {
let var_A = 1n;
let var_B = 1n;
let var_C = 1n;
let var_D = 1n;
for (let i = 1; i <= N; i++){
let resultado = 3n * var_D + 1n * var_C + 4n * var_B + 1n * var_A;
var_A = var_B;
var_B = var_C;
var_C = var_D;
var_D = resultado;
}
return var_D % 10000000000n;
}
console.log( solucionarRompecabezas(10).toString());
console.log( solucionarRompecabezas(100).toString());
Por último, sobre el problema del pot(2023, 100)
, es un número monstruosamente grande. Solo pot(2023, 3)
es 8279186167
excesivamente grandes. Ahora recordemos que este número nos indica la cantidad de iteraciones, por lo que si logras encontrar un ciclo repetitivo podrías encontrar la solución
Si, por ejemplo, detectas que pot(2023, 10)
da el mismo resultado que pot(2023, 20)
, habrías encontrado un ciclo y ya no es necesario calcular hasta elevado a 20
Además, debesDebes recordar que lo importante son los 10 últimoúltimos números, por lo que desde el digito 11 hacia la izquierda no es relevanteson relevantes y lo puedes truncar. Esto gracias a que todas las operaciones que realizas son sumas y multiplicaciones.
Para simplificarloPor ejemplo: digamosPara simplificar diremos que solo tenos interesa el último dígitonúmero de una sumala 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) 12312312* 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 = 21
.var_D = 1
+34647456
.para i en el rango de 1 +6a N {
----------..resultado = =>3 * var_D ---+ 1 * var_C + 4 * var_B + 1 * var_A
..var_A xxxxxxx8= var_B
..var_B = var_C
..var_C = var_D
..var_D = resultado 8% 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
Simplemente te olvidas de los otros números, lo cual simplifica el calculo
Entonces, si haces el % 10000000000
dentro del for
no necesitas usar BigInt
en el ejemplo de javascript e igualmente da un resultado correcto
function solucionarRompecabezas(N) {
let var_A = 1;
let var_B = 1;
let var_C = 1;
let var_D = 1;
for (let i = 1; i <= N; i++){
let 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; //Solo trabajamos con los último 10 digitos
}
return var_D % 10000000000;
}
console.log( solucionarRompecabezas(10));
console.log( solucionarRompecabezas(100));