프로젝트 중의 재 미 있 는 문제 -- 만두 먹 기 문제

제목 설명:
최근 프로젝트 에서 우연히 재 미 있 는 문 제 를 만 나 감개 무량 하고 잊 어 버 렸 다.추상 적 으로 보면 대체로:
테이블 위 에는 모두 100 개의 만두 가 있 는데 그 중 10 개의 만두 가 동전 을 빚 었 다. 동전 을 계속 먹 는 기대 횟수 는 몇 번 이 냐 고 물 었 다.
우선, 이곳 의 연속 을 정의 해 보 자. 만약 우리 가 만 두 를 먹 는 순 서 를 100 자리 의 이 진수 로 추상적으로 추정한다 면.그리고 만 두 를 먹 으 면 1 이 고 못 먹 으 면 0 이다. 그러면:
한 번 과 두 번 째 먹 으 면 110..........................................................................
만약 숫자 가... 1111.. 이 라면 여기 서 연속 되 는 4 개 1 은 3 회 연속 을 나타 낸다. 즉, 연속 만 하면 1 회 라 는 것 이다.기대 횟수, 즉 우 리 는 0 연속, 1 연속,... 9 연속 을 계산 해 야 한다.이 열 개의 계산.
주: 이곳 의 연속 은 사실 현재 위치의 이전 위치 상태 에 달 려 있 으 면 됩 니 다.따라서 DP 로 해결 할 수 있다.
이 문 제 는 숫자 를 세 는 문제 로 DP 를 사용 하여 해결 할 수 있 음 이 분명 하 다.
global [i] [j] [k]: 앞의 i 개 만두 에서 j 개의 동전 을 먹 었 고 연속 적 인 횟수 는 k 라 는 뜻 이다.
local [i] [j] [k]: 앞의 i 개 만두 에서 j 개의 동전 을 먹 었 고 k 번 째 는 i 번 째 위치 에서 계속 발생 했다 는 뜻 이다.(즉, i - 1 차 로 먹 은 것 도 만두 다).그리고 연속 횟수 는 k 입 니 다.
local[i][j][k] = local[i-1][j-1][k-1] + global[i-3][j-2][k-1]
global[i][j][k] = local[i][j][k] + global[i-2][j][k] + global[i-2][j-1][k] + local[i-3][j-2][k-1] + global[i-3][j-1][k]
분명히 상식 이 마지막 연속 여 부 를 하위 문제 로 하 는 것 은 현명 하지 못 하고 전달 관계 식 이 너무 복잡 하 다.
다음은 다른 각도 에서 분석한다.
마지막 두 분 의 상태 로 결정 합 니 다.
11: 그것 은 바로 연속 이다. 10, 01, 00, 연속 이 없 으 면 하위 문 제 를 직접 푸 시 면 됩 니 다.따라서 다음 문제 와 같이 정의: f [i] [j] [k] [0 / 1]: 앞의 i 개 만두 에서 j 개의 동전 을 먹 었 고 k 개의 연속 이 있 음 을 나타 낸다.그리고 마지막 은 0 / 1 의 횟수 입 니 다.그러면 우리 가 요구 하 는 것 은 f [100] [10] [k] [0] + f [100] [10] [k] [1] 이다.k = {1, 2, 3,..., 9} 주의: 이곳 의 마지막 1 차원 은 사실 0 / 1 의 기록 입 니 다. 물론 당신 도 두 개의 3 차원 배열 로 표시 할 수 있 습 니 다.Python 코드 는 다음 과 같 습 니 다. def compute(m,n,f,g):
    if n > m: return -1
    for i in range(m+1):
        f[i][0][0] = 1
    for j in range(n+1):
        f[0][j][0] = 0
        g[0][j][0] = 0
    f[0][0][0] = 1
    g[0][0][0] = 1
 
    for i in range(1,m+1):
        for j in range(1,min(i,n)+1):
            for k in range(0,j):
                f[i][j][k] = f[i-1][j][k] + g[i-1][j][k]
                if k != 0: g[i][j][k] = f[i-1][j-1][k] + g[i-1][j-1][k-1]
                else: g[i][j][k] = f[i-1][j-1][k]
 
    cnt = [0 for i in range(n)]
    for k in range(0,n):
        cnt[k] = f[100][10][k] + g[100][10][k]
    print cnt[1:]
 
    allSum = 1.0
    for i in range(91,101):  allSum = allSum * i
    for i in range(1,11): allSum /= i
    print "allSum = ", allSum
 
    print [float(x)/allSum for x in cnt]
    allSum2 = 0
    for i in range(1,n): allSum2 += (i * cnt[i])
    print allSum2/float(allSum)
 
