elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.
 
Inicio Ayuda Buscar Ingresar Registrarse
27 Mayo 2012, 10:16  


Tema destacado: [Overclocking] Récords de overclock del foro

+  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 5,138 veces)
ghastlyX
Colaborador
***
Desconectado Desconectado

Mensajes: 1.894



Ver Perfil
Programación algorítmica: unos problemillas
« en: 6 Septiembre 2008, 03:03 »

A raíz de ver los problemas de ohk, me ha gustado la idea y voy a poner también algunos problemas, al mismo estilo de entrada-salida que en los concursos de programación.

Por ahora pondré un par, uno facilísimo (triangulos.pdf) y otro algo más complejo (minas.pdf), si veo que gusta ya me inventaré más de diferentes tipos.

Los pongo adjuntos en pdf. Sobre el primero no hay nada que decir, es muy sencillo, respecto al segundo, como pone en el enunciado, no se puede hacer recursivamente puesto que es muy lento, buscad otro tipo de solución más dinámica xDD

En cuanto a los lenguajes, que cada uno lo haga con aquel que use y lo postee, puesto que así no queda limitado a ningún lenguaje, poniendo comentarios para que el resto podamos entender que hace su programa si no conocemos el lenguaje. La solución la daré si es necesaria en pseudocódigo.

Un saludo de ghastlyX ;)


En línea
ohk


Desconectado Desconectado

Mensajes: 1.577


Some times I think i'm crazy, I'm crazy o so crazy


Ver Perfil WWW
Re: Programación algorítmica: unos problemillas
« Respuesta #1 en: 6 Septiembre 2008, 04:37 »

Hola :D

Hombre están buenos tus ejercicios, aunque el de las minas es mas complejo, por ahora voy a resolver el primero, espero no tardarme demasiado  :P

Un saludo

OHK


En línea

Y es que a veces pienso, que si no estubiera loco, no podría salir adelante.
GroK


Desconectado Desconectado

Mensajes: 680


...I have become comfortably numb...


Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #2 en: 6 Septiembre 2008, 06:51 »

Hola ;)

Me han parecido interesantes los ejercicios, voy a postear el primero, si te parece bien:

En C:

Código
#include <stdio.h>
 
int main (void)
{
int i, j, n;
 
printf ("Introduce altura de la pared: ");
scanf ("%d", &n);
for (i = n; i >= 1; i--) { /* Bucle desde la cima hasta la base */
j = i; /* 'j' servira para saber las veces que se repiten los numeros en cada nivel de la piramide */
while (j <= n) {
printf ("%d ", i); /* Imprimimos el numero del nivel... */
j++;
} /* ...tantas veces como niveles alejados de la cima estemos */
printf ("\n");
}
printf ("\n");
return 0;
}



En Pascal:

Código
PROGRAM Triangulos;
 
VAR
i, j, n : Byte;
 
BEGIN
 
Write ('Introduce altura de la pared: ');
ReadLn (n);
For i := n DownTo 1 Do
Begin
j := i;
While (j <= n) Do
Begin
Write (i, ' ');
Inc (j);
End;
WriteLn ();
End;
WriteLn ();
 
END.



Igual se pueden optimizar algo mas, pero bueno... En cuanto pueda intentare el segundo tambien, a ver que tal

Gracias y 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
Colaborador
***
Desconectado Desconectado

Mensajes: 1.894



Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #3 en: 6 Septiembre 2008, 14:08 »

Vale, el código está bien, aunque tal y como dije, la idea es que no pidas la entrada, tú simplemente has de hacer un programa que la reciba. Y por cierto, cuidado que has puesto espacios entre los números, eso en un concurso de programación te lo darían como mal. Aunque como lo importante es la idea y esta es correcta, el problema lo doy por resuelto. Si alguien quiere aportar más soluciones para este serán bievenidas. Ahora a por el de las minas :P

El primero en C++ lo tenía así, un poco más corto:
Código
#include <iostream>
using namespace std;
 
int main()
{
   int n, i = 1;
   cin >> n;  //Recogemos n
   while(n) //Mientras n no sea cero
   {
           for(int k = 0; k < i; k++) cout << n;  //Imprimimos i veces n, para una i inicial de 1
           i++; //Aumentamos en 1 i para el siguiente nivel
           n--; //Disminuimos en 1 n
           cout << endl; //Imprimimos un salto de línea
   }
}

Pero es lo mismo, la idea es como lo has hecho.

Un saludo de ghastlyX ;)
En línea
GroK


Desconectado Desconectado

Mensajes: 680


...I have become comfortably numb...


Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #4 en: 6 Septiembre 2008, 16:48 »

Guay :D

Lo del espacio despues de los numeros lo puse deliberadamente, pensando que asi es mas legible... Pero bueno es igual, se quita y ya esta xD No sabia eso de los concursos, me lo apuntare

Ah, y me gusta tu codigo, te quedo mas corto, tiene estilo :P

