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

[Exercises 1]

/*

Modify Program 1.14 so that it outputs all permutations of distinct elements

프로그램 1.14를 수정하여 순열의 모든 개별 요소를 출력하도록 한다.

Do this by sorting the element list into ascending order prior to generating the permutations.

위의 지시사항을 실행할 때 오름차순으로 출력하도록 한다.

To sort, use the STL algorithm sort(start, end) which sorts elements in the range [start, end) into ascending order.

오름차순으로 출력할 때 STL 알고리즘 sort(start end)를 사용하도록 한다.

*/

#include <iostream>

#include <ctime>

#include <cstdlib>

#include <algorithm>

using namespace std;

 

int main(void)

{

        int arr[10]; //10개의 요소를 갖는 배열

        srand((unsigned)time(NULL));

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

        {

               arr[i] = rand() % 100 + 1; //1~100 사이

               cout << arr[i] << " ";

        }

        cout << endl;

 

        sort(arr, arr+10); //오름차순

        cout << "오름차순으로 정렬" << endl;

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

        {

               cout << arr[i] << " ";

        }

        return 0;

}

[Exercises 2]

/*

Modify Program 1.14 so that it outputs all permutations of distinct element

프로그램 1.14를 수정하여 순열의 모든 개별 요소를 출력하도록 한다.

Do this by first using next_permutation to generate permutations that are lexically larger than the initial permutation

next_pemutation을 이용하여 (사전적)오름차순으로 순열을 생성하여 위의 지시사항을 이행하고

and then using the STL algorithm prev_permutation to generate permutations that are lexically smaller than the initial permutation.

그리고 STL 알고리즘인 prev_permutation을 이용하여 (사전적)내림차순으로 순열을 생성한다.

*/

#include <iostream>

#include <algorithm>

using namespace std;

 

int main(void)

{

        char str[] = "BADCFE";

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

        do

        {

        } while (next_permutation(str, str + sizeof(str) - 1));

        cout << str << endl;

        cout << "내림차순" << endl;

        do

        {

        } while (prev_permutation(str, str + sizeof(str) - 1));

        cout << str << endl;

        return 0;

}

[Exercises 3]

/*

Modify Program 1.14 so that it outputs all permutations of distinct elements.

프로그램 1.14를 수정하여 순열의 모든 개별 요소를 출력하도록 한다.

Do this by using the fact that when next_permutation returns the value false the sequence[start, end) is the lexically smallest sequence

next_permutation이 거짓을 반환할 때 순열이 오름차순으로 정렬되는 것을 활용하여 위 지시사항을 이행한다.

Hence, subsequent invocations of next_permutation will get you the remaining(if any) permutations you need

즉, 차후의 next_permutation 알고리즘의 호출은 본인이 필요한 순열(필요하다면)을 출력해준다

*/

#include <iostream>

#include <algorithm>

using namespace std;

 

int main(void)

{

        char str[] = "BLUE";

        cout << "next_permutation 과정" << endl << endl;

        do

        {

               cout << str << endl; //모든 순열을 출력

        } while (next_permutation(str, str + sizeof(str) - 1));

        cout << endl;

        cout << "결과물" << endl << endl;

        cout << str << endl;

        return 0;

}

 

[Exercises 4]

/*

The STL algorithm count, which has the synatx count(start, end, value)

count(start, end, value)의 구문을 갖는 STL 알고리즘 count는

returns the number of occurrences of value in the range[start, end).

범위(시작~끝)안에 value의 호출횟수를 반환한다.

Write a program that uses this algorithm to determine the number of occurrences of a[0] in the integer array a[0:n-1].

이 알고리즘을 이용하여 a[0]가 배열 안에 몇번 호출되는지 확인하도록 프로그램을 작성한다

*/

#include <iostream>

#include <ctime>

#include <cstdlib>

#include <algorithm>

using namespace std;

 

int main(void)

{

        int arr[10];

        srand((unsigned)time(NULL));

        cout << "배열" << endl;

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

        {

               arr[i] = rand() % 5 + 1; //겹치는 숫자가 많도록 1~5

               cout << arr[i] << " ";

        }

        cout << endl;

        cout << "배열에서 호출된 횟수를 찾고자 하는 값: " << arr[0] << endl;

        cout << arr[0] << "은 배열에서 총 " << count(arr, arr+10, arr[0]) << "번 호출되었다" << endl;

        return 0;

}

[Exercises 5]

/*

The STL alogrithm fill which has the syntax fill(start, end, value)

fill(start, end, value)의 구문을 갖는 STL 알고리즘 fill은

set all positions in the range [start, end) to value.

범위(처음부터 끝까지) 안을 모두 value로 채운다.

Write a program that creates an integer array of a specified size and initializes all positions of this array to 0.

특정 크기가 정해진 int형 배열을 생성하고 모두 0으로 초기화하는 프로그램을 작성합니다

*/

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <ctime>

using namespace std;

 

int main(void)

{

        int arr[10]; //특정크기

        srand((unsigned)time(NULL));

 

        cout << "기존 배열" << endl;

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

        {

               arr[i] = rand() % 100 + 1; //0이 아닌 숫자로 초기화

               cout << arr[i] << " ";

        }

        cout << endl;

        cout << "모두 0으로 초기화" << endl;

        fill(arr, arr + 10, 0);

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

        {

               cout << arr[i] << " ";

        }

        cout << endl;

        return 0;

}

[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서

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