プログラム理論と言語 : 期末試験用問題集 Part2 (2009) 演習問題 2-0 オブジェクト指向言語, とりわけ Java に関する用語の設問をもうける. 重要な語句については復習をしておくこと. 1
演習問題 2-1( レジメ記載の問題を具体化した問題 ) 下記は, 整数 (int) を要素とする線形リストのプログラムである. class IntCell { private int value ; int getvalue() {return value; private IntCell next; IntCell next() {return next; IntCell(int value) {this.value = value; IntCell(int value, IntCell cell) { this.value = value; next = cell; void showvalue() {System.out.print(value+" "); class IntList { private int length = 0; private IntCell firstcell = null; void tail() { System.out.println("* first cell ("+firstcell.getvalue()+") is removed."); firstcell = firstcell.next(); length--; void cons(int x) { if (length == 0) firstcell = new IntCell(x); else { IntCell nextfirstcell = new IntCell(x,firstCell); firstcell = nextfirstcell; ; length++; void show() { IntCell presentcell = firstcell; for (int i=0;i<length;i++) { presentcell.showvalue(); presentcell = presentcell.next(); ; System.out.println("#end_of_list"); public static void main(string[] args) { IntList list = new IntList(); for (int i=0;i<args.length;i++) list.cons(integer.parseint(args[i])); // parseint は, 文字列を整数に変換する Integer クラスの静的メソッド. list.show(); list.tail(); list.show(); 2
2-1-1 IntList の main を, 整数を表す文字列の配列を渡して実行すると, 標準出力 System.out には逆順で表示される. 実行例 D:\home\lecture\pl\resume>java IntList 1 2 3 4 4 3 2 1 #end_of_list * first cell (4) is removed. 3 2 1 #end_of_list 注 : main の引数 String[] args は文字列配列で, コマンドラインからこれをもらう. 上記の例の場合は,args[0] = "1", args[1] = "2",... なる文字列配列 プログラムの動作を説明することにより, なぜ逆順になるかを示せ. 2-1-2 双方向リストのプログラムに拡張するために,IntCell に, 新たなフィールド を追加したとする. private IntCell back 2-1-2-1. 双方向リストとはいかなるリストかを述べよ 2-1-2-2. back フィールドに IntCell へのポインタを定めるためには, コンストラクタ IntCell(int,IntCell) に 1 文を追加すれば十分である. 理由も添えてその 1 文を示しなさい. ヒント : コンスタラクタにおける this はコンスタラクタで生成するオブジェクトを参照する変数.this =... なる 直接代入 による参照の再定義は不可だが, 生成途中のオブジェクトを参照するために使うのは全く問題ない. 3
演習問題 2-2 ( レジメ記載の問題を少し変えている ) 2 次元実平面上の点のクラス Point, ベクトルのクラス Vector および,3 角形のクラス Triangle を定める下記のプログラムを考える. class Point { private double x, y; Point(double x, double y) {this.x = x; this.y = y; // 座標が (x,y) の点を生成を返すコンストラクタ double getx() {return x; // X 座標取得メソッド double gety() {return y; // Y 座標取得メソッド double length() {// 原点との距離を返すメソッド return Math.sqrt(Math.pow(x,2)+Math.pow(y,2)); // sqrt は平方根,pow(x,y) は x の y 乗を返す Math クラスの静的メソッド Vector makevector(point q) {// this を始点に,q を終点にしたベクトルを返す... ( 設問 A) class Vector extends Point {// 点だが, 原点を基準にしてベクトルとみなす Vector(double x, double y) {super(x,y); // 親クラスのコンストラクタを適用 double innerproduct(vector anothervector) {// 内積 return this.getx()*anothervector.getx() + this.gety()*anothervector.gety(); class Triangle { private Point p1, p2, p3; Triangle(Point p1, Point p2, Point p3) {this.p1=p1;this.p2=p2;this.p3=p3; double area() {// 内積を用いた 3 角形の面積計算 Vector v1 = p1.makevector(p2); Vector v2 = p1.makevector(p3);... ( 設問 B) 2-2-1. ベクトルの長さを求めるために,Point クラスの double length() を継承して用いてよいか? 問題なければその理由を述べよ. 継承して利用する方法に問題があれば, その理由を述べた上で,Vector クラスに適正なメソッドを定めよ. 2-2-2. 設問 (A), 設問 (B) を実際のコードで埋めよ. ただし,(B) の面積計算はベクトルの内積を用いること. 注意 :java のユーティリティとして,Vector クラスが定義されているが, 上記のプログラムでは import していないので, クラス名 Vector を使っても構わない.java.util.Vector を import する場合は, 別クラス名にする. 4
演習問題 2-3( レジメ記載の問題と同じ ) 右図は受理機械としての有限オートマトン F A の例である ただし q0 を初期状態 q2 を受理状態とする 受理する言語は {(01) n n 1 1. FA には {0, 1 の入力記号系列が与えられる 2. 各状態で 入力系列 σ 0 σ 1...σ n 1 (n は 入力系列長 ) を受け取る 挙動は : (1) 先頭記号 σ 0 により次の状態 q next を決め (2) q next に残りの入力系列 σ 1...σ n 1 を渡し以後の処理を委ねる 3. 入力系列が空列 ( 記号が残っていない n =0) のときは 最終状態なら 受理 それ以外の場合は 非受理 のメッセージを出力し 全体の処理が終了 課題 : FA の動作を模倣するプログラム ( クラス State) を書くとして 必要なフィールドとメソッドを与え その型ならびにその挙動を説明せよ メソッド中で 別のオブジェクトに対するメソッド呼び出しを行う場合はそのことも明記すること 5
演習問題 2-4 ( レジメ記載の問題を詳細化したもの ) 授業科目には 通常の座学の講義を行う科目と 実験 演習科目に大別でき それらの成績集計方法は異なる 通常の座学の科目は 履修者名簿と期末試験の素点データを保持し 一方 実験 演習科目は 履修者毎に全部で 12 回のレポートの評点データを保持していると仮定する. 次頁のプログラムでは, 学生毎の, 座学および演習科目の成績を, それぞれ異なるクラス StudentRecordForLecture, StudentRecordForExercise として持たせている. 対応する, 座学および演習のクラス Lecture, Exercise は, それぞれ,StudentRecordForLecture の配列と StudentRecordForExercise の配列を, 内部フィールドとして保持する. 2-4-1. 受講学生は履修している科目毎に異なる. この事実は下記のプログラムのコードにおいて, どの箇所で表現されているかを答えよ. また, その理由も述べること. なお, 該当箇所は行番号を用いて指示せよ. 2-4-2. 科目のクラス Item は抽象クラスにした. この場合,(A1) 抽象クラスでなければならない,(A2) 抽象クラスにしてはいけない, あるいは,(A3) 抽象クラスにしても良い, のいずれであるかを答えよ. その際, 抽象クラスの定義や特徴に触れながら説明すること. 2-4-3. 設問 (A).double avg() は何の計算を行うメソッドかを述べよ 2-4-4. 設問 (B).Exercise クラスのコンストラクタ Exercise(String, StudentRecordForExercise[]) の定義を完成させよ. また, 自分が書いたコードの正当性も必ず述べること. 2-4-5. 演習, 座学を区別せずに, 全ての科目平均点の平均を求めるコードを与えよ. 新規のクラスを定義しても良いし, 次頁のクラスにメソッドを追加する形で与えてもよい 6
1. abstract class StudentRecord { 2. private String name; 3. abstract double score(); 4. StudentRecord(String name) {this.name=name; 5. 6. class StudentRecordForLecture extends StudentRecord{ 7. private int score; 8. double score() {return score; 9. StudentRecordForLecture(String name, int score) { 10. super(name); this.score = score; 11. 12. 13. class StudentRecordForExercise extends StudentRecord{ 14. private static final int noftimes = 12; 15. private int[] scores; 16. StudentRecordForExercise(String name, int[] rs) { 17. super(name); scores = rs; // rs.length == 12 等のチェックが必要だが 18. // 簡単のため省略 19. double score() { 20. double sum = 0.0; 21. for (int i=0;i<noftimes;i++) sum += scores[i]; 22. return sum/noftimes; 23. 24. 25. abstract class Item { 26. private String name; 27. private StudentRecord[] records; 28. Item(String name, StudentRecord[] records) { 29. this.name = name; this.records = records; 30. 31. double avg() { // 設問 (A) 32. double sum = 0.0; 33. for (int i=0; i<records.length;i++) sum += records[i].score(); 34. return sum/records.length; 35. 36. 37. class Lecture extends Item { 38. Lecture(String name, StudentRecordForLecture[] records) { 39. super(name, records); 40. 41. 42. class Exercise extends Item{ 43. Exercise(String name, StudentRecordForExercise[] records) { 44.... 設問 (B) 45. 46. 7