生成第n个Motzkin数字的最快方法是什么？

Question

我想生成所有的Motzkin编号并存储在一个数组中.公式如下:

我目前的实施速度太慢了:

void generate_slow() {
    mm[0] = 1;
    mm[1] = 1;
    mm[2] = 2;
    mm[3] = 4;
    mm[4] = 9;
    ull result;
    for (int i = 5; i <= MAX_NUMBERS; ++i) {
        result = mm[i - 1];
        for (int k = 0; k <= (i - 2); ++k) {
            result = (result + ((mm[k] * mm[i - 2 - k]) % MODULO)) % MODULO;
        }
        mm[i] = result;
    }
}

void generate_slightly_faster() {
    mm[0] = 1;
    mm[1] = 1;
    mm[2] = 2;
    mm[3] = 4;
    mm[4] = 9;
    ull result;
    for (int i = 5; i <= MAX_NUMBERS; ++i) {
        result = mm[i - 1];
        for (int l = 0, r = i - 2; l <= r; ++l, --r) {
            if (l != r) {
                result = (result + (2 * (mm[l] * mm[r]) % MODULO)) % MODULO;
            }
            else {
                result = (result + ((mm[l] * mm[r]) % MODULO)) % MODULO;
            }
        }
        mm[i] = result;
    }
}

此外,我一直在为重复矩阵找到一个封闭的形式,以便我可以应用求幂平方.有谁能建议更好的算法？谢谢.
编辑我无法应用第二个公式,因为当模数为模时,除法不适用.的最大n为10,000这超出64位整数的范围内,所以答案是模数具有较大数目m,其中m= 10 ^ 14 + 7更大的整数库是不允许的.

Answer 1

警告：以下代码是错误的，因为它使用整数除法（例如 5/2 = 2 而不是 2.5）。请随意修复它！

这是使用动态规划的好机会。这与计算斐波那契数非常相似。

sample code:

cache = {}
cache[0] = 1
cache[1] = 1

def motzkin(n):
    if n in cache:
        return cache[n]
    else:
        result = 3*n*motzkin(n - 2)/(n + 3) + (2*n + 3)*motzkin(n - 1)/(n + 3)
        cache[n] = result
        return result

for i in range(10):
    print i, motzkin(i)

print motzkin(1000)

"""
0 1
1 1
2 2
3 4
4 9
5 21
6 53
7 134
8 346
9 906
75794754010998216916857635442484411813743978100571902845098110153309261636322340168650370511949389501344124924484495394937913240955817164730133355584393471371445661970273727286877336588424618403572614523888534965515707096904677209192772199599003176027572021460794460755760991100028703368873821893050902166740481987827822643139384161298315488092901472934255559058881743019252022468893544043541453423967661847226330177828070589283132360685783010085347614855435535263090005810
"""

问题是因为这些数字变得如此之大，如果你想达到非常高的数值，将它们全部存储在缓存中将会耗尽内存。那么最好使用 for 循环来记住前两项。如果你想找到许多数字的 motzkin 数，我建议你先对数字进行排序，然后当你在 for 循环中接近每个数字时，输出结果。

编辑：我创建了一个循环版本，但得到了与之前的递归函数不同的结果。至少有一个是错的！！希望您仍然能看到它是如何工作的并能够修复它！

def motzkin2(numbers):
    numbers.sort() #assumes no duplicates
    up_to = 0
    if numbers[0] == 0:
        yield 1
        up_to += 1
    if 1 in numbers[:2]:
        yield 1
        up_to += 1

    max_ = numbers[-1]
    m0 = 1
    m1 = 1
    for n in range(3, max_ + 1):
        m2 = 3*n*m0/(n + 3) + (2*n + 3)*m1/(n + 3)
        if n == numbers[up_to]:
            yield n, m2
            up_to += 1
        m0, m1 = m1, m2



for pair in motzkin2([9,1,3,7, 1000]):
    print pair

"""
1
(3, 2)
(7, 57)
(9, 387)
(1000, 32369017020536373226194869003219167142048874154652342993932240158930603189131202414912032918968097703139535871364048699365879645336396657663119183721377260183677704306107525149452521761041198342393710275721776790421499235867633215952014201548763282500175566539955302783908853370899176492629575848442244003609595110883079129592139070998456707801580368040581283599846781393163004323074215163246295343379138928050636671035367010921338262011084674447731713736715411737862658025L)
"""