C++ Fundamentals of Data Structures(C++ 자료구조론) 1.5 연습문제 9~15

[Exercises 9]

/*

Write an iterative function to compute a binomial coefficient;

이번에는 이항계수를 구하는 비재귀 함수를 작성합니다

then transform it into an equivalent recursive function

비재귀 함수를 작성한 다음에는 똑같은 결과를 출력하는 재귀함수로 변환하시오(이건 8번 문제이므로 작성 X)

*/

#include <iostream>

using namespace std;

 

int iterBinomial(int n, int m);

 

int arr[10][10]; //전역 이차원배열

//배열을 동적할당하는 방법도 생각해봤지만 상당히 복잡해질 것이라고 예상되어 이렇게 선언했습니다.

 

int main(void)

{

        int m, n;

 

        cout << "n과 m 값 입력: ";

        cin >> n >> m;

        if (m < 0 || n < 0)

               return -1;

 

        cout << "결과 값: " << iterBinomial(n, m) << endl;

        return 0;

}

 

int iterBinomial(int n, int m)

{

        int i, j;

        for (i = 0; i <= n; i++)

        {

               for (j = 0; j <= m; j++)

               {

                       if (i == j || j == 0) //[n 0]=1, [n n]=1

                              arr[i][j] = 1;

                       else

                              arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];

               }

        }

        return arr[n][m];

}

 

[Exercises 10]

/*

Ackermann's function A(m,n) is defined as follows

Ackermann의 함수 A(m, n)은 아래와 같이 정의되어있다

This function is studied because it grows very fast for small values of m and n

이 함수는 작은 값을 지니고 있는 m과 n이 빠르게 커지기 때문에 연구되고 있다.

Write a recursive function for computing this function.

이 함수를 재귀함수로 작성해본다.

*/

#include <iostream>

using namespace std;

 

int recurAckermann(int m, int n);

 

int main(void)

{

        int m, n;

 

        cout << "m, n 값 입력:(둘 다 양수) ";

        cin >> m >> n;

        if (m <= 0 || n <= 0)

               return -1;

        cout << "결과 값: " << recurAckermann(m, n) << endl;

        return 0;

}

 

int recurAckermann(int m, int n)

{

        static int idx = 0;

        cout << ++idx << "번째 시도: " << endl;

        if (m == 0)

               return n + 1;

        else if (n == 0)

               return recurAckermann(m - 1, 1);

        else

               return recurAckermann(m - 1, recurAckermann(m, n - 1));

}

[상당히 성능이 안 좋은 것을 확인할 수 있는 부분이다]

[Exercises 11]

/*

The pigeonhole principle states that if a function f has n distinct inputs but less than n distinct outputs,

pigeonhole 원칙이란 함수 f가 n개의 상이한 입력에 대해 n개보다 작은 상이한 출력이 나온다면

then there exist two inputs a and b such that a!=b and f(a)=f(b).

a!=b이고 f(a)=f(b)인 두 개의 입력 a, b가 존재한다는 것이다.

Write a program to find the values a and b for which the range values are equal.

이와 같이 입력값이 다르면서 함수값이 같은 a, b를 찾는 프로그램을 작성한다

*/

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

 

int search(int result, int n);

 

int before[20]; //저번에 구해놓은 숫자

int now[20]; //지금 구한 숫자

 

int main(void)

{

        int equal; //같은 함수값이 있는지 확인

        int num; //무작위로 생성하는 입력값

        int cnt = 0;

        int val, result; //val: 같은 함수값을 갖는 이전 숫자

 

        srand((unsigned)time(NULL)); //시드값

        while (cnt < 20)

        {

               equal = 0;

               num = rand() % 10;

 

               //같은 값이 있는지 확인

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

               {

                       if (now[i] == num)

                       {

                              equal = 1; //중복이라면

                              break;

                       }

               }

               if (equal)

                       continue;

               result = num*num - 4 * num + 3; //함수 설정(근이 두개 이상인 함수 설정해야함)

 

               if ((val = search(result, cnt)) == -1)

               {

                       before[cnt] = result;

                       now[cnt++] = num;

               }

               else

               {

                       cout << cnt << "번째 시도" << endl;

                       cout << "a= " << val << " b= " << num << endl;

                       break;

               }

        }

        return 0;

}

 

int search(int result, int n)

{

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

               if (result == before[i])

                       return now[i];

        return -1;

}

[Exercises 12]

/*

Given n, a positive integer, determine if n is the sum of all divisors

양의 정수 n에 대해 n이 자신의 모든 제수들의 합인지 알아낸다.

if n is the sum of all t such that 1<=t<n, and t divides n

t의 범위는 1<=t<n이고 n의 제수가 되는 모든 t의 합인지를 검사한다.

*/

#include <iostream>

using namespace std;

 

int SumOfT(int n);

 

int main(void)

{

        int n;

        cout << "n 값 입력:(양수) ";

        cin >> n;

        if (n <= 0)

               return -1;

 

        if (n == SumOfT(n))

               cout << n << "은 모든 제수들의 합이다" << endl;

        else

               cout << n << "은 모든 제수들의 합이 아니다" << endl;

        return 0;

}

 

