0

之字形序列是一个序列，其中每个元素都小于或大于它的邻居：1 3 2并且2 1 2是之字形，1 2 3而1 2 2不是。

给定两个数字 n，k 找出可以从数字 1..k 生成多少个大小为 n 的序列

示例：n = 3 k = 3 答案：10

121、212、131、313、232、323、132、231、312、213（不需要生成，只是为了清楚）

我来到了这个解决方案。请告诉我是否可以做得更好。

import sys

ZAG = {}
ZIG = {}

def zag(n, i):
    result = 0

    for j in xrange(1, i):    
        if (n - 1, j) not in ZIG:
            ZIG[(n - 1, j)] = zig(n - 1, j)
        result += ZIG[(n - 1, j)]

    return result    

def zig(n, i):
    result = 0

    for j in xrange(i + 1, MAX_NUMBER + 1):
        if (n - 1, j) not in ZAG:
            ZAG[(n - 1, j)] = zag(n - 1, j)
        result += ZAG[(n - 1, j)]

    return result

def count(n): 
    if n == 1:
        return MAX_NUMBER

    result = 0

    for i in xrange(1, MAX_NUMBER + 1):
        ZIG[(1, i)] = 1
        ZAG[(1, i)] = 1

    for i in xrange(1, MAX_NUMBER + 1):
        result += 2*zag(n, i)

    return result

def main(argv):
    global MAX_NUMBER
    MAX_NUMBER = int(argv[1])
    print count(int(argv[0]))

if __name__ == "__main__":
    main(sys.argv[1:])
4

2 回答 2

0

如果您通过递归调用 Zig（值小于最后一个数字）和 Zag（值大于最后一个数字）迭代可能性来生成序列，它会变得更好一些，并且您可以让它变得更好（计算方面，不是内存方面）通过将已解决的子问题存储在静态表中。

于 2012-10-08T16:38:30.340 回答
0

整个序列中的顺序是按照前两个元素的顺序给出的。排序有两种类型：up-down-up-... 和 down-up-down-... 两种排序的序列数量相同，因为一个排序的序列可以通过交换每个数字x与k+1-x。

让U_k(n)是 长度 的第一顺序的序列数n。让U_k(n, f)是 长度 为 第一 顺序 和 第一 数字 的序列n数f。类似的定义D_k(n)和D_k(n, f)。

那么长度n（对于n>1）的序列数是：

U_k(n) + D_k(n) = 2*U_k(n) = 2*( sum U_k(n, f) for f in 1 ... k ).

同样的论点给出：

U_k(n, f) = sum D_k(n-1, s) for s = f+1 ... k
          = sum U_k(n-1, s) for s = 1 ... k-f
U_k(1, f) = 1

编辑：

实现稍微简单一些。M(n,k)返回第 n 行（从后面），并C(n,k)计算序列数。

def M(n, k):
    if n == 1: return [1]*k
    m = M(n-1, k)
    return [sum(m[:i]) for i in xrange(k)][::-1]

def C(n, k):
    if n < 1: return 0
    if n == 1: return k
    return 2*sum(M(n,k))
于 2012-10-08T17:49:55.993 回答