问题标签 [induction]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
python - 包含递归算法的棋盘格背后的直觉是什么?如何更好地制定这种算法?
您可能听说过经典的棋盘覆盖拼图。您如何使用 L 形瓷砖覆盖缺少一个角正方形的棋盘?
正如“Python 算法掌握 Python 语言中的基本算法”一书中所解释的,有一种递归方法。
这个想法是将棋盘分成 4 个较小的方格,然后将 L 形瓦片放置在较大棋盘的中心,有效地创建 4 个较小的方格,其中缺少一个瓦片并通过递归继续。
从概念上讲,它很容易理解,但我发现很难考虑实现。这是一个实现解决方案——
要运行代码,您将获得以下信息
我花了一些时间来理解这个实现。我不确定我是否完全理解它,尤其是偏移线背后的想法。有人可以尝试简洁地解释实现吗?一个人如何培养一种直觉来思考解决这类问题的方法?我发现这个解决方案非常聪明,尤其是像他们那样设置偏移线。如果有人能帮助我理解这一点,或许还有关于如何变得更好的建议,我将不胜感激。
谢谢!
algorithm - 算法介绍第三版 - 练习 2.3 -3 - nlg(n) 的归纳证明
我正在阅读《算法导论》这本书,第三版。在一个练习中,我们被要求使用归纳推理来证明
其中 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?
?它不符合我所知道的数学约定。
induction - 证明函数的正确性
我试图证明这个函数的部分正确性,我想出了一个谓词p(i)
:for the array A=[0..i]
,len(A)=i+1
当调用 recmin[A] 时,这个调用终止并返回一些 t ,即0<=t<=i A[t]
最小值
但我觉得这个谓词是错误的,我将如何证明后置条件A[0]
是最小值
math - 通过证明递归不是 O(n) 的归纳证明是 Omega(nlogn)
注意:这与家庭作业有关。
我试图证明这一点T(n/3) + T(2n/3) + n >= cn , for all c > 0
。
当我尝试这样做时,基本情况失败(T(1) = 1 >= cn, for all c > 0
,不正确)。所以为了解决这个问题,我想表明问题的下限高于O(n)
. 这是否构成正确的证明?
algorithm - scala流上的归纳证明
有人可以帮助我如何归纳推理这个 scala 代码
生成从 1 开始的自然数列表?
algorithm - 高度为 N-1 的 N 个节点的二叉树形状有多少?
有多少个高度为 N-1 的 N 个节点的二叉树形状?另外,您将如何通过归纳进行校对?
所以高度为 n-1 且节点为 n 的二叉树意味着所有节点将只有 1 个子节点,类似于链式结构?所以二叉树的数量将是n个数字的不同排列,即n。我在思考正确的方向吗?
coq - 如何在 Coq 中使用自定义归纳原则?
我读到类型的归纳原理只是关于命题的定理P
。List
所以我构造了一个基于右(或反向)列表构造函数的归纳原理。
归纳原理本身是:
但是现在,我在使用这个定理时遇到了麻烦。我不知道如何调用它来达到与induction
策略相同的效果。
例如,我试过:
但在最后一行,我得到:
定义和应用自定义归纳原则的正确步骤是list_ind_rcons
什么?
谢谢
logic - 基于示例的一般规则自动推理
我对以下我想调查的问题感兴趣。我遇到的一个问题是我什至不确定要搜索哪些术语来搜索背景信息。我尝试查找语法归纳和类似技术,但它们似乎没有解决这个问题。
假设我在几个小域上观察到一组逻辑规则。我想从它们中推断出一个通用规则,它允许我为更大的域生成一个类似的规则,该规则仍然与较小的域一致。
示例 1
所以我希望能够观察这三个实例并使用某种算法自动推断一般规则。
再举一个例子:
我知道第二个例子可以通过线拟合轻松解决。
我想要的是一些适用于这两种问题的方法。是否可以应用某种用于一阶逻辑或算术的机器学习?有没有办法使用模式学习和模式生成来完成这个?我对任何想法持开放态度。
一个稍微不同但足够的解决方案是生成一个算法、语法或函数,而不是生成一般规则,而是生成一个算法、语法或函数,在给定值 n 作为输入的情况下,生成与规则 n 对应的规则。
haskell - Haskell 自定义函数的归纳证明
我正在研究归纳,我有一些问题要弄清楚如何完成我的“destutter”函数的归纳证明,该函数删除列表中的连续重复项:
这是假设:
这是我到目前为止所做的:
证明基本情况(空列表)
证明一般情况:
这是我遇到一些问题的地方:我不知道如何使用假设来达到:
我尝试了不同的方法,但似乎没有一种方法是正确的。我做的步骤好吗?我的推理方式正确吗?
ocaml - 证明长度 (h::l) = 1 + 长度 l
我对这些看似微不足道的证明感到困惑。
例如,在归纳的情况下,如果我假设标题中的属性并且我想显示:
我从这里去哪里?这显然是正确的,但我不知道在不证明某种引理的情况下我可以采取哪些步骤。例如我可以说
但现在我必须证明一些事情
当我需要证明引理时,我很难理解,尤其是在看起来几乎微不足道的证明中。