问题标签 [proof]

我有一个计算机程序，它读取以后缀表示法编写的操作数和运算符的字符数组。然后程序扫描数组，使用堆栈计算结果，如下所示：

我如何通过归纳证明该程序正确评估任何后缀表达式？（取自练习 4.16 Java 算法（Sedgewick 2003））

Martin Fowler有一个 Money 类，它有一个货币分配例程。此例程根据给定的比率列表分配资金，而不会因四舍五入而损失任何价值。它将任何剩余值分布在结果上。

例如，按“比率”（1、1、1）分配的 100 美元将产生（34 美元、33 美元、33 美元）。

这是allocate功能：

（为了这个问题，为了简单起见，我冒昧地将 Money 类型替换为 long。）

问题是，我怎么知道它是正确的？除了最后的 for 循环之外，这一切似乎都是不言而喻的。我认为要证明函数是正确的，在最终的 for 循环中证明以下关系是正确的就足够了：

谁能证明这一点？

如果 T 是具有 n 个元素的平衡 BST，L 是左子树，R 是右子树，我如何证明它的深度小于或等于 2log(n) + 1？

我有一个归纳证明，但我不明白。

（我知道stackoverflow主要是面向编程的，但是我发现了一些关于二叉搜索树的问题并决定试一试，希望我没有做不好的事情。:)）

我正在尝试比较两种算法。我想我可以试着为他们写一个证明。（我的数学很烂，所以这个问题。）

通常在我们去年的数学课上，我们会遇到一个问题，比如 <can't use symbols in here so left them out>。

证明： (2r + 3) = n (n + 4)

然后我会完成所需的 4 个阶段并在最后得到答案。

我被卡住的地方是证明 prims 和 Kruskals - 我怎样才能将这些算法转化为上述数学算法的形式，以便我可以继续证明？

注意：我不是要求人们为我回答 - 只是帮助我把它变成一个我可以自己去尝试的形式。

首先，这是否仅适用于没有副作用的算法？

其次，我在哪里可以了解这个过程，有什么好书、文章等？

我想知道这句话背后的逻辑，证明。C 表达式 -x、~x+1 和 ~(x-1) 对于任何 x 都产生相同的结果。对于具体的例子，我可以证明这是正确的。我认为证明这一点的方法与二进制补码的性质有关。有任何想法吗？

我从冒泡排序算法的数据结构书中得到了这个公式。

我知道我们是 (n-1) * (n 次)，但为什么要除以 2？

谁能给我解释一下或给出详细的证明。

谢谢

我知道这与编程没有直接关系，但我想知道是否有人知道如何将泵引理应用于以下证明：

证明L={(a^n)(b^n)(c^m) : n!=m}不是上下文无关语言

我对应用抽水引理非常有信心，但这真的让我很恼火。你怎么看？

我正在查看我的旧算法笔记并遇到了这个证明。这是我的一个作业，我做对了，但我觉得证明确实缺乏。

问题是prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

我的证明如下：

反证法。首先，假设我们从 Q 中拉出一个 d 值为“i”的顶点。下一次，我们拉出一个 d 值为 'j' 的顶点。当我们拉出 i 时，我们已经确定了我们的 d 值并计算了从起始顶点 s 到 i 的最短路径。因为我们有正的边权重，所以当我们向路径添加顶点时，我们的 d 值不可能缩小。如果从 Q 中拉出 i 后，我们拉出具有较小 d 值的 j，我们可能没有到 i 的最短路径，因为我们可能能够通过 j 到达 i。但是，我们已经计算了到 i 的最短路径。我们没有检查可能的路径。我们不再有保证的路径。矛盾。

如何改进这个证明？或者更好的是，有不同的方法吗？它似乎很弱:)

编辑：对不起，在这种情况下，我的优先级队列是用最小堆实现的

我正在尝试解决Project Euler上的问题 50 。不要给我答案或为我解决它，只是尝试回答这个具体问题。

目标是找到添加到低于一百万的素数的最长的连续素数之和。我写了一个筛子来找到n以下的所有素数，我已经确认它是正确的。接下来，我将使用以下方法检查每个连续素数子集的总和：

我有一个空列表sums。对于每个素数，我将它添加到中的每个元素sums并检查新的总和，然后将素数附加到sums.

这是在python中

我想知道我是否要求check()两个或多个连续素数的总和低于一百万

问题是有一个素数 953，可以写成 21 个连续素数之和，但我没有找到它。