はじめMath! Javaでコンピュータ数学

第34回 集合の数学 部分集合,空集合 [後編]

この記事を読むのに必要な時間:およそ 3 分

今回は,前回学習した集合の概念を,Java言語で記述するとどうなるか具体的に取り組んでみましょう。手を動かすと,頭で考えているうちは見えてこなかった,解決すべき問題点が見えてくるものです。それらの問題点を解決していくことで,実際的なノウハウ・スキルが身に付いていきます。多少煩雑な演習問題ですが,じっくり取り組んでみてください。

問題:集合Aに対して,集合Bが真部分集合か,部分集合か,一致する要素がないか を確認するプログラムを完成してください。

配列とArrayListでそれぞれ作成してみましょう。以下に判定部分のコードを除いたものを掲載します。目的の処理を行うコードを書き足してください。

ソースコード:HairetsuDeBubunShugoHantei.javaの未完成版

01: //サンプルコード
02: //部分集合・真部分集合の判定
03: //filename : HairetsuDeBubunShugoHantei.java
04: 
05: class HairetsuDeBubunShugoHantei {
06:   public static void main(String[] args) {
07:     char a[] = {’a’,’b’,’c’,’d’,’e’};
08: // char b[] = {’b’,’d’,’a’,’c’,’e’}; //部分集合,かつ等価な集合
09:     char b[] = {’a’,’b’,’c’}; //真部分集合
10: // char b[] = {’a’,’b’,’c’,’f’}; //重複部分のある集合
11: // char b[] = {’x’,’y’,’z’}; //一致する部分のない集合
12: 
13:     //-------------------------------------------------
14:     //判定し,結果を表示するコードをここに書きましょう。
15:     //-------------------------------------------------
16: 
17:   }// end of main
18: }// end of class HairetsuDeBubunShugoHantei

ソースコード:ArrayListDeBubunShugoHantei.javaの未完成版

01: //サンプルコード
02: //部分集合・真部分集合の判定
03: //filename : ArrayListDeBubunShugoHantei.java
04: import java.util.ArrayList;
05: 
06: class ArrayListDeBubunShugoHantei {
07:  public static void main(String[] args) {
08: 
09:     //初期化
10:     ArrayList A = new ArrayList(); //集合A
11:     char a[] = {’a’,’b’,’c’,’d’,’e’};
12:     for (int i = 0 ; i < a.length ; ++i )
13:         A.add( Character.toString(a[i]) );
14:     ArrayList B = new ArrayList();//集合B
15: // char b[] = {’b’,’d’,’a’,’c’,’e’}; //部分集合,かつ等価な集合
16:     char b[] = {’a’,’b’,’c’}; //真部分集合
17: // char b[] = {’a’,’b’,’c’,’f’}; //重複部分のある集合
18: // char b[] = {’x’,’y’,’z’}; //一致する部分のない集合
19:     for (int i = 0 ; i < b.length ; ++i )
20:         B.add( Character.toString(b[i]) );
21: 
22:     //---------------------------------------------
23:     //A に対してB が部分集合か,真部分集合かを判定し,
24:     //結果を表示するコードをここに書きましょう。
25:     //---------------------------------------------
26: 
27:   }// end of main
28: }// end of class ArrayListDeBubunShugoHantei

解説

それぞれのプログラムの完成版を紹介します。この他により効果的なアルゴリズムが考えられるでしょうから,「より短く,わかりやすいコード」を目指して奮闘してみてください。

配列版もArrayList版もソースコードでは,集合Aと集合Bの要素を逐一比較し,一致する要素をカウントアップしています。ソースコードでは,配列版の13行目から22行目まで,ArrayList版の22行目から26行目までです。ArrayList版の要素チェック部分のコードがずいぶんシンプルであることに注目してください。

次の図34.1のように判定の基準を設けて処理しています。

図34.1 真・部分・重複・一致なしの判定のしかた

図34.1 真・部分・重複・一致なしの判定のしかた

この図34.1によれば,次のような条件式が考えられます。

真部分集合であるときの条件式は次の通り。

XOR(排他的論理和)をとりますから,要素数の比較は必要なくなりますので,解答例のソースコードには反映していません。

著者プロフィール

平田敦(ひらたあつし)

地方都市の公立工業高等学校教諭。趣味はプログラミングと日本の端っこ踏破旅行。2010年のLotYはRuby。結城浩氏のような仕事をしたいと妄想する30代後半♂。

コメント

コメントの記入