时间戳

首页 > 解决方案 > Python中递归定义的超操作序列

python - Python中递归定义的超操作序列

问题描述

我创建了一个简单的函数来迭代二进制操作，我想用它来递归地定义整数超操作的序列（继承、加法、乘法……）。

迭代函数为：

# f : (int,int) -> int
# x,y : int

def right_iterate(f,x,y):
    a = x
    while y - 1 > 0:
        y = y - 1
        x = f(a,x)
    return x

理想情况下，我想定义这样的超操作序列：

# H : int -> ( (int, int) -> int )
# n,x,y : int

def H(n)(x,y):
    if n == 0:
        return x+1
    else:
        return right_iterate(H(n-1),x,y)

基本上是我正在处理的方程式的精确翻译，但这在 Python 中不受支持。我想我需要做一些类似于柯里化的事情并定义一个函数h(n,x,y)-->H(n)(x,y)，但我不确定如何。

我试过使用

# H : int -> ( (int,int) -> int )
# h : (int,int) -> int
# n,x,y : int

def H(n):
    def h(x,y):
        if n == 0:
            return y + 1
        else:
            return right_iterate(H(n-1),x,y)
    return h

这是不对的，但它似乎在正确的轨道上 当n为 1 时，它的评估结果与

if y != 0:
    return x + y - 1
else:
    return x + y

当n为 2 时，计算结果为 `

if y != 0:
    return x * y - (y -1)
else:
    return x

标签： pythonfunctionrecursioncurryinginteger-arithmetic

解决方案

基于对Wikipedia上超操作的快速研究，我猜你想要类似的东西：

from operator import add

def right_iterate(f, a, b):
    c = a

    while b > 0:
        a = f(c, a)
        b -= 1

    return a

def H(n, a, b):
    if n == 0:
        return right_iterate(add, 1, b)

    if b == 0:

        if n == 1:
            return a

        if n == 2:
            return 0

        if n >= 3:
            return 1

    return H(n - 1, a, H(n, a, b - 1))

if __name__ == '__main__':
    print(H(0, 2, 3))  # 1 + 3
    print(H(1, 2, 3))  # 2 + 3
    print(H(2, 2, 3))  # 2 * 3
    print(H(3, 2, 3))  # 2 ** 3
    print(H(4, 2, 3))  # 2 ** 2 ** 2

输出

> python3 test.py
4
5
6
8
16
>

推荐阅读