Knuth up-箭头符号

Question

我用Python实现了Knuth向上箭头符号：

from functools import lru_cache


@lru_cache
def kuan(a, b, arrows):
    if arrows == 1:
        return a ** b
    res = a

    for i in range(b):
        res = kuan(a, res, arrows - 1)
    return res

这可以非常快地计算kuan(3, 3, 1)。但对于kuan(3, 3, 2)来说，它的速度慢了下来。有什么改善表现的建议吗？

Answer 1

当使用arrows==1时，您使用的是另一种方法，因此在这种情况下说它很快是没有帮助的。您希望针对较大的箭头值进行测试。由于k(3,3,2)正在减速，这意味着我们需要减少a和/或b。但是从你的方法来看，你似乎有一个额外的指数。我们应该：

a ^n 1 == a ^(n-1) ( a ^n 0 ) == a ^(n-1) 1 == ... == a ^ 1 == a
# and
a ^n b
== a ^(n-1) a^n (b-1)
...
== a ^(n-1) a ^(n-1) ... a ^(n-1) a ^n 0 # a occurs b+1 times
== a ^(n-1) a ^(n-1) ... a ^(n-1) 1 # a occurs b times
== a ^(n-1) a ^(n-1) ... a # a occurs b times

但你有

kuan(a,1,arrows) == kuan(a,a,arrows-1) # can get big
# and
kuan(a,b,arrows)
== kuan(a,kuan(a,kuan(a,...,kuan(a,a,arrows-1)...,arrows-1),arrows-1),arrows-1)
# kuan occurs b times, a occurs b+1 times

通过使用range(b-1) (或N3buchadnezzar建议的range(1,b) )可以很容易地解决这个问题。还请注意，Python中的一个常见约定是，可忽略的变量(如i )通常被命名为_。这有助于编码器认识到，i没有出现在循环中并不是一个错误。