7.集合 7.1 集合とは [集合と要素] 関東の都道府県 群馬県 栃木県 要素 埼玉県 茨城県 東京都 千葉県 神奈川県

Slides:



Advertisements
Similar presentations
0章 数学基礎.
Advertisements

離散数学入門 (集合論、ベン図) 情報システム学科 中田豊久.
アルゴリズムとデータ構造 2013年6月18日
~手続き指向からオブジェクト指向へ(Ⅰ)~
アルゴリズムとデータ構造 2010年7月5日
ファーストイヤー・セミナーⅡ 第8回 データの入力.
とても使いやすい Boost の serialization
とても使いやすい Boost の serialization
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造 2012年7月19日
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
情報工学概論 (アルゴリズムとデータ構造)
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
アルゴリズムとデータ構造 2011年6月13日
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
8.Intersecting Families
競技プログラマ向け 形式言語理論 入門 稲葉 一浩 JOI 春合宿 2012.
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
アルゴリズムとデータ構造 2011年6月14日
第6回独習Javaゼミ 第6章 セクション4~6 発表者 直江 宗紀.
アルゴリズムとデータ構造 2013年7月18日
岩村雅一 知能情報工学演習I 第8回(後半第2回) 岩村雅一
ちょっとした練習問題① 配列iroを['R', 'W', 'R', 'R', 'W' , 'W' , 'W']を宣言して、「W」のときの配列の番号をprintfで表示するようなプログラムを記述しなさい。
プログラミング言語入門 手続き型言語としてのJava
プログラムの制御構造 選択・繰り返し.
アルゴリズムとデータ構造 2011年7月4日
暗黙的に型付けされる構造体の Java言語への導入
コードクローンの分類に基づいた メソッド引き上げ手順の提案とその有効性評価
アルゴリズムとデータ構造 2013年7月16日
ローカル変数とグローバル変数 ローカル変数  定義された関数内だけで使用できる変数 グローバル変数 プログラム全体で使用できる変数.
アルゴリズムとデータ構造1 2006年7月4日
画像処理プログラムの説明.
アルゴリズムとデータ構造 補足資料5-2 「サンプルプログラムsetop.c」
1. 集合 五島 正裕.
デジタル画像とC言語.
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
もっと詳しくArrayクラスについて調べるには → キーワード検索
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
ソフトウェア制作論 平成30年11月21日.
オブジェクト・プログラミング 第8回.
アルゴリズムとデータ構造1 2006年7月11日
15.1 文字列処理の基本 15.2 文字列処理用ライブラリ関数
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング 3 2 次元配列.
アルゴリズムとデータ構造1 2006年7月4日
C#プログラミング実習 第3回.
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとプログラミング (Algorithms and Programming)
「マイグレーションを支援する分散集合オブジェクト」
サブゼミ第7回 実装編① オブジェクト型とキャスト.
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
第5回 プログラミングⅡ 第5回
プログラミング入門2 第5回 配列 for文 変数宣言 初期化
アルゴリズムとデータ構造 2010年6月17日
GUI部品とイベント処理の例 マインスィーパもどきの作成 倉敷芸術科学大学 産業科学技術学部 梶浦文夫.
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
8.文字列処理 8.1 C#の文字列 C#では, “ABCD”のように文字列を2重引用符で挟んで指定します。ASCIIコード体系のとき,以下のような内部形式となります。 1 1 文字 ‘A’ ナル文字 1 1 文字 ‘B’ A B C D \ 文字 ‘C’ 1 1 文字 ‘D’ ナル文字‘\0’
15.1 文字列処理の基本 15.2 文字列処理用ライブラリ関数
プログラミング入門2 第5回 配列 変数宣言、初期化について
3.操作を伴うデータ構造 3.1 スタック (1)データを一時的に蓄えるデータ構造のひとつ (2)最後に入れたデータが最初に取り出される。
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

7.集合 7.1 集合とは [集合と要素] 関東の都道府県 群馬県 栃木県 要素 埼玉県 茨城県 東京都 千葉県 神奈川県 7.集合 7.1 集合とは [集合と要素] 関東の都道府県 群馬県 栃木県 要素 埼玉県 茨城県 東京都 千葉県 神奈川県 集合「関東の都道府県」

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

集合の式表現(2) [集合の要素数] 要素数が無限大のとき無限集合,要素数の有限のとき有限集合と呼び, |X| = ∞ ,|X| = n と書く。     |X| = 0 のとき,空集合と呼び,φで表す。

集合の演算 A∪B A={1, 2, 3, 5}, B={1, 3, 6, 7} A∪B={1, 2, 3, 5, 6, 7} [和集合] A={1, 2, 3, 5}, B={1, 3, 6, 7} A∪B={1, 2, 3, 5, 6, 7} [和集合] A B A∩B A={1, 2, 3, 5}, B={1, 3, 6, 7} A∩B={1, 3} [積集合] A B A-B A={1, 2, 3, 5}, B={1, 3, 6, 7} A-B={2, 5} [差集合] A B

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

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

プログラム例 ①データ宣言と表示処理 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);   }

プログラム例 ②初期値の設定 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};   表示(); }

プログラム例 ③集合SにXが入っているか // 集合SにXが入っているかどうか プログラム例 ③集合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());

プログラム例 ④要素追加 // 集合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]); 表示();

プログラム例 ⑤要素削除 // 集合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]);   表示();

プログラム例 ⑥和集合 // 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]);   表示();

プログラム例 ⑦積集合 // 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]);   表示();

プログラム例 ⑧差集合 // 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]);   表示();

7.3 ビットベクトルによる集合 Maxが小さければ,0,1, 2, …,Max-1を符号なし整数のビット位置で示すことで,対応するビットの0,1で集合を表現することができます。 たとえば,16個の集合を表現するのに, 以下のような16ビット長の整数1個で表現できます。 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) とすることができます。

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

プログラム例 フォーム定義 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

プログラム例 ①データ宣言と表示処理 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);

プログラム例 ②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;

プログラム例 ③コマンド処理(その1) // 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);表示(); }

プログラム例 ④コマンド処理(その2) // 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)); 表示(); }