データ構造とプログラミング

課題提出方法

• 提出先メールアドレスは，2004f-dsap-report@crew.sfc.keio.ac.jp です．
• 本文の始めには，氏名，学籍番号，CNSログイン名を記入して下さい
• SFCのメールアドレスで送信してください
• ソースコードにはインデントをつけ、読みやすいように心がけてください
• 添付ファイルでの提出ではありません

• メール提出の課題はメール本文に書いて提出して下さい．
• プログラムのソースコードを提出する場合は添付しないで本文に書いて下さい．
• 全部できなかった場合には，3時間以上時間をかけず，できなかった理由を書いて提出してかまいません．

第13回課題

授業内の課題
メールの件名: dsap13-a
次の課題を授業内に行ってメールにて提出して下さい．
グラフにおける深さ優先探索(dfs.java)と 幅優先探索(bfs.java)のプログラムを解読し，日本語疑似コードを作れ．
(疑似コードを作る部分は，dfsメソッド，bfsメソッドの部分だけでよい)

1. 自分のプログラミング体験を全て説明し，今回の授業がどのような影響を自分に与えるかについて考察せよ．
2. 授業の感想を記し，授業の問題点と改善点があれば指摘せよ．

第12回課題

第11回課題(最終課題)

<式を作成>するとは{

	<項を作成>(メソッド呼び出し)して，それを「左項」ノードにする

	1文字読み，読んだ文字が+か-の演算子である場合，以下を操り返す{
    	読んだ文字を「演算子」ノードとして作成する
        項を作成(メソッド呼び出し)して，それを「右項」ノードにする             
        演算子ノードの左に「左項」ノードを付ける
        演算子ノードの右に「右項」ノードを付ける
        演算子ノードを「左項」ノードにする
	}
                
	「左項」ノードを返す
}


<項を作成>するとは{
	因子を作成(メソッド呼び出し)して，それを「因子」ノードにする
	「因子」ノードを返す
}


<因子を作成>するとは{
	1文字読み込む．
	読んだ文字を要素とする「因子」ノードを作成する
	「因子」ノードを返す
}

メール提出の課題
メールの件名: dsap11
締め切り:1月11日(火)12:00(正午)

1. ExpressionTree.javaを利用し， 式と項，因子の構文図に従って，式(中置式)を二分木構造にするプログラムを作成せよ．なお式は一桁の数のみ扱うこととする．
2. 前置式を表示する機能を１のプログラムに追加せよ．
3. 後置式を表示する機能を２のプログラムに追加せよ．
4. 中置式を表示する機能を３のプログラムに追加せよ．
5. キューを用いて二分木構造を表示する機能を４のプログラムに追加せよ．
6. （発展課題）複数桁の数を扱えるようにプログラムを変更せよ．

第10回課題

• 1+2
• 1+2*3
• 1+2*3-4
• 1+2*3-4/5

メールの件名: dsap10
締め切り:12月13日(月)12:00(正午)

1. CharTreeApp.javaを利用して， 1+2*3-4/5を二分木で表すプログラムを作りなさい．
2. ExpressionCalculator.javaを利用して， 入力した数式(括弧は含まず，数は1桁でよい)を二分木に変換するプログラムを作りなさい．
3. 2で作成したプログラムに計算機能を追加しなさい．
4. (発展課題)括弧を含む数式も計算できるように変更しなさい．

第9回課題

フィボナッチ数列は以下の式を満たす数列である．

• f(0)=1
• f(1)=1
• f(n)=f(n-1)+f(n-2)

フィボナッチ数列f(n)のnが7の場合の木構造を書きなさい．

(木構造の例)

メールの件名: dsap09
締め切り:12月7日(火)23:59(延期しました)

*課題2や発展課題まで作成した場合は最終的なプログラムのみを提出して下さい． 途中のプログラムは提出する必要はありません．

1. フィボナッチ数列を計算するプログラムを次の2通りで実装し，プログラムを作成せよ．
   (2通りの実装したものはそれぞれメソッドにし，1ファイルにして提出してかまいません．)
• 再帰
• 操り返し
2. 1で作成したプログラムに，計算回数(何回足したか)を数える機能を追加し， 操り返しと再帰の計算回数の差が分かるように変更せよ．
   (例えば，「操り返しによる計算回数→100回，再帰による計算回数→100回」と出力する)
3. フィボナッチ数列の計算は，操り返しと再帰ではどちらが効率的か，その理由を含めて考察せよ．
4. (発展)．操り返しと再帰の処理がどのように違うのか分かるように， ローカル変数や計算式を出力したり，
   再帰呼び出しの場合は，字下げなどをして処理の内容が理解しやすいよう表示を工夫して，実装せよ．

第8回課題

