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

 

 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [C]Juego aburrido. Problema de optimización.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: [C]Juego aburrido. Problema de optimización.  (Leído 3,787 veces)
GoKGz

Desconectado Desconectado

Mensajes: 13



Ver Perfil
[C]Juego aburrido. Problema de optimización.
« en: 5 Diciembre 2016, 18:52 pm »

Hola.

Este es un problema de optimización parecido al problema de las monedas.

El juego es así, dado un n:

                · Si n es divisible por 3, n = n/3
                · SI n es divisible por 2, n = n/2
                · Si no cumple las anteriores, n = n -1 .

Ahora lo que tengo que conseguir es el menor número de operaciones posibles.

Si nosotros lo pensamos así:
Código
  1. void juego (int n){
  2.  
  3.        if (n == 1) return ;
  4.  
  5.        if (n%3 == 0){
  6.                juego(n/3);
  7.                printf ("Op.3\n");
  8.        }
  9.        else if (n%2 == 0){
  10.                juego(n/2);
  11.                printf ("Op.2\n");
  12.        }
  13.        else{
  14.                juego(n-1);
  15.                printf ("Op.1\n");
  16.        }
  17. }
  18.  

No conseguiríamos el óptimo, ya que si por ejemplo pongo 10
El resultado es:
Código:
10/2 = 5
5-1   = 4
4/2   = 2
2/2   = 1

Utilicé 4 monedas para resolver el problema, cuando en realidad la solución óptima es:
Código:
10-1 = 9
9/3   = 3
3/3   = 3

Estoy intentando de resolver el óptimo algoritmo todavía estoy pensando, pero cualquier respuesta me vendría bien.


Saludos.


En línea

COME AT ME BRAAAAH.
engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.498



Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #1 en: 5 Diciembre 2016, 19:01 pm »

a menos que establezcas una buena formula matemática, es difícil que tu programa halle el camino más optimo sin probar opciones...


En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
GoKGz

Desconectado Desconectado

Mensajes: 13



Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #2 en: 6 Diciembre 2016, 08:24 am »

Esa es tu única respuesta, y medio obvia además?

Jajaja, saludos.
En línea

COME AT ME BRAAAAH.
engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.498



Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #3 en: 6 Diciembre 2016, 10:48 am »

Estás frente a un problema np, que esperas?
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
hsk75rv

Desconectado Desconectado

Mensajes: 36



Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #4 en: 6 Diciembre 2016, 11:04 am »

Me podeis explicar en que consiste el juego, es decir, el objetivo es ir reduciendo el número hasta que el módulo sea 1 con el mínimo de divisiones?

En línea

engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.498



Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #5 en: 6 Diciembre 2016, 17:00 pm »

Me podeis explicar en que consiste el juego, es decir, el objetivo es ir reduciendo el número hasta que el módulo sea 1 con el mínimo de divisiones?



Citar
El juego es así, dado un n:

                · Si n es divisible por 3, n = n/3
                · SI n es divisible por 2, n = n/2
                · Si no cumple las anteriores, n = n -1 .

Ahora lo que tengo que conseguir es el menor número de operaciones posibles.
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
GoKGz

Desconectado Desconectado

Mensajes: 13



Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #6 en: 6 Diciembre 2016, 17:31 pm »

Creo que tiene la misma lógica que esto:

Problema de la moneda

El denominado "problema de la moneda" es el siguiente: dados diferentes tipos de monedas, cada uno con un valor diferente, y una cantidad C, ¿cuál es el menor número de monedas necesarias para devolver el cambio C?

Para las monedas del sistema monetario del euro existe una estrategia básica para resolver el problema:

Coge una moneda con el valor V más grande tal que V <= C
Repite desde 1 con el valor C - V hasta que C = 0
Sin embargo, esta estrategia no funciona para valores aleatorios de las monedas. Por ejemplo, si las monedas tienen valores 1, 4 y 6, el número mínimo de monedas para hacer un cambio de 8 es 2 monedas de 4 (cogiendo una moneda de 6 necesitamos como mínimo 3 monedas en total).

En general, para resolver el problema de la moneda tenemos que probar todas las posibles combinaciones de coger monedas. Para la cantidad C, las posibilidades son: coger una moneda del primer tipo, coger una moneda del segundo tipo, etc. En cada caso se genera un subproblema del mismo tipo por resolver. Por ejemplo, si cogemos una moneda de valor 1, recursivamente tenemos que encontrar la mejor manera de devolver el cambio C-1, y sumarle 1 para obtener una posible solución para C. La solución para C es la mejor entre todas estas posibles maneras de coger la primera moneda.

Si denominamos A(C) el subproblema para la cantidad C, una definición resursiva para el problema es:

A(0) = 0 (si la cantidad es 0 no necesitamos ninguna moneda)
A(C) = min(1 + A(C-m_1), 1 + A(C-m_2), ..., 1 + A(C-m_k))

donde k es el número total de monedas y m_i es el valor de la moneda i. Ahora podemos escribir una solución basada en la programación dinámica:

Código
  1. int M[3] = {1, 4, 6};  // tipos de moneda diferentes
  2. int A[100001];
  3. A[0] = 0;
  4. for (int C = 1; C <= 100000; ++C) {
  5.   A[C] = 1000000000; // número grande para empezar
  6.   for (int i = 0; i < 3; ++i)
  7.      if (M[i] <= C && 1 + A[C-M[i]] < A[C])
  8.         A[C] = 1 + A[C-M[i]];
  9. }
Después del bucle el array A contendrá el resultado para cada C en el rango [0, 100000].

