７．集合 ７．１ 集合とは ［集合と要素］ 関東の都道府県 群馬県 栃木県 要素 埼玉県 茨城県 東京都 千葉県 神奈川県

Presentation on theme: "７．集合 ７．１ 集合とは ［集合と要素］ 関東の都道府県 群馬県 栃木県 要素 埼玉県 茨城県 東京都 千葉県 神奈川県"— Presentation transcript:

1 ７．集合 ７．１ 集合とは ［集合と要素］ 関東の都道府県 群馬県 栃木県 要素 埼玉県 茨城県 東京都 千葉県 神奈川県
７．集合 ７．１　集合とは ［集合と要素］ 関東の都道府県 群馬県 栃木県 要素 埼玉県 茨城県 東京都 千葉県 神奈川県 集合「関東の都道府県」

2 集合の式表現（１） ［集合の要素］ 集合Xが要素2,6を持つとき，以下のように書く。 X = {2, 6} 順序は意味を持たないので，
は同じことを示す。 ［元として含まれる］ 要素 a が集合Xの要素のとき，a はXに属するといい， 　　a ∈ X または X∋ a　　　（元として含まれる） と記述する。 要素 b が集合Xの要素でないとき， 　　b ∈ X または X∋ b　　　（元として含まれる）

3 集合の式表現（２） ［集合の要素数］ 要素数が無限大のとき無限集合，要素数の有限のとき有限集合と呼び， |X| = ∞ ，|X| = n
と書く。 　　　 |X| = 0 のとき，空集合と呼び，φで表す。

4 集合の演算 Ａ∪Ｂ Ａ＝｛1, 2, 3, 5｝, Ｂ＝｛1, 3, 6, 7｝ Ａ∪Ｂ＝｛1, 2, 3, 5, 6, 7｝ ［和集合］
Ａ＝｛1, 2, 3, 5｝, Ｂ＝｛1, 3, 6, 7｝ Ａ∪Ｂ＝｛1, 2, 3, 5, 6, 7｝ ［和集合］ Ａ Ｂ Ａ∩Ｂ Ａ＝｛1, 2, 3, 5｝, Ｂ＝｛1, 3, 6, 7｝ Ａ∩Ｂ＝｛1, 3｝ ［積集合］ Ａ Ｂ Ａ－Ｂ Ａ＝｛1, 2, 3, 5｝, Ｂ＝｛1, 3, 6, 7｝ Ａ－Ｂ＝｛2, 5｝ ［差集合］ Ａ Ｂ

5 ７．２ 配列による集合 すべての要素が同じ型のとき，配列を用いて集合を表現できる。 ６ ４ ３ ７ ２ ５ 上記のように，順序は任意でよい。
７．２　配列による集合 すべての要素が同じ型のとき，配列を用いて集合を表現できる。 ６ ４ ３ ７ ２ ５ 上記のように，順序は任意でよい。 ＣやＣ＋＋では，集合の要素数と配列の要素数を等しくする必要があるので，初期化時に動的に確保する必要がある。 Ｃ＃では，newキーワードでサイズが決まった時点で配列の大きさを決める。また，C#では，ギザギザの形の配列を宣言できるので，他のＣ処理系よりも配列による集合表現が容易である。

6 プログラム例 フォーム定義 Name:textBox1 Name:textBox2 Name:button1 Name:button2
Name:listBox1 Name:button5 Name:button6 Name:button7 Name:textBox3

7 プログラム例 ①データ宣言と表示処理 public int[][] Set = new int[3][]; public void 表示()
{ 　　string S; listBox1.Items.Clear(); 　　foreach(int[] A in Set) 　　{ if(A.Length==0) S="[]"; else 　　 　　S=""; 　　foreach(int X in A) S += X.ToString()+", "; 　　S = "[" + S.Substring(0,S.Length-2)+ "]"; } listBox1.Items.Add(S); 　　}

8 プログラム例　②初期値の設定 private void button1_Click(object sender, System.EventArgs e) { 　　Set[0]= new int[3]{1,2,3}; 　　Set[1]= new int[0]{}; 　　Set[2]= new int[4]{4,5,6,7}; 　　表示(); }

9 プログラム例 ③集合ＳにＸが入っているか // 集合SにXが入っているかどうか
プログラム例　③集合ＳにＸが入っているか // 集合SにXが入っているかどうか private bool SetMember(int X, int[] S) { for(int i=0;i<S.Length;i++) 　　if(X==S[i])return true; 　　return false; } private void button2_Click(object sender, System.EventArgs e) 　　int EL=int.Parse(textBox1.Text); 　　int ID=int.Parse(textBox2.Text); 　　if(ID>=0 && ID<=2) 　　　　　MessageBox.Show(SetMember(EL,Set[ID]).ToString());

10 プログラム例 ④要素追加 // 集合SにXを追加 private int[] AddMember(int X,int[] S) {
プログラム例　④要素追加 // 集合SにXを追加 private int[] AddMember(int X,int[] S) { 　　if(SetMember(X,S)) return S; 　　int[] S2=new int[S.Length+1]; 　　for(int i=0;i<S.Length;i++) S2[i]=S[i]; 　　S2[S.Length]=X; 　　return S2; } private void button3_Click(object sender, System.EventArgs e) 　　int EL=int.Parse(textBox1.Text); 　　int ID=int.Parse(textBox2.Text); 　　Set[ID]=AddMember(EL,Set[ID]); 表示();

