Librería de códigos C# (Compartan aquí sus códigos)
DarK_FirefoX:
18 - Hallar la menor cantidad de inserciones necesarias para que una cadena sea palíndromo
Ya expliqué anteriormente que es un palíndromo.
Citar
Palíndromo es una palabra, número o frase que se lee igual hacia adelante que hacia atrás.
Este código es extremadamente sencillo. Supongamos que la entrada es un string y que no tiene espacios.
Este código lo hice de manera recursiva, tenemos también un método portal:
Código
/// <summary>
/// Método portal
/// </summary>
static int PalindromInsertions(string line)
{
if (line.Length == null)
throw new NullReferenceException("La cadena no puede ser null");
if (line.Length == 1)
return 0;
return PalindromInsertions(line, 0, line.Length - 1);
}
static int PalindromInsertions(string line, int inf, int sup)
{
if (inf > sup)
return 0;
if (line[inf] == line[sup])
return PalindromInsertions(line, inf + 1, sup - 1);
else
return Math.Min(1 + PalindromInsertions(line, inf + 1, sup),
1 + PalindromInsertions(line, inf, sup - 1));
}
El método portal lo utilicé para validar la entrada de que no sea null y si tiene longitud 1 entonces no es necesario hacer inserciones para que sea palíndromo, pues ya es palíndromo.
Luego se llama al método PalindromInsertions() pasándole la cadena, el límite inferior y el superior (en principio, 0 y line.Length - 1 respectivamente).
El objetivo del método y de la recursividad en este caso es ver si la los caracteres de la cadena evaluada en los límites son iguales, si lo son, se llama recursivo aumentado y disminuyendo los limites inferior y superior respectivamente, en caso de que no lo sea, se va a devolver el Mínimo de hacer una inserción por la izquierda y haber una inserción por la derecha. Para esto utilizamos el método Min() de la clase Math. Este método devuelve el mínimo entre dos enteros (tiene otras sobrecargas para distintos tipos de datos). Representamos hacer 1 inserción sumándole 1 al llamado recursivo del método manteniendo un límite y aumentando o disminuyendo el límite inferior o superior respectivamente.
Al principio del método, comprobamos si los límites se superpusieron (ya revisamos la cadena completa). En este caso base, devolvemos 0. (No es necesario hacer inserciones)
Espero se entienda.
19 - Rotar un array n veces a la derecha
En este caso utilizaré nuevamente un array de int para simplificar. El método recibe un array de int y un int que representa la cantidad de posiciones a rotar.
Código
public static void RotarDerecha(int[] a, int veces)
{
if (veces == a.Length || veces % a.Length == 0) return;
int aMover = a[0];
int posicion = 0;
int contador = 0;
while (contador < a.Length)
{
int proxPosicion = (posicion + veces) % a.Length; //Calculamos nueva posición
int proxValor = a[proxPosicion]; //Guardamos el elemento que esta en esa nueva posición
a[proxPosicion] = aMover; //Ponemos el elemento a mover en la nueva posición
aMover = proxValor; //Asignamos a la variable del elemento a mover el valor que estaba en la nueva posición
posicion = proxPosicion; //Guardamos la posición del nuevo elemento
contador++; //Hicimos un movimiento
}
}
Lo primero que tenemos que darnos cuenta es que rotar a la derecha significa mover cada elemento a la derecha n veces. En caso de que las rotaciones sobrepasen la longitud del array se deberá comenzar desde el inicio del array. ¿Cómo resolvemos esto? Bueno, cada posición nueva viene dada por el resto que deja la posición más la cantidad de rotaciones con la longitud del array. Esto nos garantiza que siempre nos va a quedar en una posición (y en la que es) dentro del array.
Lo primero que hacemos es comprobar si la cantidad de veces es igual a la longitud del array o si la cantidad de veces deja resto 0 con la longitud del array. En este caso no se hace ninguna rotación.
Luego, debemos tener una variable, para saber cuántas rotaciones estamos haciendo y saber cuándo vamos a parar. También una variable para llevar el elemento que estamos moviendo (en principio, el primero) y una variable para llevar su posición.
Ahora, utilizaremos el ciclo while para controlar la cantidad de movimientos que se han hecho. Vamos a ejecutar el ciclo while mientras la variable contador sea menor que la longitud del array.
Dentro del ciclo lo que haremos será calcular la posición nueva de ese elemento. Guardar en una variable el elemento en esa nueva posición y hacer un Swap entre el elemento que llevamos para mover y ese nuevo (que será el nuevo que queremos mover). También debemos guardar en la variable posicion la posición de ese nuevo elemento. Por último, incrementar la variable contador pues ya se hizo un movimiento.
He tenido poco tiempo, por eso solo dejo estos dos.
Salu2s
DarK_FirefoX:
20 - Saber si dos cadenas son anagramas
El objetivo del siguiente código es comprobar si dos cadenas son anagramas. Lo primero ¿Qué es un anagrama? Es una palabra o frase que resulta de la transposición de letras de la otra palabra o frase. En el siguiente código vamos solo a tener en cuenta "palabras".
Código
public static bool SonAnagramas(string a, string b)
{
if (a.Length != b.Length) return false;
for (int i = 0; i < a.Length; i++)
{
bool igualdad = false;
for (int j = 0; j < b.Length; j++)
{
if (a[i] == b[j])
{
b = b.Remove(j,1);
igualdad = true;
break;
}
}
if (!igualdad) return false;
}
return b.Length == 0;
}
El objetivo del código es ir verificando los caracteres de una cadena con la otra. Primero verificamos si las longitudes son iguales. En caso de que no lo sean, se devuelve false pues una tiene caracteres que no tiene la otra. El objetivo es iterar por una cadena y fijar un carácter, y entonces iterar sobre la segunda y comprobar si se encuentra uno igual. En caso de que se encuentre uno igual se modifica la segunda cadena y se elimina el carácter. El objetivo de esto es que si al final de iterar la longitud de esta cadena es mayor que 0 entonces no es un anagrama. Si lo es, en caso contrario. También hay que tener en cuenta que si por un carácter fijado en la primera cadena no se elimina ningún carácter en la segunda cadena, entonces ya podemos decir que no es un anagrama.
Para eliminar un carácter de la cadena, utilizamos el método Remove() que pertenece a la clase string, el método recibe una posición a partir de la cual se va a eliminar caracteres y la cantidad de caracteres a eliminar. El método devuelve un nuevo string, por lo tanto hay que asignárselo a la variable pues este no modifica la instancia sobre la cual se llame.
21 - Contar ficheros de una extensión dada dentro de un directorio incluyendo subcarpetas (recursivamente)
El siguiente código lo que hará es contar la cantidad de ficheros de una extensión dada dentro de un directorio y sus subdirectorios.
Primero que todo, utilizaremos un método portal al cual le pasaremos como parámetro la ruta del directorio, y la extensión (Ej.: ".txt", ".jpg", etc.) En este método utilizaremos dos cosas que voy a explicar a continuación:
Primero, la clase DirectoryInfo dentro del namespace System.IO (recuerden añadirlo). Esta clase tiene métodos para copiar, mover, renombrar, eliminar y enumerar directorios y subdirectorios. Aquí creamos una instancia de esta clase pasándole como parámetro al constructor de la misma la ruta del directorio.
También utilizamos un delegate Func que encapsula un método y devuelve un valor, en este caso utilizamos:
Código
Func<FileInfo, bool>
Que recibe un parámetro FileInfo como parámetro de entrada y devuelve bool. Este delegate lo vamos a utilizar como condición para comprobar si el fichero tiene una extensión dada. El delegate devuelve true si la extensión del archivo referido por la instancia de FileInfo es igual a la extensión definida por el usuario.
Nota: Asumo que tienen algún conocimiento sobre delegate y encapsulamiento de métodos. Sino, pueden investigar sobre esto.
Ahora, FileInfo es otra clase dentro del namespace System.IO. Tiene métodos para copiar, mover, renombrar, eliminar y abrir ficheros. La misma referencia a un fichero dentro de un directorio.
Código
/// <summary>
/// Método portal
/// </summary>
public static int ContarFicheros(string path, string extension)
{
DirectoryInfo dir = new DirectoryInfo("Prueba"); //Creamos el DirectoryInfo pasándole la ruta del directorio
Func<FileInfo, bool> extensionCondition = delegate(FileInfo fileInfo) { return fileInfo.Extension == extension; }; //Creamos el delegate
return ContarFicheros(dir, extension, extensionCondition);
}
Ahora, el método que se llama para contar los ficheros:
Código
public static int ContarFicheros(DirectoryInfo directory, string extension, Func<FileInfo, bool> extensionCondition)
{
int total = 0;
if (directory.GetDirectories().Count() == 0)
{
total = directory.GetFiles().Count(extensionCondition);
return total;
}
else
{
total += directory.GetFiles().Count(extensionCondition);
foreach (var directorio in directory.GetDirectories())
total += ContarFicheros(directorio, extension, extensionCondition);
return total;
}
}
Recibe como parámetro el DirectoryInfo, la extensión y el delegate. El método tiene un enfoque recursivo, utilizando como caso de parada la condición de que un directorio no tenga más subdirectorios. En este caso solamente cuenta los ficheros en este directorio.
En caso contrario, cuenta los ficheros y llama recursivo por cada subdirectorio.
Para obtener los directorios utilizamos el método GetDirectories() dentro de la clase DirectoryInfo el cual devuelve un DirectoryInfo[] con todos los subdirectorios dentro del directorio actual. Y para contar los ficheros utilizamos el método de extensión Count() del método GetFiles() contenido en la clase DirectoryInfo. El método GetFiles() devuelve un FileInfo[] que representa todos los ficheros en el directorio actual. Y con el método Count() los contamos, utilizando una sobrecarga donde se le pasa un delegate
Código
Func<FileInfo, bool>
El cual representa la condición que tienen que cumplir los ficheros para contarlos.
Nota: En vez de definir el delegate con un método anónimo como lo hice en el código, se puede también definir utilizando expresiones Lambda (aunque esto ya es otro tema)
Código
Func<FileInfo, bool> extensionCondition = s => s.Extension == extension; ;
Espero que este código sea útil y se entienda.
22 - Saber si una cadena tiene paréntesis balanceados
El objetivo del siguiente código es saber si una cadena esta balanceada en cuanto a los paréntesis. Dígase paréntesis a (), [], {}. El objetivo es saber si están correctamente puestos.
Para esto utilizaremos una Pila de caracteres. (Stack<char>). Una pila es una estructura de datos en la que el modo en el que se accede a sus elementos es de tipo LIFO (Last In First Out - último en entrar, primero en salir). Utilizaremos el método Push() que se utiliza para empilar (meter) un elemento en la pila, el método Pop() para desempilar (quitar) el elemento en el tope de la pila y devolverlo, también el método Peek() que devuelve el último elemento en la pila, pero no lo desempila. Por último la propiedad Count que nos da que cantidad de elementos hay en la pila.
El objetivo es ir recorriendo la cadena y a medida que encontramos un paréntesis abierto meterlo en la pila, en caso de que no sea un paréntesis abierto comprobar si es cerrado, y ver si la pila tiene elementos y en el tope de la pila está el paréntesis correspondiente abierto entonces sacarlo de la pila y seguir recorriendo la cadena. En caso de que el elemento no sea un paréntesis entonces ignorar y seguir recorriendo. Al final, el método devuelve true si la pila está vacía, false en caso contrario pues hubo algún paréntesis que no tenía su correspondiente paréntesis cerrado
Código
static bool ParentesisBalanceados(string cadena)
{
Stack<char> pila = new Stack<char>();
for (int i = 0; i < cadena.Length; i++)
{
if (cadena[i] == '(')
pila.Push('(');
else if (cadena[i] == '{')
pila.Push('{');
else if (cadena[i] == '[')
pila.Push('[');
else
{
if (cadena[i] == ')')
if (pila.Count != 0 && pila.Peek() == '(')
pila.Pop();
else return false;
else if (cadena[i] == '}')
if (pila.Count != 0 && pila.Peek() == '{')
pila.Pop();
else return false;
else if (cadena[i] == ']')
if (pila.Count != 0 && pila.Peek() == '[')
pila.Pop();
else return false;
}
}
return pila.Count == 0;
}
Ejemplo de uso:
Código
Console.WriteLine(ParentesisBalanceados("ab(xa[y*c](..[.]+++){{}}cc)*”")); //Devuelve true
Console.WriteLine(ParentesisBalanceados("ab(xa[y*c)bb]**")); //Devuelve false
Console.WriteLine(ParentesisBalanceados("a(b))(")); //Devuelve false
Nota: También se podría haber hecho utilizando un Swtich
Código
static bool ParentesisBalanceadosSwitch(string cadena)
{
Stack<char> pila = new Stack<char>();
for (int i = 0; i < cadena.Length; i++)
{
switch (cadena[i])
{
case '(':
pila.Push('(');
break;
case '{':
pila.Push('{');
break;
case '[':
pila.Push('[');
break;
case ')':
if (pila.Count != 0 && pila.Peek() == '(')
pila.Pop();
else return false;
break;
case '}':
if (pila.Count != 0 && pila.Peek() == '{')
pila.Pop();
else return false;
break;
case ']':
if (pila.Count != 0 && pila.Peek() == '[')
pila.Pop();
break;
default:
break;
}
}
return pila.Count == 0;
}
En cuanto pueda sigo haciendo!
Salu2s
DarK_FirefoX:
Voy a adentrarme ahora en lo que se conoce por combinatoria, exponiendo ejemplos sencillos y clásicos de esta rama de las matemáticas discretas.
23 - Variaciones con repetición
Lo primero que voy a hacer es poner un ejemplo:
Si quisiéramos hallar todas las variaciones con repetición en secuencias de 3 de este array:
Código
string[] valores = {"a", "b", "c", "d", "e"};
Obtendríamos el siguiente resultado:
Citar
a a a
a a b
a a c
a a d
a a e
a b a
a b b
a b c
a b d
a b e
...
...
e e a
e e b
e e c
e e d
e e e
El orden de la complejidad temporal sería un equivalente a NM, siendo N la cantidad de elementos y M el tamaño de la secuencia. Esto es deducible de la posibilidad de por cada espacio de la secuencia (M), en este caso 3, se pueden poner (N), en este caso 5 posibles elementos. Por lo tanto sería 5 * 5 * 5 = 53.
Veamos el código:
Código
//Variaciones con repetición de N elementos en M
/// <summary>
/// Método portal
/// </summary>
static void VariacionesConRepeticion(string[] original, int size)
{
VariacionesConRepeticion(original, new string[size], 0);
}
static void VariacionesConRepeticion(string[] original, string[] variacion, int pos)
{
if (pos == variacion.Length)
{
Print(variacion); //Llama al método Print(), el cual lo que hace es imprimir un array en pantalla.
Console.WriteLine();
}
else
{
for (int i = 0; i < original.Length; i++)
{
variacion[pos] = original[i];
VariacionesConRepeticion(original, variacion, pos + 1);
}
}
}
Primero que todo, veamos que utilizamos un método portal, el cual recibe el array (en este caso es de string para facilidad, pero se puede hacer de cualquier otro tipo incluso lo pueden implementar para que el método sea genérico). Lo otro que recibe es el tamaño de la variación (M) (M<=N) (N -> Cantidad de elementos).
En el método portal llamamos al método recursivo pasándole como parámetro el array original, un array "variacion" vacío con longitud M y una variable "pos" para iterar sobre este array "variacion"
Ahora, veamos, como todo método recursivo, tenemos una condición de parada que se cumplira cuando la variable "pos" (la cual itera sobre "variacion") sea igual al Length del array "variacion" (o lo que es lo mismo, que ya se ha haya rellenado ese array). En este caso, ya tenemos una variación completa, por lo tanto lo que haremos será Imprimirla en pantalla (lo que se haga puede variar de acuerdo al problema que estemos tratando de resolver.
Para imprimirlo en pantalla, utilizamos un método:
Código
static void Print<T>(T[] array)
{
for (int i = 0; i < array.Length; i++)
{
if (i == array.Length - 1)
Console.Write(array[i]); //Imprimimos el elemento del array es el último elemento
else
Console.Write(array[i] + " "); //Imprimimos el elemento del array más un espacio si no es el último elemento
}
}
Ahora, en caso de que no se cumpla la condición de parada significa que todavía estamos "armando" la variación.
Para armar tenemos un ciclo for, que recorre el array "original", y lo que hacemos es asignarle al array "variacion" en la posición "pos" (que itera sobre "variacion") el valor del array original en la posición i (itera sobre el array "original" utilizando el ciclo for.
Luego lo que hacemos es llamar recursivo pasándole al método el array "original", "variacion" y la variable "pos" incrementada en 1 (pos + 1), ya que pusimos un elemento en el array y ahora vamos a poner otro en la siguiente posición.
Voy a poner un ejemplo:
Imaginen el array "original" como había dicho:
Código
string[] valores = {"a", "b", "c", "d", "e"};
Y ahora, el array "variacion" estaría así en un principio
[ ] | [ ] | [ ]
O sea, vacío
[ a ] | [ ] | [ ] - pos = 0
[ a ] | [ a ] | [ ] - pos = 1
[ a ] | [ a ] | [ a ] - pos = 2
Luego se retorna la llamada y entonces pos=3, aquí se imprime la variación pues ya está completa. Luego el ciclo for camina y entonces la próxima asignación que se hace es:
[ a ] | [ a ] | [ b ] - pos = 2
Espero esto se haya entendido.
Si tienen alguna duda pregunten, pues esto a veces es enredado para verlo si no se ha visto alguna vez y/o no entienden bien la recursividad. Sobre todo, también es algo difícil explicarlo así en plan texto.
Seguimos con combinatoria (espero hayan entendido el anterior, pues no explicaré tan a fondo debido a la similitud
24 - Variaciones sin repetición
Este algoritmo es algo parecido, simplemente que no vamos a repetir elementos en cada variación.
Lo primero que voy a hacer es poner un ejemplo:
Utilicemos el mismo array que teníamos en el código anterior:
Código
string[] valores = {"a", "b", "c", "d", "e"};
Si quisiéramos hallar todas las variaciones sin repetición en secuencias de 3 de este array obtendríamos:
Citar
a a a
a b c
a b d
a b e
a c b
a c d
a c e
a d c
a d b
a d e
...
...
e a c
e a d
e a b
El orden de la complejidad temporal sería un equivalente a N!/(N-M)!, siendo N la cantidad de elementos y M el tamaño de la secuencia. Esto es deducible de la posibilidad de por cada espacio de la secuencia (M), en este caso 3, se pueden poner (N-1), este caso 4 elementos posibles en la próxima posición, y después en la próxima (N-2), y asi sucesivamente, por lo que quedaría algo como: 5*4*3 = 5*(5-1)*(5-2) = 5!/(5-3)! = N!/(N-M)!
Primero voy a explicar un método que vamos a utilizar aquí. Utilizaremos un método para hacer Swap entre dos elementos. Este método ya lo había explicado anteriormente en otro código, pero este tiene dos peculiaridades diferentes, primero que lo hice genérico para mostrar esto, y segundo que hace el intercambio pero de las referencias.
Este es el código:
Código
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
Primero explico la palabra clave (keyword) ref. Esta palabra clave a un argumento causa que el argumento sea pasado al método por referencia y no por valor. El efecto de pasar un argumento por referencia implica que cualquier cambio que se realice al parámetro dentro del método es reflejado en el argumento en el método desde cual fue llamado.
Para llamar a un método pasándole un argumento por referencia se haría algo así:
Código
static void Main(string[] args)
{
int numberOne = 1;
Inc(ref numberOne);
Console.WriteLine(numberOne); //El valor que se imprimirá será 2
}
public static void Inc(ref int number)
{
number++;
}
Ahora, que el método sea genérico, implica que se utilizará un placeholder, dentro de todo el método para las operaciones con este tipo de datos dentro del método. Se podrá utilizar el método con cualquier tipo de dato siempre que no cause error en tiempo de ejecución de acuerdo a la función que se realice con él. Genéricas pueden ser clases, estructuras, interfaces y métodos.
Esto es una forma EXTREMADAMENTE lazy de explicarla, recomiendo ir a la MSDN para leer sobre esto.
Una vez visto, solo resta decir sobre este método que funciona intercambiando las referencias de las variables.
Ahora veamos el método como tal:
Código
//Variaciones sin repetición de N elementos en M
/// <summary>
/// Método portal
/// </summary>
static void VariacionesSinRepeticion(string[] original, int size)
{
VariacionesSinRepeticion(original, size, 0);
}
static void VariacionesSinRepeticion(string[] original, int size, int pos)
{
if (pos == size)
{
Print(original, size);
Console.WriteLine();
}
else
{
for (int i = pos; i < original.Length; i++)
{
Swap(ref original[pos], ref original[i]);
VariacionesSinRepeticion(original, size, pos+1);
Swap(ref original[pos], ref original[i]);
}
}
}
Primero que todo démonos cuenta que es bastante parecido al otro método (VariacionesConRepeticion()). Tenemos el método portal y el método recursivo, pero vemos que solo trabajamos sobre un array, pues por eso utilizamos un método Swap para hacer intercambio de valores (que después lo volvemos a intercambiar para ponerlos en la posición original. Tenemos la condición de parada que se cumple cuando "pos" sea igual al tamaño (M) de la variación que viene dado por la variable "size"
Ahora, hay un pequeño cambio en el ciclo for, y es que el ciclo no empieza con la variable i en 0, sino que empieza con el valor de "pos". Y se hace un Swap antes del llamado recursivo y uno después, el cual pone los valores en la posición anterior a cambiarlo. Igual que en el método anterior se llama recursivo incrementando la variable "pos"
Veamos un ejemplo utilizando el siguiente array y calculando las variaciones con tamaño 3:
Código
string[] letras = { "a", "b", "c" };
Como trabajamos sobre le array "original", el mismo estaría así al principio:
[ a ] | [ b ] | [ c ] - i= 0 y pos = 0
[ a ] | [ b ] | [ c ] - i= 0 y pos = 1
[ a ] | [ b ] | [ c ] - i= 0 y pos = 2
[ a ] | [ b ] | [ c ] - i= 0 y pos = 3 (Se cumplió la condición de parada y por lo tanto se tiene una variación, se imprime)
Luego, cuando se retorne el llamado tenemos a pos = 2 e i = 2 y cuando se incremente en el ciclo no se va a cumplir la condición del ciclo, va a terminar y va retornar la llamada, donde tendremos a pos = 1 e i = 1. Aquí ahora se va a incrementar i, pues va a cumplirse la condición del ciclo y tendremos a pos = 1 e i = 2, y por lo tanto se va a hacer el Swap y va a quedar así:
[ a ] | [ c ] | [ b ] - i= 2 y pos = 1
Y después de se cumplirá la condición de parada y tendremos la variación lista. Así es prácticamente el funcionamiento del algoritmo, les recomiendo que le hagan un Debug Step-By-Step para entenderlo mejor.
Nota: Como ven en ningón momento tenemos una variación en un array nuevo, si nuestro problema requiere devolver esta variación debemos hacer una copia del array original a uno nuevo copiando "size" elementos.
Código
string[] destino = new string[size];
Array.Copy(original, destino, size);
25 - Combinaciones
Primero que todo, veamos un ejemplo:
Si quisiéramos hallar todas las combinaciones posibles de secuencias de 5 de este array:
Código
string[] valores = {"a", "b", "c", "d", "e"};
Obtendríamos:
Citar
a b c d e
En caso de que quisiéramos hallarlas en secuencias de 3, obtendríamos:
Citar
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
Consideremos cada secuencia un subconjunto del conjunto original (el array valores). Cada uno de estos subconjuntos son diferentes dos a dos.
Llamemos "combinaciones" a todas las formas posibles de tomar un subconjunto de elementos de un conjunto con un tamaño predefinido donde ninguno de estas formas son iguales y cada subconjunto no repite elemento.
Nota: Tengan en cuenta que vamos a utilizar el método Print() que declaramos y utilizamos arriba (Variaciones con repetición)
Como en casos anteriores vamos a tener un método portal, al cual le pasaremos como parámetro el array con los elementos. Ambos métodos los declaré genéricos. Repito, para entender mejor cómo funciona la genericidad de parámetros les recomiendo ir a la MSDN
Código
/// <summary>
/// Método portal
/// </summary>
static void Combinaciones<T>(T[] letras, int m)
{
Combinaciones(letras, new T[m], 0, 0);
}
Esté método recibe como parámetro el array con los elementos y un int que representa el tamaño de las combinaciones a buscar. Este int debe ser menor o igual que la cantidad de elementos del array. Por lo tanto les recomiendo que hagan una validación a este parámetro en el método portal.
El método recursivo recibe 4 parámetros, dos array y dos int. El primer array es el original, el segundo es el array para ir creando cada combinación, por lo tanto lo que se le pasa es un array nuevo con tamaño igual al int que recibió el método portal (new T[m]]. Ahora, los int que recibe son para iterar sobre los array original y combinacion respectivamente.
Luego, veamos el código del método recursivo:
Código
static void Combinaciones<T>(T[] original, T[] combinacion,
int posOriginal, int posCombinacion )
{
if (posCombinacion == combinacion.Length)
{
Print(combinacion); //Imprimimos la combinación
Console.WriteLine(); //Hacemos un salto de linea en la consola
}
else if (posOriginal == original.Length)
return;
else
{
combinacion[posCombinacion] = original[posOriginal];
Combinaciones(original, combinacion, posOriginal + 1, posCombinacion + 1);
Combinaciones(original, combinacion, posOriginal + 1, posCombinacion);
}
}
En este método lo primero que hacemos es establecer las condiciones de parada (para la recursividad).
La primera es si se completó una combinación, por lo tanto vemos que la variable que itera sobre el array combinacion llego a la longitud del array. En tal caso, imprimimos la combinación.
La segunda condición es si ya se utilizaron todos los elementos originales en las combinaciones que antecedían con un elemento fijo.
Veamos un ejemplo de cómo funcionaría la otra parte del código:
Supongamos que el array original es:
Código
string[] original = {"a", "b", "c", "d", "e"};
Antes de que se ejecute la línea:
Código
combinacion[posCombinacion] = original[posOriginal];
Tendremos el array combinacion:
[ null ] | [ null ] | [ null ]
Luego:
[ a ] | [ null ] | [ null ]
Luego se ejecutará el llamado recursivo:
Código
Combinaciones(original, combinacion, posOriginal + 1, posCombinacion + 1);
Y despues tendremos esto:
[ a ] | [ b ] | [ null ]
[ a ] | [ b ] | [ c ]
Y al llamar recursivo se cumplirá la primera condición de parada pues ya tenemos la primera combinación. Luego al salir de la recursividad, se llama recursivo de nuevo:
Código
Combinaciones(original, combinacion, posOriginal + 1, posCombinacion);
Pero esta vez solo incrementamos la variable que itera sobre el array original. Por lo tanto esa variable estará apuntando al elemento (d) del array original
Y tras hacer:
Código
combinacion[posCombinacion] = original[posOriginal];
Tendremos:
[ a ] | [ b ] | [ d ]
Luego:
[ a ] | [ b ] | [ e ]
Y Luego se cumplirá la segunda condición de parada, por lo tanto saldremos de la recursividad hasta que la variable que itere por el array combinacion este sobre el elemento 1.
Todo ira funcionando de esa manera.
Espero que se entienda, es un poco enredado, pero una vez que le hagas un step-by-step debug lo entenderán.
Luego continúo con los códigos.
Salu2s
Eleкtro:
Este hilo ya ha llegado a las 900 visitas, es un poco frustrante que nadie se haya molestado en opinar sobre los códigos o el esfuerzo en desarrollarlos y publicarlos para compartirlos con ustedes... no sean tan descortés.
Genial aporte y gracias por tu colaboración desinteresada.
Hace falta más gente como tu en el foro ...en toda la WWW en general.
Saludos
DarK_FirefoX:
26 - Evaluar una expresión en Notación Posfija (Notación Polaca Inversa)
Primero que todo, ¿Qué es la Notación Posfija (Notación Polaca Inversa)? Pues, es un método algebraico alternativo de introducción de datos, en está notación primero están los operandos y después viene el operador que se va a utilizar para realizar el cálculo sobre los operandos. En esta notación no se necesitan utilizar paréntesis para indicar el orden de las operaciones.
Veamos un ejemplo de notación posfija:
Código:
'4' '2' '10' '+' '*' '5' '-' = '43'
Para implementar esto, primero veamos el algoritmo que se utiliza:
Citar
-Si hay elementos en la bandeja de entrada
-Leer el primer elemento de la bandeja de entrada.
-Si el elemento es un operando.
-Poner el operando en la pila.
-Si no, el elemento es una función (los operadores, como "+", no son más que funciones que toman dos argumentos).
-Se sabe que la función x toma n argumentos.
-Si hay menos de n argumentos en la pila
-(Error) El usuario no ha introducido suficientes argumentos en la expresión.
-Si no, tomar los últimos n operandos de la pila.
-Evaluar la función con respecto a los operandos.
-Introducir el resultado (si lo hubiere) en la pila.
-Si hay un sólo elemento en la pila
-El valor de ese elemento es el resultado del cálculo.
-Si hay más de un elemento en la pila
-(Error) El usuario ha introducido demasiados elementos.
^^ Fuente: Wikipedia
En la implementación que hice, que estoy seguro, no es la mejor, solo tuve en cuenta los operadores +, -, *, /. Pueden añadirle más operadores para la raíz, potencia, etc.
Código
static long EvalPosFixed(string[] exp)
{
Stack<long> values = new Stack<long>();
long first, second = 0;
for (int i = 0; i < exp.Length; i++)
{
switch (exp[i])
{
case "+":
if (values.Count < 2)
throw new Exception("There are not enough arguments to operate");
second = values.Pop();
first = values.Pop();
values.Push(first + second);
break;
case "-":
if (values.Count < 2)
throw new Exception("There are not enough arguments to operate");
second = values.Pop();
first = values.Pop();
values.Push(first - second);
break;
case "*":
if (values.Count < 2)
throw new Exception("There are not enough arguments to operate");
second = values.Pop();
first = values.Pop();
values.Push(first * second);
break;
case "/":
if (values.Count < 2)
throw new Exception("There are not enough arguments to operate");
second = values.Pop();
if (second == 0)
throw new DivideByZeroException("Can't divide by 0");
first = values.Pop();
values.Push(first / second);
break;
default:
values.Push(long.Parse(exp[i]));
break;
}
}
if (values.Count > 1)
throw new Exception("The expression had more arguments than it should have");
return values.Peek();
}
El método no tiene nada complicado, recibe un array de string, el cual representa la expresión posfija, donde cada elemento del array representa un operando o un operador. En el método se recorre el array y se hace un switch para identificar los operadores. Lo demás se rige al algoritmo expuesto anteriormente.
Nota: No vuelvo a explicar el uso de una pila (Stack), pues ya lo expliqué en el código 22 - Saber si una cadena tiene paréntesis balanceados
Voy a ilustrarles, de cierta manera, el funcionamiento del algoritmo:
Supongamos que la entrada es:
Código
string[] expresion = { "4", "2", "10", "+", "*", "5", "-"};
Luego:
EntradaOperaciónPilaComentario4Introducir en la pila42Introducir en la pila4, 210Introducir en la pila4, 2, 10+Suma4, 12Toma los dos últimos valores de la pila (2, 10) y los sustituye por el resultado (12)*Multiplicación48Toma los dos últimos valores de la pila (4, 12) y los sustituye por el resultado (48)5Introducir en la pila48 5-Resta43Toma los dos últimos valores de la pila (48, 5) y los sustituye por el resultado (43)
Al finalizar, el resultado (en este caso 43) será el único elemento en la pila.
Espero que hayan entendido este código.
Salu2s
Navegación
[#] Página Siguiente
[*] Página Anterior