engel lex, me das una mano para calcular la formula de la función del principio? Por que esto me preguntaron en el final de Estructura de Datos, aprobé con 6 pero no supe hacer ese ejercicio.

Había que hacer la fórmula y luego programarlo en "programación dinámica"

Agradezco cualquier respuesta.
« Última modificación: 6 Diciembre 2016, 17:34 pm por GoKGz » En línea

COME AT ME BRAAAAH.
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #7 en: 6 Diciembre 2016, 17:34 pm »

No se si será lo que buscas o no, pero yo lo plantearía de la siguiente forma.

n_{0} = 2^{r_{0}}3^{s_{0}}n'_{0},\ \ mcd(2^{r_{0}}3^{s_{0}},n'_{0})=1

Así que por narices tendrás que dividir r0 veces por 2 y s0 veces por 3 y al menos harás r0+s0 llamadas.

Si n'0=1 ya habrás terminado, sino, repites el proceso anterior con

n'_{0} - 1 = n_{1} = 2^{r_{1}}3^{s_{1}}n'_{1},\ \ mcd(2^{r_{1}}3^{s_{1}},n'_{1})=1

Así hasta encontrar un n'k = 1.

El problema se traduce en encontrar la máxima potencia, r,  de dos que divide a un número, la máxima potencia, s, de tres que lo divide, sumar los exponentes (r+s) y a esto sumarle el resultado de volver a aplicar el proceso al termino que queda al dividir el número por 2r3s y restarle uno.
« Última modificación: 6 Diciembre 2016, 17:46 pm por do-while » En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
MCKSys Argentina
Moderador Global
***
Desconectado Desconectado

Mensajes: 4.969


Diviértete crackeando, que para eso estamos!


Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #8 en: 6 Diciembre 2016, 17:55 pm »

No soy un experto en el tema, pero tomando tu ejemplo:

No conseguiríamos el óptimo, ya que si por ejemplo pongo 10
El resultado es:
Código:
10/2 = 5
5-1   = 4
4/2   = 2
2/2   = 1

Utilicé 4 monedas para resolver el problema, cuando en realidad la solución óptima es:
Código:
10-1 = 9
9/3   = 3
3/3   = 3

Y si tenemos en cuenta las "reglas" que pones:


                · Si n es divisible por 3, n = n/3
                · SI n es divisible por 2, n = n/2
                · Si no cumple las anteriores, n = n -1 .


Ese si no se cumplen las anteriores haría que tu ejemplo sea inválido. Como 10 es múltiplo de 2, entonces lo que propones como óptimo estaría mal y la 1era solución sería correcta.

Pero, bueh, como dije, no soy experto en el tema y quizás no entendí bien el problema.

Saludos!
En línea

MCKSys Argentina

"Si piensas que algo está bien sólo porque todo el mundo lo cree, no estás pensando."

GoKGz

Desconectado Desconectado

Mensajes: 13



Ver Perfil
Re: [C]Juego aburrido. Problema de optimización.
« Respuesta #9 en: 6 Diciembre 2016, 18:04 pm »

No se si será lo que buscas o no, pero yo lo plantearía de la siguiente forma.

n_{0} = 2^{r_{0}}3^{s_{0}}n'_{0},\ \ mcd(2^{r_{0}}3^{s_{0}},n'_{0})=1

Así que por narices tendrás que dividir r0 veces por 2 y s0 veces por 3 y al menos harás r0+s0 llamadas.

Si n'0=1 ya habrás terminado, sino, repites el proceso anterior con

n'_{0} - 1 = n_{1} = 2^{r_{1}}3^{s_{1}}n'_{1},\ \ mcd(2^{r_{1}}3^{s_{1}},n'_{1})=1

Así hasta encontrar un n'k = 1.

El problema se traduce en encontrar la máxima potencia, r,  de dos que divide a un número, la máxima potencia, s, de tres que lo divide, sumar los exponentes (r+s) y a esto sumarle el resultado de volver a aplicar el proceso al termino que queda al dividir el número por 2r3s y restarle uno.

A mi me suena más a esto: A(C) = min(1 + A(C-m_1), 1 + A(C-m_2), ..., 1 + A(C-m_k))
Algo con funciones mínimo, es prácticamente igual que el problema de la moneda.


No soy un experto en el tema, pero tomando tu ejemplo:

Y si tenemos en cuenta las "reglas" que pones:

Ese si no se cumplen las anteriores haría que tu ejemplo sea inválido. Como 10 es múltiplo de 2, entonces lo que propones como óptimo estaría mal y la 1era solución sería correcta.

Pero, bueh, como dije, no soy experto en el tema y quizás no entendí bien el problema.

Saludos!

La onda es hacer un algoritmo que utilice el menor numero de monedas posibles, por eso puse un contraejemplo de que mi algoritmo no es el mejor, entendes?
En línea

COME AT ME BRAAAAH.
Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Estoy Aburrido... Recomiendenme un Juego !!
Juegos y Consolas
....Gusto.... 1 1,110 Último mensaje 6 Noviembre 2004, 18:22 pm
por ¤ Nerviozzo ¤
[Opinion] Problema acerca de optimización en código - Uso dinámico de arrays « 1 2 3 »
Programación C/C++
Miky Gonzalez 21 4,930 Último mensaje 19 Noviembre 2014, 18:51 pm
por Miky Gonzalez
Ayuda, problema de optimización de memoria
GNU/Linux
JonaLamper 0 892 Último mensaje 27 Mayo 2015, 15:57 pm
por JonaLamper
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines