Java 7 を使用してすること(なお、発展課題は解答しなくても不合格の原因にはならない)。
レポートには表紙をつけてください。
提出先: 2号館レポートボックス
順序木を利用し、キーの値で値を整列するデータ構造を作成することを考えま す。 そのためには、java.util.Map を実装し、 java.util.AbstractMap を継承し、 最小限のプログラムで動作させます。 まず、文字列をキーとして、整数値を整列するような TDUMap3 を目標としま す。 完成した後、Generics を利用した任意の型のキーと値を使用できる TDUMap を作成します。
こちらで用意したプログラムはすべて kadai フォルダに入っており、 kadai パッケージに含まれます。 また、テストプログラムを用意したので、活 用すること。 解答のプログラムは kaitou パッケージに作成しなさい。
はじめに、型 E の配列を受け取って java.util.Set<E> として動作する kadai.TDUSet<E> を作成します。 これは java.util.AbstractSet<E> を継承し、配列を受け取るコンスト ラクタと、 size() メソッドと iterator メソッドを実装するだけで実現できます。 なお、この TDUSet に関しては add や remove などの要素を変更するような実装は 一切しないことにします。 そのため、下記のように実装しました。
package kadai;
import java.util.AbstractSet;
import java.util.Iterator;
import kaitou.TDUIterator;
public class TDUSet<E> extends AbstractSet<E>{
private E[] set;
public TDUSet(E[] array){
set = array;
}
@Override
public int size(){
return set.length;
}
@Override
public Iterator<E> iterator(){
return new TDUIterator<E>(set);
}
}
これが動作するように kaitou.TDUIterator<E> を作成しなさい。 なお、 public void remove() に関しては、 java.lang.UnsupportedOperationException 例外を投げなさい。 これをテストするために、 TDUSetTest, TDUIteratorTest を利用しなさい。
次に、キーとして文字列、データとして整数値を持つようなクラスを java.util.Map<String,Integer> の実装として作成することを考えます。 そのため、まず、二分木の節となるクラスを java.util.Map.Entry<String,Integer> を実装したクラスが必要です。 そのため、 TDUMapEntry1 を java.util.AbstractMap.SimpleEntry<String,Integer>を継承し、 下記のように作成しました。
package kadai;
import java.util.AbstractMap;
public class TDUMapEntry1 extends AbstractMap.SimpleEntry<String,Integer>
{
private static final long serialVersionUID = 1L;
public TDUMapEntry1(String s ,Integer i){
super(s,i);
left=null;
right=null;
}
public TDUMapEntry1 left;
public TDUMapEntry1 right;
}
次に、TDUMap1 を java.util.AbstractMap<String,Integer> を継承し て作成することを考えます。 但し、このクラスは TDUMapEntry1 で作られた二分木に対して、根のオブジェ クトの参照からサイズ(節点の数)を返すメソッド int size() を実装すること だけを目標として考えます。 まずkadai.AbstractTDUMap1 を下記のように作成しました。
package kadai;
import java.util.AbstractMap;
import java.util.Set;
import java.util.Map;
public abstract class AbstractTDUMap1 extends AbstractMap<String,Integer> {
protected TDUMapEntry1 root;
protected AbstractTDUMap1(){
root=null;
}
protected AbstractTDUMap1(TDUMapEntry1 root){
this.root = root;
}
@Override
final public int size(){
return size2(root);
}
@Override
public Set<Map.Entry<String,Integer>> entrySet(){
return null;
}
protected abstract int size2(TDUMapEntry1 p);
}
これを継承し、二分木のサイズがきちんと返るように protected int size2(TDUMapEntry1 p) という関数を実装したクラス kaitou.TDUMap1 を作成しなさい。 これのテストには、 TDUMap1Test を使用しなさい。 なお、レポートに報告するには、この TDUMap1Test の size() メソッド呼び 出し箇所( assertEquals(0,m.size()), assertEquals(1,m.size()), assertEquals(2,m.size()), assertEquals(3,m.size()), assertEquals(6,m.size()) の 5箇所)におけるデータの木構造を図示したもの作成し、それぞれ size がどのように動作するか説明すること。
次に、 TDUMap1 を継承し、 entrySet() を正常に出力するようなクラス TDUMap2 を作ります。 もともと、java.util.AbstractMap は、この entrySet() だけを実装すれば動 作するようになっていますので、これを実装することで正常な java.util.Map として動作するようになります。 entrySet() を作成するために次のアルゴリズムを考えます。 大まかな方針は、まずTDUMapEntry1 の木構造から java.util.Map.Entry<String,Integer> の配列を作り、次に TDUSet に渡 したものを 戻り値として返すことです。
上記に基づいて途中まで作成したのが下記の AbstractTDUMap2 クラスです。 これを継承し、正常に動作するようにTDUMap2を作成しなさい。
package kadai;
import java.util.Map;
import java.util.Set;
import kaitou.TDUMap1;
public abstract class AbstractTDUMap2 extends TDUMap1 {
protected AbstractTDUMap2(){
super();
}
protected AbstractTDUMap2(TDUMapEntry1 root){
super(root);
}
protected Map.Entry<String,Integer>[] array;
protected int index;
@SuppressWarnings("unchecked")
@Override
public Set<Map.Entry<String,Integer>> entrySet(){
array = (Map.Entry<String,Integer>[]) new Map.Entry[size()];
index=0;
traverse(root);
return new TDUSet<Map.Entry<String,Integer>>(array);
}
protected abstract void traverse(TDUMapEntry1 p);
}
これが正常に動作することを確かめるために、TDUMap2Testを使用しなさい。 なお、プログラムの説明には、TDUMap2Testの各 entrySet() のうち、要素数0,1,3,6のそれぞれの呼び出し を呼び出すとき の木構造 と、 traverse で作成する配列をそれぞれ図示したもの作成し、 traverse がどのように動作するか説明すること。 但し、同じ結果になる場合は重複させなくてよい。
最後に TDUMap3 として put メソッドにより要素を追加できるように実装し ます。 put は次のように実装します。
ここまでを実装したクラス kadai.AbstractTDUMap3 を以下に示します。 これを継承し、 protected Integer put2(TDUMapEntry p, TDUMapEntry e) を実装したクラス TDUMap3 を作りなさい。 なお、この実装する put2(TDUMapeEntry p, TDUMapEntry e) の仕様は次の通りです。
package kadai;
import kaitou.TDUMap2;
public abstract class AbstractTDUMap3 extends TDUMap2 {
protected AbstractTDUMap3(){
super();
}
@Override
public Integer put(String s, Integer i){
final TDUMapEntry1 e = new TDUMapEntry1(s,i);
if(root==null){
root=e;
return null;
}
return put2(root,e);
}
protected abstract Integer put2(TDUMapEntry1 p, TDUMapEntry1 e);
}
作成したプログラムが正常に動作するかどうか、TDUMap3Testを使用して確かめなさい。 なお、TDUMap3Test において TDUMap3 の初期状態、 put("jkl",12) の呼び出し、 put("def",456) の呼び出し、 put("pqr",678) の呼び出し、 put("mno",567) の呼び出しに関して、TDUMap3 の内 部の木の構造を示し、 put2 がどのように動作するかを木の構造を用いて説明 しなさい。
Generics を使用し、任意の型 K, V を登録できる TDUMap<K extends Comparable<? super K>,V> を作ることを考える。 これを実現するため、Generics に対応した kadai.TDUMapEntry<K,V> を次のように定義する。
package kadai;
import java.util.AbstractMap;
public class TDUMapEntry<K,V> extends AbstractMap.SimpleEntry<K,V>
{
private static final long serialVersionUID = 1L;
public TDUMapEntry(K s ,V i){
super(s,i);
left=null;
right=null;
}
public TDUMapEntry<K,V> left;
public TDUMapEntry<K,V> right;
}
これを用いて、TDUMap を作成しなさい。 なお、作成すべきメソッド、フィールドなどは概ね次のようになるはずです。
package kaitou;
import java.util.AbstractMap;
import java.util.Map;
import java.util.Set;
import kadai.TDUMapEntry;
import kadai.TDUSet;
public class TDUMap<K extends Comparable<? super K>, V> extends AbstractMap<K, V> {
private TDUMapEntry<K,V> root;
public TDUMap(){...}
public TDUMap(TDUMapEntry<K,V> root){...}
@Override
public int size(){...}
private int size2(TDUMapEntry<K,V> p) {...}
private Entry<K, V>[] array;
private int index;
@SuppressWarnings("unchecked")
@Override
public Set<Entry<K, V>> entrySet(){...}
private void traverse(TDUMapEntry<K,V> p) {...}
@Override
public V put(K s, V i){...}
private V put2(TDUMapEntry<K,V> p, TDUMapEntry<K,V> e) {...}
}
これが正常に動作することを TDUMapTestによりテスト結果を 報告しなさい。
下記のプログラム test.TDUMapDemo がどのようなプログラムか説明しなさい。 そして、HashMap, TreeMap, TDUMap についてそれぞれ 5 回測定し、結果を比較しなさい。 また、どうしてそのような結果になったかを考察しなさい。
package test;
import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;
import kaitou.TDUMap;
public class TDUMapDemo {
final private static int n = 10000;
final private static int wordLength = 5;
public static void main(String[] args) {
@SuppressWarnings("unchecked")
Map<String,Double>[] maps = (Map<String, Double>[])(new Map[]{
new HashMap<String,Double>(),
new TreeMap<String,Double>(),
new TDUMap<String,Double>()
});
int k = (int)(Math.random() * maps.length);
String[] testWords = generateStrings(n);
double[] testDoubles = generateDouble(n);
StopWatch sw = new StopWatch();
test(maps[k],testWords,testDoubles);
System.out.println(maps[k].getClass().getName()+":"+sw);
}
private static void test(Map<String, Double> m, String[] testWords,
double[] testDoubles) {
for(int i=0; i<testWords.length; i++){
m.put(testWords[i], testDoubles[i]);
m.entrySet();
}
}
private static double[] generateDouble(int n2) {
double[] result = new double[n2];
for(int i=0 ; i<n2; i++){
result[i]=Math.random();
}
return result;
}
private static String[] generateStrings(int n2) {
String[] result = new String[n2];
for(int i=0; i<n2; i++){
result[i]=generateString(wordLength);
}
return result;
}
final private static String alphabets = "abcdefghijklmnopqrstuvwxyz";
private static String generateString(int i) {
StringBuilder result = new StringBuilder();
for(int j=0; j<i; j++){
result.append(alphabets.charAt((int)(Math.random()*alphabets.length())));
}
return result.toString();
}
}
package test;
import java.util.Date;
public class StopWatch {
private Date now ;
public StopWatch() {
now=new Date() ;
}
@Override
public String toString(){
Date next=new Date();
double time=(double)(next.getTime()-now.getTime())/1000.0 ;
now=next;
return String.valueOf(time);
}
}
上記のプログラムをまとめたものを ダウンロード できます。
プログラムの動作の説明において、特定のデータ構造を例示し、図示して説明 すること。 但し、図とプログラムに矛盾がある場合、不合格になります。
今回の合否の分水嶺は、課題 2-2, 2-3, 2-4 の再帰のプログラムの説明にお ける終了条件の説明がプログラムと一致しているか否かという点であろうと考 えています。 ご注意下さい。
なお、再帰が遅いという指摘がありますが、極端に遅いわけではありません。 次のプログラムを試すと、どの程度の遅さか分かると思います。
package test;
public class RecursiveTest {
public static final int N = 1000;
private static Job job;
interface Job {
void perform();
}
private static class Pi implements Job{
@Override
public void perform() {
double x = Math.PI*2.0;
}
}
private static class Sqrt implements Job{
@Override
public void perform() {
double x = Math.sqrt(2.0);
}
}
private static class Sin implements Job{
@Override
public void perform() {
double x = Math.sin(2.0);
}
}
private static class Log implements Job{
@Override
public void perform() {
double x = Math.log(2.0);
}
}
private static class Rand implements Job {
@Override
public void perform() {
double x = Math.random();
}
}
public static void main(String[] args) throws InterruptedException {
StopWatch sw = new StopWatch();
Job[] jobs = {new Pi(), new Rand(), new Sqrt(), new Sin(), new Log()};
int r = (int)(Math.random()*2);
job = jobs[(int)(Math.random()*jobs.length)];
switch(r){
case 0:
loop1(0);
break;
case 1:
rec1(0);
break;
}
System.out.println(r+","+job.getClass().getSimpleName()+":"+sw);
}
private static void loop1(int n) {
for(int i=n; i<N; i++)
loop2(0);
}
private static void loop2(int i) {
for(int j=i; j<N; j++)
loop3(0);
}
private static void loop3(int i) {
for(int k=i; k<N; k++){
job.perform();
}
}
private static void rec1(int n) throws InterruptedException{
if(n<N){
rec2(0);
rec1(n+1);
}
}
private static void rec2(int n) {
if(n<N){
rec3(0);
rec2(n+1);
}
}
private static void rec3(int n) {
if(n<N){
job.perform();
rec3(n+1);
}
}
}
古い問題は別ページへ
ランダムにカードを引いて集めることを考える。 そのために、部分的に開発したソフトウェア gacha の仕様の一部 の説明を別に示した。 さて、以下の設問において kotae パッケージを作り、 その中に指定されたクラスを作成せよ。
なお、テストクラスを用意したので、各設問 において、指示のあるテストクラスを用いてテストを行い、正常であった旨を 報告せよ。
player/Statistics1 を10回実行して、3種類のカードが揃うまでの回数を計測 し、平均値を求めなさい。
Deck1 のカードに加え、Rare カードとして (id=10, name="RareAka"), (id=11, name="RareAo"), (id=12, name="RareKuro"), となる 3 つの合計 6 種類のカードを持つ Deck2 クラス kotae パッケージに作成しなさい。 但し、これらのカード種自体は Deck2 の static メソッド getList により List<Card> 型のインスタンスが得られるようにすること。
なお、テスト用にDeck2Testプログラムを 用意したので、活用すること。
Deck2 を使う Main2, Statistics2 を示す。
package player;
import kotae.Deck2;
import java.io.IOException;
public class Main2 {
public static void main(String[] args) throws IOException {
new Player().play(new Deck2());
}
}
package player;
import kotae.Deck2;
public class Statistics2 {
public static void main(String[] arg){
int[] watchlist = {0,1,2,10,11,12};
Statistics s = new Statistics(watchlist, new Player(), new Deck2());
s.calc();
}
}
Statistics2 を10回実行して、6種類のカードが揃うまでの回数を計測 し、平均値を求めなさい。
次に、プレイヤーの手の揃い具合により、確率が変動するようなカード種 SuperRare を考える。 これは、カード種に対してプレイヤーの所持カードを見せることで、レア度を 変えるようにする。 つまり、まず、以下のようなメソッドを作成する。
ここまでを作成したクラスをAbstractSuperRareとして以下に示す。
package card;
import java.util.List;
import kotae.SuperRare;
import player.CardCollection;
public abstract class AbstractSuperRare extends AbstractCard {
private CardCollection cardcollection;
protected int zenmaisuu;
protected List<SuperRare> mokuhyou;
protected AbstractSuperRare(){
super();
}
protected final boolean alreadyOwned() {
return cardcollection.contains(this);
}
protected final void setMokuhyou(List<SuperRare> list) {
this.mokuhyou = list;
this.zenmaisuu = list.size();
}
public final void setCardCollection(CardCollection cc) {
this.cardcollection=cc;
}
}
このクラスを継承し、次の仕様を持つ rate メソッドを実装する SuperRare クラスを kotae パッケージに作りなさい。
なお、テスト用 にSuperRareTestプログラム を用意したので、活用すること。
また、 SuperRareFactory クラスを示す。
package card;
import java.util.List;
import player.CardCollection;
import kotae.SuperRare;
public class SuperRareFactory extends AbstractCardFactory<SuperRare> {
public SuperRareFactory(int num, String[] names) {
super(num, names, new SuperRare());
}
public List<SuperRare> getList(CardCollection cc){
List<SuperRare> list = super.getList();
for(SuperRare card : list){
card.setCardCollection(cc);
card.setMokuhyou(list);
}
return list;
}
}
SuperRareAka, SuperRareAo, SuperRareKuro と既存の Aka, Ao, Kuro を混ぜたDeck3 と、それを使う Main3, Statistics3 を示す。
package gacha;
import java.util.List;
import player.CardCollection;
import card.Card;
import card.SuperRareFactory;
public class Deck3 extends AbstractDeck {
public static List<Card> getList(CardCollection cardcollection){
List<Card> list= Deck1.getList();
String[] names = new String[]{"SuperRareAka", "SuperRareAo", "SuperRareKuro"};
SuperRareFactory superRareFactory = new SuperRareFactory(20,names);
list.addAll(superRareFactory.getList(cardcollection));
return list;
}
public Deck3(CardCollection cardcollection){
super(getList(cardcollection));
bunpu = new Bunpu3(this);
}
}
package player;
import gacha.Deck3;
import java.io.IOException;
public class Main3 {
public static void main(String[] args) throws IOException {
Player player = new Player();
player.play(new Deck3(player.collection));
}
}
package player;
import gacha.Deck3;
public class Statistics3 {
public static void main(String[] arg){
int[] watchlist = {0,1,2,20,21,22};
Player player = new Player();
Statistics s = new Statistics(watchlist, player, new Deck3(player.collection));
s.calc();
}
}
Statistics3 を10回実行して、6種類のカードが揃うまでの回数を計測 し、平均値を求めなさい。
「不当景品類及び不当表示防止法」4条の２や、告示された 「懸賞による景品類の提供に関する事項の制限」の第5項などを参照し、 本課題における実験結果と比較して、なぜこのような法律があるのか考察しな さい。
3種類のカードがそれぞれ確率1/3で出るとき、繰り返し引いて全種類揃うまで の平均試行回数を求めなさい。
なお、以上の提供したファイルをすべてまとめた 課題ファイル集 を用意した。
Eclipse のセッティングの方法
なお、問題訂正などでプログラムが変更になった場合、上記の最新のファイル 集をダウンロードした後で、作業中のプロジェクトでもう一度importして下さ い。 上書きするファイルが検出されるとダイアログが表示されますが、 Yes ALL で問題だけ最新の状態になるはずです。
なお、写したと思われるほど酷似したレポートが複数提出された場合、原著が どれかの調査を行わず、抽選で一通のレポートのみを評価 の対象とし、他は提出済みの不合格レポートとして再提出は課しません。 自分で意図せずに他人にコピーされてしまった場合も同様ですので、レポート の取り扱いについては十分に注意して下さい。