últimos mensajes de: hadree

Mostrar Mensajes
Páginas: [1]

1	Programación / .NET (C#, VB.NET, ASP) / Re: [Reto] Backtracking - Laberinto	en: 25 Noviembre 2010, 16:57 pm
Cita de: ghastlyX en 24 Noviembre 2010, 18:57 pm El enunciado tiene muchas imprecisiones. Cuando dice la primera solución, entiendo que se refiere a la primera que encuentre el backtracking, pero no queda claro ni especifica qué criterio usar. Lo segundo que pide es, bajo mi punto de vista, erróneo. Con el enunciado actual no se prohíben los ciclos, de forma que existen infinitos caminos para la gran mayoría de laberintos. Se tendría que especificar una longitud máxima o bien exigir que no haya ciclos. Lo tercero es correcto, pero en lugar de un backtracking puede resolverse mediante Dijkstra, cuya complejidad para un grafo G = (V, E) es O((V + E)logV) mientras que el backtracking no es polinómico. He picado Dijkstra en C++ para el problema, he probado un par de ejemplos y los resuelve bien. El código es simple así que no debería ser problema pasarlo a otro lenguaje sabiendo un poco de C++. 1) Por supuesto lo de la primera solución se refiere a la primera solución es decir la primera encontrada, no me parece que haya ninguna duda... 2) En cuanto a los ciclos, si la verdad es que no lo había puesto, pero se da por hecho ya que realizando los movimientos básicos comentados se quedaría atascado si intentase pasar de nuevo por una casilla ya recorrida. 3) Se puede resolver con Dijkstra, pero la idea original era que fuera por backtracking y con una representación matricial que no que fuera considerada como un grafo. 4) El código no lo he probado pero parece tener buena pinta... ************************************************************** Cita de: .::IT::. en 24 Noviembre 2010, 18:57 pm No se porque paso por mi mente que podría ser una tarea jaja en fin esta interesante PD: Yo ya lo tengo resuelto y pensaba ponerlo más adelante simplemente quería saber si había gente dispuesta a intentarlo... ************************************************************** .

