问题标签 [discrete-mathematics]

生成一个列表列表（或打印，我不介意）一个大小为 N 的帕斯卡三角形，代码行数尽可能少！

这是我的尝试（python 2.6中的 118 个字符使用技巧）：

解释：

• 列表理解的第一个元素（当长度为 0 时）是[1]
• 下一个元素通过以下方式获得：
• 取上一个列表并制作两个列表，一个在开头填充 0，另一个在末尾填充。
  • 例如，对于第二步，我们采取[1]并制作[0,1]和[1,0]
• 将两个新列表逐个元素相加
  • 例如，我们创建一个新列表[(0,1),(1,0)]并使用 sum 进行映射。
• 重复n次，仅此而已。

用法（漂亮的印刷，实际上是在代码高尔夫 xD 之外）：

输出：

我有一个朋友需要计算以下内容：

在完整的图 Kn (k<=13) 中，有 k*(k-1)/2 条边。每条边可以以​​ 2 种方式定向，因此有 2^[(k*(k-1))/2] 种不同的情况。

她需要计算P[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]

X !-> Y 表示“没有从 X 到 Y 的路径”，而 P[ ] 是概率。

所以蛮力算法是检查每一个 2^[(k*(k-1))/2] 个不同的图，因为它们是完整的，在每个图中只需要考虑一组 A，B， C,D 因为对称。

然后将 P[A !-> B] 计算为“节点 1 和 2 之间没有路径的图的数量”除以图的总数，即 2^[(k*(k-1))/2]。

蛮力方法适用于数学到 K8，但她需要 K9，K10... 到 K13。

我们显然不需要在案例中找到最短路径，只想找到是否有一条。

有人有优化建议吗？（这听起来像是典型的 Project Euler 问题）。

例子：

最小图 K4 有 4 个顶点，给出 6 条边。因此，如果我们标记 4 个顶点 A、B、C 和 D，则有 2^6 = 64 种可能的方式来为边分配方向。

在某些图表中，没有从 A 到 B 的路径（比如说其中的 X），而在其他一些图中，没有从 C 到 D 的路径（假设是 Y）。但是在某些图中，没有从 A 到 B 的路径，同时也没有从 C 到 D 的路径。这些是 W。

所以和。P[A !-> B]=X/64_P[C !-> D]=Y/64P[A !-> B && C !-> D] = W/64

更新：

• A、B、C 和 D 是 4 个不同的谓词，因此我们至少需要 K4。
• 请注意，我们正在处理有向图，因此使用 UT 矩阵的正常表示是不够的。
• 在mathematica中有一个函数可以找到有向图中节点之间的距离，（如果它返回无穷大，则没有路径），但这有点矫枉过正，因为我们不需要距离，只要有路径或不是。

将两个二进制数相乘需要 n^2 时间，但以某种方式可以更有效地完成一个数字的平方。（n 是位数）怎么可能？

还是不可能？这是精神错乱！

在我们大学的离散数学课程中，老师向他的学生展示了阿克曼函数，并让学生在纸上开发该函数。

除了作为递归优化的基准之外，阿克曼函数还有什么实际用途吗？

我的问题是(g^x) mod p在 JavaScript 中快速计算，^取幂mod是模运算。所有输入都是非负整数，x大约有 256 位，并且p是 2048 位的质数，g最多可以有 2048 位。

我发现的大多数可以在 JavaScript 中执行此操作的软件似乎都使用 JavaScript BigInt 库（http://www.leemon.com/crypto/BigInt.html）。在我的慢速浏览器（带有 SpiderMonkey 的 Firefox 3.0）上，用这个库进行一次这样大小的幂运算大约需要 9 秒。我正在寻找至少快 10 倍的解决方案。对于 2048 位数字来说，使用平方和乘法（通过平方求幂，http ://en.wikipedia.org/wiki/Exponentiation_by_squaring ）的明显想法太慢了：它需要多达 4096 次乘法。

升级浏览器不是一种选择。使用另一种编程语言不是一种选择。将号码发送到 Web 服务不是一种选择。

是否有更快的替代方案实施？

更新：按照下面 outis 的回答中提到的文章http://www.ccrwest.org/gordon/fast.pdf的建议，通过做一些额外的准备（即预先计算几百次幂） ，可以对 2048-位模幂运算最多仅使用 354 次模乘。（传统的平方和乘法方法要慢得多：它使用最多 4096 次模乘。）这样做在 Firefox 3.0 中将模幂运算速度提高了 6 倍，在 Google Chrome 中提高了 4 倍。我们没有得到 4096/354 的完全加速的原因是 BigInt 的模幂算法已经比平方和乘法更快，因为它使用了蒙哥马利归约 ( http://en.wikipedia.org/wiki/Montgomery_reduction ) .

