Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

덴치 문제..푼 결과

2005.10.11 10:56

박기현 조회 수:4564 추천: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 9003
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 5973
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 6881
49 Re.. Turbo code Decoder file 송홍엽 2004.04.13 4240
48 퍼즐에 상금을 부여합니다...^^ 송홍엽 2004.04.15 4257
47 Re..Turbo code Encoder file 송홍엽 2004.04.13 4346
46 2000년에 어딘가에 올린 글입니다.."열정" 송홍엽 2004.04.15 4422
45 오늘같은 날 송홍엽 2004.10.11 4434
44 combinatorial search problem file 송홍엽 2004.07.21 4499
43 marginally Gaussian but not jointly Gaussian 송홍엽 2004.05.13 4544
» 덴치 문제..푼 결과 [1] 박기현 2005.10.11 4564
41 [퍼온글]과학자들은 왜 속이는가 송홍엽 2006.02.07 4627
40 랜덤변수의 variance가 0이면? 송홍엽 2004.05.13 4630
39 정보화와 정보이론 송홍엽 2004.08.06 4634
38 uncorrelated but not independent 송홍엽 2004.05.13 4724
37 채널코딩에 관한 첫번째 이야기 송홍엽 2003.10.13 4761
36 수학자와 공학자 송홍엽 2006.05.09 4763
35 지금 내 전공분야는 공부한던 시절엔 나에게 가장 힘든 분야였답니다... 송홍엽 2003.06.03 4872
34 채널코딩 세째 이야기 송홍엽 2003.11.13 4992
33 [펀글] 프로그램 설계시 좋은 코딩 습관 송홍엽 2009.12.27 5115
32 오류정정부호에 대한 이야기 송홍엽 2004.04.13 5119
31 [퍼온글] 달력의 유래 송홍엽 2004.04.01 5189
30 [퍼온글] 명왕성 이야기 송홍엽 2006.04.26 5380