需要帮助理解算法的感应证明的解释 [英] Need help understanding explanation of induction proof for algorithm

问题描述

我无法理解作者Steven Skiena的书算法设计手册如何使用归纳法来证明以下算法代表/返回伪代码中的y = y + 1：

I'm having trouble understanding how the author Steven Skiena of the book The Algorithm Design Manual used the induction method to prove the following algorithm that represents/returns y = y + 1 in pseudocode:

Increment(y)
        if y = 0 then return(1) else
            if (y mod 2) = 1 then
                 return(2 · Increment(y/2)) 
            else return(y + 1)

具体我不明白他如何从第一个等式 2·增量（m + 1/2） 到达下一个 2·增量（m） 在下面的证明中。在他的全文中他指出：



对于奇数，答案取决于增量（y / 2）返回的内容。这里我们要使用我们的归纳假设，但它并不完全正确。我们假设增量在y = n - 1时正常工作，而不是大约一半的值。我们可以通过加强我们的假设来解决这个问题。一般情况适用于所有y≤n-1。原则上我们没有任何成本，但是必须确定算法的正确性。



现在，案例奇数y（即y = 2m + 1对于某个整数m）可以用

处理：

Specifically I don't understand how he got from the first equation/equality 2·Increment(m + 1/2) to the next one 2·Increment(m) in the proof below. In his full text he states that:

"For the odd numbers, the answer depends upon what is returned by Increment(y/2). Here we want to use our inductive assumption, but it isn’t quite right. We have assumed that increment worked correctly for y = n − 1, but not for a value which is about half of it. We can fix this problem by strengthening our assumption to declare that the general case holds for all y ≤ n−1. This costs us nothing in principle, but is necessary to establish the correctness of the algorithm.

Now, the case of odd y (i.e. y = 2m + 1 for some integer m) can be dealt with
as:

2·Increment((2m + 1)/2) = 2·Increment(m + 1/2)
                        = 2·Increment(m)
                        = 2(m + 1)
                        = 2m +2 = y + 1

我有什么尝试过：



我明白算法是r是递归的，偶数和奇数都是正确的，总是递增y的输入值。然而，作者使用归纳来证明算法，并且对于y = m + 1的情况，我不知道为什么+ 1/2只是消失了。我不认为它适合m只是大到1/2的情况，因为我们说的是m + 1是偶数还是奇数，所以1/2几乎无关紧要。

"

What I have tried:

I understand that the algorithm is recursive and that it is correct for both even and odd numbers always incrementing the input value of y. However, the author is using induction to prove the algorithm and for the case where y = m + 1, I don't know why the + 1/2 just dissapeared. I don't think it fits the cases where m is just to big that 1/2 is almost insignificant since we're talking whether m + 1 is even or odd.

推荐答案

归纳仅适用于以*开头的整数，所以即使作者没有对正在使用的数字做任何其他陈述，也可以假设一切都完全在整数领域。



此外，如果计算导致非整数值，则非整数部分被切断，而不是舍入。这是标准整数数学：5/2 = 2（加上余数）



在这些假设下，m + 1/2被解释为m。



*：更准确地说，感应适用于任何有序和可数的集合（甚至可数无限），但除非另有说明，否则暗示总是一组整数。 br $> b $ b



在旁注中，我发现作者选择不清楚是不幸的。感应不是一个简单的解释方法，它不会在示例中不必要地引入绊脚石。

Induction only works on whole numbers to start with*, so even if the author didn't make any other statement as to the numbers being used, it's reasonable to assume everything is completely in the realm of integers.

Also, in case of calculations resulting in non-integral value, the non-integral part is cut off, not rounded. This is standard integer mathematics: 5/2 = 2 (plus remainder)

Under these assumptions, m+1/2 is interpreted as m.

*: to be more precise, induction works on any set that is ordered and countable (even countably infinite), but the implication is always the set of whole numbers, unless stated otherwise.


On a sidenote, I find it unfortunate that the author chose not to be clearer. Induction is not a trivial method to explain, it doesn't help to needlessly introduce tripping stones in the example(s).

这篇关于需要帮助理解算法的感应证明的解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！