- PDF 무료 다운로드

Size: px

Start display at page:

Download ""

재량 망절
4 years ago
Views:

2 예제 1.1 (MATLAB m-file pnk.m) function val = pnk(n,k) k-permutation from n-set P(n,k) = n (n-1) (n-2)... (n-k+1) if (k > n) val = NaN; disp('invalid input: Check if k > n') return val = 1; for i = n-k+1:n; val = val * i;

3 예제 1.2 (combinatorial explosion) A. 알파벳의대문자 26 개를길이 (length) 가 7 인이진수열 (binary sequences) 로기호화하는데얼마나많은경우가존재하는가? ( 풀이 ) 길이가 7 인 2 7 =128 개의이진수열 (binary sequence) 이존재한다. 따라서 A, B,, Z 의 26 개문자에대한표현은 P(2 7 =128,26) 개중에서선택된다. >> pnk(2^7,26) ans = e+053 B. a, b, c, e, i, n, r, s, t, u 각각을정확히한번만사용한단어가존재하는지조사하려고한다. 10 개의글자에대한모든가능한 permutation 을일반화하고그것을사전에서찾는데 1 밀리세컨드 (1/1000 초 ) 가걸린다고가정하자. 그렇다면이프로그램으로모든순열을체크하는데얼마나오래걸리겠는가? ( 풀이 ) n 개의글자에대한 P(n, n)=n! 개의순열이존재하므로실행시간은 >> pnk(10,10) *.001 Running time in Second ans = e+003 >> ans / 60 Running time in Minutes ans = 예제 1.3 (MATLAB m-file cnk.m) function val = cnk(n,k)

4 k-combination from n-set C(n,k) = n (n-1) (n-2)... (n-k+1) / k (k-1)... 1 = (n-k+1)/1 (n-k+2)/2... (n-k+k)/k C(n,k) = C(n,n-k) : Useful formula when k > n/2 if (k > n) val = NaN; disp('invalid input: Check if k > n') return elseif ( k > n/2 ) k = n - k; val = 1; for i = 1:k val = val * (n-k+i)/i; 예제 1.4 ( 조합경우의수 ) 한중국식당은디너스페셜 (dinner special) 의일부분으로 8 개의메인요리 (main dishes) 중정확히두가지를주문하도록하고있다. 그렇다면주문할수있는메인요리는얼마나많은다른조합 (combination) 이있는가? >> cnk(8,2) ans = 28

5 예제 1.6 ( 파스칼의삼각수, pastree.m) function val = pastree(n, print) Generating pascal's combinatorial triangle if print is defined and equals to 1, print the complete triangle n = 0 : [1] n = 1 : [1 1] n = 2 : [1 2 1] n = 3 : [ ] C(n+1,k+1) = C(n,k) + C(n,k+1) if ( nargin == 1 ) print = 0;

6 val = [1]; for i=1:n val = [0 val] + [val 0]; if (print==1); fprintf(1,'3d:',i); disp(val) >> pastree(5,1); : 1 1 2: : : : 예제 2.1 (k-samples) 컴퓨터는 n 개의이진숫자 (binary digits) 로정수를표현하는데, 부호 (sign) 를

7 나타내기위해 1 비트 (bit) 를사용하고정수의크기를나타내기위해서 n-1 비트를사용한다. 이것을정수의부호 - 크기표현 (sign-magnitude representation of integers) 이라고부른다. 이러한표시로얼마나많이다른정수들을표시할수있는가? ( 풀이 ) n 개의채워야할칸 (slot) 이존재한다고생각할수있고이때각각의칸을채우는경우에는두가지방법이있으므로총 2ⁿ 의다른비트방식이존재한다는것을알수있다. 그러나, 여기엔 +0 과 -0 이모두포함되어있으므로우리가원하는답은 2ⁿ-1 이됨을쉽게알수있다. 예제 2.3 (MATLAB m-file hnk1.m) 네개의주사위를던져졌을때, 얼마나다른경우의가능한결과가나오겠는가? (( 답 )) 예를들어첫번째주사위가 4 가나오고나머지세개가 2 가나온경우나처음세개의주사위에서 2 가나오고마지막에 4 가나온경우는같은경우이므로순서에상관하지않는다. 또한모두가같은값을가질수있기때문에반복 (repetition) 이허락된다. 따라서이것은집합 {1, 2, 3, 4, 5, 6} 으로부터의 4-selections 이므로 function val = hnk1(n,k)