更新：从 BigInt 的代码开始，似乎值得做两级手动优化（和内联）Karatsuba 乘法（http://en.wikipedia.org/wiki/Karatsuba_algorithm），然后才恢复到 base-32768 O( n^2) 在 BigInt 中实现的乘法。这将 2048 位整数的乘法速度提高了 2.25 倍。不幸的是，模运算并没有变得更快。

更新：使用http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf和 Karatsuba 乘法和预计算幂（定义在http://www.ccrwest.org/gordon/ fast.pdf )，我可以在 Firefox 3.0 中将单次乘法所需的时间从 73 秒缩短到 12.3 秒。这似乎是我能做的最好的，但它仍然太慢。

更新：Flash Player 中的 ActionScript 2 (AS2) 解释器不值得使用，因为它似乎比 Firefox 3.0 中的 JavaScript 解释器慢：对于 Flash Player 9，它似乎慢 4.2 倍，对于 Flash Player 10，它似乎慢了 2.35 倍。有人知道 ActionScript2 和 ActionScript3 (AS3) 在数字处理方面的速度差异吗？

更新：Flash Player 9 中的 ActionScript 3 (AS3) 解释器不值得使用，因为它的速度与 JavaScript int Firefox 3.0 几乎相同。

更新：如果使用 Flash Player 10 中的 ActionScript 3 (AS3) 解释器int代替Number，并且Vector.<int>使用代替Array. 2048 位大整数乘法至少要快 2.41 倍。因此，可能值得在 AS3 中进行模幂运算，如果可用，在 Flash Player 10 中执行它。请注意，这仍然比 Google Chrome 的 JavaScript 解释器 V8 慢。有关各种编程语言和 JavaScript 实现的速度比较，请参阅http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html 。

更新：有一个非常快速的 Java 解决方案，如果安装了 Java 插件，可以从浏览器的 JavaScript 调用。以下解决方案比使用 BigInt 的纯 JavaScript 实现快约 310 倍。

任何人都可以将此代码翻译成 Silverlight (C#) 吗？

我没有上过任何高于大学基础微积分的数学课。然而，在我的编程工作过程中，我从博客和阅读中学到了很多数学和计算机科学，我真的相信我有一个不错的数学头脑。例如，我喜欢并在 Project Euler 上取得了成功。

我想潜入并真正开始学习一些很酷的数学，特别是离散数学、集合论、图论、数论、组合学、范畴论、lambda 演算等。到目前为止，我的印象是我有能力学习这些在概念层面上，但我对数学语言和符号感到非常困难。我只是不会“说这种语言”，虽然我正在努力学习它，但我的进展非常缓慢。即使是一个公式或术语繁重的段落，我也可能需要几个小时才能完成。是的，我可以查找术语和定义，但这是一个非常繁重的过程，它在很大程度上掩盖了我正在尝试学习的理论的简单性。

我真的很害怕我将不得不回到我停下来的地方，买一本中级数学教科书，并投入一些认真的时间来练习以这种思维方式训练自己。不过，这听起来非常无聊，所以我想知道是否有其他人对此有任何想法或经验。

在十进制（以 10 为底）中，1/3只能近似为 0.33333 重复。

二进制中的等价数字是多少，只能表示为近似值？

我知道仿射密码用 SG 代替 BD。我需要以 的形式找到加密公式，y = a x + b其中 a 和 b 是系数。根据上面的信息，我最终不得不方程： a+b=18所以 3a+b=6 我的工作是这样的：

所以，O 想乘以2 mod 26

我找不到数字 2 与 26 ( y = ax + b mod 26)的乘法逆

谁能帮我找到a和b？

在观看了 Michael Feather 的 SCNA 演讲“自我教育和工匠”之后，我很想听听离散数学证明有用的软件开发中的实际示例。

嗨，我正在尝试建立一个 RSA 密码系统，除了 d 选择的素数之外，我拥有所有值：p=1889, q=2003, n=3783667, phi=3779776,e= 61

我被困在寻找 d 任何人都可以帮我弄清楚吗？

设置 RSA 密码系统

• 两个不同的大素数p和q被选择，n = pq并且Φ(n) = (p − 1)(q − 1)被计算。

• 选择一个整数e，以便计算gcd(Φ(n), e) = 1乘法逆运算d = e^(−1)，ZΦ(n)即

  ed ≡ 1 (mod Φ(n))。

• 然后丢弃数字p、q和。Φ(n)

• 该对(e, n)作为公共加密密钥发布
• 该数字d是秘密解密密钥。