Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

덴치 문제..푼 결과

2005.10.11 10:56

박기현 조회 수:4521 추천: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 8438
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 5821
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 5785
» 덴치 문제..푼 결과 [1] 박기현 2005.10.11 4521
48 marginally Gaussian but not jointly Gaussian 송홍엽 2004.05.13 4500
47 combinatorial search problem file 송홍엽 2004.07.21 4455
46 채널코딩에 관한 첫번째 이야기 송홍엽 2003.10.13 4411
45 오늘같은 날 송홍엽 2004.10.11 4407
44 2000년에 어딘가에 올린 글입니다.."열정" 송홍엽 2004.04.15 4361
43 Re..Turbo code Encoder file 송홍엽 2004.04.13 4299
42 퍼즐에 상금을 부여합니다...^^ 송홍엽 2004.04.15 4202
41 Re.. Turbo code Decoder file 송홍엽 2004.04.13 4189
40 퍼온글 -- 계산이 이상해요... 송홍엽 2004.10.21 4176
39 수학사 바로잡기 (3) - 월간 과학동아 2008년 7월호 강석기 기자의 글 송홍엽 2008.06.20 4160
38 학위논문작성시 주의점 송홍엽 2006.09.24 4043
37 퍼즐 4 송홍엽 2004.04.15 3983
36 [퍼온글] 해석학적 극한의 의미 송홍엽 2008.12.18 3899
35 퍼온글 - 수학계 동향 (2000) 송홍엽 2004.10.21 3875
34 [퍼온글] 명왕성 이야기 송홍엽 2007.05.23 3868
33 [퍼온글] FM방식 개발한 암스트롱 송홍엽 2008.09.24 3817
32 퍼즐 3 송홍엽 2004.04.15 3771
31 우리학부 전공 2-3학년생에 대한 조언 송홍엽 2008.05.22 3756
30 움직이는 글자 태그 송홍엽 2008.09.04 3756