伪代码的归纳证明 [英] Proof of induction on pseudocode

问题描述

给出伪代码

MUL(a,b) 
   x=a
   y=0
   WHILE x>=b DO
      x=x-b
      y=y+1
   IF x=0 THEN
      RETURN(true)
   ELSE
      RETURN(false)

在while循环运行 n 次后，让x(n)和y(n)表示x和y的值.

Let x(n) and y(n) denote the value of x and y after the while loop has run n times.

我必须通过归纳证明来证明

I have to show by the proof of induction that

x(n)+ b * y(n)= a

x(n) + b*y(n) = a

我所做的事情:

P(n):x(n)+ by(n)= a

P(n): x(n) + by(n) = a

让a和b为任意数字，则第一个循环将给出x(1)= a-b和y(1)= 0 +1 = 1

Let a and b be arbitrary numbers then the first loop will give x(1) = a - b and y(1) = 0 + 1 = 1

P(1):x(1)+ by(1)= a< => a = a

P(1): x(1) + by(1) = a <=> a = a

所以P(1)是真的.

假设P(n)为真.我们想证明P(n + 1)也成立.

Assume P(n) is true. We want to show that P(n+1) is also true.

对于步骤n +1，循环将给出x(n + 1)= x(n)-b和y(n + 1)= y(n)+1

For step n + 1 the loop will give x(n+1) = x(n) - b and y(n+1) = y(n) + 1

P(n + 1):x(n + 1)+ by(n + 1)= a< => x(n)+ by(n)= a

P(n+1): x(n+1) + by(n+1) = a <=> x(n) + by(n) = a

使用P(n)为真的假设，得出P(n + 1)也为真，证明是完全的.

Using the assumption that P(n) is true, it follows that P(n+1) is also true, and the proof is complete.

我的问题:由于这是我第一次在伪代码上使用归纳证明，因此我不确定该怎么做.我只想知道这是否是解决问题的正确方法，如果不是，该过程应该是什么样?

My question: Since this is my first time using the proof of induction on a pseudocode, I'm not sure how to go about it. I just want to know if this is the right way to work around the problem, and if not what should the process be like?

谢谢

推荐答案

当您(几乎)正确回答问题时，回答此问题似乎有点过头了，但我还是会这样做:

As you got it (almost) right in your question, answering this feels like overkill, but I'll do it anyway:

您的方法很好，尽管您不应该忽略根本不执行循环迭代的情况，例如 a< b 并对应于 P ₀ .如果您证明 P ₁ 是真实的，并且当 P _{时 P n + 1 是真实的> n} 是真的，您什么都没说 P ₀ .

Your approach is fine, although you should not ignore the case where no loop iterations are executed at all, which is the case when a < b and corresponds to P₀. If you prove P₁ is true, and P_n+1 is true when P_n is true, you don't say anything about P₀.

因此，通过稍作修改，归纳证明的推导如下:

So with that slight modification, the derivation of the proof by induction goes as follows:

将 P _n 定义为在执行 n 个循环迭代后的表达式x + b*y的值:

Define P_n as the value of the expression x + b*y after n iterations of the loop have been executed:

P _n :x _n + b.y _n = a

P_n : x_n + b.y_n = a

要证明 P _n 对于所有 n> = 0

请注意，这是一种可能的情况:当第一次评估while循环的条件时，尚未执行任何迭代，因此 n 为0，但是我们确实有两个值变量: x ₀ 和 y ₀ .

Note that this is a possible case: when the condition of the while loop is first evaluated, no iterations have been performed yet, so n is 0, yet we do have the values for the two variables at play: x₀ and y₀.

循环的前提条件由循环之前的赋值语句确定:

The pre-condition for the loop is determined by the assignment statements that precede the loop:

x=a
y=0

所以我们有:

P ₀ :x ₀ + by ₀ = a + b.0 = a

P₀ : x₀ + b.y₀ = a + b.0 = a

2.归纳步骤: P _{n + 1}

在此我们假定 P _n 对于给定的 n 是正确的:

2. Inductive Step: P_n+1

Here we assume that P_n is true for a given n:

P _n :x _n + b.y _n = a

P_n : x_n + b.y_n = a

这是开始循环的下一个迭代时的先决条件，其中执行以下语句:

This is the pre-condition when starting the next iteration of the loop, in which the following statements are executed:

x=x-b
y=y+1

通过替换，我们得到该特定迭代的后置条件，根据定义，该特定迭代为 P _{n + 1}

By substitution we get the post-condition for that particular iteration which by definition is P_n+1:

P _{n + 1} :(x _n -b)+ b.(y _n + 1)= x _n + by _n = P _n = a

P_n+1 : (x_n - b) + b.(y_n + 1) = x_n + b.y_n = P_n = a

这篇关于伪代码的归纳证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！