Descargar Solución de la galería de códigos de msdn aqui
Suma de Entero, 8 Damas en un tablero de ajedrez, Construccion de Subconjuntos {1,3,4,5,... N} 2^N, Descomponer en factores primos, Numero mas cercano, trio pitagoricos, Numeros primos.
Metodo para suma de enteros: (Descompone en sumandos el numero que se pasa por parametro)
#region Suma de Entero /// <summary> /// Descompone en sumandos el numero que se pasa por parametro /// </summary> /// <param name="number">numero a descomponer</param> public void BreakDownAdds(int number) { BreakDown(number, number, string.Empty); } /// <summary> /// Parte recursiva del metodo BreakDownAdds. /// /// </summary> /// <param name="originalNumber">numero original</param> /// <param name="rest">numero que puedo ir quitando</param> /// <param name="des">cadena que contiene la suma hasta ahora</param> private void BreakDown(int originalNumber, int rest, string descomposicion) { if (originalNumber < 0 || rest <= 0) return; //quite de mas ó no puedo quitar mas ningun numero if (originalNumber == 0)// ya tengo en descomposicion la cadena a imprimir { Console.WriteLine(descomposicion); return; } // quito,pero tengo la oportunidad de quitar de nuevo el mismo numero BreakDown(originalNumber - rest, rest, (string.IsNullOrEmpty(descomposicion))
? rest.ToString() : descomposicion + "+" + rest); //no quito y disminuyo en uno al numero qe se puede ir quitando BreakDown(originalNumber, rest - 1, descomposicion); } #endregion
Colocar 8 damas en el tablero: (Imprime todas las posibilidades de colocar 8 reinas en un tablero de ajedrez)
#region 8 Damas en un tablero de ajedrez /// <summary> /// Imprime todas las posibilidades de colocar 8 reinas en un tablero de /// ajedrez /// <param name="n">cantidad de reinas</param> /// <returns>La cantidad de formas de poner las damas</returns> /// </summary> public int EightQueens(int n) { int cantidad = 0; bool[,] array = new bool[n, n]; PEightQueens(n, array, ref cantidad); return cantidad; } private void PEightQueens(int reinas, bool[,] array, ref int cant) { if (reinas == 0 && CheckQueensAll(array)) { cant++; PrintSolution(array, cant); return; } if (reinas == 0) return; int columna = array.GetLength(0) - reinas; for (int fila = 0; fila < array.GetLength(0); fila++) { if (CheckThreat(ref array, fila, columna)) { array[fila, columna] = true; PEightQueens(reinas - 1, array, ref cant); array[fila, columna] = false; } } } private bool CheckQueensAll(bool[,] array) { for (int i = 0; i < array.GetLength(0); i++) for (int j = 0; j < array.GetLength(0); j++) for (int k = 0; k < array.GetLength(0); k++) for (int m = 0; m < array.GetLength(0); m++) if ((i != k) && (j != m) && array[i, j] && array[k, m]
&& Threat(i, j, k, m))
{
return false;
}
return true;
}
private bool CheckThreat(ref bool[,] array, int fila, int columna)
{
for (int i = 0; i <= fila; i++)
for (int j = 0; j <= columna; j++)
if (array[i, j] && Threat(i, j, fila, columna))
return false;
return true;
}
private bool Threat(int x1, int y1, int x2, int y2)
{
/*
* OJO
*
* Vean que se hace un cast a double, de no hacer esto ocurre que -5/3 = -1 == 1 !!!!
*
*/
return (x1 == x2 || y1 == y2 || (y1 - y2) / (double)(x1 - x2) == 1.0
|| (y1 - y2) / (double)(x1 - x2) == -1.0); } private void PrintSolution(bool[,] array, int numero) { Console.WriteLine("Solucion # {0}", numero); Console.Write("{"); for (int i = 0; i < array.GetLength(0); i++) for (int j = 0; j < array.GetLength(1); j++) if (array[i, j]) Console.Write(" {0} ", j); Console.Write("}" + Environment.NewLine); } #endregion
Construccion de Subconjuntos: ( Metodo que imprime todos los subconjuntos de los numeros enteros hasta N. Otra manera de ver esto es que imprime los subconjuntos del conujunto {1,2,3,4,.. N})
#region [ Construccion de Subconjuntos {1,3,4,5,... N} 2^N] /// <summary> /// Metodo que imprime todos los subconjuntos de los numeros enteros hasta <para>N</para> /// Otra manera de ver esto es que imprime los subconjuntos del conujunto {1,2,3,4,.. N} /// </summary> /// <param name="n">Cantidad de enteros</param> public void Sets(int n) { bool[] bools = new bool[n]; PrintSolution(ref bools, 0); PSets(ref bools, 0, n); } /// <summary> /// Metodo recursivo para hallar los conjuntos. /// </summary> /// <param name="bools">arreglo de bools</param> /// <param name="p">numero inicial</param> /// <param name="max">numero maximo</param> private void PSets(ref bool[] bools, int p, int max) { for (int i = p; i < max; i++) { if (bools[i]) continue; bools[i] = true; PrintSolution(ref bools, max); PSets(ref bools, i, max); bools[i] = false; } } /// <summary> /// Metodo que imprime el conjunto /// </summary> /// <param name="c">arreglo de bool</param> /// <param name="cant">la cantidad de elementos que voy a imprimir</param> private void PrintSolution(ref bool[] c, int cant) { Console.Write("{"); for (int i = 0; i < cant; i++) if (c[i]) Console.Write(" {0} ", i + 1); Console.WriteLine("}"); } #endregion
Descomponer en factores primos:
#region Descomponer en factores primos public string DescomponerEnFactoresPrimos(int n) { string result = ""; DescomponerEnFactoresPrimos(n, 2, ref result); return result; } private void DescomponerEnFactoresPrimos(int numero, int divisor, ref string result) { if (numero == 1) return; if (numero % divisor == 0) { result += divisor + ","; DescomponerEnFactoresPrimos(numero / divisor, divisor, ref result); } else DescomponerEnFactoresPrimos(numero, divisor + 1, ref result); } #endregion
Numero mas cercano: (Retorna el numero mas cercano)
#region Numero mas cercano /// <summary> /// Retorna el numero mas cercano /// </summary> /// <param name="operandos">arreglo con los numeros a usar</param> /// <param name="resultado">numero al que se debe aproximar las operaciones</param> /// <returns>el numero mas cercano al que se debe aproximar</returns> public long ButNear(int[] operandos, long resultado) { // Mala entrada if (operandos == null || operandos.Length == 0) throw new Exception(); // Solo se puede hacer una operacion if (operandos.Length == 1) return operandos[0]; long parcial = 0; Combinations(operandos, resultado, ref parcial, 0); return parcial; } private void Combinations(int[] operandos, long resultado, ref long parcial, int pos) { if (pos >= operandos.Length) { ButNearR(operandos, resultado, ref parcial, operandos[0], 1); return; } Combinations(operandos, resultado, ref parcial, pos + 1); for (int i = pos + 1; i < operandos.Length; i++) { Swap(operandos, pos, i); Combinations(operandos, resultado, ref parcial, pos + 1); Swap(operandos, i, pos); } } private void ButNearR(int[] operandos, long resultado, ref long parcial,
long parcial1, int pos) { if (pos >= operandos.Length) { parcial = Proximity(resultado, parcial, parcial1); return; } ButNearR(operandos, resultado, ref parcial, parcial1 + operandos[pos], pos + 1); ButNearR(operandos, resultado, ref parcial, parcial1 - operandos[pos], pos + 1); ButNearR(operandos, resultado, ref parcial, parcial1 * operandos[pos], pos + 1); if (operandos[pos] != 0) ButNearR(operandos, resultado, ref parcial, parcial1 / operandos[pos], pos + 1); } private long Proximity(long result, long parcialA, long parcialB) { return (Math.Abs(result - parcialA) > Math.Abs(result - parcialB))
? parcialB : parcialA; } private void Swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } #endregion
Trio pitagoricos:
#region trio pitagoricos public void TrioPitagoricos() { int x, y, z;//x=2mn y=m^2-n^2 z=m^2+n^2 for (int n = 1; n < 12; n++) for (int m = 1; m < 12; m++) if (m + n < 12 && DivisorComun(m, n)) { x = 2 * m * n; y = m * m - n * n; z = m * m + n * n; if (x * x + y * y == z * z && n * n <= m * m) Console.WriteLine("n={0} , m={1}, x={2}, y={3}, z={4}", n, m, x, y, z); } } public bool DivisorComun(int m, int n) { if (m < n) { int tmp = m; m = n; n = tmp; } for (int i = 2; i <= n; i++) if (m % i == 0 && n % i == 0) return false; return true; } #endregion
Numeros primos: (Este metodo no funciona bien porque si el numero a n no es primo entonces no se puede decir nada.)
#region Primos #region Pequenno teorema de Fermat /// <summary> /// Este metodo no funciona bien porque /// si el numero a n no es primo entonces no se puede decir nada. /// Por ejemplo: /// /// n = 341 = 11 * 31 y si cumple que 2^340 = 1 (mod 341) /// </summary> /// <param name="n"></param> /// <returns></returns> public bool IsPrimeFermat(int n) { Random r = new Random(Environment.TickCount); int a = r.Next(n - 1); return (((long)Math.Pow(a, n)) % n == 1); } #endregion /// <summary> /// Algoritmo determinista para saber si un numero es primo /// </summary> /// <param name="n">numero a determinar si es primo</param> /// <returns>Retorna true si y solo si n es primo</returns> public bool IsPrime(int n) { for (int i = 2; i <= Math.Sqrt(n); i++) if (n % i == 0) return false; return true; } #endregion
Este es el codigo completo:
#region Using using System; #endregion namespace methods { /// <summary> /// Main Class /// </summary> class Program { /// <summary> /// Entry Point /// </summary> /// <param name="args">args</param> static void Main(string[] args) { Program p = new Program(); // Numero mas cercano int numero = 207; Console.WriteLine("El numero mas cercano a {0} es {1}",numero
, p.ButNear(new int[] { 83, -100, 17, 34, 17 }, numero)); // Descomone un numero en sumandos p.BreakDownAdds(4); // Imprime las 92 soluciones para poner 8 damas de ajedrez en un tablero int cant = p.EightQueens(8); // Imprime los subconjuntos del conjunto {1,2,3,4, ... n} en este caso {1,2,3,4,5,6} p.Sets(6); //Ver si un numero es primo Console.WriteLine(p.IsPrime(17)); Console.WriteLine(p.IsPrimeFermat(17)); } #region Suma de Entero /// <summary> /// Descompone en sumandos el numero que se pasa por parametro /// </summary> /// <param name="number">numero a descomponer</param> public void BreakDownAdds(int number) { BreakDown(number, number, string.Empty); } /// <summary> /// Parte recursiva del metodo BreakDownAdds. /// /// </summary> /// <param name="originalNumber">numero original</param> /// <param name="rest">numero que puedo ir quitando</param> /// <param name="des">cadena que contiene la suma hasta ahora</param> private void BreakDown(int originalNumber, int rest, string descomposicion) { if (originalNumber < 0 || rest <= 0) return; //quite de mas ó no puedo quitar mas ningun numero if (originalNumber == 0)// ya tengo en descomposicion la cadena a imprimir { Console.WriteLine(descomposicion); return; } // quito,pero tengo la oportunidad de quitar de nuevo el mismo numero BreakDown(originalNumber - rest, rest, (string.IsNullOrEmpty(descomposicion))
? rest.ToString() : descomposicion + "+" + rest); //no quito y disminuyo en uno al numero qe se puede ir quitando BreakDown(originalNumber, rest - 1, descomposicion); } #endregion #region 8 Damas en un tablero de ajedrez /// <summary> /// Imprime todas las posibilidades de colocar 8 reinas en un tablero de /// ajedrez /// <param name="n">cantidad de reinas</param> /// <returns>La cantidad de formas de poner las damas</returns> /// </summary> public int EightQueens(int n) { int cantidad = 0; bool[,] array = new bool[n, n]; PEightQueens(n, array, ref cantidad); return cantidad; } private void PEightQueens(int reinas, bool[,] array, ref int cant) { if (reinas == 0 && CheckQueensAll(array)) { cant++; PrintSolution(array, cant); return; } if (reinas == 0) return; int columna = array.GetLength(0) - reinas; for (int fila = 0; fila < array.GetLength(0); fila++) { if (CheckThreat(ref array, fila, columna)) { array[fila, columna] = true; PEightQueens(reinas - 1, array, ref cant); array[fila, columna] = false; } } } private bool CheckQueensAll(bool[,] array) { for (int i = 0; i < array.GetLength(0); i++) for (int j = 0; j < array.GetLength(0); j++) for (int k = 0; k < array.GetLength(0); k++) for (int m = 0; m < array.GetLength(0); m++) if ((i != k) && (j != m) && array[i, j] && array[k, m]
&& Threat(i, j, k, m))
{
return false;
}
return true;
}
private bool CheckThreat(ref bool[,] array, int fila, int columna)
{
for (int i = 0; i <= fila; i++)
for (int j = 0; j <= columna; j++)
if (array[i, j] && Threat(i, j, fila, columna))
return false;
return true;
}
private bool Threat(int x1, int y1, int x2, int y2)
{
/*
* OJO
*
* Vean que se hace un cast a double, de no hacer esto ocurre que -5/3 = -1 == 1 !!!!
*
*/
return (x1 == x2 || y1 == y2 || (y1 - y2) / (double)(x1 - x2) == 1.0
|| (y1 - y2) / (double)(x1 - x2) == -1.0); } private void PrintSolution(bool[,] array, int numero) { Console.WriteLine("Solucion # {0}", numero); Console.Write("{"); for (int i = 0; i < array.GetLength(0); i++) for (int j = 0; j < array.GetLength(1); j++) if (array[i, j]) Console.Write(" {0} ", j); Console.Write("}" + Environment.NewLine); } #endregion #region [ Construccion de Subconjuntos {1,3,4,5,... N} 2^N] /// <summary> /// Metodo que imprime todos los subconjuntos de los numeros enteros hasta <para>N</para> /// Otra manera de ver esto es que imprime los subconjuntos del conujunto {1,2,3,4,.. N} /// </summary> /// <param name="n">Cantidad de enteros</param> public void Sets(int n) { bool[] bools = new bool[n]; PrintSolution(ref bools, 0); PSets(ref bools, 0, n); } /// <summary> /// Metodo recursivo para hallar los conjuntos. /// </summary> /// <param name="bools">arreglo de bools</param> /// <param name="p">numero inicial</param> /// <param name="max">numero maximo</param> private void PSets(ref bool[] bools, int p, int max) { for (int i = p; i < max; i++) { if (bools[i]) continue; bools[i] = true; PrintSolution(ref bools, max); PSets(ref bools, i, max); bools[i] = false; } } /// <summary> /// Metodo que imprime el conjunto /// </summary> /// <param name="c">arreglo de bool</param> /// <param name="cant">la cantidad de elementos que voy a imprimir</param> private void PrintSolution(ref bool[] c, int cant) { Console.Write("{"); for (int i = 0; i < cant; i++) if (c[i]) Console.Write(" {0} ", i + 1); Console.WriteLine("}"); } #endregion #region Descomponer en factores primos public string DescomponerEnFactoresPrimos(int n) { string result = ""; DescomponerEnFactoresPrimos(n, 2, ref result); return result; } private void DescomponerEnFactoresPrimos(int numero, int divisor, ref string result) { if (numero == 1) return; if (numero % divisor == 0) { result += divisor + ","; DescomponerEnFactoresPrimos(numero / divisor, divisor, ref result); } else DescomponerEnFactoresPrimos(numero, divisor + 1, ref result); } #endregion #region Numero mas cercano /// <summary> /// Retorna el numero mas cercano /// </summary> /// <param name="operandos">arreglo con los numeros a usar</param> /// <param name="resultado">numero al que se debe aproximar las operaciones</param> /// <returns>el numero mas cercano al que se debe aproximar</returns> public long ButNear(int[] operandos, long resultado) { // Mala entrada if (operandos == null || operandos.Length == 0) throw new Exception(); // Solo se puede hacer una operacion if (operandos.Length == 1) return operandos[0]; long parcial = 0; Combinations(operandos, resultado, ref parcial, 0); return parcial; } private void Combinations(int[] operandos, long resultado, ref long parcial, int pos) { if (pos >= operandos.Length) { ButNearR(operandos, resultado, ref parcial, operandos[0], 1); return; } Combinations(operandos, resultado, ref parcial, pos + 1); for (int i = pos + 1; i < operandos.Length; i++) { Swap(operandos, pos, i); Combinations(operandos, resultado, ref parcial, pos + 1); Swap(operandos, i, pos); } } private void ButNearR(int[] operandos, long resultado, ref long parcial,
long parcial1, int pos) { if (pos >= operandos.Length) { parcial = Proximity(resultado, parcial, parcial1); return; } ButNearR(operandos, resultado, ref parcial, parcial1 + operandos[pos], pos + 1); ButNearR(operandos, resultado, ref parcial, parcial1 - operandos[pos], pos + 1); ButNearR(operandos, resultado, ref parcial, parcial1 * operandos[pos], pos + 1); if (operandos[pos] != 0) ButNearR(operandos, resultado, ref parcial, parcial1 / operandos[pos], pos + 1); } private long Proximity(long result, long parcialA, long parcialB) { return (Math.Abs(result - parcialA) > Math.Abs(result - parcialB)) ? parcialB : parcialA; } private void Swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } #endregion #region trio pitagoricos public void TrioPitagoricos() { int x, y, z;//x=2mn y=m^2-n^2 z=m^2+n^2 for (int n = 1; n < 12; n++) for (int m = 1; m < 12; m++) if (m + n < 12 && DivisorComun(m, n)) { x = 2 * m * n; y = m * m - n * n; z = m * m + n * n; if (x * x + y * y == z * z && n * n <= m * m) Console.WriteLine("n={0} , m={1}, x={2}, y={3}, z={4}", n, m, x, y, z); } } public bool DivisorComun(int m, int n) { if (m < n) { int tmp = m; m = n; n = tmp; } for (int i = 2; i <= n; i++) if (m % i == 0 && n % i == 0) return false; return true; } #endregion #region Primes #region Pequenno teorema de Fermat /// <summary> /// Este metodo no funciona bien porque /// si el numero a n no es primo entonces no se puede decir nada. /// Por ejemplo: /// /// n = 341 = 11 * 31 y si cumple que 2^340 = 1 (mod 341) /// </summary> /// <param name="n"></param> /// <returns></returns> public bool IsPrimeFermat(int n) { Random r = new Random(Environment.TickCount); int a = r.Next(n - 1); return (((long)Math.Pow(a, n)) % n == 1); } #endregion /// <summary> /// Algoritmo determinista para saber si un numero es primo /// </summary> /// <param name="n">numero a determinar si es primo</param> /// <returns>Retorna true si y solo si n es primo</returns> public bool IsPrime(int n) { for (int i = 2; i <= Math.Sqrt(n); i++) if (n % i == 0) return false; return true; } #endregion } }
Descargar Solución de la galería de códigos de msdn aqui
No hay comentarios:
Publicar un comentario