Java 6 を使って作りなさい。
レポート締切日: 2009年12月2日20:00
提出先: レポートボックス
二人のプレイヤーでじゃんけんを行うようなクラスを作成すること考えます。 「プレイヤー」は「戦略」を持ち、その戦略に従って「手」を出します。 手には Gu, Choki, Pa があります。 プレイヤーは「ボックス」において双方の手を出し、一回の勝敗を決めます。
このようなクラスを作成するため、以下の小問に答えなさい。
課題の設問内のテストプログラムを変更しました。 こちらの意図通りに作成できたプログラムに関しては、変更後のテストプログラムでも正常に動作しますので、新たなプログラムの修正は生じません。 但し、修正前のテストプログラムでは見落としていた誤りを見つけられるようになっています。 既にレポートを作成してしまっていても、必ず修正後のテストプログラムと結合し、正常 に動作することを確認してください。
また、レポート本文中のテストプログラムの説明は、Ex132, Ex142, Ex152 に関して行って下さい。二度手間になってしまいますが、よろしくお願いします。
なお、この問題は既に２ちゃんねるに質問され、解答が出ました。 今後、同じ質問をあちこちで何度もするのはマナー違反ですので、お控え下さい。 但し、もう上記の解答は消されたようです(11/26)。
以下のプログラムが動作するように、クラス Hand1 を作成しなさい。 必要であれば、さらにクラスを追加して良い。
class Ex11 {
public static void main(String[] arg){
for(int i=0; i<3; i++){
System.out.println(new Hand1(i));
}
}
}
Gu Choki Pa
まず、下記のクラスと interface を追加してください。
interface Hand {
int wins(Hand h);
int getType();
}
interface HandBuilder {
Hand getInstance(int hand);
}
class HandBuilder1 implements HandBuilder {
public HandBuilder1(){}
public Hand getInstance(int hand){
if(hand <0 || hand>2 ){
return null;
}
return new Hand1(hand);
}
}
そして、問 1-1 で作成した Hand1 クラスに対して、 Hand を implement し、 次の条件を満たすように getType メソッドと wins メソッドを実装しなさい。
そして、下記のテストプログラムを実行し、出力が予想と一致しているか確か めなさい。
class Ex12 {
public static void main(String[] arg){
final HandBuilder hb = new HandBuilder1();
final Hand[] hands = new Hand[3];
for(int i=0; i<3 ; i++){
hands[i] = hb.getInstance(i);
}
for(Hand h : hands){
System.out.print("\t"+h);
}
System.out.println();
for(Hand h1 : hands){
System.out.print(h1);
for(Hand h2 : hands){
System.out.print("\t"+h1.wins(h2));
}
System.out.println();
}
}
}
Gu Choki Pa Gu 0 1 -1 Choki -1 0 1 Pa 1 -1 0
さらに、下記の interface を追加します。
interface Tactics {
void setHandBuilder(HandBuilder hb);
Hand getHand();
}
この Tactics を実装し、次の条件を満たすクラス Tactics1, Tactics2 を作 成しなさい。
なお、どちらの Tactics も、 setHandBuilder により HandBuilder オブジェ クトを登録できるほかに、コンストラクタにも HandBuilder オブジェクトを 与えて作成と登録を同時にできるようにして下さい。
作成した Tactics1, Tactics2 に対して、下記のテストプログラムを実行し、 正常に動作していることを示しなさい。
class Hand0 implements Hand {
public Hand0(int i){
}
public int wins(Hand h){
return 0;
}
public int getType(){
return 0;
}
@Override public String toString(){
return "Gu";
}
}
class HandBuilder0 implements HandBuilder {
public HandBuilder0(){}
public Hand getInstance(int hand){
return new Hand0(0);
}
}
class Ex132 {
private static void examineTactics(Tactics t){
for(int i=1; i<=20 ; i++){
System.out.print(i+": "+t.getHand()+" ");
}
System.out.println();
}
public static void main(String[] arg){
final HandBuilder hb0 = new HandBuilder0();
final HandBuilder hb1 = new HandBuilder1();
examineTactics(new Tactics1(hb0));
examineTactics(new Tactics2(hb0));
examineTactics(new Tactics1(hb1));
examineTactics(new Tactics2(hb1));
}
}
class Ex13 {
private static void examineTactics(Tactics t){
for(int i=1; i<=20 ; i++){
System.out.print(i+": "+t.getHand()+" ");
}
System.out.println();
}
public static void main(String[] arg){
final HandBuilder hb = new HandBuilder1();
examineTactics(new Tactics1(hb));
examineTactics(new Tactics2(hb));
}
}
なお、三行目はランダムに出るので、必ず上記のようになるわけではありませ ん。 Gu, Choki, Pa が大体 1/3 出ていれば構いません。 しかし、他の行は必ず上記の出力と一致すること。
下記のクラス Box を追加します。
class Box {
private Player player1, player2;
public Box(){}
public void setPlayer1(Player p){
player1 = p;
}
public void setPlayer2(Player p){
player2 = p;
}
public Hand[] play(){
final Hand[] result = new Hand[2];
result[0]=player1.getHand();
result[1]=player2.getHand();
switch(result[0].wins(result[1])){
case -1:
player1.lose();
player2.win();
break;
case 0:
player1.draw();
player2.draw();
break;
case 1:
player1.win();
player2.lose();
break;
}
return result;
}
}
このプログラムが動作するように Player クラスを作成しなさい。
Player クラスには、 getHand(),
wins()
win()
, lose(), draw() メソッドを実装し
ます。
さらに、次の条件にも合致するようにメソッドを実装して下さい。
名前 : 勝った数 win(s), 負けた数 lose(s), 引き分けの数 draw(s)
そして、下記のテストプログラムで動作を確認しなさい。
class Tactics0 implements Tactics {
public Tactics0(HandBuilder hb){
setHandBuilder(hb);
}
private HandBuilder hb;
public void setHandBuilder(HandBuilder hb){
this.hb = hb;
}
public Hand getHand(){
return hb.getInstance(1);
}
}
class Ex142 {
private static int round=0;
private static void test(Tactics t1, Tactics t2){
System.out.println("テスト"+(++round));
final Player player1 = new Player("Kaiji");
player1.setTactics(t1);
final Player player2 = new Player("Funai");
player2.setTactics(t2);
final Box box = new Box();
box.setPlayer1(player1);
box.setPlayer2(player2);
for(int i=1; i<=10; i++){
Hand[] h = box.play();
System.out.println(i+": "+h[0]+" v.s. "+h[1]);
}
System.out.println(player1.result());
System.out.println(player2.result());
}
public static void main(String[] arg){
final HandBuilder hb0 = new HandBuilder0();
final HandBuilder hb1 = new HandBuilder1();
test(new Tactics1(hb0), new Tactics0(hb0));
test(new Tactics1(hb1), new Tactics0(hb1));
test(new Tactics2(hb1), new Tactics0(hb1));
test(new Tactics2(hb1), new Tactics2(hb0));
test(new Tactics1(hb1), new Tactics2(hb1));
}
}
class Ex14 {
public static void main(String[] arg){
final HandBuilder hb = new HandBuilder1();
final Player player1 = new Player("Kaiji");
player1.setTactics(new Tactics1(hb));
final Player player2 = new Player("Funai");
player2.setTactics(new Tactics2(hb));
final Box box = new Box();
box.setPlayer1(player1);
box.setPlayer2(player2);
for(int i=1; i<=50; i++){
Hand[] h = box.play();
System.out.println(i+": "+h[0]+" v.s. "+h[1]);
}
System.out.println(player1.result());
System.out.println(player2.result());
}
}
テスト1 1: Gu v.s. Gu 2: Gu v.s. Gu 3: Gu v.s. Gu 4: Gu v.s. Gu 5: Gu v.s. Gu 6: Gu v.s. Gu 7: Gu v.s. Gu 8: Gu v.s. Gu 9: Gu v.s. Gu 10: Gu v.s. Gu Kaiji: 0 win(s), 0 lose(s), 10 draw(s) Funai: 0 win(s), 0 lose(s), 10 draw(s) テスト2 1: Choki v.s. Choki 2: Choki v.s. Choki 3: Gu v.s. Choki 4: Choki v.s. Choki 5: Gu v.s. Choki 6: Choki v.s. Choki 7: Choki v.s. Choki 8: Pa v.s. Choki 9: Choki v.s. Choki 10: Choki v.s. Choki Kaiji: 2 win(s), 1 lose(s), 7 draw(s) Funai: 1 win(s), 2 lose(s), 7 draw(s) テスト3 1: Gu v.s. Choki 2: Choki v.s. Choki 3: Pa v.s. Choki 4: Gu v.s. Choki 5: Choki v.s. Choki 6: Pa v.s. Choki 7: Gu v.s. Choki 8: Choki v.s. Choki 9: Pa v.s. Choki 10: Gu v.s. Choki Kaiji: 4 win(s), 3 lose(s), 3 draw(s) Funai: 3 win(s), 4 lose(s), 3 draw(s) テスト4 1: Gu v.s. Gu 2: Choki v.s. Gu 3: Pa v.s. Gu 4: Gu v.s. Gu 5: Choki v.s. Gu 6: Pa v.s. Gu 7: Gu v.s. Gu 8: Choki v.s. Gu 9: Pa v.s. Gu 10: Gu v.s. Gu Kaiji: 3 win(s), 3 lose(s), 4 draw(s) Funai: 3 win(s), 3 lose(s), 4 draw(s) テスト5 1: Pa v.s. Gu 2: Gu v.s. Choki 3: Pa v.s. Pa 4: Gu v.s. Gu 5: Pa v.s. Choki 6: Choki v.s. Pa 7: Pa v.s. Gu 8: Choki v.s. Choki 9: Gu v.s. Pa 10: Pa v.s. Gu Kaiji: 5 win(s), 2 lose(s), 3 draw(s) Funai: 2 win(s), 5 lose(s), 3 draw(s)
なお、上記の勝敗の数字の一部は乱数によって変化しますので、この通りの出力が必ず出るわけではありません。 自ら行った各テストがそれぞれ成功しているかどうか、理由をつけて説明しなさい。 また、レポート作成時には、テスト結果全てを添付して下さい。
HandBuilder1 クラスの getInstance は毎回 Hand オブジェクトを作成しています。 しかし、実際に必要なのは Gu, Choki, Pa のそれぞれのオブジェクトだけで す。 そこで、シングルトンデザインパターンのような考え方で、オブジェクトは Gu, Choki, Pa の 3 つしか生成しない getInstance メソッドを持つ HandBuilder2 を作成しなさい。 なお、必要であれば、 Hand1 など他のクラスも置き換えても構いません。
そして、次のテストプログラムにおいて、 Ok が 3 つ出ることを確認しなさ い。
class Ex152 {
public static void main(String[] arg){
final HandBuilder hb = new HandBuilder2();
final Hand[][] h = new Hand[3][2];
for(int j=0; j<2; j++){
for(int i=0; i<3; i++){
h[i][j] = hb.getInstance(i);
}
}
for(int i=0; i<3; i++){
System.out.print(h[i][0]);
if(h[i][0]==h[i][1]){
System.out.println(" Ok");
}else{
System.out.println(" NG");
}
}
}
}
class Ex15 {
public static void main(String[] arg){
final HandBuilder hb = new HandBuilder2();
for(int i=0; i<3; i++){
final Hand h1 = hb.getInstance(i);
final Hand h2 = hb.getInstance(i);
System.out.print(h1);
if(h1==h2){
System.out.println("Ok");
}else{
System.out.println("NG");
}
}
}
}
Gu Ok Choki Ok Pa Ok
そして、次のプログラムを動作させ、効果を確かめなさい。 なお、下記のプログラムにおいて heap エラーが出るときは、繰り返し回数を 10万回に減らしても良い。
Ex16 は HandBuilder1 のテストを行った後、 HandBuilder2 のテストを行っていました。 そのため、HandBuilder1 が確保したメモリーを流用して動作していた可能性があります。 つまり、HandBuilder2 のテストを単体で動作させたときよりも、 HandBuilder1 のテストを行った後に HandBuilder2 のテストを行った方が動作が高速になる可能性があります。 そのため、下記のように Ex162 としてそれぞれが単独でしか動作しないように改めました。 java Ex162 1 と動かすと HandBuilder1 が動作し、 java Ex162 2 で動かすと HandBuilder2 が動作します。 これをそれぞれでたらめな順番で 5 回位計測して平均をとると、それなりに正確な計測になると期待できます。
Ex162 で計測を行うと、HandBuilder1 と HandBuilder2 で実行時間に 3 倍も違いがでたりはしないようです。 極端な結果の出るようなプログラムを与えて、勘違いを招くようなことをしてしまったことに関して、お詫びいたします。
import java.util.Date;
import java.util.ArrayList;
class StopWatch {
private Date now;
public StopWatch(){
now = new Date();
}
@Override public String toString(){
final Date next = new Date();
double result = (double)( next.getTime()-now.getTime())/1000;
now = next;
return String.valueOf(result);
}
}
class Ex162 {
public static void main(String[] arg){
final HandBuilder hb = arg[0].equals("1")
? new HandBuilder1()
: new HandBuilder2();
final StopWatch sw = new StopWatch();
test(hb);
System.out.println(sw);
}
/* class Ex16 {
public static void main(String[] arg){
final StopWatch sw = new StopWatch();
test(new HandBuilder1());
System.out.println(sw);
test(new HandBuilder2());
System.out.println(sw);
}
*/
private static void test(HandBuilder hb){
final Player player1 = new Player("Kaiji");
player1.setTactics(new Tactics1(hb));
final Player player2 = new Player("Funai");
player2.setTactics(new Tactics2(hb));
final Box box = new Box();
box.setPlayer1(player1);
box.setPlayer2(player2);
final ArrayList<Hand[]> list = new ArrayList<Hand[]>();
for(int i=1; i<=1000000; i++){
final Hand[] result = box.play();
list.add(result); // (*)
}
System.out.println(player1.result());
System.out.println(player2.result());
}
}
上記の Ex16 の中の (*) の行を取り除くと、実行速度の違いが大きく変わり ます。 この原因を考察しなさい。
各問にあるテストプログラムに関して、どのように動作して作成したメ ソッドが呼び出されるのかを説明しなさい。
なお、作成するプログラムは全部合計で 100 行強程度です。
レポート締切日:
提出先: レポートボックス
4年生は冬休み中もやりとり可能なメールアドレスをレポートに記入すること(hotmail は不可です)。 また、PDF によるレポートのやりとりを行えるようにしておくこと。 冬休み中に電子メールで PDF によるレポートのやりとりができないと、合格できない場合が生じるので注意すること。
提出締切り日にインフルエンザ等の病気を理由に登校できない状況においては、 2,3 年生についても PDF ファイルによる電子メールでの提出を許可する場合が あります。 そのため、 PDF ファイルの作成法や電子メールでの提出可能な環境の整備等は、 保険として準備しておくことをお勧めします。 ワープロなどのファイルをPDF ファイルとして出力するソフトウェアは無料でも 有料でも入手できます。
なお、この問題も既に２ちゃんねるに質問され、解答が出ました。 この問題に関しても、今後、同じ質問をあちこちで何度もするのはマナー違反ですので、お控え下さい(12/3)。
はじめに、型 E の配列を受け取って java.util.Set<E> として動作する tdu.TDUSet<E> を作成します。 これは java.util.AbstractSet<E> を継承し、配列を受け取るコンスト ラクタと、 size() メソッドと iterator メソッドを実装するだけで実現できます。 なお、この TDUSet に関しては add や remove などの要素を変更するような実装は 一切しないことにします。 そのため、下記のように実装しました。
package tdu;
import java.util.AbstractSet;
import java.util.Iterator;
public class TDUSet<E> extends AbstractSet<E>{
private E[] set;
public TDUSet(E[] array){
set = array;
}
public int size(){
return set.length;
}
public Iterator<E> iterator(){
return new TDUIterator<E>(set);
}
}
これが動作するように tdu.TDUIterator<E> を作成しなさい。 なお、 public void remove() に関しては、何もしないメソッドて構いません。 また、下記のテストプログラムが動作することを確かめなさい。
import tdu.*;
import java.util.Set;
class Ex21 {
private static <E> void print(Set<E> s){
for(E e : s){
System.out.println(e);
}
}
public static void main(String[] arg){
final Integer[] array = {9,1,2,8,3,4,5,7,6};
final TDUSet<Integer> set = new TDUSet<Integer>(array);
print(set);
System.out.println(set);
}
}
次に、 java.util.Map<String,Integer> として動作するクラスを作成 することを考えます。 そのため、まず、java.util.Map.Entry<String,Integer> として動作し、 二分木の節となるクラス TDUMapEntry を下記のように作成しました。
package tdu;
import java.util.AbstractMap;
public class TDUMapEntry extends AbstractMap.SimpleEntry<String,Integer>
{
public TDUMapEntry(String s ,Integer i){
super(s,i);
left=null;
right=null;
}
public TDUMapEntry left, right;
}
次に、 java.util.AbstractMap<String,Integer> を実装したクラス TDUMap1 を下記のように作成しました。 但し、このクラスは TDUMapEntry で作られた二分木に対して、サイズ(節点の数)を返すメソッド int size() を実装することだけを目標として考えます。 これを、途中まで作成したのが下記のクラスです。
package tdu;
import java.util.AbstractMap;
import java.util.Set;
import java.util.Map;
public class TDUMap1 extends AbstractMap<String,Integer> {
protected TDUMapEntry root;
public TDUMap1(){
root=null;
}
public TDUMap1(TDUMapEntry root){
this.root = root;
}
@Override public int size(){
return size(root);
}
@Override
public Set<Map.Entry<String,Integer>> entrySet(){
return null;
}
private int size(TDUMapEntry p){
}
}
これに対して、二分木のサイズがきちんと返るように private int size(TDUMapEntry p) という関数を実装しなさい。 そして、次のテストプログラムで正常に動作することを確かめなさい。 なお、プログラムの説明には、下記のテストプログラムにおいて、 printSize を呼び出すときの木構造を図示したもの作成し、 size がどのよう に動作するか説明すること。
import tdu.*;
class Ex22 {
private static void printSize(TDUMapEntry e){
final TDUMap1 m = new TDUMap1(e);
System.out.println(m.size());
}
public static void main(String[] arg){
final TDUMapEntry e1 = new TDUMapEntry("abc",123);
final TDUMapEntry e2 = new TDUMapEntry("def",456);
final TDUMapEntry e3 = new TDUMapEntry("ghi",789);
final TDUMapEntry e4 = new TDUMapEntry("jkl",12);
final TDUMapEntry e5 = new TDUMapEntry("mno",345);
final TDUMapEntry e6 = new TDUMapEntry("pqr",678);
printSize(null);
printSize(e1);
e1.left=e2;
printSize(e1);
e1.right=e3;
printSize(e1);
e2.left=e4;
e2.right=e5;
e3.right=e6;
printSize(e1);
}
}
次に、 TDUMap1 を継承し、 entrySet() を正常に出力するようなクラス TDUMap2 を作ります。 もともと、java.util.AbstractMap は、この entrySet() だけを実装すれば動 作するようになっていますので、これを実装することで正常な java.util.Map として動作するようになります。 entrySet() を作成するために次のアルゴリズムを考えます。 大まかな方針は、まずTDUMapEntry の木構造から java.util.Map.Entry<String,Integer> の配列を作り、次に TDUSet に渡 したものを 戻り値として返すことです。
上記に基づいて途中まで作成したのが下記の TDUMap2 クラスです。 これが正常に動作するように private void traverse(TDUMapEntry e) を実装 しなさい。
package tdu;
import java.util.Map;
import java.util.Set;
public class TDUMap2 extends TDUMap1 {
public TDUMap2(){
super();
}
public TDUMap2(TDUMapEntry root){
super(root);
}
private Map.Entry<String,Integer>[] array;
private int index;
@SuppressWarnings({"unchecked"})
@Override
public Set<Map.Entry<String,Integer>> entrySet(){
final int size = size();
if(size==0){
return null;
}
array = (Map.Entry<String,Integer>[]) new Map.Entry[size];
index=0;
traverse(root);
return new TDUSet<Map.Entry<String,Integer>>(array);
}
private void traverse(TDUMapEntry p){
}
}
これが正常に動作することを確かめるために、下記のプログラムを実行し、正 しい値が得られるか調べなさい。 なお、プログラムの説明には、下記のテストプログラムにおいて、 printMap を呼び出すときの木構造と、 traverse で作成する配列をそれぞれ 図示したもの作成し、 traverse がどのように動作するか説明すること。
import tdu.*;
class Ex23 {
private static void printMap(TDUMapEntry e){
final TDUMap2 m = new TDUMap2(e);
System.out.println(m.entrySet());
for(String str : m.keySet()){
System.out.print(" "+str+": "+m.get(str));
}
System.out.println();
}
public static void main(String[] arg){
final TDUMapEntry e1 = new TDUMapEntry("abc",123);
final TDUMapEntry e2 = new TDUMapEntry("def",456);
final TDUMapEntry e3 = new TDUMapEntry("ghi",789);
final TDUMapEntry e4 = new TDUMapEntry("jkl",12);
final TDUMapEntry e5 = new TDUMapEntry("mno",345);
final TDUMapEntry e6 = new TDUMapEntry("pqr",678);
printMap(e1);
e1.left=e2;
printMap(e1);
e1.right=e3;
printMap(e1);
e2.left=e4;
printMap(e1);
e2.right=e5;
printMap(e1);
e3.right=e6;
printMap(e1);
}
}
[abc=123] abc: 123 [def=456, abc=123] def: 456 abc: 123 [def=456, abc=123, ghi=789] def: 456 abc: 123 ghi: 789 [jkl=12, def=456, abc=123, ghi=789] jkl: 12 def: 456 abc: 123 ghi: 789 [jkl=12, def=456, mno=345, abc=123, ghi=789] jkl: 12 def: 456 mno: 345 abc: 123 ghi: 789 [jkl=12, def=456, mno=345, abc=123, ghi=789, pqr=678] jkl: 12 def: 456 mno: 345 abc: 123 ghi: 789 pqr: 678
最後に TDUMap3 として put メソッドにより要素を追加できるように実装し ます。 TDUMap3 は TDUMap2 を継承し、 put(String s, Integer i) をオーバライド するクラスです。 put は次のように実装します。
これが正常に動作するように、 private Integer put2(TDUMapEntry p, TDUMapEntry e) を実装しなさい。 なお、この実装する put2(TDUMapeEntry p, TDUMapEntry e) の仕様は次の通りです。
package tdu;
public class TDUMap3 extends TDUMap2 {
public TDUMap3(){
super();
}
@Override
public Integer put(String s, Integer i){
final TDUMapEntry e = new TDUMapEntry(s,i);
if(root==null){
root=e;
return null;
}
return put2(root,e);
}
private Integer put2(TDUMapEntry p, TDUMapEntry e){
}
}
作成したプログラムが正常に動作するかどうか、下記のテストプログラムを動 かし java.util.TreeMap と同等の出力が得られるか確かめなさい。 なお、下記のプログラムにおいて TDUMap3 の初期状態、 test("jkl",12) の呼び出し、 test("def",456) の呼び出し、 test("pqr",678) の呼び出し、 test("mno",567) の呼び出しに関して、TDUMap3 の内 部の木の構造を示し、 put2 がどのように動作するかを木の構造を用いて説明 しなさい。 なお、完全に同じにはならないので、同じでない点については指摘すること。
テストプログラムを差し替えました。 もう、4 年生の締切り間近なので、レポートには反映させなくても構いません。 但し、 TDUMap3 が下記の Ex243 でも正常に動作しないと合格できませんので、 チェックをお願いします。
import java.util.Map;
import java.util.TreeMap;
import tdu.*;
class Ex243 {
private static Map<String,Integer> map;
public static void test(Map<String,Integer> m){
map = m;
System.out.println(m.getClass().getName()+":");
System.out.println(m.entrySet());
test("jkl",12);
test("def",456);
test("mno",345);
test("abc",123);
test("ghi",789);
test("pqr",678);
test(new String("jkl"),901);
test("ABC",456);
test("def",234);
test("mno",567);
}
private static void test(String s, int i){
System.out.println("previous: "+map.put(s,i));
System.out.println("EntrySet: "+map.entrySet());
for(String str : map.keySet()){
System.out.print(" "+str+": "+map.get(str));
}
System.out.println();
}
@SuppressWarnings({"unchecked"})
final private static Map<String,Integer>[] maps
= (Map<String,Integer>[])
new Map[]{ new TreeMap<String,Integer>()
,new TDUMap3()};
public static void main(String[] arg){
for(Map<String,Integer> m : maps){
test(m);
}
}
}
import java.util.Map;
import java.util.TreeMap;
import tdu.*;
class Test {
final private Map<String,Integer> m;
public Test(Map<String,Integer> m){
this.m = m;
}
public void execute(){
System.out.println(m.getClass().getName()+":");
System.out.println(m.entrySet());
test("jkl",12);
test("def",456);
test("mno",345);
test("abc",123);
test("ghi",789);
test("pqr",678);
test("jkl",901);
test("def",234);
test("mno",567);
}
private void test(String s, int i){
System.out.println("previous: "+m.put(s,i));
System.out.println("EntrySet: "+m.entrySet());
for(String str : m.keySet()){
System.out.print(" "+str+": "+m.get(str));
}
System.out.println();
}
}
class Ex242 {
@SuppressWarnings({"unchecked"})
final private static Map<String,Integer>[] maps
= (Map<String,Integer>[])
new Map[]{ new TreeMap<String,Integer>()
,new TDUMap3()};
public static void main(String[] arg){
for(Map<String,Integer> m : maps){
final Test t = new Test(m);
t.execute();
}
}
}
import tdu.*;
class Ex24 {
private static void test(String s, int i){
m.put(s,i);
System.out.println(m.entrySet());
for(String str : m.keySet()){
System.out.print(" "+str+": "+m.get(str));
}
System.out.println();
}
private static TDUMap3 m;
public static void main(String[] arg){
m = new TDUMap3();
System.out.println(m.entrySet());
test("jkl",12);
test("def",456);
test("mno",345);
test("abc",123);
test("ghi",789);
test("pqr",678);
}
}
発展問題2-5
上記で実装した put はデータの順序がランダムになっているときは
要素数 n に対して平均で O(log n) 程度の時間で要
素の追加ができる。
しかし、 get に関してはそのようになっていない。
この場合 get はどのように動作するのかマニュアルを参考に説明しなさい。
さらに、 TDUMap3 を継承し、平均で O(log n) で動作するような
get を実装したクラス TDUMap4 を作りなさい。
また、正常に動作することを確認できるようなテストを作成し、テスト結果を
報告しなさい。
発展問題2-6
Generics を使用し、任意の型 K, V を登録できる TDUMap5<K,V> を作
りなさい。
また、正常に動作することを確認できるようなテストを作成し、テスト結果を
報告しなさい。
発展問題2-7
二分木の登録アルゴリズムとして、入力系列によらず追加、検索とも O(log
n) 時間で動作する赤黒木があります。
実際、 java.util.TreeMap の実装にはこの赤黒木が使用されています。
赤黒木のアルゴリズムを実装した TDUMap6 を作成しなさい。
また、正常に動作することを確認できるようなテストを作成し、テスト結果を
報告しなさい。
プログラム
上記のプログラムをまとめたものを
ダウンロード
できます。
課題2のレポート作成上の注意
プログラムの動作の説明において、特定のデータ構造を例示し、図示して説明
すること。
但し、図とプログラムに矛盾がある場合、不合格になります。
今回の合否の分水嶺は、課題 2-2, 2-3, 2-4 の再帰のプログラムの説明にお
ける終了条件の説明がプログラムと矛盾している点であろうと考えております。
ご注意下さい。
採点基準
-
問題をちゃんと理解すること。
特に解答が楽になるようにとか、「わかりやすく」とか「しっかり」など、非
科学的な理由で勝手に問題を作り替えてはいけません。
-
プログラムが正常に動作すること。
指定した出力を正確に出すこと。
また、指定していない表示を行わないこと。
さらに、多少の動作条件の変化に対して、正常に対応できること。
特に、テストに対しては正常に動作しても、考えうる他の正常な入力に対して暴走するようなプログラムは不可です。
-
実行例を付けること。
実行可能なプログラムに関して、正しく実行された実行例を必ずつけること。
なお、問題の趣旨を理解しており、膨大な出力のうち、全ての出力が必ずしも
必要ないと判断される場合は、出力の一部を省略しても良い。
-
説明が適切であること。
プログラムの内容を正しく説明していなければなりません。
また、テストの内容を理解し、テスト結果からプログラムが正常であることを
理由を付けて判定すること。
レポート作成上の注意点
- プログラミングのレポートでは必ずプログラムの説明をすること。
その時に、一行一行を日本語に直訳するのではなく、データの読み込みとか、
出力とかの部分に分割し、機能毎に使用した手法を説明すること。
プログラム中にコメントを入れてもプログラムの説明とはみなさないので注意
する事。
プログラムの説明ではつぎのように説明をしてください。
- プログラム全体の構成
- 各部分の機能
- それぞれの機能を実現するために行ったプログラミング上の工夫
- 「問題を解きなさい」という問に対して「解きました。合ってました」で
は正解ではないことはわかるはず。
「テストしなさい」という問に対しては、テストの方法の説明、実際のテスト
の実施方法、テスト結果、検証などを説明して下さい。
- レポートは手書きでもワープロでも構いません。但し、実行結果はコン
ピュータの出力を添付すること。
また、なるべく白黒で作成すること。実行結果などでどうしても色が付いてしまうような場合はそのままで構いません。
実行結果が無いレポートは不合格です。
- 考察は必ず書いて下さい。
- 不必要なことはなるべく書かない事。
長過ぎるレポートは減点します。またなるべく両面印刷にしてください。
但し、文字は必要以上に小さくしない事。レポート本文の文字は 10 ポイント
以上のものを使う事。
なお、写したと思われるほど酷似したレポートが複数提出された場合、原著が
どれかの調査を行わず、抽選で一通のレポートのみを評価
の対象とし、他は提出済みの不合格レポートとして再提出は課しません。
自分で意図せずに他人にコピーされてしまった場合も同様ですので、レポート
の取り扱いについては十分に注意して下さい。
坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科