• 次の3つの式f(n)のnがn=1,n=2,n=3と増加する時，その結果を表にせよ
• f(n)=n!
• f(n)=10^n
• f(n)=n^10
(^はべき乗を表します．10^2は10の2乗の事です．)
• 階乗のプログラム(FactorialCalculator.java)
の 25行目からのトレース表を書きなさい．なお，factorial()メソッド内の処理も正確にトレースしなさい． なお，入力した整数は5とする．

メールの件名: dsap08
締め切り:11月29日(月)12:00(正午)

10進数の数を入力すると，2進数に変換するプログラムを，次の2通りで実装し，プログラムを提出せよ．
(2通りの実装したものはそれぞれメソッドにし，1ファイルにして提出してかまいません．)

1. くり返しを用いて実装せよ
2. 再帰を用いて実装せよ

第7回課題

削除する要素を指定できる連結リストにおいて，次の行の参照モデルを作成せよ

• 97行目直後
• 107行目delete()中の56行目直後
• 107行目delete()中の66行目直後
• 107行目delete()中の71行目直前

メールの件名: dsap07
締め切り:11月15日(月)12:00(正午)

*課題の2番目は1番目の改良なので，2番目までできたら，2番目のみを提出して下さい

1. ソート済みリストは，double型をデータとして 扱っているが， これをStudent型に変更せよ
• Student型は，名前(String型)，ふりがな(String型)，学籍番号(int型)を持つ
• Student型は，Item型を参考にして実装せよ
• なお，ソートはふりがな順(あ-お順)でソートせよ
• Student型の実装は，Item型の実装ようにカプセル化せよ
2. 1で作成したプログラムに，次の操作を行うテストプログラムを追加せよ
   (テストプログラムはソート済みリストのmain(70-84行目)を参考にせよ)
1. 名前「佐藤太郎」，ふりがな「さとうたろう」，学籍番号「70455555」のStudentをリストに追加する
2. 名前「井野花子」，ふりがな「いのはなこ」，学籍番号「70422222」のStudentをリストに追加する
3. Studentリストを表示する
4. 名前「木村正男」，ふりがな「きむらただお」，学籍番号「70477777」のStudentをリストに追加する
5. 名前「石井由美」，ふりがな「いしいゆみ」，学籍番号「70433333」のStudentをリストに追加する
6. 名前「長井武夫」，ふりがな「ながいたけお」，学籍番号「70411111」のStudentをリストに追加する
7. Studentリストを表示する
8. 1項目を削除する
9. Studentリストを表示する

第6回課題

1. 次の中置式を後置式に変換しなさい(教科書のような 表を作成する)
• 1*2+3/4
• (1+2)/(3-4)
• 1+2*3/(4-5)
2. 中置式→後置式変換プログラム(infix.java)と 後置式計算プログラム(postfix.java)をつなげて， 中置式を計算するプログラムを作成しなさい
3. (発展)2のプログラムは1桁の数字の計算しか出来ませんが， これを複数桁の数字でも計算できるようにしなさい

• できる人は発展課題までやって下さい．
• 課題1に関しては授業中に行い，終わり次第すぐにメール提出して下さい
• 後に提出する課題2，3のメールの件名は同じ(dsap06)で結構です
• プログラムに関しては必ず実行結果と考察をレポートする事

第5回課題

• スタックのプログラム(Stack.java)の51行目から61行目まで
• キューのプログラム(Queue.java)の68行目から87行目まで

String name = "tarou";
System.out.println( name.charAt(0) );

第4回課題

• 挿入ソート(insertSort.java) に番兵を組み込んで、速度を向上させたプログラム
• 上記のプログラムの実行結果
• プログラムの考察

第3回課題

• 5,7,3,4,2,6,1(ランダム)
• 7,6,5,4,3,2,1(降順)
• 1,2,3,6,5,7,4(ある程度ソート済み)

• 普通の線形探索と番兵を使ったものでは、比較回数がどのように減るか(説明を書く)
• 挿入ソートに番兵を組み込んで、速度を向上させよ(プログラムを作る)
• 講義・演習の感想を書け

第2回課題

1. insertを二分探索にせよ
2. doubleの配列を文字列にせよ
3. 発展:配列をPersonにせよ

String a =  "a";
String b = "b";
if(0 < a.compareTo(b)){
	......
}

第1回課題

1. Private変数に外部からアクセスすると、どのようなエラーが起こるか
2. 等値演算子 == と　equals() の違いを説明する例題を作れ
3. array.javaの内容を整数から文字列に変更せよ

• 次の3つの課題をメール本文に書いて提出して下さい．
• プログラムのソースコードも添付しないで本文に書いて下さい．
• 全部できなかった場合には，3時間以上時間をかけず，できなかった理由を書いて提出してかまいません．