좀 야매로 때려맞췄습니다;;
머리가 복잡해져서 중간에 실수한게 있을수도 있구.. 또 아이디어 자체가 틀린것일수도 있지만..
올려 봅니다.
Define: Discrete Function Eo[n,k]
=> n명에서 k명을 방법 1로 뽑을 경우의 평균 시행 횟수
Define: Discrete Function En[n,k]
=> n명에서 k명을 방법 2로 뽑을 경우의 평균 시행 횟수
Eo[n,k] =
먼저 각각의 경우의 확률을 보면
┳ 0명 뽑힐 확률 2*1/2^n
┣ 1명 뽑힐 확률 2*C(n,1)/2^n
┣ 2명 뽑힐 확률 2*C(n,2)/2^n
:
┣ k명 뽑힐 확률 2*C(n,k)/2^n
:
┗ [n/2] 명 뽑힐 확률 [x]는 x보다 작은 최대 정수
C(n,k) = (k) = n! 을 의미함
(n) ━━━━
k!(n-k)!
이는 Geomatric이므로 각각의 역수가 평균이 된다. 즉
Eo[n,k] = 2^n/2*C(n,k) = 2^(n-1) / C(n,k) {Eo함수}
한편 En[n,k]는 1~k까지 뽑히면 뽑는 상황의 상태가 변한다. 다시 보면
En[n,k] ┳ 0명 뽑힘 ━ 상태유지
┣ 1명 뽑힘 ━ En[n-1,k-1]
┣ 2명 뽑힘 ━ En[n-2,k-2]
:
┣ k명 뽑힘 ━ En[n-k,0]
:
┗ 상태유지
가 된다. 즉 상태가 변화할 확률은 1명 뽑힐 확률 + 2명 ... k명 뽑힐 확률로 다음과 같다.
k △
∑ C(n,i)/ 2^(n-1) = Sump(n,k) (- Sum of Probabilities)
i=1
이 상태가 되었을 때 앞으로의 평균 시행 횟수를 Ea[n,t]라고 하면 En[n,k] 는 다음과 같이 쓸 수 있다.
En[n,k] = 1/Sump(n,k) + Ea[n,t] - 1 {1}
이것은 Geomatric에서 일정 수 Ea를 더한 만큼 가게 되며 Ea값이 n, k에 의해서만
바뀌기 때문게 가능한 가정이다.
12줄 위의 그림에서 Ea를 구해 보면, 평균은 각각의 확률 * 각각의 시행 평균 / 전체 확률 이 되므로
k
∑ (En[n-i,k-i] + 1) * C(n,i)/ 2^(n-1)
i=1
Ea[n,k] = ━━━━━━━━━━━━━━━━━━━━ {2}
Sump(n,k)
가 된다. +1항은 k 이하의 사람이 뽑혀 En으로 내려갈 때 뽑힐 때 셋 횟수를 더한 값이다.
위 식에서 2^(n-1) 항은 소거되고, 새 함수를 정의하여
k △
∑ C(n,i) = Sumc(n,k)
i=1
로 한 후, Ea를 {1}식에 대입하여 정리하면
┏ k ┓
┃ ∑ (En[n-i,k-i] + 1) * C(n,i) ┃ + 2^(n-1) - Sumc(n,k)
┗ i=1 ┛
En[n,k] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sumc(n,k)
┏ k ┓
┃ ∑ En[n-i,k-i] * C(n,i) ┃ + 2^(n-1)
┗ i=1 ┛
= ━━━━━━━━━━━━━━━━━━━━ {En함수}
Sumc(n,k)
가 된다.
En의 initial condition 을 살펴보면, 정리 전 식에서 i = k일 때 평균(En[n-i,k-i] + 1)이 1이 되므로
En[n,0] = 0 (n=자연수)
이 된다.
------------------------------------------------------------------------------------------------
Problem 1-1:
답 : Eo[10,3] = 512/120
Problem 1-2:
답 : En[10,3] ≒ 7.54794 (풀이는 맨 아래에)
Problem 1-3:
En'[10,4] ┳ 0명 뽑힘 ━ 상태유지
┣ 1명 뽑힘 ━ En[9,2]
┣ 2명 뽑힘 ━ En[8,1]
┣ 3명 뽑힘 ━ En[7,0]
┣ 4명 뽑힘 ━ En[4,1]
:
┗ 상태유지
상태변화는 1~4명 뽑혔을 때까지에서 일어나며 변화 확률은 Sump(10,4)가 된다. 위와 같은 방법으로
Ea'를 구하면
┏ 3 ┓
┃ ∑ (En[10-i,3-i] + 1) * C(10,i)/ 2^(9) ┃ + (En[4,1] + 1) * C(10,4)/ 2^(9)
┗ i=1 ┛
Ea'[10,4] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sump(10,4)
┏ 3 ┓
┃ ∑ (En[10-i,3-i] + 1) * C(10,i) ┃ + (En[4,1] + 1) * C(10,4)
┗ i=1 ┛
= ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sumc(10,4)
가 되며 이를 {1}식에 ' notation사용하여 대입하면
┏ 3 ┓
┃ ∑ (En[10-i,3-i] + 1) * C(10,i) ┃ + (En[4,1] + 1)*C(10,4) + 2^9 - Sumc(10,4)
┗ i=1 ┛
En'[10,4] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sumc(10,4)
┏ 3 ┓
┃ ∑ En[10-i,3-i] * C(10,i) ┃ + En[4,1]*C(10,4) + 2^9
┗ i=1 ┛
= ━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sumc(10,4)
가 된다.
답 : En'[10,4] ≒ 4.52179
Problem 2-1:
답: En[n,3] = 얼마 안되므로 재귀로 표현할 수 있다.
Problem 2-2:
답: En[n,k] = 지금 방법으로는 표현 불가, n,k를 알면 알고리즘으로 사용 가능
--------------------------------------------------------------------------------------------------
Algorithm for Calculating En[n,k]
┏ k ┓
┃ ∑ En[n-i,k-i] * C(n,i) ┃ + 2^(n-1)
┗ i=1 ┛
En[n,k] = ━━━━━━━━━━━━━━━━━━━━
Sumc(n,k)
En[n,0] = 0
이며 이를 C 함수로 나타내면 다음과 같다.
double En(int n, int k) {
int i;
double s1, s2;
/* 이 부분은 n, k가 초기에 정상적으로 입력되었다고 가정할 때 주석처리가 가능하다
if(n<2*k+1 || k<0 || n<3 ) {
cout << "잘못된 숫자 입력n";
return 0;
}
*/
if(k==0)
return 0;
else {
s1 = expi(2,n-1); // (exponent for integer - expi(int a, int b) 는 double a^b를 리턴)
s2 = 0;
for(i=1;i<=k;++i) {
s1 += En(n-i,k-i)*C(n,i); // C(int a,int b) 는 int a!/[ b! * (a-b)! ]를 리턴
s2 += C(n,i);
}
}
return s1/s2;
}
double expi(int a, int b) {
int i;
double s = a;
for(i=1;i<b;++i)
s *= a;
return s;
}
int C(int a, int b) {
int i;
int s1, s2;
/* 이 부분은 a, b가 초기에 정상적으로 입력되었다고 가정할 때 주석처리가 가능하다
if(a<b) {
cout << "잘못된 숫자 입력n";
return 0;
}
*/
s1 = 1;
s2 = 1;
for(i=0;i<b;++i) {
s1 *= a-i;
s2 *= i+1;
}
return s1/s2;
}
-----------------------------------------------------------------------
답을 위해 작성한 main 함수
#include<iostream>
using namespace std;
double En(int n, int k);
double expi(int a, int b);
int C(int a, int b);
void main()
{
cout << En(10,3) << endl;
cout << ( En(9,2)*C(10,1) + En(8,1)*C(10,2) + En(4,1)*C(10,4) + expi(2,9) )/( C(10,1)+C(10,2)+C(10,3)+C(10,4) ) << endl;
}
--------------------------------------------------------------------------
결과창
7.54794
4.52179
Press any key to continue
........................................................................................
■ 박기현: c코드의 En함수에서 주석처리된 if 구문에서 n<3은 필요도 없고 En[2,0]때문에 맞지도 않는군요.. 수정해야겠습니다. (pl2115@hotmail.com) -[10/13-01:38]-
........................................................................................
■ 송홍엽: 고생했다... 정답을 검토할동안 조금만 기다려다오.. (hy.song@coding.yonsei.ac.kr) -[10/14-20:46]-