C++ Fundamentals of Data Structures(C++ 자료구조론) 1.7 연습문제

[Exercises 1]

/*

Compare the two functions n^2 and 2^n/4 for various values of n.

2^n 함수와 2^n/4의 함수에 다양한 n을 대입하며 비교한다.

Determine when the second becomes larger than the first.

2^n/4가 n^2보다 커지는 구간을 찾는다.

*/

#include <iostream>

using namespace std;

 

int f(int n);

int g(int n);

 

int main(void)

{

        cout << "n" << "\t" << "f(n)" << "\t" << "g(n)" << endl;

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

        {

               cout << i << "\t" << f(i) << "\t" << g(i) << endl; //9부터 (2^n)/4가 크다

        }

        return 0;

}

 

int f(int n)

{

        return n*n;

}

 

int g(int n)

{

        int res = 1;

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

               res *= 2;

        return res/4;

}

[Exercises 2]

/*

Prove by induction

귀납법을 이용하여 증명한다

*/

(a)Σi = n(n + 1) / 2, n >= 1

 

->

S = n + (n - 1) + ... + 2 + 1

S = 1 + 2 + ... + (n - 1) + n

두 S를 더하면

2S = (n + 1) + (n + 1) + ... + (n + 1) + (n + 1) = n(n + 1)

즉, S = (n)(n + 1) / 2

 

(b)Σi ^ 2 = n(n + 1)(2n + 1) / 6, n >= 1

 

->

n = 1일 경우(1 / 6)(2)(3) = 1

n = k일 경우(k / 6)(k + 1)(2k + 1)

n = k + 1일 경우(k / 6)(k + 1)(2k + 1) / 6 + (k + 1) ^ 2 라고 가정

6으로 통분{ k(k + 1)(2k + 1) + 6(k + 1) ^ 2 } / 6

(k + 1)로 묶으면(k + 1)(k(2k + 1) + 6(k + 1)) / 6

이를 인수분해하면(k + 1)(k + 2)(2k + 3) / 6 즉(k + 1) { (k + 1) + 1 } {2(k + 1) + 1} / 6

 

c)Σx^i = (x ^ (n + 1) - 1) / (x - 1), x != 1, n >= 0

 

->

Σx^i = (1 - x ^ (n + 1)) / (1 - x)

n = 0일 경우(1 - x) / (1 - x) = 1

n = k일 경우(1 - x ^ (k + 1)) / (1 - x)

n = k + 1일 경우(1 - x ^ ((k + 1) + 1)) / (1 - x) 즉, (1 - x ^ (k + 2)) / (1 - x) 라고 가정

Σx^i + x^k + 1 = (1 - x ^ (k + 1)) / (1 - x) + x ^ (k + 1) = (1 - x ^ (k + 1)) / (1 - x) + ((x ^ (k + 1))(1 - x)) / (1 - x) = (1 - x ^ (n + 1) + x ^ (n + 1)(1 - x)) / (1 - x)

= (1 - x ^ (n + 1) + x ^ (n + 1) - x ^ (n + 2)) / (1 - x) = (1 - x ^ (n + 2)) / (1 - x)

[Exercises 3]

/*

Determine the frequency counts for all statements in the following two program segments

다음 두 프로그램의 모든 코드의 실행 빈도수를 찾는다

*/

(a)

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

        for (j = 1; j <= i; j++)

               for (k = 1; k <= j; k++)

                       x++;

 

->

Σ(Σ(Σ1)))

=1 / 6(n)(n + 1)(n + 2)

즉, O(n ^ 3)

 

(b)

i = 1;

while (i <= n)

{

        x++;

        i++;

}

 

->

while문에서 i만 n까지 증가하면 되므로

O(n)

 

[8번 문제]

/*

Show that the following equalities are correct

다음의 식들이 맞는지 증명한다

*/

(a) 5n^2-6n=Theta(n^2)

 

-> 4n^2<=(5n^2-6n)<=5n^2 즉, n>=6일 때, 5n^2-6n=Theta(n^2)

 

(b) n!=O(n^2)

 

-> cn^n-n!=n(cn^(n-1)-(n-1)!)>=0

즉 c=1, n=1 일 때 성립

 

(c) 2n^2+nlogn=Theta(n^2)

 

-> cn^2-2n^2-nlogn=n(n(c-2)-logn)>=0

즉 c=3, n=1일 때 성립

n(n(c-2)-logn)<=0

즉, c=1, n=1일 때 성립

 

(d) Σi^2=Theta(n^3)

 

