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
| | | |-+  Programación algorítmica: unos problemillas
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] Ir Abajo Respuesta Imprimir
Autor Tema: Programación algorítmica: unos problemillas  (Leído 10,290 veces)
GroK


Desconectado Desconectado

Mensajes: 681


...I have become comfortably numb...


Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #10 en: 9 Septiembre 2008, 02:39 am »

Buenas, ya he vuelto :D

Pues al final me he metido con el de grafos, me ha gustado mucho xD Y por cierto, decirte que me falto implementarle lo de varios casos por falta de tiempo, es decir, la entrada al programa es identica, solo que obvia el numero de casos y solo te resolvera el primero, si quieres probar otros casos hay que ejecutar de nuevo el programa (sorry, obviamente no presentaria eso asi en un concurso xDD)

Pero nada, queria que simplemente le echaras un vistazo a la parte principal del programa, el algoritmo y tal que es lo que importa al fin y al cabo, y ver que cambiarias tu o como lo harias (seguro que se puede hacer mas eficientemente que el mio :))

Aqui te lo dejo (Otra cosa, solo lo he hecho en pascal, en cuanto vuelva a tener un rato disponible intentare pasarlo a C a ver):

Código
  1. program circulos;
  2.  
  3. const
  4. MAX = 20;
  5.  
  6. type
  7. TValores  = Record
  8.                Asignado : boolean;
  9. Color       : boolean; { 'True' = Verde; 'False' = Amarillo }
  10. End;
  11. TVertices = array [0..MAX] of TValores;
  12. TCasos = array [1..MAX] of TVertices;
  13.  
  14. var
  15. nCasos : integer;
  16. nVertices : integer;
  17. nAristas : integer;
  18. inicio, fin  : integer;
  19. vertices : TVertices;
  20. casos : TCasos;
  21. flag : boolean;
  22. i : integer;
  23.  
  24. procedure init_vertices (var c : TCasos);
  25.  
  26. var
  27. i, j : integer;
  28.  
  29. begin
  30.  
  31. for i := 1 to MAX do
  32. for j := 0 to MAX do
  33. begin
  34. c[i][j].Asignado := false;
  35. c[i][j].Color := false;
  36. end;
  37.  
  38. end;
  39.  
  40. function evalua (var v : TVertices; inicio, fin : integer) : boolean;
  41.  
  42. begin
  43.  
  44. if (v[inicio].Asignado = false) and (v[fin].Asignado = false) then { si ninguno ha sido asignado aun }
  45. begin
  46. v[inicio].Asignado := true;
  47. v[inicio].Color := true;
  48. v[fin].Asignado := true;
  49. v[fin].Color := false;
  50. evalua := true;
  51. end
  52. else
  53. begin
  54. if (v[inicio].Asignado) xor (v[fin].Asignado) then { si uno de los dos esta asignado }
  55. begin
  56. if v[fin].Asignado = false then
  57. begin
  58. v[fin].Asignado := true; { lo marcamos como coloreado }
  59. v[fin].Color := not v[inicio].Color; { y le ponemos el color contrario al del otro vertice }
  60. end
  61. else
  62. begin  { en caso de que el que no estuviese coloreado aun fuera el vertice inicial, lo mismo para este }
  63. v[inicio].Asignado := true;
  64. v[inicio].Color := not v[fin].Color;
  65. end;
  66. evalua := true;
  67. end
  68. else
  69. begin  { si entramos aqui es porque ambos ya estan coloreados, comprobemos si es incompatible }
  70. if v[inicio].Color = v[fin].Color then
  71. evalua := false
  72. else
  73. evalua := true;
  74. end;
  75. end;
  76.  
  77. end;
  78.  
  79. { -- MAIN --}
  80.  
  81. begin  
  82.  
  83. init_vertices (casos);
  84. flag := true;
  85. readln (nCasos);
  86. readln (nVertices, nAristas);
  87. for i := 1 to nAristas do
  88. begin
  89. readln (inicio, fin);
  90. flag := flag and (evalua (vertices, inicio, fin));
  91. end;
  92. if flag then
  93. writeln ('Miguel, a pintar')
  94. else
  95. writeln ('No pierdas el tiempo');
  96.  
  97. end.

