Programación algorítmica: unos problemillas

[ghastlyX]

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

[:ohk<any>]

Hola

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 

Un saludo

OHK

[GroK]

Hola

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

En C:

Código (c) [Seleccionar] Expandir

#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 (pascal) [Seleccionar] Expandir

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

[ghastlyX]

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

El primero en C++ lo tenía así, un poco más corto:

Código (cpp) [Seleccionar] Expandir

#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

[GroK]

Guay

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

Ahora a por el de las minas, como tu dices. Saludos

[chrominum]

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

Código (csharp) [Seleccionar] Expandir

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 (csharp) [Seleccionar] Expandir

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();
        }
    }
}

[ghastlyX]

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

[ghastlyX]

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

Un saludo de ghastlyX

[GroK]

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

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 Y eso me lo se bien )

Saludos

[ghastlyX]

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