->

Σi^2=(n)(n+1)(2n+1)/6=1/6(2n^3+3n^2+n)

cn^3-(2n^3+3n^2+n)/6>=0

즉, c=1 n=1일 때 성립

cn^3-(2n^3+3n^2+n)/6<=0

즉, c=1, n=1일 때 성립

 

(e) Σi^3=Theta(n^4)

 

->

Σi^3=(n^2+n)^2/4=(n^4+2n^3+n^2)/4

cn^4-(n^4+2n^3+n^2)/4>=0

즉, c=1 n=1일 때 성립

cn^4-(n^4+2n^3+n^2)/4<=0

즉, c=1/4, n=1일 때 성립

 

(f) n^2n+6*2^n=Theta(n^2n)

 

->

cn^2n-(n^2n+6*2^n)=n^2n(c-1)-6*2^n>=0

즉, c=2 n=3일 때 성립

cn^2n-(n^2n+6*2^n)=n^2n(c-1)-6*2^n<=0

즉, c=1 n=3일 때 성립

 

(g) n^3+10^6n^2=Theta(n^3)

 

->

cn^3-(n^3+10^6n^2)=n^2((c-1)n-10^6)>=0

즉 c=10^7, n=1일 때 성립

cn^3-(n^3+10^6n^2)=n^2((c-1)n-10^6)<=0

즉 c=10^6, n=1일 때 성립

 

(h) 6n^3/(logn+1)=O(n^3)

 

->

cn^3>=6n^3/(logn+1), c(logn+1)>=6

즉, c=1, n=1일 때 성립

c(logn+1)<=6인 경우에는 이를 만족하는 c 찾을 수 없다 즉 BigOh만 만족

 

(i) n^1.001+nlogn=Theta(n^1.001)

 

->

cn^1.001-(n^1.001+nlogn)>=0인 경우 이를 만족하는 c를 찾을 수 없다

cn^1.001-(n^1.001+nlogn)<=0

즉 c=1, n=1일 때 성립

BigOh는 만족하지 않으므로 세타는 성립 X 오메가만 만족

 

(j) n^k+n+n^klogn=Theta(n^klogn), k>=1

 

->

cn^klogn-(n^k+n+n^klogn)=n^k((c-1)logn-1)-n>=0인 경우 이를 만족하는 c를 찾을 수 없다

n^k((c-1)logn-1)-n<=0

즉, c=1, n=1일 때 성립

BigOh는 만족하지 않으므로 세타는 성립 X 오메가만 만족

 

(k) 10n^3+15n^4+100(n^2)2^n=O((n^2)2^n)

 

->

c(n^2)2^n-(10n^3+15n^4+100(n^2)2^n)=n^2((c-100)2^n-10n-15n^2)>=0

즉, c=115, n=1 일때 성립

 

(l) 33n^3+4n^2=Omega(n^2)

(m) 33n^3+4n^2=Omega(n^3)

 

->

33n^3+4n^2>=c(n^3)

즉, c=1, n=0일 때 성립

33n^3+4n^2>=(n^3)

[9번 문제]

/*

Show that the following equalities are incorrect

다음 식들이 틀렸다는 것을 보인다

*/

(a) 10n^9+9=O(n)

 

->

cn-10n^9+9=n(c-10n)-9>=0일 때 이를 만족하는 c를 찾을 수 없다

하지만 10n^9+9<=11n^2인 경우

n=3일 때 만족 즉, O(n^2)

 

(b) n^2(logn)=Theta(n^2)

 

->

cn^2-n^2(logn)=n^2(c-logn)>=0일 때 이를 만족하는 c를 찾을 수 없다

BigOh가 만족 X 즉, 세타 또한 성립 X

 

(c) n^2/logn=Theta(n^2)

 

->

cn^2-n^2/logn=n^2(c-1/logn)>=0

즉, c=1, n=10일 때 성립

n^2(c-1/logn)<=0인 경우에는 이를 만족하는 c를 찾을 수 없다

따라서 세타 성립 X

 

(d) n^3(2^n)+6n^2(3^n)=O(n^2(2^n))

 

->

cn^2(2^n)-n^3(2^n)-6(n^2)3^n=n^2((c-n)2^n-6*3^n)>=0, 2^n=O(3^n)이므로 만족하는 c를 찾을 수 없다

[Exercises 15]

