계산 지그재그 순서

Question

지그재그 순서가 순서입니다 : 1 3 2 및 2 1 2는 지그재그 있으며, 1 2 3 및 1 2 2는 없습니다. N 주어진 두 숫자와

, 크기가 n 인 다수의 시퀀스 예

번호 1..k로부터 생성 될 수있는 방법을 알아 K : 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:]) 

Answer 1

전체 시퀀스의 순서는 처음 두 요소의 순서와 함께 제공됩니다. 두 가지 유형의 순서가 있습니다 : up-down-up -... and down-up-down -... 두 순서의 순서가 동일합니다. 한 순서의 순서는 각각 다른 순서로 변환 될 수 있기 때문에 숫자 x과 k+1-x.

U_k(n)은 처음으로 길이가인 순서의 수로합시다. U_k(n, f)을 길이가 n이고 첫 번째 숫자가 f 인 순서의 번호로합시다. 비슷하게 D_k(n)과 D_k(n, f)을 정의하십시오.

(n>1 용) 길이 n의 시퀀스의 다음 수는 다음과 같습니다

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)) 

Answer 2

당신은 (마지막 숫자보다 적은 값) 지그에 재귀 호출을 통해 시퀀스를 생성하고 지그재그은 조금 더 좋아진다, 가능성을 반복 (마지막 숫자보다 더 큰 값), 그리고 당신이 그것을 할 수 있다면 해결 된 하위 문제를 정적 테이블에 저장하여 더 나은 (계산 방식, 메모리 방식이 아님)