Ale, ahi lo tienes, dispara :P

Decirte tambien que voy a estar fuera hasta el viernes o asi, en cuanto vuelva a estar online le meto mano al susodicho problema nº 2, y tal vez traducir este a C

Gracias de nuevo por tus problemas, de verdad que son muy interesantes y me he entretenido mucho con ellos, sobre todo el ultimo claro (pa haber salido de un examen de GRAFOS hoy mismo y ponerme a hacer problemas de GRAFOS... xDD hay que echarle ganas)

Saludos!


En línea

"I put on my Hendrix album and my son said 'Dad, who's that?' and i said 'Well son, that's God' "- Robert Plant

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #11 en: 9 Septiembre 2008, 19:14 pm »

Supongo que estará bien, Pascal no sé, por los comentarios que pones parece que está bien, pero no te lo puedo asegurar. He hecho en cinco minutillos una solución en C++ con comentarios en cada línea, así podrás ver si es lo mismo:
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. //Definimos los colores como constantes
  6. const int VERDE = 0;
  7. const int AMARILLO = 1;
  8.  
  9. bool dfs(vector<vector<int> >& grafo, int nodo, int color, vector<int>& color_nodo)
  10. {
  11.     bool flag = true;  //Declaramos el flag como true
  12.     for(int i = 0; i < grafo[nodo].size(); i++)  //Mientras nuestro nodo tenga conexiones...
  13.     {
  14.             if(color_nodo[grafo[nodo][i]] == - 1) //Si el nodo al que está conectado no está pintado...
  15.             {
  16.                color_nodo[grafo[nodo][i]] = not color;  //Le ponemos el color contrario
  17.                flag = dfs(grafo, grafo[nodo][i], not color, color_nodo);  //flag recibe el valor del DFS en dicho nodo
  18.             }
  19.             else if(color_nodo[grafo[nodo][i]] == color) return false;  //Si tiene el mismo color, es imposible el bicolouring, devolvemos false
  20.     }
  21.     return flag;  //Si no se ha salido antes, devuelve flag.
  22. }            
  23.  
  24. int main()
  25. {
  26.    int q; //Número de casos
  27.    cin >> q; //Recogemos los casos
  28.    while(q--) //Mientras siga habiendo casos...
  29.    {
  30.            int n, p; //Nodos y conexiones respectivamente
  31.            cin >> n >> p; //Recogemos ambos valores
  32.            vector<int> color_nodo(n, -1); //Declaramos un arreglo de tamaño n para guardar el color de cada nodo
  33.            vector<vector<int> > grafo(n); //Declaramos una matriz especificando solamente una dimensión
  34.            while(p--) //Mientras haya conexiones por recoger...
  35.            {
  36.                 int origen, destino;  
  37.                 cin >> origen >> destino;  //Recogemos los nodos de origen y destino
  38. //Ambos nodos están conectados, por lo que hay que poner la conexión hacia ambos lados
  39. //La matriz grafo indicará las conexiones: grafo[i].size() será la el número de conexiones donde cada j de grafo[i][j] es el nodo al que se conecta
  40.                 grafo[origen].push_back(destino);  //Añadimos el nodo al que se conecta, en ambos sentidos
  41.                 grafo[destino].push_back(origen);
  42.            }
  43.            color_nodo[0] = VERDE;  //Al primer nodo le asignamos color verde (puede ser al revés, es un simple número)
  44.            if(dfs(grafo, 0, VERDE, color_nodo)) cout << "Miguel, a pintar" << endl;  //Hacemos DFS y según qué devuelva mostramos una salida u otra
  45.            else cout << "No pierdas el tiempo" << endl;
  46.    }
  47. }

Venga, que seguro que más gente aparte de GroK sabe programar. Quiero una solución para el de las minas :P

Un saludo de ghastlyX ;)


En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #12 en: 21 Septiembre 2008, 21:50 pm »

