可计算性（计算机模型、计算完备性）一题

---

    可计算性（计算机模型、计算完备性）一题
    作者：tyc611.cublog.cn，2008-10-23

---

【问题描述】
一个计算机只有以下功能：
1）赋值
2）+1
3）指定次数的循环
4）只处理0和正整数
5） 不考虑溢出

请实现如下操作：
A）算术运算：自减(a - 1)、加(a + b)、减(a - b)、乘(a * b)、除(a / b)、模(a % b)
B）逻辑运算：布尔值(!!a)、非(!a)、与(a && b)、或(A || b)
C）关系运算：小于(a < b)、小于等于(a <= b)、大于(a > b)、大于等于(a >= b)、相等(a == b)、不等(a != b)
D）条件运算：条件运算符(a ? b : c)

其中，
1. 上面的操作符语义与C/C++基本相同，可以以此理解和实现
2. 如果是逻辑运算，则当操作数非零时结果为1，操作数为零时结果为0；不需要实现&&和||操作符的短路计算
3. 如果是关系运算，则当表达式为真时结果为1，表达式为假时结果为0

【实现】
（注：如果下面的表达式为布尔表达式，则用1表示结果真，用0表示结果假）
1. 加法

a + b
    x = a
    loop b
        x = x + 1
    return x

2. 自减（注：如果a == 0，则a - 1为0）

a - 1
    x = 0
    y = 0
    loop a
        y = x
        x = x + 1
    return y

3. 减法（注意：如果a < b，则a - b为0）

a - b
    x = a
    loop b
        x = x - 1
    return x

4. 乘法

a * b
    x = 0
    loop b
        x = x + a
    return x

5. 布尔值（用!!a表示计算a的布尔值；如果a >= 1则!!a为1，否则!!a为0）

!!a
    x = a -1
    y = a - x
    return y

6. 逻辑非（如果a == 0，则!a为1，否则!a为0）

!a
    x = !!a
    y = 1 - x
    return y

7. 小于

a < b
    x = b - a
    y = !!x
    return y

8. 小于等于

a <= b
    x = b < a
    y = !x
    return y

9. 大于

a > b
    x = b < a
    return x

10. 大于等于

a >= b
    x = a < b
    y = !x
    return y

11. 等于

a == b
    x = a - b
    y = b - a
    z = x + y
    r = !z
    return r

12. 不等

a != b
    x = a == b
    y = !x
    return y

13. 逻辑与

a && b
    x = !!a
    y = !!b
    z = x + y
    r = z == 2
    return r

14. 逻辑或

a || b
    x = !!a
    y = !!b
    z = x + y
    r = !!z
    return r

15. 条件运算

a ? b : c
    x = !!a
    y = !x
    r = b * x
    s = c * y
    t = r + s
    return t

16. 除法（如果b为0，则a / b为a；否则，结果为a / b的整数部分（如果a < b则为0））

a / b
    t = a
    r = 0
    loop a
        x = t >= b
        r = r + x
        t = t - b
    return r

17. 求模

a % b
    x = a / b
    y = x * b
    z = a - y
    return z

最后，欢迎大家评论：
如果发现错误还望指出
如果有更好的实现（主要从效率和代码简洁两方面权衡），希望共享之
（减法是后面其它运算的重要基本，但上面实现的减法的效率太低了，不知道能不能改进）

---