小编典典

仅使用增量,循环,分配,零的关系运算

algorithm

我们只允许使用以下操作:

  1. incr(x)-调用此函数后,它将为x分配x +1
  2. Assign(x,y)-此函数会将y的值分配给x(x = y)
  3. 零(x)-此函数将为x分配0(x = 0)
  4. 循环X {}-括号内的操作将执行X次

例如,可以按以下方式实现加法:

add(x, y) {
    loop x
        { y = incr(y) }
    return y
}

如何使用这四个操作实现关系运算符?关系运算为:

  1. eq(x,y)-x是否等于y?
  2. lt(x,y)-x是否小于y?
  3. gt(x,y)-x是否大于y?

我们也有相反的观点:

  1. ne(x,y)-x不等于y吗?
  2. gte(x,y)-x是否大于或等于y?
  3. lte(x,y)-x是否小于或等于y?

任何帮助将不胜感激。


阅读 260

收藏
2020-07-28

共1个答案

小编典典

自然数集N在加法和减法下是封闭的:

N + N = N
N - N = N

这意味着两个自然数的加法或减法也是自然数(考虑到0 - 1is 0和not -1,我们不能有负自然数)。

但是,自然数集N在关系运算下不会关闭:

N < N = {0, 1}
N > N = {0, 1}

这意味着比较两个自然数的结果是真实性(即1)或虚假性(即0)。

因此,我们将布尔值集(即{0, 1})视为自然数的受限集(即N)。

false = 0
true  = incr(false)

我们必须回答的第一个问题是“我们如何对if语句进行编码,以便我们可以基于真实性或虚假性进行分支?” 答案很简单,我们使用以下loop操作:

isZero(x) {
    y = true
    loop x { y = false }
    return y
}

如果循环条件为true(即1),则循环仅执行一次。如果循环条件为false(即0),则循环不会执行。我们可以用它来编写分支代码。

那么,我们如何定义关系运算呢?事实证明,所有内容都可以通过以下方式定义lte

lte(x, y) {
    z = sub(x, y)
    z = isZero(z)
    return z
}

我们知道这x ≥ y与相同y ≤ x。因此:

gte(x, y) {
    z = lte(y, x)
    return z
}

我们知道,如果x > y为真x ≤ y则为假。因此:

gt(x, y) {
    z = lte(x, y)
    z = not(z)
    return z
}

我们知道这x < y与相同y > x。因此:

lt(x, y) {
    z = gt(y, x)
    return z
}

我们知道,如果x ≤ yy ≤ xx = y。因此:

eq(x, y) {
    l = lte(x, y)
    r = lte(y, x)
    z = and(l, r)
    return z
}

最后,我们知道如果x = y为true,x ≠ y则为false。因此:

ne(x, y) {
    z = eq(x, y)
    z = not(z)
    return z
}

现在,我们需要做的就是定义以下功能:

  1. sub函数定义如下:

    sub(x, y) {
    loop y
        { x = decr(x) }
    return x
    

    }

    decr(x) {
    y = 0
    z = 0

    loop x {
        y = z
        z = incr(z)
    }
    
    return y
    

    }

  2. not功能与该isZero功能相同:

    not(x) {
    y = isZero(x)
    return y
    

    }

  3. and功能与该mul功能相同:

    and(x, y) {
    z = mul(x, y)
    return z
    

    }

    mul(x, y) {
    z = 0
    loop x { z = add(y, z) }
    return z
    }

    add(x, y) {
    loop x
    { y = incr(y) }
    return y
    }

这就是您所需要的。希望有帮助。

2020-07-28