高中生程式解題系統：集合運算 Set Operations

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=b050。

直接用 C++ STL algorithm 裡的 set_union、set_intersection、set_difference、includes來寫。

程式碼：

#include <iterator>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int n;
    int count = 0;

    while( cin >> n )
    {
        count = count + 1;

        if( n == 0 ) break;

        vector<char> *dataSet = new vector<char>[n];

        for( int i = 0; i < n; i++ )
        {
            string input;
            cin >> input;

            for( unsigned j = 0; j < input.length(); j++ )
                input[j] = tolower(input[j]);

            for( unsigned j = 0; j < input.length(); j++ )
                dataSet[i].push_back(input[j]);

            sort(dataSet[i].begin(), dataSet[i].end());
        }

        cout << "Test Case " << count << ":\n";

        for( int i = 0; i < n; i++ )
        {
            char name = 'A' + i;

            cout << name << ": {";
            copy(dataSet[i].begin(), dataSet[i].end(), ostream_iterator<char>(cout, ""));
            cout << "}" << endl;
        }

        // Union and intersection
        for( int i = 0; i < n; i++ )
        {
            char setName = 'A' + i;
            for( int j = i + 1; j < n; j++ )
            {
                char name = 'A' + j;
                vector<char> setUnion( dataSet[i].size() + dataSet[j].size() );
                vector<char>::iterator iter = set_union( dataSet[i].begin(), dataSet[i].end(),
                           dataSet[j].begin(), dataSet[j].end(), setUnion.begin());

                cout << setName << "+" << name << ": {";
                copy(setUnion.begin(), iter, ostream_iterator<char>(cout, ""));
                cout << "}" << endl;

                vector<char> setIntersection( min(dataSet[i].size(), dataSet[j].size()) );
                iter = set_intersection( dataSet[i].begin(), dataSet[i].end(),
                           dataSet[j].begin(), dataSet[j].end(), setIntersection.begin());

                cout << setName << "*" << name << ": {";
                copy(setIntersection.begin(), iter, ostream_iterator<char>(cout, ""));
                cout << "}" << endl;

            }
        }

        for( int i = 0; i < n; i++ )
        {
            char setName = 'A' + i;
            for( int j = 0; j < n; j++ )
            {
                char name = 'A' + j;
                if( i != j )
                {
                    vector<char> difference( max(dataSet[i].size(), dataSet[j].size()) );
                    vector<char>::iterator iter = set_difference( dataSet[i].begin(), dataSet[i].end(),
                                    dataSet[j].begin(), dataSet[j].end(), difference.begin());

                    cout << setName << "-" << name << ": {";
                    copy(difference.begin(), iter, ostream_iterator<char>(cout, ""));
                    cout << "}" << endl;
                }
            }
        }

        for( int i = 0; i < n; i++ )
        {
            char setName = 'A' + i;
            for( int j = 0; j < n; j++ )
            {
                char name = 'A' + j;
                if( i != j )
                {
                    if(includes( dataSet[i].begin(), dataSet[i].end(),
                                 dataSet[j].begin(), dataSet[j].end()) == true)
                    {
                        cout << setName << " contains " << name << endl;
                    }
                    else
                    {
                        cout << setName << " does not contain " << name << endl;
                    }
                }
            }
        }

        delete [] dataSet;
    }
}