c# - recursividad - Compara dos factoriales sin calcular

recursividad c# (8)

¿Hay alguna forma de comparar qué número factorial es mayor entre dos números sin calcular?
El escenario es que estoy creando una aplicación de consola AC # que toma dos entradas factoriales como

123!!!!!! 456!!!

todo lo que quiero hacer es comparar qué valor factorial es mayor que el otro, el fragmento de código que hice es

try { string st = Console.ReadLine(); Int64 factCount = 0; while (st.Contains(''!'')) { factCount = st.Where(w => w == ''!'').Count(); st = st.Replace(''!'', '' ''); }; decimal result = 1 ; for (Int64 j = 0; j < factCount; j++) { UInt64 num = Convert.ToUInt64(st.Trim()); for (UInt64 x = num; x > 0; x--) { result = result * x; } } if (factCount == 0) { result = Convert.ToUInt64(st.Trim()); } string st2 = Console.ReadLine(); Int64 factCount2 = 0; while (st2.Contains(''!'')) { factCount2 = st2.Where(w => w == ''!'').Count(); st2 = st2.Replace(''!'', '' ''); }; decimal result2 = 1; for (Int64 j = 0; j < factCount2; j++) { UInt64 num = Convert.ToUInt64(st.Trim()); for (UInt64 x = num; x > 0; x--) { result2 = result2 * x; } } if (factCount2 == 0) { result2 = Convert.ToUInt64(st2.Trim()); } if (result == result2) { Console.WriteLine("x=y"); } else if (result < result2) { Console.WriteLine("x<y"); } else if (result > result2) { Console.WriteLine("x>y"); } } catch (Exception ex) { Console.WriteLine(ex.Message); Console.ReadLine(); }

pero el error que obtengo es
el valor es demasiado grande o demasiado pequeño para el decimal
Entendí el error, pero ¿hay alguna forma de hacerlo?

Indique si hay algún otro tipo de datos que tenga un valor mayor que el decimal o si existe alguna otra forma de comparar estos factores.

Después de implementar la sugerencia de @Bathsheba, cambio un poco mi código

string st = Console.ReadLine(); int factCount = 0; while (st.Contains(''!'')) { factCount = st.Where(w => w == ''!'').Count(); st = st.Replace(''!'', '' ''); }; string st2 = Console.ReadLine(); int factCount2 = 0; while (st2.Contains(''!'')) { factCount2 = st2.Where(w => w == ''!'').Count(); st2 = st2.Replace(''!'', '' ''); }; int resultFactCount = factCount - factCount2; decimal result = 1; decimal result2 = 1; if (resultFactCount > 0) { for (Int64 j = 0; j < resultFactCount; j++) { UInt64 num = Convert.ToUInt64(st.Trim()); for (UInt64 x = num; x > 0; x--) { result = result * x; } } if (factCount == 0) { result = Convert.ToUInt64(st.Trim()); } UInt64 num1 = Convert.ToUInt64(st.Trim()); if (result == num1) { Console.WriteLine("x=y"); } else if (result < num1) { Console.WriteLine("x<y"); } else if (result > num1) { Console.WriteLine("x>y"); } } else { int resultFactCount1 = System.Math.Abs(resultFactCount); for (Int64 j = 0; j < resultFactCount1; j++) { UInt64 num = Convert.ToUInt64(st.Trim()); for (UInt64 x = num; x > 0; x--) { result2 = result2 * x; } } if (factCount2 == 0) { result2 = Convert.ToUInt64(st2.Trim()); } UInt64 num1 = Convert.ToUInt64(st.Trim()); if (result2 == num1) { Console.WriteLine("x=y"); } else if (result2 < num1) { Console.WriteLine("x<y"); } else if (result2 > num1) { Console.WriteLine("x>y"); } }

Perdón por decirlo pero todavía 123! es tan grande que estoy recibiendo el mismo error

Tradicionalmente m!!...! con n ! s significa m(mn)(m-2n).... sin embargo, aquí se toma como (...((m!)!)!...)!
Nota de Alec, sí lo sé, esta es una notación desafortunada, pero se ve que la definición convencional es mucho más útil (en combinatoria, el lugar de donde provienen los factores) que la que OP quiere.
Me gustaría poner esto en un comentario, pero sería eclipsado por los demás y esto es bastante importante.

A diferencia de las otras respuestas, puede hacerlo sin ninguna aproximación.

Aquí está :

123 !!!!!! > 456 !!!

significa en realidad

123 !!!!! > 456 !! 123 !!!! > 456 !

y también

123 !!! > 456

Entonces solo necesita probar lo anterior. Es simple porque tiene al menos un operando que puede caber en un UInt64

