配列が別の配列のサブセットであるかどうかを確認しますか？ （C++）

Question

希望のアイデアは：セットサイズ&メンバを入力するには、サイズが有効であれば1番目のサブセット（A）を入力し、Aが有効なサブセットであれば2番目のサブセット（B）と同じにします。

#include "stdafx.h" 
#include <iostream> 
using namespace std; 

int main() 
{ 
    while (true) { 
     int i = 0; 
     int k = 0; 
     int * set; 
     int setSize; 
     cout << "Input size of set" << endl; 
     cin >> setSize; 
     if (setSize <= 0) { 
      cout << "Invalid size!" << endl; 
     } 
     else { 
      set = new int[setSize]; 
      for (int i = 0; i < setSize; i++) 
      { 
       cout << "set[" << i + 1 << "]="; 
       cin >> set[i]; 
      } 
      int * A; 
      int sizeA; 
      cout << "Input size of subset A" << endl; 
      cin >> sizeA; 
      if (sizeA <= 0 || sizeA > setSize) { 
       cout << "Invalid size for a subset, please try again!" << endl; 
      } 
      else { 
       A = new int[sizeA]; 
       cout << "Input members of A" << endl; 
       for (int i = 0; i < sizeA; i++) 
       { 
        cout << "A[" << i + 1 << "]="; 
        cin >> A[i]; 
       } 
       for (i = 0; i < sizeA; i++) 
       { 
        for (k = 0; k < setSize; k++) 
        { 
         if (A[i] == set[k]) 
          break; 
        } 
        if (k == setSize) { 
         return 0; 
        } 
        else{ 
         int * B; 
         int sizeB; 
         cout << "Input size of subset B" << endl; 
         cin >> sizeB; 
         if (sizeB <= 0 || sizeB > setSize) { 
          cout << "Invalid size for a subset, please try again!" << endl; 
         } 
         else { 
          B = new int[sizeB]; 
          cout << "Input members of B" << endl; 
          for (int i = 0; i < sizeB; i++) 
          { 
           cout << "B[" << i + 1 << "]="; 
           cin >> B[i]; 
          } 
          for (i = 0; i < sizeB; i++) 
          { 
           for (k = 0; k < setSize; k++) 
           { 
            if (B[i] == set[k]) 
             break; 
           } 
           if (k == setSize) { 
            cout << "Not a subset, please try again!" << endl; 
            break; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

そして私は、ビット列に」日を変換し、いくつかの操作を実行したいと思います...

Answer 1

ではなくスプーンフィード完全な答え、私はプログラミングアプローチする方法についていくつかのアドバイスを与えるでしょうこのような問題。

まず、すべてをmain()に書き込まないでください。代わりに、適切なデータ構造で動作し、適切な結果を返す関数を宣言します。この機能のためには、結果はboolでなければならないことは明らかだ - 二番目の配列は、最初のサブセットである場合はtrue、そうでない場合はfalse：

bool is_subset(std::vector<int> a, std::vector<int> b); 

それはそれが容易になり、それにその大きさを周りに運ぶので、私はvectorを選びました一緒に働く

これで、テストを開始することができます（はい、まずテストを書いてください - is_subset()を実装するまではテストは失敗しますが、これはテストがうまくいくことを示しています）。私はの考えることができる最も簡単なテストでは、「空のセットは、自身のサブセットです？」：

int main() 
{ 
    assert(is_subset({}, {})); 
} 

は、このテストに合格するために十分なコードを記述します。

bool is_subset(std::vector<int> a, std::vector<int> b) 
{ 
    return a == b; 
} 

これは明らかに完全ではありませんが、大丈夫です。これまでのテストを満たすには十分ですが、テストを追加する必要があります。だから、先に行くと別のテストを書く：

int main() 
{ 
    // empty set is a subset of itself 
    assert(is_subset({}, {})); 

    // empty set is a subset of a non-empty set 
    assert(is_subset({1}, {})); 
} 

そして、それは渡します

bool is_subset(std::vector<int> a, std::vector<int> b) 
{ 
    using std::begin; 
    using std::end; 

    return std::includes(begin(a), end(a), begin(b), end(b)); 
} 

さらにいくつかの基本的なテストがあります - 些細なセットは常に自身のサブセットであり、無非が空集合は、例えば、空集合の部分集合である。

次に、テストでより創造的になることができます。テストのリストが増えるにつれて、あなたの自然言語の散文よりはるかに明確な関数の必要なものについての記述を作成しています（例えば、 'set'は何を意味していますか？

テスト済みの機能があれば、入力（stdinまたはコマンド引数から）と出力（stdoutまたは終了コード）の細かい点を追加できます。別々の関数を使用して、必要に応じて異なるI/O関数をアルゴリズムと組み合わせて組み合わせることができます。

また、あなたがintの代わりに、このようなlongやstd::stringなどの型を使用することができますので、このようなテンプレートを使用するなど、さらなる改善、を見て（しかしdoubleを試みる前に、必ず浮動小数点平等の問題点を認識していることができますかfloat）。

---

ここで私はいくつかのテスト実装したら、私の完全なプログラムは次のようになります。

#include <cassert> 
#include <algorithm> 
#include <vector> 

bool is_subset(std::vector<int> a, std::vector<int> b); 

int main() 
{ 
    // empty set is a subset of itself 
    assert(is_subset({}, {})); 

    // empty set is a subset of a non-empty set 
    assert(is_subset({1}, {})); 

    // no non-empty set is a subset of an empty set 
    assert(!is_subset({}, {1})); 

    // Two different non-empty sets 
    assert(!is_subset({0}, {1})); 

    // Proper subset 
    assert(is_subset({1, 2, 3}, {2})); 

    // Unordered proper subset 
    assert(is_subset({1, 3, 2}, {2})); 

    // All values in subset must be in superset 
    assert(!is_subset({1, 2, 3}, {2, 2})); 
    assert(is_subset({1, 2, 2, 3}, {2, 2})); 
} 


bool is_subset(std::vector<int> a, std::vector<int> b) 
{ 
    using std::begin; 
    using std::end; 

    // The includes() algorithm requires sorted inputs 
    std::sort(begin(a), end(a)); 
    std::sort(begin(b), end(b)); 
    return std::includes(begin(a), end(a), begin(b), end(b)); 
} 

---

通過中の他の観測のカップル：

• が慣れ親しむをC++標準ライブラリを使用します。 vectorを使用すると、メモリをnew[]とで管理する必要はなく、<algorithm>の関数を使用することで、標準変換を再実装する時間が大幅に短縮され、コードもはっきりしたものになります。
• 可能であれば、メモリ管理を避けてください。可能であれば標準コレクションを使用し、そうでない場合はスマートポインタオブジェクトを使用し、避けられない場合には未処理のCスタイルポインタを優先します。そして、プログラムが終了しようとしている場合でも、割り当てたメモリを常にクリーンアップしてください。これによりValgrindなどのツールを使用してプログラムの正確性を簡単に理解できるだけでなく、より大きなプログラムでの関数の再利用も可能になります。