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

[Exercises 1]

/*

Horner's rule is a means for evaluating plynomial A(x)=anx^n+an-1x^n-1+...+a1x+a0 at a point x0 using a minimum number of multiplications.

Horner의 법칙은 주어진 점 x0에서 최소의 곱으로 다항식 A(x)를 계산하는 것입니다.

This rule is A(x)=(...(anx0+an-1)x0+...+a1)x0+a0

이 법칙은 위와 같습니다.

Write a C++ program to evaluate a polynomial using Horner's rule.

Horner의 법칙을 이용하여 다항식을 계산하는 C++ 프로그램을 작성합니다.

*/

#include <iostream>

using namespace std;

 

double horner(int size, int x, double *arr);

 

int main(void)

{

        double arr[] = { 1, 2, 3, 4 };

        int size, x=2;

        double result;

 

        size = sizeof(arr) / sizeof(double);

 

        result = horner(size, x, arr);

        cout << "결과: " << result << endl;

        return 0;

}

 

double horner(int n, int x, double *arr)

{

        double result = 0;

 

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

        {

               result = result*x + arr[(n - 1) - i]; //다항식 값 구하기

               cout << "f(" << i << ") =" << result << endl;

        }

        return result;

}

[Exercises 2]

/*

Given n Boolean variables x1, ...., xn we wish to print all possible combinations of truth values they can assume.

n개의 부울리안 변수 x1,....xn이 주어졌을 때, 이 변수들이 가질 수 있는 가능한 값의 조합을 모두 출력하고자 한다.

For instance, if n=2, there are four possibilites:true, true; true, false; false, true; false, false.

예를 들자면 n=2일 때 네가지의 조합이 있습니다: (참, 참); (참, 거짓); (거짓, 참); (거짓, 거짓)

Write C++ program to accomplish this and do a frequency count

이를 구하는 C++ 프로그램을 작성하고 빈도수 체크를 한다

*/

#include <iostream>

#include <cmath>

using namespace std;

 

void BoolComb(int *arr, int n);

 

int main(void)

{

        int n;

        int arr[100]; //충분히 크게

        cout << "참 거짓의 조합" << endl << endl;

        while (1)

        {

               cout << "n 값 입력:(1 이상) ";

               cin >> n;

               if (n <= 0)

                       return -1;

               BoolComb(arr, n);

        }

        return 0;

}

 

void BoolComb(int *arr, int n)

{

        int m = pow(2, n); //2^n

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

               arr[i] = i;

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

        {

               for (int j = n - 1; j >= 0; j--)

               {

                       int k = arr[i] >> j; //비트 연산

 

                       if (k & 1) ///8비트 모두 동일할 경우

                              cout << "참 ";

                       else

                              cout << "거짓 ";

               }

               cout << endl;

        }

}

 

[Exercises 3]

/*

trace the acition of the code

코드의 동작 하나하나를 확인한다

on the elements 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 searching for x=1, 3, 13, or 21

x가 1, 3, 13 또는 21인 경우를 n이 2, 4, 6, 8, 10, 12, 14, 16, 18, 20일 때 찾아본다

*/

#include <iostream>

using namespace std;

 

int main(void)

{

        int *a;

        for (int n = 2; n <= 20; n += 2) //2~20 사이 짝수일 때

        {

               a = new int[n];

               int i = 0;

               int j = n - 1;

               int x = 21; //x 값은 원하는 x 값으로 변환시키면 된다

               cout << "n: " << n << "\t" << "x: " << x << endl;

               int idx = 0;

               do

               {

                       int k = (i + j) / 2;

                       if (a[k] <= x)

                              i = k + 1;

                       else

                              j = k - 1;

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

                       cout << "i: " << i << " j: " << j << endl;

               } while (i <= j);

               delete[]a;

        }

        return 0;

}

[Exercises 4]

/*

Write a C++ program that prints out the integer values of x, y, and z in nondecreasing order.

x, y, z 값을 오름차순으로 출력하는 C++ 프로그램을 작성합니다

*/

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

 

void swap(int &x, int &y);

 

int main(void)

{

        int x, y, z;

        srand((unsigned)time(NULL)); //시드 설정

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

        {

               x = rand() % 9 + 1;

               y = rand() % 9 + 1;

               z = rand() % 9 + 1;

               cout << "기존의 x, y, z 값" << endl;

               cout << "x: " << x << " y: " << y << " z: " << z << endl;

               if (x > y)

                       swap(x, y);

               if (y > z)

                       swap(y, z);

               if (x > y)

                       swap(x, y);

               cout << "오름차순 후" << endl;

               cout << "x: " << x << " y: " << y << " z: " << z << endl;

        }

        return 0;

}

 

void swap(int &x, int &y)

{

        int temp = x;

        x = y;

        y = temp;

}

[Exercises 5]

