比较两个阶乘而不计算
Compare two factorials without calculating
有什么方法可以不用计算就可以比较两个数中哪个阶乘数大？
场景是我正在创建一个 c# 控制台应用程序，它采用两个阶乘输入，如
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();
}
但我得到的错误是
值对于小数来说太大或太小
我理解错误，但有什么办法可以做到这一点
请建议是否有任何其他数据类型可以容纳大于十进制的值，或者是否有任何其他方法来比较这些阶乘
在实施@Bathsheba 的建议后，我更改了一些代码
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！！！太大了，我得到了同样的错误
Traditionally m!!...! with n !s means m(m-n)(m-2n).... however here is is taken as (...((m!)!)!...)!
Note from Alec, yes I know, this is an unfortunate notation, but you see the conventional definition is far more useful (in combinatorics, the place where factorials come from) than the one the OP wants.
I would put this in a comment but it'd be eclipsed by the others and this is quite important.
这里，a!!定义为(a!)!。
123!!!!!! 绝对是巨大的。如果你用墨水写下来，我想你需要的粒子比宇宙中的还要多。
因此您不能直接比较数字。我推测没有一个数字 class 可以做到这一点。
您可以做的是考虑商123!!!!!! / 456!!!。许多倍数将是相似的，因此您可以取消它们。另请注意，尾随 ! 将取消。这是因为 x > y 暗示，并且被 x 暗示！ > 是的！其中 x 和 y 是正整数。
最终你会到达一个点，在那里你可以评估它是小于还是大于 1，从而得出你的答案。
我可以告诉你经过检查 123!!!!!! 更大，因为 123!!! 比 456 大。
BigInteger 类型可以处理大整数。但对于您的示例来说还不够大。
小的阶乘可以分解成它们的素因子，而不必先计算阶乘本身，并且可以抵消相同的因子。
您也可以按照建议 取消尾随 !，因为 123!!!大于456，（123！！！）！！！也将大于 (456)!!!
对于给定的数字，假设 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值。
与其他答案不同，您无需任何近似即可做到。
这里是：
123 !!!!!! > 456 !!!
实际上是
123 !!!!! > 456 !!
123 !!!! > 456 !
还有
123 !!! > 456
所以你只需要证明 above.It 是简单的，因为你至少有一个操作数可以放入 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();
}
}
这应该很简单：
正如其他人所说，您可以删除所有常见的“！”因为 x > y <==> x! > y!
您的程序基本上必须证明阶乘 (123!!!) 大于普通数字。您可以通过快速退出循环来解决这个问题。在计算阶乘时，只要乘积大于 456，您就可以 return，因为阶乘总是会随着额外的迭代而增长。
// 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!";
}
如果您想为输入参数解析更大的数字，也可以将 BigInteger 与此方法一起使用。
正如其他人所说，123!!!!!!和 456！只是 太大 无法用计算机表示，x!! <=> y! 类型的比较减少为 x! <=> y.
一旦达到可能的最小数量 !（从字符串中删除它们），就可以计算操作数。其中一个数字将是一个普通整数（没有阶乘），所以这里没有工作。另一个将至少有一个阶乘，否则比较是微不足道的。
假设比较是x! <=> y（一个阶乘）。如果 x >= y，你就完成了。如果 x < y，计算 x! 并比较。
假设比较是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 <= 4，评估 x!! 并进行比较。
对于更多的阶乘，请记住 x!!! = (x!)!!，计算 x!，并使用上面的步骤。
让我们定义一个类型来表示重复阶乘的运算：
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> 我们可以找到想要的答案。
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 的重复阶乘比 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 的重复次数少于 other。因为 X > Y 意味着 X！ > 是的！依此类推，我们可以将这个问题减少到我们知道 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);
???
}
现在我们需要了解 this.BaseNumber 与 other.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 或更高，那么我们可以通过与上述相同的逻辑 return -1。否则，如果我们最终得到的数字大于 this.BaseNumber，我们也可以 return -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
此时我们将尝试一个一个地评估阶乘，直到我们超过另一个数字。
由于另一个数是可以存储在变量中的数，这意味着如果我们在计算上达到了更高的数，或者捕获了溢出异常，那么它就是一个更大的数，否则就是一个更小的数.
以下是伪代码，不是实际代码：
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;
}
有什么方法可以不用计算就可以比较两个数中哪个阶乘数大？
场景是我正在创建一个 c# 控制台应用程序，它采用两个阶乘输入，如
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();
}
但我得到的错误是
值对于小数来说太大或太小
我理解错误，但有什么办法可以做到这一点
请建议是否有任何其他数据类型可以容纳大于十进制的值，或者是否有任何其他方法来比较这些阶乘
在实施@Bathsheba 的建议后，我更改了一些代码
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！！！太大了，我得到了同样的错误
Traditionally
m!!...!withn!s meansm(m-n)(m-2n)....however here is is taken as(...((m!)!)!...)!
Note from Alec, yes I know, this is an unfortunate notation, but you see the conventional definition is far more useful (in combinatorics, the place where factorials come from) than the one the OP wants.
I would put this in a comment but it'd be eclipsed by the others and this is quite important.
这里，a!!定义为(a!)!。
123!!!!!! 绝对是巨大的。如果你用墨水写下来，我想你需要的粒子比宇宙中的还要多。
因此您不能直接比较数字。我推测没有一个数字 class 可以做到这一点。
您可以做的是考虑商123!!!!!! / 456!!!。许多倍数将是相似的，因此您可以取消它们。另请注意，尾随 ! 将取消。这是因为 x > y 暗示，并且被 x 暗示！ > 是的！其中 x 和 y 是正整数。
最终你会到达一个点，在那里你可以评估它是小于还是大于 1，从而得出你的答案。
我可以告诉你经过检查 123!!!!!! 更大，因为 123!!! 比 456 大。
BigInteger 类型可以处理大整数。但对于您的示例来说还不够大。
小的阶乘可以分解成它们的素因子，而不必先计算阶乘本身，并且可以抵消相同的因子。
您也可以按照建议 !，因为 123!!!大于456，（123！！！）！！！也将大于 (456)!!!
对于给定的数字，假设 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值。
与其他答案不同，您无需任何近似即可做到。
这里是：
123 !!!!!! > 456 !!!
实际上是
123 !!!!! > 456 !!
123 !!!! > 456 !
还有
123 !!! > 456
所以你只需要证明 above.It 是简单的，因为你至少有一个操作数可以放入 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();
}
}
这应该很简单：
正如其他人所说，您可以删除所有常见的“！”因为 x > y <==> x! > y!
您的程序基本上必须证明阶乘 (123!!!) 大于普通数字。您可以通过快速退出循环来解决这个问题。在计算阶乘时，只要乘积大于 456，您就可以 return，因为阶乘总是会随着额外的迭代而增长。
// 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!";
}
如果您想为输入参数解析更大的数字，也可以将 BigInteger 与此方法一起使用。
正如其他人所说，123!!!!!!和 456！只是 太大 无法用计算机表示，x!! <=> y! 类型的比较减少为 x! <=> y.
一旦达到可能的最小数量 !（从字符串中删除它们），就可以计算操作数。其中一个数字将是一个普通整数（没有阶乘），所以这里没有工作。另一个将至少有一个阶乘，否则比较是微不足道的。
假设比较是x! <=> y（一个阶乘）。如果 x >= y，你就完成了。如果 x < y，计算 x! 并比较。
假设比较是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 <= 4，评估 x!! 并进行比较。
对于更多的阶乘，请记住 x!!! = (x!)!!，计算 x!，并使用上面的步骤。
让我们定义一个类型来表示重复阶乘的运算：
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> 我们可以找到想要的答案。
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 的重复阶乘比 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 的重复次数少于 other。因为 X > Y 意味着 X！ > 是的！依此类推，我们可以将这个问题减少到我们知道 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);
???
}
现在我们需要了解 this.BaseNumber 与 other.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 或更高，那么我们可以通过与上述相同的逻辑 return -1。否则，如果我们最终得到的数字大于 this.BaseNumber，我们也可以 return -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
此时我们将尝试一个一个地评估阶乘，直到我们超过另一个数字。
由于另一个数是可以存储在变量中的数，这意味着如果我们在计算上达到了更高的数，或者捕获了溢出异常，那么它就是一个更大的数，否则就是一个更小的数.
以下是伪代码，不是实际代码：
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;
}