Pues ante la ausencia de respuestas, aclaro como se hace el de las minas. Recursivamente sería empezar en cada una de las casillas de la primera fila e ir probando cada camino desde ahí. Esto es terriblemente lento además de que probamos más de una vez el mismo camino. La solución es por DP.

Creamos una matriz de carácteres para guardar el mapa y otra del mismo tamaño para almacenar números. Entonces simplemente hay que recorrer dicha matriz: si en la posición hay una mina el número lo ponemos a un máximo declarado antes, de lo contrario será el mínimo entre el de arriba y las dos diagonales de arriba + 1. No hace falta decir que la primera fila ha de valer cero en todas las casillas excepto las que tengan minas. La solución final es el mínimo de todas las posiciones de la última fila.

No pondré más problemas, puesto que no tengo demasiado tiempo y casi nadie se pasa por aquí a resolverlos :P

Un saludo de ghastlyX ;)
En línea

Nakp
casi es
Ex-Staff
*
Desconectado Desconectado

Mensajes: 6.336

he vuelto :)


Ver Perfil WWW
Re: Programación algorítmica: unos problemillas
« Respuesta #13 en: 22 Septiembre 2008, 23:29 pm »

jeje.. aqui va el mio de triángulos

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main(){
  5. int m, i, j;
  6. scanf("%i",&m);
  7. for(i = m; i >= 1; i--){
  8. for(j = m; j >= i; j--){
  9. printf("%i",i);
  10. }
  11. printf("\n");
  12. }
  13. return 0;
  14. }

acabo de ponerme a hacerlos así que ya hago el de minas (ni lo he leido)

salu2
« Última modificación: 26 Septiembre 2008, 02:29 am por Nakp » En línea

Ojo por ojo, y el mundo acabará ciego.
Nakp
casi es
Ex-Staff
*
Desconectado Desconectado

Mensajes: 6.336

he vuelto :)


Ver Perfil WWW
Re: Programación algorítmica: unos problemillas
« Respuesta #14 en: 25 Septiembre 2008, 02:28 am »

Pues ante la ausencia de respuestas, aclaro como se hace el de las minas. Recursivamente sería empezar en cada una de las casillas de la primera fila e ir probando cada camino desde ahí. Esto es terriblemente lento además de que probamos más de una vez el mismo camino. La solución es por DP.

Creamos una matriz de carácteres para guardar el mapa y otra del mismo tamaño para almacenar números. Entonces simplemente hay que recorrer dicha matriz: si en la posición hay una mina el número lo ponemos a un máximo declarado antes, de lo contrario será el mínimo entre el de arriba y las dos diagonales de arriba + 1. No hace falta decir que la primera fila ha de valer cero en todas las casillas excepto las que tengan minas. La solución final es el mínimo de todas las posiciones de la última fila.

No pondré más problemas, puesto que no tengo demasiado tiempo y casi nadie se pasa por aquí a resolverlos :P

Un saludo de ghastlyX ;)

 ahm... que se me hace que se resuelve con una matriz de adyacencia :xD deja un rato libre que no se queda sin solución
En línea

Ojo por ojo, y el mundo acabará ciego.
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #15 en: 25 Septiembre 2008, 19:44 pm »

¿Matriz de adyacencia? No es de grafos el problema, es de DP y se resuelve como expliqué en el post anterior, supongo que pensarías en BFS o Dijkstra, pero va de dinámica.

Un saludo de ghastlyX ;)
En línea

Nakp
casi es
Ex-Staff
*
Desconectado Desconectado

Mensajes: 6.336

he vuelto :)


Ver Perfil WWW
Re: Programación algorítmica: unos problemillas
« Respuesta #16 en: 26 Septiembre 2008, 07:19 am »

¿Matriz de adyacencia? No es de grafos el problema, es de DP y se resuelve como expliqué en el post anterior, supongo que pensarías en BFS o Dijkstra, pero va de dinámica.

Un saludo de ghastlyX ;)

en realidad se me ocurrió warshall pero apenas lo entiendo :¬¬ y en 6 horas tengo un control de lectura! :laugh:
En línea