2	Programación / .NET (C#, VB.NET, ASP) / Re: [Reto] Backtracking - Laberinto	en: 23 Noviembre 2010, 22:27 pm
Gracias, me parece bien así...."reto" suena más interesante....jajajaja

3	Programación / .NET (C#, VB.NET, ASP) / Re: Criptografía - Cifrado por sustitución	en: 22 Noviembre 2010, 19:14 pm
Bueno es solo para empezar más adelante pueden añadirse otros algoritmos.

Programación / .NET (C#, VB.NET, ASP) / Criptografía - Cifrado por sustitución

en: 22 Noviembre 2010, 17:19 pm

En criptografía, el cifrado por sustitución es un método de cifrado por el que unidades de texto plano son sustituidas con texto cifrado siguiendo un sistema regular; las "unidades" pueden ser una sola letra (el caso más común), pares de letras, tríos de letras, mezclas de lo anterior, entre otros.

El receptor descifra el texto realizando la sustitución inversa.

Los cifrados por sustitución son comparables a los cifrados por transposición. En un cifrado por transposición, las unidades del texto plano son cambiadas usando una ordenación diferente y normalmente bastante compleja, pero las unidades en sí mismas no son modificadas. Por el contrario, en un cifrado por sustitución, las unidades del texto plano mantienen el mismo orden, lo que se cambia son las propias unidades del texto plano.

Existen diversos tipos de cifrados por sustitución. Si el cifrado opera sobre letras simples, se denomina cifrado por sustitución simple; un cifrado que opera sobre grupos de letras se denomina, poligráfico. Un cifrado monoalfabético usa una sustitución fija para todo el mensaje, mientras que un cifrado polialfabético usa diferentes sustituciones en diferentes momentos del mensaje-por ejemplo los homófonos, en los que una unidad del texto plano es sustituida por una de entre varias posibilidades existentes para el texto cifrado.

En esta ocasión vamos a realizar un pequeño programa para implementar el cifrado por sustitución simple, no obstante es posible con unas pocas modificaciones implementar un sistema diferente.

Este sistema es muy simple y puede ser fácilmente descifrado, pero sirve como base para aprender a realizar la sustitución de caracteres en cadenas y de paso realizar nuestro primer programa para codificar textos....

Aunque se implementa solo la versión simple (que opera sobre letras simples), vamos a realizar la sustitución de las distintas letras, del abecedario:

"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "ñ", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"

Por una selección de caracteres del conjunto unicode :

"א", "η", "Σ", "Τ", "ϊ", "ψ", "φ", "σ", "ב", "ג", "ה", "ז", "Ϧ", "ﬥ", "ﬢ", "ﬠ", "ﬨ", "ף", "", "ם", "ן", "Ϣ", "Ϩ", "Ϝ", "ס", "Ϯ", "ך"

Este sería un ejemplo:

Código:

Este es un texto de prueba que se va a codificar para probar
el algoritmo de sustitución.

Código:

ϊםןϊڊϊםڊϢﬥڊןϊסןﬠڊΤϊڊﬨұϢϊηאڊףϢϊڊםϊڊϨאڊאڊΣﬠΤבψבΣאұڊﬨאұאڊﬨұﬠηאұڊϊ
זڊאזφﬠұבןϦﬠڊΤϊڊםϢםןבןϢΣבóﬥ.

Y bueno aquí tenéis el código del ejemplo:

Código:


Public Class Form1

    ''**************************************************
    ''VARIABLES GLOBALES
    ''**************************************************
    Dim Chars1() As String = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "ñ", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", " "}
    Dim Chars2() As String = {"א", "η", "Σ", "Τ", "ϊ", "ψ", "φ", "σ", "ב", "ג", "ה", "ז", "Ϧ", "ﬥ", "ﬢ", "ﬠ", "ﬨ", "ף", "ұ", "ם", "ן", "Ϣ", "Ϩ", "Ϝ", "ס", "Ϯ", "ך", "ڊ"}

    ''**************************************************
    ''EVENTOS
    ''**************************************************

    Private Sub btnBorrarTodo_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnBorrarTodo.Click
        borrarTodo()
    End Sub

    Private Sub btnSubirResultado_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnSubirResultado.Click
        subirResultado()
    End Sub

    Private Sub btnCalcular_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnCalcular.Click
        calcular()
    End Sub

    ''**************************************************
    ''SUBPROCEDIMIENTOS y FUNCIONES
    ''**************************************************

    Sub borrarTodo()
        txtOrigen.Text = ""
        txtDestino.Text = ""
    End Sub

    Sub subirResultado()
        txtOrigen.Text = txtDestino.Text
        txtDestino.Text = ""
    End Sub

    Sub calcular()
        ''
        If txtOrigen.Text <> "" Then
            ''
            If opCodificar.Checked Then
                ''CODIFICAR
                txtDestino.Text = CodCaracteres(txtOrigen.Text)
                ''
            Else
                ''DECODIFICAR
                txtDestino.Text = DecodCaracteres(txtOrigen.Text)
                ''
            End If
            ''
        End If
        ''
    End Sub

    ''**************************************************

    Function CodCaracteres(ByVal str As String) As String
        ''
        Dim k As Integer = 0
        Dim c1 As String = ""
        Dim c2 As String = ""
        ''
        str = str.ToLower
        ''
        While k < Chars1.Length
            ''
            c1 = Chars1(k)
            c2 = Chars2(k)
            ''
            While str.Contains(c1) = True
                str = str.Replace(c1, c2)
            End While
            ''
            k += 1
            ''
        End While
        ''
        Return str
        ''
    End Function

    Function DecodCaracteres(ByVal str As String) As String
        ''
        Dim k As Integer = 0
        Dim c1 As String = ""
        Dim c2 As String = ""
        ''
        While k < Chars2.Length
            ''
            c1 = Chars1(k)
            c2 = Chars2(k)
            ''
            While str.Contains(c2) = True
                str = str.Replace(c2, c1)
            End While
            ''
            k += 1
            ''
        End While
        ''
        Return str
        ''
    End Function

    ''**************************************************
    
End Class

Y por último aquí tenéis el ejecutable de prueba:

Unicoder.zip

.

Programación / .NET (C#, VB.NET, ASP) / [Reto] Backtracking - Laberinto

en: 22 Noviembre 2010, 17:17 pm

************************************

Hola a todos, soy nuevo en el foro y se ma ha ocurrido la idea de este hilo para explicar como realizar el algoritmo de "backtracking" para calcular el camino de ida desde la entrada de un laberinto, hasta la salida del mismo (en caso de haberla).

Os propongo realizar un pequeño programa que cumpla lo siguiente:

Código:


Dado un laberinto escriba un programa que usando
los cuatro movimientos del laberinto, arriba, abajo,
izquierda y derecha calcule (si existen):

1) La primera solución.
2) El total de las soluciones
3) La mejor solución en cuanto a menor número de pasos.

Los datos de entrada son recibidos en un fichero
de texto laberinto.txt que tiene la siguiente estructura:

a.) La primera línea tiene dos números enteros que
son el número de filas nf y el número de columnas nc  del laberinto.
b.) Las siguientes nf líneas tienen un total de nc números enteros cada
una de ellas separados por blancos que pueden ser: 0, 1, 2, 3 y 4

