Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

덴치 문제..푼 결과

2005.10.11 10:56

박기현 조회 수:4596 추천: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 9200
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 6145
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 8214
89 학위논문 작성에 관한 조언 file 송홍엽 2014.01.25 2132
88 [펀글] 한겨레 2011.12.23. 정봉주 유죄판결은 법적 착시현상 송홍엽 2011.12.25 2340
87 2013년 12월 31일 오후에 작성한 글: 새해는 시속 1400키로의 속도로 달려온다. file 송홍엽 2014.01.17 2460
86 [펀글]프로운동선수의 대학학업 병행하기 송홍엽 2009.12.17 2923
85 [펀글] 왜 우린 이런거 못만드냐고... 송홍엽 2010.05.09 2964
84 [펀글] 교육의 의미 송홍엽 2008.02.19 2965
83 [펀글] 조선일보 1월2일 사설: 교육개혁 송홍엽 2008.01.03 2982
82 암호이야기 송홍엽 2008.05.21 3010
81 [펀글] 한반도 운하 건설을 반대하며 송홍엽 2008.02.20 3285
80 디지털 이야기... 송홍엽 2003.10.06 3342
79 [소고] 수학이란.... 송홍엽 2004.04.13 3411
78 [펀글-조선일보] 대중적인 책 내면 ‘이단아’ 취급 송홍엽 2006.09.18 3412
77 Re..랜덤변수의 variance가 0이면? 김태환 2005.07.30 3432
76 손바닥/손등 게임 송홍엽 2005.09.30 3446
75 유명한 퍼즐1 송홍엽 2004.04.01 3488
74 DMS와 정보량 송홍엽 2004.04.04 3531
73 [일반인을 위한 교양강좌] CDMA 통신기술 (2001.7) 송홍엽 2003.10.13 3575
72 [퍼온글]독도대첩 송홍엽 2005.03.15 3610
71 [교양상식] 정수와 암호 송홍엽 2004.04.13 3634
70 Golomb-Puzzle 2003.12 file 송홍엽 2004.04.02 3635