/*

Write a C++ function that searches an unsorted array a[0::n-1] for the element x

정렬되어 있지 않은 배열 a(0부터 n-1 사이)에서 x를 찾는 C++ 함수를 작성하빈다.

If x occurs, then return the leftmost position of x in the array, else return -1

x를 찾는다면 0에 제일 가까운 인덱스를 반환하고 못 찾는다면 -1을 반환한다

*/

#include <iostream>

using namespace std;

 

int search(int *a, int n, int x);

 

int main(void)

{

        int x;

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

        cout << "배열에서 찾고 싶은 숫자: ";

        cin >> x;

        if (search(arr, sizeof(arr) / sizeof(int), x) != -1)

        {

               cout << "배열의 " << search(arr, sizeof(arr) / sizeof(int), x) << "번째 인덱스에 " << x << "가 존재한다" << endl;

        }

        else

        {

               cout << x << "는 존재하지 않는다" << endl;

        }

        return 0;

}

int search(int *a, int n, int x)

{

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

        {

               if (a[i] == x)

               {

                       return i; //0부터 n-1까지 찾는 과정이므로 제일먼저 나온 x가 0에서 제일 가까운 인덱스이다

               }

        }

        return -1; //못 찾을 경우

}

[Exercises 6]

/*

The factorial function n! has value 1 when n<=1 and value n*(n-1)! when n>1

팩토리얼 함수 n!은 n<=1일 경우 1의 값을 가지고 n>1일 경우 n*(n-1)! 값을 갖는다.

Write both a recursive and an iterative C++ function to compute n!

n! 함수를 작성하되 재귀함수와 비재귀 함수 둘다 작성합니다

*/

#include <iostream>

using namespace std;

 

int recurFactorial(int n); //recursive 재귀

int iterFactorial(int n); //iterative 비재귀

 

int main(void)

{

        int n;

        cout << "n 값 입력: ";

        cin >> n;

        cout << "재귀함수 값: " << recurFactorial(n) << endl;

        cout << "비재귀함수 값: " << iterFactorial(n) << endl;

        cout << "똑같은 결과가 나옴을 확인할 수 있습니다" << endl;

        return 0;

}

 

int recurFactorial(int n)

{

        if (n == 1)

               return 1;

        else

               return n*recurFactorial(n - 1);

}

 

int iterFactorial(int n)

{

        int Multiply = 1;

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

               Multiply *= i;

        return Multiply;

}

[Exercises 7]

/*

The Fibonacci numbers are defined as::f0=0, f1=1, and f(i)=f(i-1)+f(i-2) for i>1

피보나치 숫자는 i>1일 때 f(0)=0, f(1)=1, 그리고 f(i)=f(i-1)+f(i-2)라고 정의되어있다

Wrte both a recursve and an iterative C++ function to compute f

피보나치 수열도 전 문제와 마찬가지로 재귀와 비재귀 함수로 작성해본다

*/

#include <iostream>

using namespace std;

 

int recurFibonnaci(int n);

int iterFibonnaci(int n);

 

int main(void)

{

        int n;

        cout << "몇번째의 피보나치 수열을 확인하고 싶으십니까?";

        cin >> n;

        cout << "재귀함수 결과: " << recurFibonnaci(n) << endl;

        cout << "비재귀함수 결과: " << iterFibonnaci(n) << endl;

        cout << "결과가 같음을 확인할 수 있습니다" << endl;

        return 0;

}

 

int recurFibonnaci(int n)

{

        if (n == 0 || n == 1)

               return n;

        else

               return recurFibonnaci(n - 2) + recurFibonnaci(n - 1);

}

 

int iterFibonnaci(int n)

{

        int f1, f2, f3;

 

        f1 = 0;

        f2 = 1;

 

        if (n == 0)

               return f1;

        else if (n == 1)

               return f2;

        else

        {

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

               {

                       f3 = f1 + f2;

                       f1 = f2; //f1의 값에 f2의 값을

                       f2 = f3; //f2의 값에 f3의 값을

               }

        }

        return f3;

}

 

[Exercises 8]

/*

Write a recursive function for computing the binomial coeffiecient [n m] as defiend in Section 1.5.2, where [n 0]=[n n]=1.

섹션 1.5.2에서 [n 0]=[n n]=1이라고 정의되어있는 이항 게수 [n m]을 계산하는 재귀함수를 작성한다

*/

#include <iostream>

using namespace std;

 

int recurBinomial(int n, int m);

 

int main(void)

{

        int m, n;

        int result;

 

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

        cin >> n >> m;

        if (m < 0 || n < 0)

               return -1;

 

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

        return 0;

}

 

int recurBinomial(int n, int m) //결국 이항 계수는 조합(Combination) 값이다

{

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

               return 1; //섹션 1.5.2 정의

        else

               return (recurBinomial(n - 1, m - 1) + recurBinomial(n - 1, m));

}

[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://www.quora.com/How-can-I-print-all-possible-boolean-combinations-of-n-variables-in-C++

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

*2번 문제는 링크를 참고해서 작성했습니다