Ahora a por el de las minas, como tu dices. 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

chrominum


Desconectado Desconectado

Mensajes: 564


Viceroy: No es lo que tengo, es COMO lo tengo


Ver Perfil WWW
Re: Programación algorítmica: unos problemillas
« Respuesta #5 en: 6 Septiembre 2008, 21:48 »

Mi solución en c# del ejercicio de los Triángulos:

Código
using System;
using System.Collections.Generic;
using System.Text;
 
namespace Triangulos
{
   class TriangulosApp
   {
       static void Main(string[] args)
       {
           byte metros, nivel = 1, i;
           Console.Write("Introduce los metros de la pared: ");
           metros = Convert.ToByte(Console.ReadLine());
           while (metros > 0 && metros < 10)
           {
               for (i = 0; i < nivel; i++)
                   Console.Write(metros);
               Console.WriteLine();
               metros--;
               nivel++;
           }
           Console.ReadKey();
       }
   }
}

Y mi otra soluciona al problema de los triángulos haciendo uso de los RepUnit (para conseguir cogido mas corto):

Código
using System;
using System.Collections.Generic;
using System.Text;
 
namespace TriangulosRepUnit
{
   class TriangulosRepUnitApp
   {
       static void Main(string[] args)
       {
           byte metros, nivel;
           Console.Write("Introduce los metros de la pared: ");
           metros = Convert.ToByte(Console.ReadLine());
           for (nivel = 1; metros > 0 && metros < 10; nivel++)
           {
               Console.WriteLine((Math.Pow(10, nivel) - 1) / 9 * metros);
               metros--;
           }
           Console.ReadKey();
       }
   }
}
« Última modificación: 6 Septiembre 2008, 22:07 por ArcheritONE » En línea

ghastlyX
Colaborador
***
Desconectado Desconectado

Mensajes: 1.894



Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #6 en: 7 Septiembre 2008, 00:01 »

Son correctas ambas, me ha gustado la segunda, es una forma original de resolverlo, más de tipo matemática que no directa. Eso sí, como ya he dicho, no hay que pedir la entrada con lo de "Introduce los metros de la pared", simplemente recoged los datos, al estilo de UVa, USACO, OIE, IOI, ACM, Topcoder, etc. Poniendo eso en los concursos os daría error, puesto que la salida que produce tiene que ser idéntica a los ejemplos, y en ellos no aparecen peticiones de entrada de datos. Bueno, ya que el de los triángulos está resuelto, intentad el de las minas, que es algo más complejo.

Se podría hacer recursivamente, mirando TODOS los caminos desde cada parcela, pero es brutalmente lento, una solución recursiva no será considerada correcta. En mi primer post di una gran pista de cómo resolverlo, la repetiré: buscad una solución más dinámica!

Un saludo de ghastlyX ;)
En línea
ghastlyX
Colaborador
***
Desconectado Desconectado

Mensajes: 1.894



Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #7 en: 8 Septiembre 2008, 00:43 »

Bueno, voy a poner uno nuevo, esta vez de grafos, lo dejo adjunto. A ver si alguien da ya una solución para el de las minas, para el que no se haya dado cuenta con las pistas o no conozca ese tipo de problemas, es de programación dinámica. Si nadie publica nada tendré que dar yo la solución :P

Un saludo de ghastlyX ;)
En línea
GroK


Desconectado Desconectado

Mensajes: 680


...I have become comfortably numb...


Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #8 en: 8 Septiembre 2008, 03:46 »

Si nadie publica nada tendré que dar yo la solución :P

No!! Esperame xDD Tengo un examen mañana y por eso no lo he intentado hasta ahora, no he tenido tiempo, pero cuando llegue me pongo (encima en el examen me cae programacion dinamica :xD Y eso me lo se bien :P)

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
Colaborador
***
Desconectado Desconectado

Mensajes: 1.894



Ver Perfil
Re: Programación algorítmica: unos problemillas
« Respuesta #9 en: 8 Septiembre 2008, 20:47 »

OK, me esperaré un poco más y mientras si eso quizá ponga alguno nuevo más. Por ahora hay tres: uno directo, otro DP y otro de grafos.

Un saludo de ghastlyX ;)

PD: Hay que ver, que a muchos los sacan de APIs, hooks y ese tipo de programación y se pierden xDD
En línea
GroK


Desconectado Desconectado

Mensajes: 680


...I have become comfortably numb...


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

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
program circulos;
 
const
MAX = 20;
 
type
TValores  = Record
               Asignado : boolean;
Color       : boolean; { 'True' = Verde; 'False' = Amarillo }
End;
TVertices = array [0..MAX] of TValores;
TCasos = array [1..MAX] of TVertices;
 
var
nCasos : integer;
nVertices : integer;
nAristas : integer;
inicio, fin  : integer;
vertices : TVertices;
casos : TCasos;
flag : boolean;
i : integer;
 
