除法操作使用增量，循环，赋值，零

Question

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

incr(x) -一旦这个函数被调用，它将给x赋值x + 1

assign(x, y) -该函数将y的值赋给x (x = y)

zero(x) -该函数将0赋值给x (x = 0)

loop X { } -括号内的操作将执行X次

如何实现除法运算?

Answer 1

虽然Sarid的答案是正确的，但可以通过以下方式更有效地计算floor(x / y):

divide(x, y) {
    x = incr(x)
    z = 0
    loop x {
        x = sub(x, y)
        l = isTrue(x)
        z = add(z, l)
    }
    return z
}

add和sub函数已经在这里定义过了:

仅使用自增、循环、赋值、零的减法操作

isTrue函数定义如下:

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

请注意，我们之前定义的true和false如下:

false = 0
true  = incr(false)

这个函数的唯一问题是divide(n, 0)返回n + 1而不是错误。

Answer 2

这个问题结合了另外两个已经在SO中回答过的帖子:

关系操作
<
2. 减法操作/gh>

从这些问题中我们可以看到如何实现sub(x,y), gt(x,y), lte(x,t)和add(x,y)。
通过使用这些，我们可以实现除运算- ceil(x/y)和floor(x/y):

装天花板(x/y)

div_ceil(x,y){
    r = 0
    loop x{
        z = 0
        l = gt(x,z)
        r = add(r,l)
        x = sub(x,y)
    }
    return r
}

解释:
我们循环x次，每次从x中减去y，然后计算循环的次数，直到x不再大于0。当它大于0时，将1加到结果中。

为什么循环运行x次?
因为这是为了得到结果所需要的最大时间。这是y == 1，减去1乘以x，我们将得到r == x。

---

地板(x/y)

div_floor(x,y){ 
    r = 0
    t = 0
    loop x{
        t = add(t,y)
        l = lte(t,x)
        r = add(r,l)
    }
    return r
}

或者，如果你愿意，通过简单地使用上面的div_ceil方法，我们也可以得到floor(x/y):

div_floor(x,y){
    z = div_ceil(x,y)
    k = div_ceil(incr(x),y)
    l = eq(z,k)
    z = sub(z,l)
    return z
}

简单比较x/y和x+1/y的结果。如果它们相等意味着我们在dev(x,y)中做了一个四舍五入(天花板)，所以我们需要减去1来得到地板结果。如果它们不相等，则结果应保持相同。

---

测试,指出

请在这里查看这些方法的正确性。
我在c++中实现了所有的函数，所以它们的行为完全相同(通过只使用允许的操作)。

我假设除以0是一个未定义的行为。在y==0的情况下，这些方法将返回一些值而不是错误。