알고리즘 --- 보 너 스 만두

제목 설명
설 을 쇠 자 엄 마 는 만두 100 마 리 를 만 들 었 는데 그 중 10 마리 에 동전 1 개가 들 어 있 었 다.샤 오 밍 은 이 100 마리 의 만 두 를 차례대로 먹고 샤 오 밍 이 k 개의 동전 을 계속 먹 으 면 샤 오 밍 은 k - 1 개의 동전 을 받는다.
예 를 들 어 110111 은 만두 6 마리, 1 은 동전 이 있 음 을 나타 내 고 0 은 없 음 을 나타 낸다.11. 만두 2 개 를 연속 으로 먹 으 면 샤 오 밍 은 동전 1 개 를 받는다.111 연속 지각 3 개, 샤 오 밍 은 동전 2 개 얻 기;그래서 샤 오 밍 은 모두 세 개의 동전 을 받 았 다.
-- 샤 오 밍 이 받 은 동전 의 기대 치 는.
분석 하 다.
원 하 는 정의: E(X)=∑iXiP(Xi)
이 문제 에서 랜 덤 이벤트 X 는 샤 오 밍 이 최종 적 으로 얻 은 동전 의 수량 입 니 다. x * 8712 ° [0, 9]
계산 P (Xi) = cases (x = i) allcases

기대 계산

그러면 원래 의 문 제 는 샤 오 밍 이 동전 k 를 얻 고 가능 한 모든 cases 의 수량 으로 간략화 된다.
동적 계획 을 사용 하고 하위 문 제 는 다음 과 같이 정의 합 니 다.

f [i] [j] [k] - 앞의 i 개 만두, j 개 동전 이 있 는 만두, 점 수 는 k 이 고 i 번 째 만 두 는 동전 이 없 으 며 모든 가능 한 상황 의 총수 입 니 다.

g [i] [j] [k] - 앞의 i 개의 만두, j 개의 동전 이 있 는 만두, 점 수 는 k 이 고 i 번 째 만 두 는 동전 을 함유 하 며 가능 한 모든 상황 의 총수 입 니 다.

그렇다면 전달 공식 은 다음 과 같다.

f [i] [j] [k] - i 번 만 두 는 동전 이 포함 되 어 있 지 않 기 때문에 i 번 만 두 를 사용 하지 않 습 니 다.

f[i][j][k] = f[i-1][j][k] + g[i-1][j][k]

g [i] [j] [k] - i 번 째 만두 에 동전 이 들 어 있 으 면 이 동전 을 얻 을 수 있 습 니 다. i - 1 번 째 만두 에 동전 이 들 어 있 는 지 여부 에 달 려 있 습 니 다.

g[i][j][k] = f[i-1][j-1][k] + g[i-1][j-1][k-1]

코드
1.DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#!/usr/bin/env python
import sys
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:]
#(100, 10)
allSum =
1.0
for i
in range(
91,
101): allSum = allSum * i
for i
in range(
1,
11): allSum /= i
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)
2. 시 뮬 레이 션
컴퓨터 로 시 뮬 레이 션 할 수 있 습 니 다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#!/usr/bin/python
import random
def helper(vec):
flag =
False
count =
0
for i
in range(len(vec)):
if vec[i]:
if flag: count +=
1
else: flag =
True
else:
flag =
False
return count
N =
100000
score =
0
cnt = [
0
for i
in range(
100)]
for i
in range(N):
count =
0
for i
in range(len(cnt)): cnt[i] =
0
while count <
10:
index = random.randrange(
0,
100)
if cnt[index]:
continue
count +=
1
cnt[index] =
1
score += helper(cnt)
print float(score) / N
결 과 는 약 0.9 정도 다.
뒷말
사실 이 문제 의 결 과 는 어느 정도 직관 에 어 긋 난다.기대 0.9 정도, 즉 평균 상황 에서 두 연속 1.
사실 이 문제 와 비슷 하 다. 수학 적 으로 생일 역설 이라는 유명한 역설 이 있다.
생일 역설 은 한 방 에 23 명 이나 23 명 이상 이 있 으 면 적어도 두 사람의 생일 이 같은 확률 이 50% 보다 높다 는 것 을 말한다.