8 k-selection from n-set H(n,k) = 1 if n=1 H(n+1,k) = 1 + H(n,1) H(n,k) val = 1; if n==1; return; for i=1:k; val = val + hnk1(n-1, i); >> val=hnk1(6,4) val = 126 개의가능한경우가있다. 126 >> tic; val=spnk1(10,15), toc val = Elapsed time is seconds. 연산에소요된시간은약 3.5 초이다. 예제 2.5 (MATLAB m-file Hnk.m) function val = hnk(n,k) k-slection from n-set H(n,k) = C(n+k-1, k) = C(n+k-1, n-1) : Useful formula when k > n-1 cn = n+k-1; ck = k; if ( k > n-1 ) ck = n-1;

9 val = 1; for i = 1:ck; val = val * (cn-ck+i)/i; >> val=hnk(6,4) val = 예제 2.4 의결과와같은값을가진다. 126 >> tic; val=hnk(10,15), toc val = Elapsed time is seconds. 연산에소요된시간은천분의 2.3 초이다.

10 예제 3.2 ( 중복원소의패턴 ) 3 개의사각형과 2 개의삼각형과 4 개의원을가진퍼즐이있다. 한줄로이 9 개를배열해서형성할수있는얼마나많은패턴이있는가? function val = ptn(n) ptn(n) = number of patterns from repeated set ptn(n) = sum(n)! / n(1)! n(2)!... n(length(n))! = 1...n(1)/1...n(1)... (n(1)+1)...(n(1)+n(2))/1...n(2)... (n(1)+...+n(r-1)+1)...(n(1)+...+n(r))/1...n(r) r = length(n); ns = sort(n); ns = ns(r:-1:1); counter=ns(1); val = 1; for k = 2:r; for i = 1:ns(k); counter = counter+1; val = val * counter/i; >> ptn( [2 3 4] ) ans = 1260

11 예제 3.3 ( 중복원소의분할 ) function val = part(n) part(n) = number of partition to make r-subsets with n(1),...,n(r) elements where n(k1)=n(k1+1)=...=n(k1+r1),..., n(kp)=...=n(kp+rp) part(n) = C(n(1)+...+n(r),n(1))... C(n(k1)+.+n(r),n(k1))...C(n(k1+r1)+.+n(r),n(k1+r1)) / r1!... C(n(kp)+.+n(r),n(kp))...C(n(kp+rp)+.+n(r),n(kp+rp)) / rp!... C(n(r),n(r)) r = length(n); elements = sum(n); ns = sort(n); rp = 1; val = 1; for k = 1:r; val = val * cnk(elements, ns(k)); elements = elements - ns(k); if (k==r) val = val / pnk(rp,rp); elseif (ns(k)~=ns(k+1)) val = val / pnk(rp,rp); rp = 1; else rp = rp + 1;

12 >> part([3 2 2]) ans = 105 예제 3.5 (k- 부분집합으로의분할 ) 5 개의집합을가진원소를 3 개의블록으로분할하는데얼마나많은방법이존재하는가? ( 풀이 ) 정리 3.3 에의해 S(5,3) = 3S(4,3) + S(4,2). 이때, 정리 3.3 의 2 번에의해, S(4,3) = 3S(3,3) + S(3,2) S(4,2) = 2S(3,2) + S(3,1) S(3,2) = 2S(2,2) + S(2,1). 정리 3.3 의 1 번에의해, S(2,1) = S(3,1) = 1 이고 S(3,3) = 1, S(2,2) = 1. 따라서, S(4,3) = 3*1 + (2*1 + 1) = 6 이고 S(4,2) = 2*(2*1 + 1) + 1 = 7. 그러므로 S(5,3) = 3*6+7 = 25. function val = snk(n,k)

13 k-slection from n-set S(1,1) = S(n,n) = 1 if n=1 S(n,k) = k S(n-1,k) + S(n-1,k-1), 1 <= k < n val = 1; if n>k & k>1; val = k*snk(n-1,k) + snk(n-1,k-1); >> snk(5,3) ans = 25

15 list=[]; for i=1:4 for j=1:4 for k=1:4 list = [list; i*100+j*10+k]; list disp(['samples: Total ' int2str(length(list)) ' Elements listed'])

16 list=[]; for i=1:4 for j=i:4 for k=j:4 list = [list; i*100+j*10+k]; list disp(['selections: Total ' int2str(length(list)) ' Elements listed']) list=[]; for i=1:4 for j=1:4 for k=1:4 if (i~=j & i~=k & j~=k) list = [list; i*100+j*10+k]; list disp(['permutations: Total ' int2str(length(list)) ' Elements listed']) list=[]; for i=1:4 for j=i+1:4 for k=j+1:4 list = [list; i*100+j*10+k]; list disp(['combinations: Total ' int2str(length(list)) ' Elements listed'])

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = 1 2 3 4 5 6 7 8 9 B = 8 7 6 5 4 3 2 1 0 >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = 0 0 0 0 1 1 1 1 1 >> tf = (A==B) % A 의원소와 B 의원소가똑같은경우를찾을때 tf = 0 0 0 0 0 0 0 0 0 >> tf