[CㆍC++로 배우는 자료구조론] 04 재귀호출 연습문제

26 

가. 1번

나. n이 1000일때부터 1일때까지 1000번 호출. 그리고 Pow2(x, 1)이 Pow2(x,0)까지 호출하기때문에 총 1001번.

다. 호출횟수는 

예를들면, n=32이거나 33일 경우 6번 호출. n=31이면 5번 호출.

27.

void Asterisk(int n)

{

if (n == 0) return;

printf("*");

Asterisk(n - 1);

}

28. 

void Func(int n)

{

if (n > 3600)

return;

printf("%d\n", n);

Func(2 * n);

printf("%d\n", n);

}

29.

void Func(int n)

{

if (n == 1)

printf(" %d", n);

else

{

Func(n - 1);

printf(" %d", n);

Func(n - 1);

}

}

30.

줄어들거나 늘어날 숫자 하나와, 

특정 숫자에서의 마무리. 즉 재귀하지 않는 것.

32. 

1

2

3

4

5

6

7

8

9

10

33. left는 p(=a[0])보다 큰걸 찾을때까지 증가

right는 작은걸 찾을때까지 감소

둘이 만나면 브레이크.

둘이 안만나면 멈출때의 left와 right인덱스에 있는 값을 바꾼다.

맨 마지막엔 a[0]와 right인덱스의 값을 바꾼다.

즉 왼쪽에는 a[0]보다 작은, 오른쪽엔 큰 숫자들로 나열한다.

가. 8 0 4 1 3 2 5 7 9 6

나. 4 0 6 1 7 2 5 3 8 9

다. 5 0 1 2 3 4 6 7 8 9                     

#include<stdio.h>

#define SIZE 10

void swap(int a[], int p1, int p2)

{

int temp = a[p1];

a[p1] = a[p2];

a[p2] = temp;

}

void Func(int n[])

{

int p = n[0];

int left = 1;

int right = SIZE - 1;

while (1)

{

while (left < right && n[left] <= p) left++;

while (left < right && n[right] >= p) right--;

if (left >= right) break;

swap(n, left++, right--);

}

swap(n, 0, right);

for (int i = 0; i < SIZE; i++)

printf("%d ", n[i]);

}

int main() {

int a[] = { 5,0,6,1,7,2,8,3,9,4 };

int b[] = { 8,0,6,1,7,2,5,3,9,4 };

int c[] = { 4,9,8,7,6,5,3,2,1,0 };

Func(c);

return 0;

}

35. Recurse(3*n + 1)은 n=2k+1 , 홀수라고 가정하면 6K + 3 + 1 = 2(3k+2) 가 되어 무조건 짝수가 된다.

이러면 if(n % 2 == 0)

Recurse( n / 2 ) ; 를 실행하는데 문제는 n이 0이 되어도 계속 실행이 된다.

따라서 If(n == 0) return; 을 맨 윗줄에 추가해줘야 한다.

36.

N/2

N%2