procedure init_vertices (var c : TCasos);
 
var
i, j : integer;
 
begin
 
for i := 1 to MAX do
for j := 0 to MAX do
begin
c[i][j].Asignado := false;
c[i][j].Color := false;
end;
 
end;
 
function evalua (var v : TVertices; inicio, fin : integer) : boolean;
 
begin
 
if (v[inicio].Asignado = false) and (v[fin].Asignado = false) then { si ninguno ha sido asignado aun }
begin
v[inicio].Asignado := true;
v[inicio].Color := true;
v[fin].Asignado := true;
v[fin].Color := false;
evalua := true;
end
else
begin
if (v[inicio].Asignado) xor (v[fin].Asignado) then { si uno de los dos esta asignado }
begin
if v[fin].Asignado = false then
begin
v[fin].Asignado := true; { lo marcamos como coloreado }
v[fin].Color := not v[inicio].Color; { y le ponemos el color contrario al del otro vertice }
end
else
begin  { en caso de que el que no estuviese coloreado aun fuera el vertice inicial, lo mismo para este }
v[inicio].Asignado := true;
v[inicio].Color := not v[fin].Color;
end;
evalua := true;
end
else
begin  { si entramos aqui es porque ambos ya estan coloreados, comprobemos si es incompatible }
if v[inicio].Color = v[fin].Color then
evalua := false
else
evalua := true;
end;
end;
 
end;
 
{ -- MAIN --}
 
begin  
 
init_vertices (casos);
flag := true;
readln (nCasos);
readln (nVertices, nAristas);
for i := 1 to nAristas do
begin
readln (inicio, fin);
flag := flag and (evalua (vertices, inicio, fin));
end;
if flag then
writeln ('Miguel, a pintar')
else
writeln ('No pierdas el tiempo');
 
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
Colaborador
***
Desconectado Desconectado

Mensajes: 1.894



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

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
#include <iostream>
#include <vector>
using namespace std;
 
//Definimos los colores como constantes
const int VERDE = 0;
const int AMARILLO = 1;
 
bool dfs(vector<vector<int> >& grafo, int nodo, int color, vector<int>& color_nodo)
{
    bool flag = true;  //Declaramos el flag como true
    for(int i = 0; i < grafo[nodo].size(); i++)  //Mientras nuestro nodo tenga conexiones...
    {
            if(color_nodo[grafo[nodo][i]] == - 1) //Si el nodo al que está conectado no está pintado...
            {
               color_nodo[grafo[nodo][i]] = not color;  //Le ponemos el color contrario
               flag = dfs(grafo, grafo[nodo][i], not color, color_nodo);  //flag recibe el valor del DFS en dicho nodo
            }
            else if(color_nodo[grafo[nodo][i]] == color) return false;  //Si tiene el mismo color, es imposible el bicolouring, devolvemos false
    }
    return flag;  //Si no se ha salido antes, devuelve flag.
}            
 
int main()
{
   int q; //Número de casos
   cin >> q; //Recogemos los casos
   while(q--) //Mientras siga habiendo casos...
   {
           int n, p; //Nodos y conexiones respectivamente
           cin >> n >> p; //Recogemos ambos valores
           vector<int> color_nodo(n, -1); //Declaramos un arreglo de tamaño n para guardar el color de cada nodo
           vector<vector<int> > grafo(n); //Declaramos una matriz especificando solamente una dimensión
           while(p--) //Mientras haya conexiones por recoger...
           {
                int origen, destino;  
                cin >> origen >> destino;  //Recogemos los nodos de origen y destino
//Ambos nodos están conectados, por lo que hay que poner la conexión hacia ambos lados
//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
                grafo[origen].push_back(destino);  //Añadimos el nodo al que se conecta, en ambos sentidos
                grafo[destino].push_back(origen);
           }
           color_nodo[0] = VERDE;  //Al primer nodo le asignamos color verde (puede ser al revés, es un simple número)
           if(dfs(grafo, 0, VERDE, color_nodo)) cout << "Miguel, a pintar" << endl;  //Hacemos DFS y según qué devuelva mostramos una salida u otra
           else cout << "No pierdas el tiempo" << endl;
   }
}

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
Colaborador
***
Desconectado Desconectado

Mensajes: 1.894



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

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.334

he vuelto :)


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

jeje.. aqui va el mio de triángulos

Código
#include <stdio.h>
#include <stdlib.h>
 
int main(){
int m, i, j;
scanf("%i",&m);
for(i = m; i >= 1; i--){
for(j = m; j >= i; j--){
printf("%i",i);
}
printf("\n");
}
getchar();
getchar();
return 0;
}

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 por Nakp » En línea

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

Mensajes: 6.334

he vuelto :)


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

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.
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 603 Último mensaje 12 Enero 2012, 02:18
por Felipe_Henriquez
Powered by SMF 1.1.16 | SMF © 2006-2008, Simple Machines