5

我在网上浏览了具体数学的内容。我至少听说过提到的大部分功能和技巧，但有一整节是关于特殊数字的。这些数字包括斯特林数、欧拉数、谐波数等。现在我从来没有遇到过这些奇怪的数字。它们如何帮助解决计算问题？它们一般用在什么地方？

4

7 回答 7

5

谐波数几乎无处不在！音乐和声，快速排序的分析... 斯特林数（第一类和第二类）出现在各种组合和划分问题中。欧拉数也出现在几个地方，最显着的是在多对数函数的排列和系数中。

于 2009-05-23T15:57:25.137 回答
4

你提到的很多数字都用于算法分析。您的代码中可能没有这些数字，但如果您想估计代码运行需要多长时间，您将需要它们。您也可能在代码中看到它们。其中一些数字与组合学有关，计算某事发生的方式有多少。

有时仅仅知道有多少种可能性是不够的，因为您需要列举各种可能性。 Knuth 的 TAOCP 第 4 卷正在进行中，提供了您需要的算法。

这是使用斐波那契数作为数值积分问题的一部分的示例。

谐波数是对数的离散模拟，因此它们出现在差分方程中，就像对数出现在微分方程中一样。这是与谐波数相关的谐波均值的物理应用示例。参见Gamma一书，了解许多谐波数在作用中的示例，尤其是“这是一个谐波世界”一章。

于 2009-05-23T16:28:58.193 回答
3

这些特殊数字可以在许多方面帮助解决计算问题。例如：

  • 您想知道计算 2 个数字的 GCD 的程序何时将花费最长的时间：尝试 2 个连续的斐波那契数。

  • 您想粗略估计大量的阶乘，但您的阶乘程序花费的时间太长：使用Stirling's Approximation。

  • 您正在测试素数，但对于某些数字，您总是得到错误的答案：可能是您正在使用费马的素数测试，在这种情况下，卡迈克尔数是您的罪魁祸首。

我能想到的最常见的一般情况是循环。大多数情况下，您使用一种语法类型来指定循环(start;stop;step)，在这种情况下，可以通过使用所涉及数字的属性来减少执行时间。

例如，当 n 在循环中很大时，将所有从 1 到 n 的数字相加肯定比使用 identity 慢sum = n*(n + 1)/2。

像这样的例子还有很多。他们中的许多人都在密码学中，信息系统的安全性有时取决于这些技巧。它们还可以帮助您解决性能问题、内存问题，因为当您知道公式时，您可能会找到一种更快/更有效的方法来计算其他事情——您真正关心的事情。

有关更多信息，请查看 wikipedia，或直接尝试 Project Euler。你会很快开始找到模式。

于 2009-05-23T16:24:08.163 回答
2

这些数字中的大多数都计算某些类型的离散结构（例如，斯特林数计算子集和循环）。这样的结构，以及因此的这些序列，隐含地出现在算法分析中。

OEIS有一个详尽的列表，列出了 Concrete Math 中出现的几乎所有序列。该列表的简短摘要：

  • 哥伦布数列
  • 二项式系数
  • Rencontres 数字
  • 斯特林数字
  • 欧拉数
  • 超因子
  • Genocchi 数字

您可以浏览各个序列的 OEIS 页面，以获取有关这些序列的“属性”的详细信息（尽管不完全是应用程序，如果您最感兴趣的话）。

此外，如果您想了解这些序列在算法分析中的实际用途，请翻阅 Knuth 的计算机编程艺术索引，您会发现许多关于这些序列的“应用”的参考资料。John D. Cook 已经提到了斐波那契数和谐波数的应用；这里还有一些例子：

斯特林循环数出现在寻找数组最大元素的标准算法的分析中（TAOCP Sec. 1.2.10）：找到最大值时必须更新当前最大值多少次？事实证明，在元素k数组中找到最大值时需要更新最大值的概率是。由此，我们可以得出，平均而言，大约需要更新。np[n][k] = StirlingCycle[n, k+1]/n!Log(n)

Genocchi 数的出现与计算“瘦”的BDD的数量有关（TAOCP 7.1.4 练习 174）。

于 2009-05-25T14:55:11.240 回答
1

不一定是您提到的参考文献中的幻数，但尽管如此-

0x5f3759df

- 臭名昭著的幻数，用于通过对牛顿的根近似给出良好的初步估计来计算数字的平方根，通常归因于 John Carmack 的工作 -更多信息在这里。

和编程无关吧？:)

于 2009-05-23T16:38:04.597 回答
0

这与编程直接相关吗？肯定有关系，但我不知道有多密切。

特殊的数字，例如 e、pi 等，到处都是。我认为没有人会为这两个争论。Golden_ratio也以惊人的频率出现，从艺术到其他特殊数字本身（看看连续斐波那契数之间的比率。）

各种数列和数族也出现在数学的许多地方，因此也出现在编程中。一个美丽的地方是整数序列百科全书。

我会建议这是一个经验的事情。例如，当我在很多很多年前学习线性代数时，我了解了矩阵的特征值和特征向量。我承认，在我看到它们在各种地方使用之前，我根本没有意识到特征值/特征向量的重要性。在统计学中，根据他们告诉您的有关协方差矩阵估计的不确定性、置信椭圆的大小和形状、主成分分析或马尔可夫过程的长期状态。在数值方法中，它们会告诉您方法的收敛性，无论是优化还是 ODE 求解器。在机械工程中，您将它们视为主要应力和应变。

于 2009-05-24T12:29:42.087 回答
0

Reddit 上的讨论

于 2009-05-24T19:25:56.883 回答