int SumOfT(int n)

{

        int sum = 0;

 

        for (int i = 1; i <= n / 2; i++) //n/2가 최대 제수

        {

               if ((n % i) == 0)

               {

                       cout << "현재 t: " << i << endl;

                       sum += i;

               }

        }

        return sum;

}

[Exercises 13]

/*

Consider the function F(x) defined by

함수 F(x)를 확인한다

if(x is even) F=x/2; //짝수일 경우

else F=F(F(3x+1)); //홀수일 경우

Prove that F(x) terminates for all integers x

F(x) 함수가 모든 변수 x에 대하여 정상 종료가 되는 것을 증명한다.

*/

k=0일 경우

(2i+1)2^0-1은 짝수이기 때문에 정상종료된다

 

k>0이고 ((2i+1)2^k-1)이 홀수일 경우

F((2i + 1)2 ^ k - 1)

= F(F(3((2i + 1)2 ^ k - 1) + 1))

= F(F(3(2i + 1)2 ^ k - 2)) //k>0이므로 3(2i + 1)2 ^ k - 2는 짝수

= F((3(2i + 1)2 ^ k - 2) / 2) //짝수를 2로 나누었으니 또한 짝수

= F(((6i + 3)2 ^ k - 2) / 2)

= F((2(3i + 1) + 1)2 ^ {k - 1}-1) //((2i+1)2^k-1)보다 작은 k-1이 계수이므로 정상 종료가 된다

[14번 문제]

/*

If S is a set of n elements, the powerset of S is the set of all possible subsets of S

S가 n의 원소로 이루어진 집합인 경우, S의 멱집합은 모든 S의 부분집합으로 이루어져있다.

For example, if S=(a, b, c), then powerset (S)={(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)}.

예를 들어, S=(a, b, c)일 경우 멱집합은 (S)={(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)}이다

Write a recursive function to compute powerset(S)

멱집합을 출력하도록 재귀함수를 작성한다

*/

#include <iostream>

using namespace std;

 

void powerset(char *S, char bit);

 

int main(void)

{

        char S[3] = { 'a', 'b', 'c' };

        char bit = 1; //bit연산을 위해

        cout << "멱집합 출력" << endl;

        cout << "{";

        powerset(S, bit);

        cout << "}" << endl;

        return 0;

}

 

void powerset(char *S, char bit)

{

        cout << "(";

 

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

        {

               if (bit&(1 << i)) //2번 문제와 유사하다

                       cout << S[i] << " ";

        }

 

        cout << "), ";

 

        bit++;

        if (bit == 8) //2^3

        {

               cout << "()"; //공집합

               return;

        }

 

        powerset(S, bit);

}

[Exercises 15]

/*

There are three towers and sixty-four disks of different diameters placed on the first tower

세개의 타워가 있고 각각 크기가 다른 64개의 디스크가 첫번째 타워에 위치하고 있다.

The disks are in order of decreasing diameter as one scans up the tower

디스크들은 위로 올라갈수록 작아지는 순서로 배치되어있다.

Monks were supposed to move the disks from tower 1 to tower 3 obeying the following rules

스님들은 다음의 규칙을 지키며 모든 디스크들을 첫번째 타워에서 세번째 타워로 옮겨야했다.

(a) only one disk can be moved at any time and

(a) 한번에 한개씩의 디스크만 움직일 수 있다

(b) no disk can be placed on top of disk with smaller diameter

(b) 현재 디스크보다 작은 디스크 위로 디스크를 배치할 수 없습니다.

Write a recursive function that prints the sequence of moves that accomplish this task

이러한 움직임을 출력하는 재귀 함수를 작성한다

*/

#include <iostream>

using namespace std;

 

void HanoiTowerMove(int num, char from, char by, char to);

 

int main(void)

{

        int num;

        cout << "디스크는 몇개인가?";

        cin >> num;

        HanoiTowerMove(num, 'A', 'B', 'C'); // A B C는 기둥을 나타냄

        return 0;

}

 

void HanoiTowerMove(int num, char from, char by, char to)

{

        if (num == 1) //이동할 원반의 수가 1개라면

        {

               printf("원반 1을 %c에서 %c로 이동 \n", from, to);

        }

        else

        {

               HanoiTowerMove(num - 1, from, to, by); //A에서 C로 이동 후 B로 간다

               printf("원반 %d을(를) %c에서 %c로 이동 \n", num, from, to);

               HanoiTowerMove(num - 1, by, from, to); //B에서 A로 이동 후 C로 간다

        }

}

[64개로 할 경우 너무나도 많은 이동이 있기 때문에 5개로 줄였습니다]

[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://stackoverflow.com/questions/36513592/proof-that-a-function-terminates

*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.

*13번 문제는 링크를 참고해서 증명했습니다

*15번 문제는 예전에 윤성우 저 자료구조 책을 공부했을 때 하노이타워를 이미 공부했었기 때문에 코드를 그대로 가져왔습니다.