我有一个无法解决的数学问题：我不知道如何找到 n 的值，以便
365! / ((365-n)! * 365^n) = 50%.
我正在使用 Casio 500ms 科学计算器，但我不知道如何使用。
对不起，因为我的问题太简单了，我正在改变我的职业，所以我必须复习和升级我的数学，这是我多年来忽视的科目。
问问题
120 次
3 回答
2
如果您可以采用导数，则理论上可以使用像牛顿法这样的求根方案。但是这个函数只定义在整数上，因为它使用阶乘。
一种出路是认清身份
n! = gamma(n+1)
这将有效地允许您将功能扩展到实线。伽马函数是在正实线上定义的，尽管它在负整数处确实有奇点。当然，你仍然需要这个表达式的导数，因为 gamma 是可微的，所以可以这样做。
顺便说一句，像牛顿法这样的方法处理此类问题的危险在于它可能仍会偏离负实线。选择较差的起始值，您可能会得到垃圾。（我没有仔细研究过这个函数的形状，所以我不会声称它会在你身上发散哪一组起始值。）
是否值得跳过上述套圈？当然不是。比牛顿法更好的选择可能是布伦特算法或割线法，这里不需要您计算导数。但即使这样也是浪费精力。
认识到这确实是整数上的问题，可以使用像二等分这样的工具来非常有效地解决解决方案。它从不需要导数，并且在整数上可以很好地工作。一旦您解决了尽可能短的间隔，算法将终止，并在此过程中进行不同的函数评估。
最后，要小心这个函数，因为它确实涉及一些相当大的阶乘，这很容易溢出许多工具来评估阶乘。例如，在 MATLAB 中，如果我确实尝试评估阶乘（365）：
factorial(365)
ans =
Inf
我得到一个溢出。我需要使用符号工具箱之类的工具，或者我自己的一套可变精度整数工具。或者，人们可以认识到这些阶乘中的许多项将被抵消，因此
365! / (365 - n)! = 365*(365-1)*(365-2)*...*(365-n+1)
关键是，如果我们不小心，我们会因为如此大的值而溢出。如果您有一个不会溢出的工具，请使用它，并按照我的建议使用二分法。在这里，使用 MATLAB 中的符号工具箱，我得到了一个仅使用 7 个函数评估的解决方案。
f = @(n) vpa(factorial(sym(365))/(factorial(sym(365 - n))*365^sym(n)));
f(0)
ans =
1.0
f(365)
ans =
1.4549552156187034033714015903853e-157
f(182)
ans =
0.00000000000000000000000095339164972764493041114884521295
f(91)
ans =
0.000004634800180846641815683109605743
f(45)
ans =
0.059024100534225072005461014516788
f(22)
ans =
0.52430469233744993108665513602619
f(23)
ans =
0.49270276567601459277458277166297
或者，如果您不能选择这样的选项，但确实有一个可以评估 gamma 函数日志的工具，并且您有一个可用的 rootfinder，就像 MATLAB 一样......
f = @(n) exp(gammaln(365+1) - gammaln(365-n + 1) - n*log(365));
fzero(@(n) f(n) - .5,10)
ans =
22.7677
正如您在此处看到的，我使用了与 gamma 和阶乘函数相关的恒等式，然后在 MATLAB 中使用了 gamma 函数的对数 gammaln。一旦完成所有肮脏的工作，然后我将整个混乱取幂，这将是一个合理的数字。Fzero 告诉我们交叉发生在 22 和 23 之间。
于 2013-05-16T13:43:03.100 回答
1
于 2013-05-16T12:16:36.490 回答
0
我假设你有一些特殊的理由想要一个实际的算法，即使你只有一个特定的问题要解决。
你正在寻找一个值 n ......
365! / ((365-n)! * 365^n) = 0.5
因此...
(365! / ((365-n)! * 365^n)) - 0.5 = 0.0
问题的一般形式是找到x这样的值f(x)=0。这种事情的一个经典算法是Newton-Raphson 方法。
[编辑- 正如 woodchips 在评论中指出的那样，阶乘是一个仅限整数的函数。我的辩护 - 对于某些问题（其中的生日问题），使用近似函数进行概括是很常见的。我记得用于生日问题的阶乘的斯特林近似值-据此，Knuth 使用它。生日问题的维基百科页面提到了几个可以推广到非整数值的近似值。
当我第一次写这个答案时，我没想到要提到这一点，这当然很糟糕。]
一个问题是您需要该函数的导数。这更像是一个数学问题，尽管您可以通过在任一侧取短距离的值来估计任何点的导数。
您也可以将其视为优化问题。优化问题的一般形式是找到一个最大化/最小化x的值。f(x)在您的情况下，您可以将您的功能定义为...
f(x)=((365! / ((365-n)! * 365^n)) - 0.5)^2
因为平方，结果永远不会是负数，所以尽量减少。无论x你得到最小的值，f(x)也会给你想要的结果。
对于整个领域的优化问题并没有那么多的算法——你使用的方法取决于你的函数的复杂性。但是，只要您的语言可以处理大数字，这种情况应该很简单。可能最简单的优化算法称为爬山算法，但在这种情况下，它可能应该称为rolling-down-the-hill。幸运的是，Newton-Raphson是一种爬山方法（或者非常接近一种方法——可能有一些我不记得的小技术问题）。
[如上所述的编辑，如果您需要实际说明的问题的整数解决方案（而不是实值近似值），这将不起作用。整数域中的优化是那些有助于使优化本身成为一个领域的尴尬问题之一。分支定界对于复杂函数很常见。但是，在这种情况下，爬山仍然有效。原则上，您甚至仍然可以使用经过调整的 Newton-Raphson 版本——您只需要进行一些舍入并检查如果您的移动很小，您不会一直舍入到您开始的同一个地方。]
于 2013-05-16T12:56:40.843 回答