Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

덴치 문제..푼 결과

2005.10.11 10:56

박기현 조회 수:4777 추천:337

좀 야매로 때려맞췄습니다;;
머리가 복잡해져서 중간에 실수한게 있을수도 있구.. 또 아이디어 자체가 틀린것일수도 있지만..

올려 봅니다.



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]-
번호 제목 글쓴이 날짜 조회 수
공지 논문에 영어작문 주의사항 몇 가지 송홍엽 2008.05.22 9962
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 6677
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 8905
68 수학사 바로잡기 (1) - 오일러의 36명 장교문제와 조선시대 최석정 (수정본 - 일부 오류 수정) [1] file 송홍엽 2008.06.03 7347
67 [펀글] 전화기를 최초로 발명한 사람은 누구인가 송홍엽 2008.05.23 7166
66 [퍼온글] 우리전공의 학부생이 공부하면 좋을 수학과목 ?? 송홍엽 2003.03.23 6634
65 김정한 교수의 '창의적 수학교육' [1] file 송홍엽 2008.06.20 6406
64 [퍼온글] 에르도쉬 넘버 [1] file 송홍엽 2004.10.23 6095
63 [퍼온글] 애플컴퓨터 로고의 유래(?) 송홍엽 2006.02.09 6080
62 [펀글] 영문이력서 작성법 송홍엽 2011.03.27 6009
61 게임의 확률과 기대값 송홍엽 2004.12.02 5925
60 [펀글] 프로그램 설계시 좋은 코딩 습관 송홍엽 2009.12.27 5537
59 [퍼온글] 명왕성 이야기 송홍엽 2006.04.26 5516
58 오류정정부호에 대한 이야기 송홍엽 2004.04.13 5448
57 [퍼온글] 달력의 유래 송홍엽 2004.04.01 5365
56 채널코딩 세째 이야기 송홍엽 2003.11.13 5173
55 지금 내 전공분야는 공부한던 시절엔 나에게 가장 힘든 분야였답니다... 송홍엽 2003.06.03 5087
54 수학자와 공학자 송홍엽 2006.05.09 5065
53 채널코딩에 관한 첫번째 이야기 송홍엽 2003.10.13 4985
52 uncorrelated but not independent 송홍엽 2004.05.13 4811
51 정보화와 정보이론 송홍엽 2004.08.06 4810
50 combinatorial search problem file 송홍엽 2004.07.21 4803