lunes, 12 de noviembre de 2012

Métodos útiles


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, 2ref 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 + 1ref 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, -100173417 }, 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, 2ref 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 + 1ref 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