11 プログラム例 ⑤要素削除 // 集合SからXを削除 private int[] DelMember(int X,int[] S) {
プログラム例　⑤要素削除 // 集合SからXを削除 private int[] DelMember(int X,int[] S) { 　　if(!SetMember(X,S))return S; 　　int[] S2=new int[S.Length-1]; 　　int ii=0; 　　for(int i=0;i<S.Length;i++)if(S[i]!=X) S2[ii++]=S[i]; 　　return S2; } private void button4_Click(object sender, System.EventArgs e) 　　int EL=int.Parse(textBox1.Text); 　　int ID=int.Parse(textBox2.Text); 　　Set[ID]=DelMember(EL,Set[ID]); 　　表示();

12 プログラム例 ⑥和集合 // S1とS2の和集合 private int[] SetUnion(int[] S1,int[] S2) {
プログラム例　⑥和集合 // S1とS2の和集合 private int[] SetUnion(int[] S1,int[] S2) { 　　int[] S = S2; 　　foreach (int EL in S1) S = AddMember(EL,S); 　　return S; } private void button5_Click(object sender, System.EventArgs e) 　　int ID1=int.Parse(textBox2.Text); 　　int ID2=int.Parse(textBox3.Text); 　　Set[ID1]=SetUnion(Set[ID1],Set[ID2]); 　　表示();

13 プログラム例　⑦積集合 // S1とS2の積集合 private int[] SetIntersection(int[] S1,int[] S2) { 　　int[] S = new int []{}; 　　foreach (int EL in S1) if(SetMember(EL,S2))S = AddMember(EL,S); 　　return S; } private void button6_Click(object sender, System.EventArgs e) 　　int ID1=int.Parse(textBox2.Text); 　　int ID2=int.Parse(textBox3.Text); 　　Set[ID1]=SetIntersection(Set[ID1],Set[ID2]); 　　表示();

14 プログラム例　⑧差集合 // S1とS2の差集合 private int[] SetDifference(int[] S1,int[] S2) { 　　int[] S = new int []{}; 　　foreach (int EL in S1) if(!SetMember(EL,S2)) S = AddMember(EL,S); 　　return S; } private void button7_Click(object sender, System.EventArgs e) 　　int ID1=int.Parse(textBox2.Text); 　　int ID2=int.Parse(textBox3.Text); 　　Set[ID1]=SetDifference(Set[ID1],Set[ID2]); 　　表示();

15 ７．３　ビットベクトルによる集合 Maxが小さければ，0，1, 2, …，Max－1を符号なし整数のビット位置で示すことで，対応するビットの0，１で集合を表現することができます。 たとえば，１６個の集合を表現するのに， 以下のような１６ビット長の整数１個で表現できます。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 1 1 1 1 1 集合演算も，整数同士のビット演算AND，ORで代替することができます。差集合は， 　　　A－B　＝　A And ( Not B） とすることができます。

16 BitArray型 C#では，小型の配列としてBitArrayクラスが用意されており，ビット演算，ビット位置のセットが簡単にできます。

17 プログラム例 フォーム定義 Name:button2 Name:textBox1 Name:textBox2 Name:button1
Name:lblDsp1 Name:lblDsp2 Name:button3 Name:button4 Name:button5 Name:button9 Name:lblDsp3 Name:button6 Name:button7

18 プログラム例 ①データ宣言と表示処理 BitArray myBA1 = new BitArray(10,false);
private string Bit列(BitArray A) { string S=""; for(int i=0;i<A.Length;i++) { if(A[i]) S += "1"; else S +="0"; } return S; private void 表示() lblDsp1.Text=Bit列(myBA1); lblDsp2.Text=Bit列(myBA2); lblDsp3.Text=Bit列(myBA3);

19 プログラム例 ②Form1_Load，要素追加，要素削除
private void Form1_Load(object sender, System.EventArgs e) { 表示(); } private BitArray AddMember(BitArray BA,int Member) { BitArray B=BA; if(Member < BA.Length) B[Member]=true; return B; } private BitArray DeleteMember(BitArray BA,int Member) if(Member < BA.Length) B[Member]=false;

20 プログラム例 ③コマンド処理（その１） // BA1に要素を追加
private void button1_Click(object sender, System.EventArgs e) {　myBA1=AddMember(myBA1,int.Parse(textBox1.Text)); 表示(); } // BA2に要素を追加 private void button2_Click(object sender, System.EventArgs e) { myBA2=AddMember(myBA2,int.Parse(textBox2.Text)); 表示(); } // BA1に要素があるかどうか？ private void button3_Click(object sender, System.EventArgs e) { MessageBox.Show(myBA1[int.Parse(textBox1.Text)].ToString()); } // BA2に要素があるかどうか？ private void button4_Click(object sender, System.EventArgs e) { MessageBox.Show(myBA2[int.Parse(textBox2.Text)].ToString()); } // BA1 Or BA2 private void button5_Click(object sender, System.EventArgs e) { BitArray A=(BitArray)myBA1.Clone(); myBA3=A.Or(myBA2);表示(); }

21 プログラム例 ④コマンド処理（その２） // BA3 = BA1 And BA2
private void button6_Click(object sender, System.EventArgs e) {　BitArray A=(BitArray)myBA1.Clone(); myBA3=A.And(myBA2);表示(); } // BA3 = BA1 - BA2 private void button7_Click(object sender, System.EventArgs e) { BitArray A=(BitArray)myBA1.Clone(); BitArray B=(BitArray)myBA2.Clone(); myBA3=A.And(B.Not());表示(); // BA1から要素の削除 private void button8_Click(object sender, System.EventArgs e) {　myBA1=DeleteMember(myBA1,int.Parse(textBox1.Text)); 表示(); } // BA2から要素の削除 private void button9_Click(object sender, System.EventArgs e) {　myBA2=DeleteMember(myBA2,int.Parse(textBox2.Text)); 表示(); }