Así que esto debería darte algo como esto:

public class Program { static bool LeftIsGreaterThanRightSide(UInt64 leftSide, int leftSidefactCount, UInt64 rightSide) { try { checked // for the OverflowException { UInt64 input2 = leftSide; int factCount = leftSidefactCount; UInt64 result = 1; for (Int64 j = 0; j < factCount; j++) { UInt64 num = input2; for (UInt64 x = num; x > 0; x--) { result = result * x; } } // None of the operand are great or equal than UInt64.MaxValue // So let''s compare the result normaly return result > rightSide; } } catch (OverflowException) { // leftSide overflowed, rightSide is a representable UInt64 so leftSide > rightSide ; return true; } } static void Main() { String input1 = Console.ReadLine(); String input2 = Console.ReadLine(); int fact1Count = input1.Count(c => c == ''!''); int fact2Count = input2.Count(c => c == ''!''); UInt64 x = Convert.ToUInt64(input1.Replace("!", String.Empty).Trim()); UInt64 y = Convert.ToUInt64(input2.Replace("!", String.Empty).Trim()); x = x == 0 ? 1 : x ; // Handling 0 ! y = y == 0 ? 1 : y; if (fact1Count > fact2Count) { fact1Count = fact1Count - fact2Count; Console.WriteLine(LeftIsGreaterThanRightSide(x, fact1Count, y) ? "x > y" : "x <= y"); } else { fact2Count = fact2Count - fact1Count; Console.WriteLine(LeftIsGreaterThanRightSide(y, fact2Count, x) ? "y > x" : "y <= x"); } Console.ReadLine(); } }

Aquí, a!! se define como (a!)! .

123!!!!!! es absolutamente gigantesco Creo que necesitarías más partículas que las que existen en el universo si fueras a escribir con tinta.

Por lo tanto, no puede comparar los números directamente. Supongo que no hay una clase numérica que pueda hacer esto.

Lo que puedes hacer es considerar el cociente 123!!!!!! / 456!!! 123!!!!!! / 456!!! . Muchos de los múltiplos serán similares, por lo que puede cancelarlos. Tenga en cuenta también que detrás ! se cancelará Esto es porque x> y lo implica, y está implícito en x! > y! donde xey son números enteros positivos.

Eventualmente, llegarás a un punto en el que puedes evaluar esto como si fuera menor o mayor que 1, dando así tu respuesta.

Puedo decirte en la inspección que 123!!!!!! es más grande desde 123!!! es más grande que 456 .

Como otras personas dijeron, 123 !!!!!! y 456 !!! son demasiado grandes para ser representados por una computadora, y una comparación del tipo x!! <=> y! x!! <=> y! reduce a x! <=> y x! <=> y .

Una vez que llegue a la cantidad mínima posible de ! (cortándolos de las cuerdas), puedes evaluar los operandos. Uno de los números será un número entero común (sin factorial), por lo que no hay trabajo aquí. El otro tendrá al menos un factorial, de lo contrario, la comparación es trivial.

Supongamos que la comparación es x! <=> y x! <=> y (un factorial). Si x >= y , has terminado. Si x < y , evalúa x! y compara

Supongamos que la comparación es x!! <=> y x!! <=> y (dos factoriales). Tabulando los valores más pequeños:

1!! = 1! = 1 2!! = 2! = 2 3!! = 6! = 720 4!! = 24! = 620,448,401,733,239,439,360,000 5!! = 120! = about 6.6895 * 10^198 6!! = 720! = about 2.6012 * 10^1746

Entonces, para cualquier y , x > 4 resultará en x!! > y x!! > y . Para x <= 4 , evalúa x!! y compara

Para más factoriales, recuerda que x!!! = (x!)!! x!!! = (x!)!! , evalúa x! y usa los pasos anteriores.

Definamos un tipo para representar una operación de factoriales repetidos:

public struct RepeatedFactorial { private readonly int _baseNumber; private readonly int _repeats; public int BaseNumber { get { return _baseNumber; } } public int Repeats { get { return _repeats; } } public RepeatedFactorial(int baseNumber, int repeats) { if (baseNumber < 0 || repeats < 0) throw new ArgumentOutOfRangeException(); _baseNumber = baseNumber; _repeats = repeats; } }

Ahora, si implementamos un IComparable<Factorial> , podemos encontrar la respuesta deseada.

public int CompareTo(RepeatedFactorial other) { // ? }

Consideremos primero algunos de los casos más simples.

De acuerdo, los únicos casos que no se manejan son los que tienen menos factoriales repetidos que other o viceversa. Pasemos una de esas cajas a la otra, así que tenemos menos que enfrentar:

Ahora solo tenemos que preocuparnos de que tenga menos repeticiones que other . ¡Ya que X> Y implica X! > ¡Y! y así sucesivamente podemos reducir este problema a uno en el que sabemos que tiene cero repeticiones:

public int CompareTo(RepeatedFactorial other) { if (BaseNumber == 0) { // If Repeats is zero the value of this is zero, otherwise // this is the same as a value with BaseNumber == 1 and no factorials. // So delegate to the handling of that case. if (Repeats == 0) return other.BaseNumber == 0 && other.Repeats == 0 ? 0 : -1; return new RepeatedFactorial(1, 0).CompareTo(other); } if (other.BaseNumber == 0) // Likewise return other.Repeats == 0 ? 1 : CompareTo(new RepeatedFactorial (1, 0)); if (Repeats == other.Repeats) // X < Y == X! < Y!. X > Y == X! > Y! And so on. return BaseNumber.CompareTo(other.BaseNumber); if (Repeats > other.Repeats) return -other.CompareTo(this); if (Repeats != 0) return new RepeatedFactorial(BaseNumber, 0).CompareTo(new RepeatedFactorial(other.BaseNumber, other.Repeats - Repeats); ??? }

Ahora necesitamos this.BaseNumber cómo this.BaseNumber compara con otro. other.BaseNumber con el número apropiado de factoriales aplicados. ¡Obviamente si other.BaseNumber es mayor que 12, entonces desde 13! es mayor que int.MaxValue debe ser mayor que this.BaseNumber :

Ahora nos queda calcular el número real. Sin embargo, si al comienzo de un ciclo de factoriales tenemos 13 o más, entonces podemos devolver -1 con la misma lógica que la anterior. De lo contrario, si alguna vez terminamos con un número mayor que this.BaseNumber podemos devolver -1 .

Y, por lo tanto, tenemos nuestra respuesta y nunca tenemos que calcular un factorial mayor que 12 !.

Poniendolo todo junto:

public struct RepeatedFactorial : IComparable<RepeatedFactorial> { private readonly int _baseNumber; private readonly int _repeats; public int BaseNumber { get { return _baseNumber; } } public int Repeats { get { return _repeats; } } public RepeatedFactorial(int baseNumber, int repeats) { if (baseNumber < 0 || repeats < 0) throw new ArgumentOutOfRangeException(); _baseNumber = baseNumber; _repeats = repeats; } public int CompareTo(RepeatedFactorial other) { if (BaseNumber == 0) { // If Repeats is zero the value of this is zero, otherwise // this is the same as a value with BaseNumber == 1 and no factorials. // So delegate to the handling of that case. if (Repeats == 0) return other.BaseNumber == 0 && other.Repeats == 0 ? 0 : -1; return new RepeatedFactorial(1, 0).CompareTo(other); } if (other.BaseNumber == 0) // Likewise return other.Repeats == 0 ? 1 : CompareTo(new RepeatedFactorial (1, 0)); if (Repeats == other.Repeats) // X < Y == X! < Y!. X > Y == X! > Y! And so on. return BaseNumber.CompareTo(other.BaseNumber); if (Repeats > other.Repeats) return -other.CompareTo(this); if (Repeats != 0) return new RepeatedFactorial(BaseNumber, 0).CompareTo(new RepeatedFactorial(other.BaseNumber, other.Repeats - Repeats)); int accum = other.BaseNumber; for (int rep = 0; rep != other.Repeats; ++rep) { if (accum > 12 || accum > BaseNumber) return -1; for (int mult = accum - 1; mult > 1; --mult) accum *= mult; } return BaseNumber.CompareTo(accum); } }

Editar:

Me acabo de dar cuenta de que en realidad estaba usando valores de 64 bits en su pregunta. ¡Eso se adapta fácilmente, y nunca más tenemos que calcular 20!

public struct RepeatedFactorial : IComparable<RepeatedFactorial> { private readonly ulong _baseNumber; private readonly long _repeats; public ulong BaseNumber { get { return _baseNumber; } } public long Repeats { get { return _repeats; } } public RepeatedFactorial(ulong baseNumber, long repeats) { if (baseNumber < 0 || repeats < 0) throw new ArgumentOutOfRangeException(); _baseNumber = baseNumber; _repeats = repeats; } public int CompareTo(RepeatedFactorial other) { if (BaseNumber == 0) // This is the same as a value with BaseNumber == 1 and no factorials. // So delegate to the handling of that case. return new RepeatedFactorial(1, 0).CompareTo(other); if (other.BaseNumber == 0) // Likewise return CompareTo(new RepeatedFactorial (1, 0)); if (Repeats == other.Repeats) // X < Y == X! < Y!. X > Y == X! > Y! And so on. return BaseNumber.CompareTo(other.BaseNumber); if (Repeats > other.Repeats) return -other.CompareTo(this); if (Repeats != 0) return new RepeatedFactorial(BaseNumber, 0).CompareTo(new RepeatedFactorial(other.BaseNumber, other.Repeats - Repeats)); ulong accum = other.BaseNumber; for (long rep = 0; rep != other.Repeats; ++rep) { if (accum > 20 || accum > BaseNumber) return -1; for (ulong mult = accum - 1; mult > 1; --mult) accum *= mult; } return BaseNumber.CompareTo(accum); } }

Esto debería ser fácil:

Como otros han dicho, puedes eliminar todos los "¡" comunes! porque x > y <==> x! > y! x > y <==> x! > y!

El programa esencialmente tendrá que demostrar que un factorial (123 !!!) es más grande que un número ordinario. Puede resolver esto con una salida rápida del ciclo. Al calcular el factorial, puede regresar tan pronto como el producto sea más grande que 456, ya que un factorial siempre crecerá con iteraciones adicionales.

// While string parsing check if one number equals 0 and has at least // one "!" - if yes set its value to 1 ( because 0! = 1! = 1 ) int x = 123; int y = 456; int numberOfFactorials = 3; try { for( int i = 0; i < numberOfFactorials; ++i ) { for ( int j = x-1; j > 0; --j ) { x *= j; // This quick exit will return after one iteration // because 123*122 > 456 if ( x > y ) return "x is bigger than y"; } } return x == y ? "gosh they are the same!" : "x is smaller than y"; } catch( OverflowException e ) { return "x Overflowed so it is bigger than y!"; }

También puede usar BigInteger con este Método si desea analizar números aún mayores para Parámetros de entrada.

Para enteros positivos, en caso de que ambos lados tengan el mismo número de factoriales, sería tan simple como comparar los dos números

123!!!! 456!!!! 456 > 123 456!!!! > 123!!!!

De lo contrario, la comparación de los dos factores, se reduce a esto

123!!!!!! 456!!! (123!!!)!!! (456!!!) 123!!! 456

En este punto trataremos de evaluar los factoriales uno por uno, hasta que hayamos superado el otro número.

Como el otro número es un número que puede almacenarse en una variable, esto significa que el tiempo ha alcanzado computacionalmente un número más alto, o ha atrapado una excepción de desbordamiento, entonces es un número mayor, de lo contrario, es más pequeño.

El siguiente es un código pesudo, no un código real:

int max_factorial (int x, int x_fact, int y, int y_fact) { int A=1,B=1,F=0,product=1,sum=0; if (x_fact == y_fact) return (x>y?x:y); if (x_fact > y_fact) { A = x; B = y; F = x_fact-y_fact; } else { A = y; B = x; F = y_fact-x_fact; } for (int k=0; k<F; k++) { try { for (int i=1; i<A; i++) { // multiplication in terms of addition // P * i = P + P + .. P } i times sum = 0; for (int p=0; p<i; p++) sum += product; product = product + sum; if (product > B) return A; } } catch (OverflowException e) { return A; } } return B; }

Para números dados, suponiendo que 456!!! significa ((456!)!)! tenemos

123!!!!!! == (123!!!)!!!

123!!! >>> 456 // >>> stands for "much, much...much larger", ">>" is not enough

¡incluso 123! (que es 1.2e205 ) mucho más grande que solo 456

Para estimar los valores reales de los factores, usemos la aproximación de Stirling

https://en.wikipedia.org/wiki/Stirling%27s_approximation

es decir

ln(n!) == n * ln(n) - n lg(n!) == ln(n!)/ln(10) == n * ln(n) / ln(10) - n / ln(10) == n * lg(n) - n / ln(10) n! == n ** n / exp(n)

Entonces ((456!)!)! es sobre

lg(456!) == 1014 lg((456!)!) == 1e1014 * 1014- 1e1014/ln(10) == 1e1017 lg(((456!)!)!) == 1e(1e1017) ((456!)!)! == 1e(1e(1e1017))

que es un número extremadamente grande (tenga en cuenta la triple exponenciación) y es por eso que no se puede representar como un valor ingenuo de BigInteger .

BigInteger Type puede manejar enteros grandes. Pero no lo suficientemente grande como para su ejemplo.

Los factoriales pequeños pueden tenerse en cuenta en sus factores primos, sin tener que calcular primero el factorial en sí mismo, y los factores idénticos pueden cancelarse.

¡También puedes cancelar el final ! ¡como lo sugirió Leherenn arriba , desde 123! es más grande que 456, (123 !!!) !!! también será más grande que (456) !!!