0

ジグザグシーケンスは、すべての要素が隣接する要素よりも少ないまたは多いシーケンスです。1 3 2および2 1 2はジグザグで1 2 3あり、そうで1 2 2はありません。

nが与えられた2つの数値を使用して、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

シーケンス全体の順序は、最初の2つの要素の順序で示されます。順序付けには、up-down-up-...とdown-up-down-...の2つのタイプがあります。1つの順序付けのシーケンスは、それぞれを交換することで別の順序に変換できるため、両方の順序付けのシーケンスの数は同じです。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 に答える
0

Zig (最後の数値よりも小さい値) および Zag (最後の数値よりも大きい値) への再帰呼び出しによってシーケンスを生成し、可能性を反復すると、少し良くなり、さらに良くすることができます (計算に関しては、解決済みのサブ問題を静的テーブルに保存することによって。

于 2012-10-08T16:38:30.340 に答える