@LucasDamian Vaya si lo he notado! A principios de año no estuvo, luego volvió hacia primavera-verano y ahora parece que no está otra vez. Cuando se va, nos deja a Mauricio y a mi prácticamente "solos ante el peligro" :-)
@MauricioContreras jaja. No, pero es cierto que somos pocos los que solíamos responder en la etiqueta python, y que tus respuestas y las de FJSevilla son siempre de alta calidad. Si he observado, de septiembre a acá, algunos colaboradores nuevos que también dan muy buenas respuestas
huy, tienes razón! me había liado porque tú y yo también solemos estar solos ante el peligro pero en otro frente, que es el chat los fines de semana XD
a quien quería referirme era a Patricio Moracho! pero tu respuesta también fue buena, eh? XXD
Pues una familia de problemas que no se puede resolver en tiempo polinomial. O dicho de otra forma, que en ellos el tiempo que se necesita para resolverlos crece exponencialmente a medida que el tamaño de la entrada es más grande
en tu caso, que si para encontrar la solución para un número N tarda 1 segundo, para el número 2N no tarda 2 segundos, sino quizás 4. A medida que crece N, el tiempo crece, pero a un ritmo mucho mayor (2^N por ejemplo).
Este tipo de problemas son por desgracia muy comunes en el mundo de la computación. Lo de P/NP es una forma de medir la complejidad de un problema
generalmente los problemas NP son aquellos en los que buscas una solución óptima bajo algún criterio (en tu caso el cirterio era que el producto sea lo mayor posible), y en los que no es posible encontrar un algoritmo que "ataje", sino que la única forma de dar con el óptimo es examinar (casi) todos los casos posibles
Por ejemplo, un problema NP que me recuerda mucho al que tú planteaste es el problema de "la mochila". Tienes una mochila con capacidad máxima para llevar, digamos 20Kg. Y tienes un montón de objetos, cada uno de ellos con un peso y con un valor. El problema es rellenar la mochila con todos los objetos que puedas, de forma que el valor de lo transportado sea el máximo posible (sin pasarse del peso de 20Kg)
Yo lo acabo de resolver en python, mira a ver si puedes aprovecharlo
def test(n):
a, b = 0, 1
result = [a]
found = False
while (a < n**.5):
if a*b == n:
found = True
break
result.append(b)
a, b = b, a+b
if not found:
result.append(b)
return result[-2:] + [found]
en cuanto a sea mayor, ya no vas a encontrar solución, pues b será aún mayor también por lo que su producto será mayor que a**2 y por tanto mayor que n
La traducción a JS es directa, por cierto. Esto me ha funcionado:
test = function(n){
var [a, b] = [0, 1];
var found = false;
while (a < n**.5) {
if (a*b == n) {
found = true;
break;
}
[a, b] = [b, a+b];
}
return [a, b, found];
}
@IsraelGonzález lo de asignar a [a, b]? Yo tampoco sabía que JS pudiera hacerlo, pero como en python estoy tan acostumbrado a verlo, y ya que JS ha ido copiando cosas de Python, he buscado si JS podría y he encontrado que sí
en algunos casos regresa falso con los ultimos numeros que probo
y se pasa en un n+1
function productFib(prod) { let a = 0, b = 1; found = false; while (a < prod ** .5) { if (a * b == prod) { found = true; break } else if (a * b > prod) { return [a, b, found] } [a, b] = [b, a + b]; } return [a, b, found] }
@IsraelGonzález Pero no lo veo... 610*987 es solo 602070, aún por debajo de 447577
ah, no, no
que está por encima, me bailó una cifra
Sí, no acabo de entender por qué, pero puede ser cosa de la raiz cuadrada. Y eso me ha dado una idea para quitar esa raiz y dejar todo mucho más comprensible
test = function(n){
var [a, b] = [0, 1];
var found = false;
while (a*b <= n) {
if (a*b == n) {
found = true;
break;
}
[a, b] = [b, a+b];
}
return [a, b, found];
}
