主页 / 问题 / 1602191
Accepted
u111
Asked:2024-12-11 16:36:36 +0000 UTC2024-12-11 16:36:36 +0000 UTC

无递归的阿克曼函数

  • 772

如何不用递归计算阿克曼函数？

递归实现：

def ack(n, m):
    if n == 0:
        return m + 1
    if m == 0:
        return ack(n - 1, 1)
    return ack(n - 1, ack(n, m - 1))
python

3 个回答

  1. 在同一个维基百科中，有一个没有递归的实现的链接。

    https://doi.org/10.1016%2F0304-3975%2888%2990046-1

    def ack(n, m):
    if n == 0:
        return m + 1
    if m == 0:
        return ack(n - 1, 1)
    return ack(n - 1, ack(n, m - 1))

def ack1(i, n):
    stack = []
    stack.append(i)
    stack.append(n)
    while len(stack) > 1:
        n_cur = stack.pop()
        i_cur = stack.pop()
        if i_cur == 0:
            stack.append(n_cur + 1)
        elif n_cur == 0:
            stack.append(i_cur - 1)
            stack.append(1)
        else:
            stack.append(i_cur - 1)
            stack.append(i_cur)
            stack.append(n_cur - 1)
    result = stack.pop()
    return result

for i in range(4):
    for j in range(4):
        a1 = ack(i, j)
        a2 = ack1(i, j)
        print(a1, a2)
        assert a1 == a2
    • 4
  2. Best Answer

    来自与 @maestro 的答案相同的来源，第二个选项：无堆栈，m*ack(m,n)两个大小数组上的循环长度(m+1)和(n+1)

    该函数ack_2在性能方面与堆栈实现进行了比较。例如，它可以轻松自然地计算A(4,1)，这是递归函数无法计算的（堆栈溢出），而且我没有等待 @maestro 的答案中带有内部堆栈的函数。

    理论上，与递归和内部堆栈实现不同，此实现可以计算任何参数的 Ackerman 函数。但仅限于理论上。实际上，即使是计算也A(4,2)需要大约10^20_000（10 的 20000 次方）运算。他们活不了那么长。甚至我们的宇宙——估计最后一个黑洞将在10^107年后蒸发，之后空荡荡的宇宙中将不再剩下重子物质，也就没有什么可指望的了。

    def ack(n, m):
    if n == 0:
        return m + 1
    if m == 0:
        return ack(n - 1, 1)
    return ack(n - 1, ack(n, m - 1))

    
def ack_2(i, n):
    """
    Вычисляет функцию Аккермана без рекурсии.
    Подробности см. в статье Jerrold W. Grossman and R.Suzanne Zeitman
    "An inherently iterative computation of ackermann's function"
    https://doi.org/10.1016%2F0304-3975%2888%2990046-1
    
    Аргументы:
        i (int): Степень гипероперации, i >= 0.
        n (int): Аргумент гипероперации, n >= 0.
    Возвращаемое значение:
        int: значение функции Аккермана.
    """
    vals = [0] * (i + 1)
    goal = [1] * (i) + [-1]
    
    while True:
        value = vals[0] + 1
        for j, v in enumerate(vals):
            vals[j] += 1
            if v == goal[j]:
                goal[j] = value
            else:
                break

        if vals[i] == n + 1:
            return value


    
for i in range(4):
    for n in range(4):
        a1 = ack(i, n)
        a2 = ack_2(i, n)
        print((i,n), a1, a2)
        assert a1 == a2

    (0, 0) 1 1
(0, 1) 2 2
(0, 2) 3 3
(0, 3) 4 4
(1, 0) 2 2
(1, 1) 3 3
(1, 2) 4 4
(1, 3) 5 5
(2, 0) 3 3
(2, 1) 5 5
(2, 2) 7 7
(2, 3) 9 9
(3, 0) 5 5
(3, 1) 13 13
(3, 2) 29 29
(3, 3) 61 61
    • 4 
  3. '''
Написать скрипт, вычисляющий функцию Аккермана без применения рекурсии
'''

import os
import time

def ackermann(m, n):
    stack = [(m, n)]
    while stack:
        m, n = stack.pop()
        if m == 0:
            n += 1
            if stack:
                stack[-1] = (stack[-1][0], n)
        elif n == 0:
            stack.append((m - 1, 1))
        else:
            stack.append((m - 1, None))
            stack.append((m, n - 1))
    return n

m, n = 2, 0  # Пример значений для функции Аккермана
start_time = time.time()
result = ackermann(m, n)
execution_time = time.time() - start_time

print(f"Результат функции Аккермана A({m}, {n}) = {result}")
print(f"Время выполнения: {execution_time:.6f} секунд")

print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")

    结果：

    Результат функции Аккермана A(2, 0) = 3
Время выполнения: 0.000006 секунд
    • 0

相关问题