比较两个阶乘而不计算
有没有什么办法可以比较两个数字中哪个因子数字更大而没有计算？
场景是我创buildac＃控制台应用程序，它需要两个阶乘input
123!!!!!! 456!!! 我所要做的就是比较哪个因子值大于其他因子，我所做的那段代码是
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(); }
但我得到的错误是
十进制数值太大或太小
我明白这个错误，但有什么办法可以做到这一点
请build议是否有任何其他数据types的价值大于十进制或有任何其他方式来比较这些因子
执行@Bathshebabuild议后，我改变了一下我的代码
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"); } }
对不起，但仍然123！ 是如此之大，我得到同样的错误
传统上
m!!...!与n!m(mn)(m-2n)....但是这里是(...((m!)!)!...)!
请注意，亚历克，是的，我知道，这是一个不幸的表示法，但是你看到传统的定义远比OP想要的更有用（在组合因子来自的地方）。
我会把这个评论，但它会被其他人黯然失色，这是非常重要的。
在这里， a!! 被定义为(a!)! 。
123!!!!!! 是绝对巨大的。 如果你用墨水写下来，我认为你需要比宇宙中更多的粒子。
因此你不能直接比较数字。 我认为没有一个class级可以做到这一点。
你能做什么，就是考虑商123!!!!!! / 456!!! 123!!!!!! / 456!!! 。 许多倍数是相似的，所以你可以取消它们。 还要注意，尾随! 将取消。 这是因为x> y暗示，并且由x暗示！ > y！ 其中x和y是正整数。
最终你会达到一个点，你可以评估这是小于或大于1，所以让你的答案。
我可以通过检查告诉你123!!!!!! 自123!!!以来更大123!!! 大于456 。
不像其他答案， 你可以做任何近似。
这里是 ：
123 !!!!!! > 456 !!!
实际上是指
123 !!!!! > 456 !! 123 !!!! > 456 !
并且
123 !!! > 456
所以你只需要certificate上面的内容。这很简单，因为你至less有一个操作数可以适合UInt64
所以这应该给你这样的东西：
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(); } }
对于给定的数字，假设456!!! 意味着((456!)!)! 我们有
123!!!!!! == (123!!!)!!!
和
123!!! >>> 456 // >>> stands for "much, much...much larger", ">>" is not enough
即使123! （ 1.2e205 ）远远大于456
为了估计阶乘的实际值，我们使用斯特林近似
https://en.wikipedia.org/wiki/Stirling%27s_approximation
即
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)
所以((456!)!)! 是关于
lg(456!) == 1014 lg((456!)!) == 1e1014 * 1014- 1e1014/ln(10) == 1e1017 lg(((456!)!)!) == 1e(1e1017) ((456!)!)! == 1e(1e(1e1017))
这是非常庞大的数字 （注意三重指数） ，这就是为什么不能表示为天真的BigInteger值。
这应该很容易：
正如其他人所说，你可以删除所有常见的“！” 因为x > y <==> x! > y! x > y <==> x! > y!
你的程序本质上必须certificate一个阶乘（123 !!!）比一个普通的数字更大。 你可以通过快速退出循环来解决这个问题。 在计算阶乘时，只要产品大于456，就可以返回，因为阶乘会随着迭代次数的增加而增加。
// 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!"; }
如果要为input参数parsing更大的数字，也可以使用此方法使用BigInteger。
正如其他人所说，123 !!!!!! 和456 !!! 只是太大 ，不能用电脑代表，而且x!! <=> y!型的比较x!! <=> y! x!! <=> y! 简化为x! <=> y x! <=> y 。
一旦你达到最小可能的数量! （将它们从string中切除），您可以评估操作数。 其中一个数字将是一个普通的整数（没有阶乘），所以在这里没有工作。 另一个将至less有一个阶乘，否则比较是微不足道的。
假设比较是x! <=> y x! <=> y （一个因子）。 如果x >= y ，就完成了。 如果x < y ，则评估x! 并比较。
假设比较是x!! <=> y x!! <=> y （两个阶乘）。 列出最小值：
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
所以，对于任何y ， x > 4将导致x!! > y x!! > y 。 对于x <= 4 ，评估x!! 并比较。
对于更多的因式分解，请记住x!!! = (x!)!! x!!! = (x!)!! ，评估x! ，并使用上面的步骤。
BigIntegertypes可以处理大整数。 但是对于你的例子来说还不够大。
小的因子可以被考虑到他们的主要因素中，而不必首先计算因子本身，并且可以取消相同的因子。
你也可以取消尾随! 就像上面Leherenn所build议的那样 ，因为123！ 大于456，（123 !!!）!!! 也会比（456）更大！
让我们定义一个types来表示重复阶乘的操作：
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; } }
现在，如果我们实现一个IComparable<Factorial>我们可以find答案。
public int CompareTo(RepeatedFactorial other) { // ? }
先来考虑一些简单的例子。
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); ??? }
好的，唯一没有处理的情况是this重复的因子less于other ，反之亦然。 让我们把其中的一种情况变成另一种情况，所以我们没有办法处理：
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); ??? }
现在我们只需要担心this重复次数less于other次数。 由于X> Y意味着X！ > Y！ 等等，我们可以把这个问题减less到我们知道this问题有零个重复：
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); ??? }
现在我们需要如何将other.BaseNumber与其他this.BaseNumber进行比较，并应用适当数量的阶乘。 显然，如果other.BaseNumber大于12那么从13开始！ 大于int.MaxValue它必须大于this.BaseNumber ：
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); if (other.BaseNumber > 12) return -1; // this is less than other ??? }
现在我们计算实际的数字。 但是，如果在阶乘的循环开始时，我们有13或更高，那么我们可以通过与上面相同的逻辑返回-1 。 否则，如果我们最终得到一个比this.BaseNumber更大的this.BaseNumber我们也可以返回-1 。
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); }
因此，我们有我们的答案，而不必计算大于12的因子！
把它放在一起：
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); } }
编辑：
我刚刚意识到你实际上在你的问题中使用了64位的值。 这很容易适应，我们仍然不会超过计算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); } }
对于正整数，如果双方都有相同数目的阶乘，那么就比较两个数字一样简单
123!!!! 456!!!! 456 > 123 456!!!! > 123!!!!
否则，比较两个因子，归结到这一点
123!!!!!! 456!!! (123!!!)!!! (456!!!) 123!!! 456
在这一点上，我们将尝试逐个评估因子，直到我们超过了另一个数。
由于另一个数字是一个可以存储在一个variables中的数字，这意味着我们已经计算出了一个更高的数字，或者发生了溢出exception，那么这个数字就是一个更大的数字，否则就是一个较小的数字。
以下是一个pesudo代码，而不是一个实际的代码：
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; }