CERO: Indica muro (no se puede pisar la casilla);
UNO: Libre sin penalización. (+1 pasos)
DOS: Libre con penalización. (+2 pasos)
TRES: Libre con penalización. (+3 pasos)
CUATRO: Libre con penalización. (+4 pasos)

c.) La última línea del fichero tiene cuatro números enteros:

Fe = fila de entrada.
Ce = columna de entrada.
Fs = fila de salida.
Cs = columna de salida.

Código:


La estructura del laberinto en el archivo sería la siguiente:

---------------------------
nf nc
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
fe fs ce cs
---------------------------
12 12
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 1 1 1 0
0 4 0 4 0 4 3 3 4 0 4 0
0 3 0 2 0 3 0 1 0 0 1 0
0 4 0 3 0 3 0 1 0 1 4 0
0 3 0 4 0 3 0 4 0 1 0 0
0 4 0 1 1 1 3 1 2 1 0 0
0 3 0 0 1 0 0 1 0 1 3 1
0 4 0 0 1 1 0 2 0 4 0 0
0 2 0 0 0 1 0 3 0 4 0 0
0 1 1 1 1 1 0 4 1 4 3 0
0 0 0 0 0 0 0 0 0 0 0 0
1 0 7 11
---------------------------

Os animáis a intentarlo :cool: ??

Código:

//El código lo pondré en unos días, a ver si la gente participa...:D

Programación / Programación C/C++ / Backtracking - Laberinto

en: 22 Noviembre 2010, 17:12 pm

Código:


Dado un laberinto escriba un programa que usando
los cuatro movimientos del laberinto, arriba, abajo,
izquierda y derecha calcule (si existen):

1) La primera solución.
2) El total de las soluciones
3) La mejor solución en cuanto a menor número de pasos.

Los datos de entrada son recibidos en un fichero
de texto laberinto.txt que tiene la siguiente estructura:

a.) La primera línea tiene dos números enteros que
son el número de filas nf y el número de columnas nc  del laberinto.
b.) Las siguientes nf líneas tienen un total de nc números enteros cada
una de ellas separados por blancos que pueden ser: 0, 1, 2, 3 y 4

CERO: Indica muro (no se puede pisar la casilla);
UNO: Libre sin penalización. (+1 pasos)
DOS: Libre con penalización. (+2 pasos)
TRES: Libre con penalización. (+3 pasos)
CUATRO: Libre con penalización. (+4 pasos)

c.) La última línea del fichero tiene cuatro números enteros:

Fe = fila de entrada.
Ce = columna de entrada.
Fs = fila de salida.
Cs = columna de salida.

Código:


La estructura del laberinto en el archivo sería la siguiente:

---------------------------
nf nc
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
fe fs ce cs
---------------------------
12 12
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 1 1 1 0
0 4 0 4 0 4 3 3 4 0 4 0
0 3 0 2 0 3 0 1 0 0 1 0
0 4 0 3 0 3 0 1 0 1 4 0
0 3 0 4 0 3 0 4 0 1 0 0
0 4 0 1 1 1 3 1 2 1 0 0
0 3 0 0 1 0 0 1 0 1 3 1
0 4 0 0 1 1 0 2 0 4 0 0
0 2 0 0 0 1 0 3 0 4 0 0
0 1 1 1 1 1 0 4 1 4 3 0
0 0 0 0 0 0 0 0 0 0 0 0
1 0 7 11
---------------------------

Os animáis a intentarlo :cool: ??

Código:

//El código lo pondré en unos días, a ver si la gente participa...:D

Páginas: [1]