함수 (4)

(1)

함수 (4)

Chan-Su Shin

(2)

예제 (5) Hanoi 탑

"64개의 원판을 하나씩 옮겨서 세번째 기둥 위에 원래 상태대로 옮겨 놓되, 옮기는 과정에서 절대로 큰 원판이 작은 원판 위에 놓이지 않도록 하여라. 모든 원판이 옮겨지면 세상은 종말이 올 것이며, 충실한 자는 상을 받을 것이고 불충실한 자는 벌을 받을 것이다"

(3)

예제 (5) Hanoi 탑

• T(n) : n개의 원반을 규칙에 맞게 다른 막대로 옮기는 데 필요한 최소

이동 횟수

• T(64) = T(63) + 1 + T(63) = 2 * T(63) + 1

(4)

예제 (5) Hanoi 탑

• T(n) = 2 * T(n-1) + 1

• T(1) = 1

• T(2) = 2 * T(2-1) + 1 = 2 * T(1) + 1 = 3

• T(3) = 2 * T(3-1) + 1 = 2 * 3 + 1 = 7

(5)

예제 (5) Hanoi 탑

• T(n) = 2 * T(n-1) + 1

• T(1) = 1

• T(n) + 1 = 2 * T(n-1) + 2 = 2 * (T(n-1) + 1)

• S(n) = T(n) + 1 이라고 가정

• S(n) = 2 * S(n-1)

• S(1) = T(1) + 1 = 2

• 수열 S(n)은 초항이 2이고 공비가 2인 등비수열이 된다.

• 그러면

S(n) = 초항 * (공비)^n-1= 2 * 2^n-1 = 2ⁿ T(n) = S(n) – 1 = 2ⁿ - 1

(6)

예제 (5) Hanoi 탑

• 그러면 64개의 원반을 옮기기 위해선, 2⁶⁴ – 1번 옮겨야 한다.

• 하나의 원반을 옮기는 데, 1초가 걸린다고 가정하면

2⁶⁴ – 1 = 18446744073709551615(초)가 걸린다

• 계산하면 584,942,417,400 년이 소요된다.

• Just do it!

click here

(7)

예제 (5) Hanoi 탑

A C

B

(8)

Hanoi 탑

• A, B, C 세개의 막대가 있다고 가정한다.

• A 막대에 있는 n개의 원판을 C 막대로 옮긴다고 하자.

• (1) (n-1)개의 원판을 A 막대에서 B 막대로 옮긴다.

• (2) 가장 큰 원판 하나를 A 막대에서 C 막대로 옮긴다.

• (3) B 막대에 있는 (n-1)개의 원판을 C 막대로 옮긴다.

A B C

(9)

Hanoi program

• move (int, char, char, char) 함수를 만든다.

• move( k, ‘A’, ‘B’, ‘C ); 라고 호출하면

– ‘A’ 막대에 있는 크기가 가장 작은 k개의 원판을 ‘C’ 막대로 옮긴다.

– 여기서 ‘B’ 막대는 원판을 이동할 때 중간에 이용되는 막대임을 나타낸다.

• 만약, move( k, ‘A’, ‘C’, ‘B’ ); 라고 호출하면?

• 만약, move( k, ‘B’, ‘A’, ‘C’ ); 라고 호출하면?

• 만약, move ( 1, ‘B’, ‘A’, ‘C’ ); 라고 호출하면?

(10)

Hanoi 탑

• move ( 64, ‘A’, ‘B’, ‘C’ );

– (1) move( 63, ‘A’, ‘C’, ‘B’ );

– (2) move( 1, ‘A’, ‘B’, ‘C’ );  printf(“ move 1 disk from ‘A’ to ‘C’ \n”);

– (3) move( 63, ‘B’, ‘A’, ‘C’ );

A B C A C C

B

(11)

Hanoi program

void move(int n, char a, char b, char c) {

move( n-1, a, c, b );

move( 1, a, b, c );

move( n-1, b, a, c );

}

• move ( 3, ‘A’, ‘B’, ‘C’ ); 이라고 호출했다면?

(12)

Hanoi program

void move(int n, char a, char b, char c) {

if ( n == 1 )

printf(“ move disk from %c to %c\n”, a, c );

else {

move( n-1, a, c, b );

move( 1, a, b, c );

move( n-1, b, a, c );

} }

• move ( 3, ‘A’, ‘B’, ‘C’ );

이라고 호출했다면?

(13)

Hanoi program

int main(void) {

int n;

scanf(“%d”, &n);

move( n, ‘A’, ‘B’, ‘C’ );

return 0;

}

(14)

마지막 예제: 숫자 탐색

• 1, 4, 5, 10, 21, 39, 55, 70, 86, 92, 100, 241

• 위에서처럼 작은 수부터 큰 수로 정렬된 숫자들이 있다.

– 오름차순

• 임의의 자연수 x가 주어질 때, x 가 위의 숫자들 중에 있는지 없는지

판별하고, 있다면 몇 번째 숫자인지 출력하라.

• 예

– 9 – 240 – 100

(15)

마지막 예제: 숫자 탐색 – 92를 찾아라!

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 1, 4, 5, 10, 21, 39, 55, 70, 86, 92, 100, 241

1, 4, 5, 10, 21, 39, 55, 70, 86, 92, 100, 241

(16)

마지막 예제: 숫자 탐색 – 90를 찾아라!

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 1, 4, 5, 10, 21, 39, 55, 70, 86, 92, 100, 241

1, 4, 5, 10, 21, 39, 55, 70, 86, 92, 100, 241

(17)

마지막 예제: 숫자 탐색

int search( int from, int to, int x ) {

int a;

if (from > to) return 0;

a = (from + to)/2;

if ( x > a번째 숫자 )

return search( a+1, to, x );

else if ( x < a번째 숫자 )

return search ( from, a-1, x );

else

return a;

}