Ojo por ojo, y el mundo acabará ciego.
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #17 en: 26 Septiembre 2008, 17:07 pm »

Pues no te sé decir si por Floyd-Warshall funcionaría, pero si no me equivoco creo que mediante ese algoritmo tienes complejidad cúbica, tal y como he explicado sólo cuadrática. Olvida algoritmos de búsquedas de caminos en grafos para este problema. De hecho, olvida los grafos para este problema, se puede resolver sin haber visto un grafo en la vida.

Un saludo de ghastlyX ;)
En línea

juancho77


Desconectado Desconectado

Mensajes: 455


rie con demencia


Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #18 en: 20 Noviembre 2008, 04:55 am »

Citar
Creamos una matriz de carácteres para guardar el mapa y otra del mismo tamaño para almacenar números. Entonces simplemente hay que recorrer dicha matriz: si en la posición hay una mina el número lo ponemos a un máximo declarado antes, de lo contrario será el mínimo entre el de arriba y las dos diagonales de arriba + 1. No hace falta decir que la primera fila ha de valer cero en todas las casillas excepto las que tengan minas. La solución final es el mínimo de todas las posiciones de la última fila.

Ya que estamos. Me tome el trabajo de pasar el algortimo a Java  :-*
Código
  1. import java.io.*;
  2. import java.util.Random;
  3. public class minas {
  4.    public static void main() throws Exception {
  5.        char[][] caracteres;
  6.        int [][] resultado;
  7.        System.out.print("Ingrese cantidad de filas:");
  8.        int filas=Integer.parseInt(br.readLine());
  9.        System.out.print("Ingrese cantidad de columnas:");
  10.        int columnas=Integer.parseInt(br.readLine());
  11.        caracteres=new char[filas][columnas];
  12.        resultado=new int[filas][columnas];
  13.        Random rnd=new Random();
  14.        for (int i=0; i<filas; i++)
  15.        {
  16.            for(int j=0;j<columnas;j++)
  17.            {
  18.                //genero la tabla/////////////
  19.                int aleat=rnd.nextInt(2);
  20.                if (aleat==1)
  21.                    caracteres[i][j]='M';
  22.                    else caracteres[i][j]='L';
  23.                //////////////////////////////
  24.                //
  25.                if (caracteres[i][j]=='M')
  26.                    resultado[i][j]=99;
  27.                else //si esta libre
  28.                {
  29.                    if (i==0) //si es la primera fila
  30.                        resultado[i][j]=0;
  31.                    else //en cualquier otro caso
  32.                    {
  33.                        if ((j>0)&&(j<columnas-1))
  34.                            resultado[i][j]=min(resultado[i-1][j-1]+1,resultado[i-1][j],resultado[i-1][j+1]+1);
  35.                        else if (j==0)
  36.                            resultado[i][j]=min(resultado[i-1][j],resultado[i-1][j+1]+1,99);
  37.                             else
  38.                               resultado[i][j]=min(resultado[i-1][j],resultado[i-1][j-1]+1,99);
  39.                            }          
  40.                        }      
  41.            }
  42.        }
  43.        int menor=99;
  44.        for (int j=0; j<columnas;j++)
  45.            if (resultado[filas-1][j]<menor)
  46.                menor=resultado[filas-1][j];
  47.        if (menor==99)
  48.            System.out.println("Yum Yum");
  49.            else System.out.println(menor);
  50. }
  51.    public static int min(int num1, int num2, int num3){
  52.        int menor=num1;
  53.        if (num2<num1)
  54.            menor=num2;
  55.        if (num3<menor)
  56.            menor=num3;
  57.        return menor;
  58.    }
  59. }
En línea

Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Duda algorítmica y de Java
Java
Felipe_Henriquez 4 2,376 Último mensaje 12 Enero 2012, 02:18 am
por Felipe_Henriquez
Ejercicio de algorítmica
Dudas Generales
mariele31 1 567 Último mensaje 11 Marzo 2022, 21:37 pm
por .xAk.
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines