elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Los 10 CVE más críticos (peligrosos) de 2020


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Retos C/C++
0 Usuarios y 2 Visitantes están viendo este tema.
Páginas: 1 2 3 4 5 [6] 7 8 9 Ir Abajo Respuesta Imprimir
Autor Tema: Retos C/C++  (Leído 40,324 veces)
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #50 en: 27 Agosto 2010, 02:38 am »

No entiendo del todo el código porque no conozco el lenguaje, pero por lo que veo vas de uno en uno dentro del rango y vas haciendo el algoritmo hasta acabar. Hay una manera de hacerlo mucho más rápido.

Como pista, intenta no calcular los pasos para ningún número más de una sola vez ;)


En línea

[D4N93R]
Wiki

Desconectado Desconectado

Mensajes: 1.646


My software never has bugs. Its just features!


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #51 en: 27 Agosto 2010, 02:51 am »

ghastlyX, dices que hay una manera más rápido de hacerlo, no lo comprendo ya que como se si para un número que aún no he calculado cuál va a ser el resultado?

Es decir, si es un rango [1..10] para que comprobar si ya lo hice con 7 por ejemplo, si se que solo va a salir una sola vez. A menos de que haya entendido mal :D


En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #52 en: 27 Agosto 2010, 02:56 am »

Si tu intervalo es el [1, 10], por ejemplo cuando mires el 3 pasarás por el 10, que luego volverás a calcular cuando llegues al 10. Lo que comentaba era evitar estas repeticiones de cálculos, puesto que si el intervalo es grande (según el enunciado los números del intervalo pueden llegar a 1000000), la diferencia es notoria.
En línea

[D4N93R]
Wiki

Desconectado Desconectado

Mensajes: 1.646


My software never has bugs. Its just features!


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #53 en: 27 Agosto 2010, 03:02 am »

Ah ok!! ya lo pillo xD :P vale.. a ver si me sale xD que eso complica un poco las cosas!

Y tienes razón, eso podría mejorar mucho el performance del código.

EDIT: ghastlyX la única forma que se me ocurre de hacerlo como tu dices creo que va a ser muy lenta. Ni idea.. xD
« Última modificación: 27 Agosto 2010, 03:15 am por [D4N93R] » En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #54 en: 27 Agosto 2010, 03:20 am »

La gracia es que sea más rápido, si no mal vamos. Simplemente guarda lo que hayas calculado una vez. Cada vez que pases por un número, antes de calcularlo mira si ya está hecho.
En línea

[D4N93R]
Wiki

Desconectado Desconectado

Mensajes: 1.646


My software never has bugs. Its just features!


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #55 en: 27 Agosto 2010, 03:44 am »

Justamente eso había hecho, pero no se, en casos donde esté iterando números muy grandes, tengo que revisar una lista en cada giro. Tengo que hacerle pruebas de rendimiento a ver que tal.
 

Saludos!
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #56 en: 27 Agosto 2010, 03:58 am »

Si tienes que consultar una lista es muy lento, la idea es usar un vector, para, por ejemplo, el primer millón de números. Obviamente se pasará de ese límite calculando ciertos números, para esos simplemente si ocurre repetiré los cálculos, puesto que no tenemos memoria infinita. Así al menos el intervalo completo [1, 1000000] lo hace de forma instantánea el siguiente programa (aunque repita cálculos si sale del rango):
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. ll f(ll n, vector<ll>& v) {
  8.    if (n == 1) return 1;
  9.    if (n >= v.size()) return 1 + ((n%2 == 1)?f(3*n + 1, v):f(n/2, v));
  10.    if (v[n] == -1) v[n] = 1 + ((n%2 == 1)?f(3*n + 1, v):f(n/2, v));
  11.    return v[n];
  12. }
  13.  
  14. int main() {
  15.    vector<ll> v(1000000, -1);
  16.    ll a, b;
  17.    while (cin >> a >> b) {
  18.        ll res = 0;
  19.        for (ll i = min(a,b); i <= max(a,b); ++i) res = max(res, f(i, v));
  20.        cout << a << " " << b << " " << res << endl;
  21.    }
  22. }

De hecho esto sería una manera de resolver el problema usando memoization.

Para poder guardar todos los valores, ya que un vector no se puede usar (demasiada memoria) y una lista como tú decías es demasiado lenta (hay que recorrerla entera en el peor caso, coste lineal), la mejor manera que se me ocurre es usar un árbol binario balanceado que permita consultar si está calculado (y su valor) en tiempo logarítmico. Estos están implementados en los contenedores map de la STL de C++. En este problema en concreto no sé qué sería más rápido, si guardar todo con maps aumentando el coste de cada consulta o bien hacer cada consulta instántanea consultando un vector a costa de repetir los cálculos de números fuera del rango del vector.
En línea

[D4N93R]
Wiki

Desconectado Desconectado

Mensajes: 1.646


My software never has bugs. Its just features!


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #57 en: 27 Agosto 2010, 04:14 am »

Si exacto, ese es el problema, yo pensé usar un binarytree pero no sabes la flojera que me dió. :/

Hice las dos pruebas, con vector y con list. Obviamente Vector es mucho más rápido en grandes intervalos. En pequeños no se nota la diferencia entre ambos.

Un saludo!
En línea

[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.513

El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #58 en: 27 Agosto 2010, 04:28 am »

:xD GhastlyX publicaste la respuesta... pon el proximo reto.
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #59 en: 27 Agosto 2010, 04:50 am »

Reto #14
Como aún no he mirado los de este año, os dejo uno de la IOI del año pasado, a mi opinión, el más fácil de todos y con diferencia. Es bastante asequible.
http://www.ioi2009.org/GetResource?id=1271
En línea

Páginas: 1 2 3 4 5 [6] 7 8 9 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Retos .Net « 1 2 3 »
Ejercicios
[D4N93R] 20 14,326 Último mensaje 6 Diciembre 2010, 03:26 am
por final_frontier
Concursos y retos
Programación General
lnvisible 0 1,386 Último mensaje 12 Diciembre 2010, 19:44 pm
por lnvisible
cuando consigo nuevos retos? « 1 2 »
WarZone
Tyrz 11 3,942 Último mensaje 15 Junio 2011, 23:11 pm
por [-Franko-]
Desarrollo de Retos Informaticos
Desarrollo Web
Sinedra 0 2,370 Último mensaje 23 Febrero 2011, 19:23 pm
por Sinedra
Retos C/C++
Programación C/C++
N0body 5 9,101 Último mensaje 9 Mayo 2011, 09:54 am
por ghastlyX
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines