问题标签 [induction]

您可能听说过经典的棋盘覆盖拼图。您如何使用 L 形瓷砖覆盖缺少一个角正方形的棋盘？

正如“Python 算法掌握 Python 语言中的基本算法”一书中所解释的，有一种递归方法。

这个想法是将棋盘分成 4 个较小的方格，然后将 L 形瓦片放置在较大棋盘的中心，有效地创建 4 个较小的方格，其中缺少一个瓦片并通过递归继续。

从概念上讲，它很容易理解，但我发现很难考虑实现。这是一个实现解决方案——

要运行代码，您将获得以下信息

我花了一些时间来理解这个实现。我不确定我是否完全理解它，尤其是偏移线背后的想法。有人可以尝试简洁地解释实现吗？一个人如何培养一种直觉来思考解决这类问题的方法？我发现这个解决方案非常聪明，尤其是像他们那样设置偏移线。如果有人能帮助我理解这一点，或许还有关于如何变得更好的建议，我将不胜感激。

谢谢！

我正在阅读《算法导论》这本书，第三版。在一个练习中，我们被要求使用归纳推理来证明

其中 lg 是 log base 2。这本书提供了解决方案：

有人可以解释为什么在假设步骤中使用值 n/2 吗？根据我对归纳的理解，我会使用该值2^n，然后将其递增到2^(n+1)以涵盖 2 的所有可能幂。我想知道为什么我错了。此外，有人可以解释改变的操作吗2(n/2)lg(n/2)+n into n(lg n-1) + n?？它不符合我所知道的数学约定。

我试图证明这个函数的部分正确性，我想出了一个谓词p(i):for the array A=[0..i]，len(A)=i+1当调用 recmin[A] 时，这个调用终止并返回一些 t ，即0<=t<=i A[t]最小值

但我觉得这个谓词是错误的，我将如何证明后置条件A[0]是最小值

注意：这与家庭作业有关。

我试图证明这一点T(n/3) + T(2n/3) + n >= cn , for all c > 0。

当我尝试这样做时，基本情况失败(T(1) = 1 >= cn, for all c > 0，不正确）。所以为了解决这个问题，我想表明问题的下限高于O(n). 这是否构成正确的证明？

有人可以帮助我如何归纳推理这个 scala 代码

生成从 1 开始的自然数列表？

有多少个高度为 N-1 的 N 个节点的二叉树形状？另外，您将如何通过归纳进行校对？

所以高度为 n-1 且节点为 n 的二叉树意味着所有节点将只有 1 个子节点，类似于链式结构？所以二叉树的数量将是n个数字的不同排列，即n。我在思考正确的方向吗？

我读到类型的归纳原理只是关于命题的定理P。List所以我构造了一个基于右（或反向）列表构造函数的归纳原理。

归纳原理本身是：

但是现在，我在使用这个定理时遇到了麻烦。我不知道如何调用它来达到与induction策略相同的效果。

例如，我试过：

但在最后一行，我得到：

定义和应用自定义归纳原则的正确步骤是list_ind_rcons什么？

谢谢

我对以下我想调查的问题感兴趣。我遇到的一个问题是我什至不确定要搜索哪些术语来搜索背景信息。我尝试查找语法归纳和类似技术，但它们似乎没有解决这个问题。

假设我在几个小域上观察到一组逻辑规则。我想从它们中推断出一个通用规则，它允许我为更大的域生成一个类似的规则，该规则仍然与较小的域一致。

示例 1

所以我希望能够观察这三个实例并使用某种算法自动推断一般规则。

再举一个例子：

我知道第二个例子可以通过线拟合轻松解决。

我想要的是一些适用于这两种问题的方法。是否可以应用某种用于一阶逻辑或算术的机器学习？有没有办法使用模式学习和模式生成来完成这个？我对任何想法持开放态度。

一个稍微不同但足够的解决方案是生成一个算法、语法或函数，而不是生成一般规则，而是生成一个算法、语法或函数，在给定值 n 作为输入的情况下，生成与规则 n 对应的规则。

我正在研究归纳，我有一些问题要弄清楚如何完成我的“destutter”函数的归纳证明，该函数删除列表中的连续重复项：

这是假设：

这是我到目前为止所做的：

证明基本情况（空列表）

证明一般情况：

这是我遇到一些问题的地方：我不知道如何使用假设来达到：

我尝试了不同的方法，但似乎没有一种方法是正确的。我做的步骤好吗？我的推理方式正确吗？

我对这些看似微不足道的证明感到困惑。

例如，在归纳的情况下，如果我假设标题中的属性并且我想显示：

我从这里去哪里？这显然是正确的，但我不知道在不证明某种引理的情况下我可以采取哪些步骤。例如我可以说

但现在我必须证明一些事情

当我需要证明引理时，我很难理解，尤其是在看起来几乎微不足道的证明中。