将此递归算法转换为迭代算法

Question

我在看这个堆叠溢出问题：Game of 2/9 (Interview at Facebook)

在其中一个答案中指出，通过与递归解决方案相比，可以找到该算法：

def win29(n):
    if n<=9: return True
    n-=1
    while n>=18:
        n = n//18
    return n==1 or 4<=n<=8

我想递归算法应该是这样的：

 F(i, j) = true; if (2^i * 9^j * 9) >= N
       !(F(i+1, j) && F(i, j+1)); otherwise

将这个递归算法转换为上面的迭代算法的机制或过程(或比较)是什么？

Answer 1

以下是我可以解释的算法：

1. N < 18^k*x and x>8 & x<18：然后玩家2胜，因为他可以通过使出18的力量直到x，来迫使一场胜利。
2. N < 18*k*x*9 and x>8 & x<18或N<18*k*2*x and x>8 & x<18：使用与1相同的类推，玩家1做出移动2或9，然后使用1获胜，因为他是下一步的玩家2。简化两个方程中的剩余项，我们得到r>=9*8/18>=4 and r<9*18/18<=8 and r>=9*2/18>=1 and r<18*2/18<2，使第一名玩家获胜

因此，先后除以18，然后检查n>=4 and n<=8 or n==1，以求第一名球员获胜。

如果恰当地比较我的解释，尽管我是用另一种方式来解释的，但它可以与递归解决方案相比较，在递归解决方案中，2^i*9^j*9可以可视化为18^k*x、F(i+1,j) as 2*18^k*x和F(i,j+1) as 9*18^k*x。