/*

A complex-valued matrix X is represented by a pair of matrices (A, B) where A and B contain real values.

복소수 X는 허수가 아닌 값을 갖는 A와 B를 담고 있는 (A, B)를 통해 표현된다.

Write a program that computes the product of two complex valued matrices (A, B) and (C, D)

where (A, B)*(C, D)=(A+iB)*(C+iD)=(AC-BD)+i(AD+BC)

두개의 복소수를 표현하는 (A, B)와 (C, D)를 통해 (A, B)*(C, D)=(A+iB)*(C+iD)=(AC-BD)+i(AD+BC)를 구현하는 프로그램을 작성한다

*/

#include <iostream>

using namespace std;

 

class Complex

{

private:

        int Real; //실수

        int UnReal; //허수

public:

        Complex(int a, int b) :Real(a), UnReal(b)

        {

        }

        Complex &operator*(Complex &Cx)

        {

               return Complex(Real*Cx.Real - UnReal*Cx.UnReal, Real*Cx.UnReal + UnReal*Cx.Real);

        }

        friend ostream &operator<<(ostream &os, Complex &Cx);

};

 

ostream &operator<<(ostream &os, Complex &Cx)

{

        os << "(" << Cx.Real << " + " << Cx.UnReal << "i)" << endl;

        return os;

}

 

int main(void)

{

        Complex Com1(3, 5);

        cout << "첫 번째 복소수: " << Com1 << endl;

        Complex Com2(4, 6);

        cout << "두 번째 복소수: " << Com2 << endl;

        Complex Com3 = Com1*Com2;

        cout << "둘이 곱하면: " << Com3 << endl;

        return 0;

}

[Exercises 16]

/*

Function Magic(Program 1.26) uses a 51*51 array square independent of the value of n

1.26 프로그램에서 정의한 Magic 함수는 n 값과 상관없이 51*51 배열을 사용한다.

When n<51, excess space is used and when n>51, the function throws an exception.

n이 51보다 작을 때는 공간이 낭비되고 n이 51보다 클 때는 함수가 예외문을 throw한다.

We can eliminate these shortcomings by using a dynamically allocated n*n 2- dimensional array.

우리는 이러한 단점을 동적할당한 이차원배열을 사용하며 보완할 수 있다.

Modify Magic to do this.

Magic 함수를 수정하여 단점을 보완해라

*/

/*

Magic square

*/

#include <iostream>

#include <algorithm>

#include <iterator>

using namespace std;

 

void Magic(const int n)

{

        //Create a magic square of size n, n is odd

        const int MaxSize = 51; // maximum square size

 

        int k, l;

        int **square = new int*[n];

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

               square[i] = new int[n];

 

        //check correctness of n

        if ((n > MaxSize) || (n < 1))

               throw "Error!..n out of range";

        else if (!(n % 2))

               throw "Error!..n is even";

 

        //n is odd. Coxeter's rule can be used

        for (int i = 0; i < n; i++) //initialize square to 0

               fill(square[i], square[i] + n, 0); //STL algorithm

        square[0][(n - 1) / 2] = 1; //middle of first row

 

                                                             //i and j are current position

        int key = 2;

        int i = 0;

        int     j = (n - 1) / 2;

        while (key <= n*n)

        {

               //move up and left

               if (i - 1 < 0)

                       k = n - 1;

               else

                       k = i - 1;

               if (j - 1 < 0)

                       l = n - 1;

               else

                       l = j - 1;

               if (square[k][l])

                       i = (i + 1) % n; //square occupied, move down

               else

               {

                       //square [k][l] is unoccupied

                       i = k;

                       j = l;

               }

               square[i][j] = key;

               key++;

        }//end of while

 

         //output the magic square

        cout << "magic square of size " << n << endl;

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

        {

               copy(square[i], square[i] + n, ostream_iterator<int>(cout, " "));

               cout << endl;

        }

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

        {

               delete square[i];

        }

        delete[]square;

}

 

int main(void)

{

        int n;

        while (1)

        {

               try

               {

                       cout << "마방진의 크기: ";

                       cin >> n;

                       Magic(n);

               }

               catch (char *expn)

               {

                       cout << expn << endl;

               }

        }

        return 0;

}

[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://math.stackexchange.com/questions/225698/proof-by-induction-sum-0nxi-1-xn1-1-x

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

*2번 문제는 링크를 참고했습니다.

*8, 9번 문제는 오답이 있을 수도 있습니다. 오답이 보인다면 댓글 남겨주시면 감사하겠습니다!

*풀지 않은 문제는 끊임없이 반복해야하는 문제였기 때문에 풀지 않았습니다.