if __name__ == "__main__":
    m = 100
    n = 10
    k = n-1
    f = [[[0 for k in range(k+1)] for j in range(n+1)] for i in range(m+1)]
    g = [[[0 for k in range(k+1)] for j in range(n+1)] for i in range(m+1)]
    compute(m,n,f,g)
결 과 는 0.9
이 함 수 는 현재 항목 에서 여러 번 호출 될 수 있 기 때문이다.그러면 횟수 를 최대한 낮 춰 야 한다.다른 한편, 이 메모리 의 사용 은 매우 커서 프로젝트 에서 n 과 m 의 수 치 는 대략 10 ^ 5 입 니 다.
어떻게 신속 하고 효과적으로 실현 합 니까?
현재 의 방안 은 이것 이 세 자리 의 배열 이기 때문에 1 차원 은 하나의 평면 이다. 그러면 나 는 고정된 구간 을 사이 에 두 고 이런 평면 을 보존 하 는 것 이다. 예 를 들 어 f [i] [j] [100], f [i] [j] [200], 이렇게 하면 계산 할 때 가장 가 까 운 평면 을 선택 하여 아래로 밀어 낸다.(모든 평면의 계산 은 이전 평면 에 만 의존 하기 때문이다.)
상술 한 설법 은 좀 어 려 울 수 있 으 며, 간단 한 예 와 비교 하면 분명 하 다.
예 를 들 어 우 리 는 지금 피 폴 라 계 수 를 구 하 는 함 수 를 만 들 려 고 합 니 다. 이 함수 의 호출 횟수 가 매우 빈번 합 니 다. 그러면 우 리 는 비망록 을 사용 하 는 것 을 회상 합 니 다. 그러나 현재 메모리 가 매우 제한 되 어 있 기 때문에 앞에서 계산 한 값 을 모두 저장 할 수 없습니다.그러면 우 리 는 어떤 값 을 저장 합 니까? 매우 간단 합 니 다. 각 수의 앞 두 수 에 의존 하기 때문에 우 리 는 한 구간 을 사이 에 두 개의 수 를 저장 합 니 다.예 를 들 어 우 리 는 f [1000], f [1001], f [2000], f [2001], f [3000], f [3001] 를 저장 합 니 다................................................
사실 이것 은 1 차원 의 상황 이 고 매번 저장 하 는 것 은 두 개의 숫자 이다.위의 3 차원 행렬 은 매번 2 차원 배열 로 저장 된다.
Final words:
여기 서 BUG 를 조정 할 때 Python 이라는 동적 언어 에 한 걸음 더 들 어 갔 습 니 다. 아래 코드 가 정확 합 니까?직접 해 보 세 요.
  tmp = [0 for i in range(k+1)]
  tmp2 = [tmp[:] for i in range(n+1)]
  f = [tmp2[:] for i in range(m+1)]
  g = [tmp2[:] for i in range(m+1)]
이렇게 f 와 g 두 배열 을 정의 하 는 것 이 맞 습 니까?
DP 의 하위 문 제 는 technique 라 고 정의 합 니 다.서브 문제 정의 의 좋 고 나 쁨 은 전달 식 의 복잡 정도 에 직접적인 영향 을 미친다.