課題

計算機プログラミングI (2003年度冬学期)表紙 | 講義計画 | 資料 | 課題 | Q&A

注意

提出方法

  1. 以下の課題文をよく読む。期限等は掲示板にあるので注意。
    課題1 課題2 課題3 課題4 課題5 課題6
  2. レポートを作成する。
  3. 掲示板を通して提出する。提出したファイルが正しく読めるか、(プログラムが含まれている場合は、コンパイルできるか)を確認せよ。

体裁は自由であるが、読みやすさも評価の対象となっていることに注意せよ。

プログラムを提出する場合には、コンパイルに必要なプログラムが全て提出されていることをよく確認すること。

課題

第1課題 デバグ

プログラムを編集・コンパイル・実行する際には様々な誤り(エラー)が生じる。

誤りが発生した例を3つ挙げ、それぞれ

  • どのようなプログラムをどのように実行した場合に生じたか
  • どのような誤りが報告(エラーメッセージ)されたか

を示し、さらに

  • 誤りの原因
  • 修正する方法

を推測して説明せよ

第2課題 変数・オブジェクト・メソッド

[2-1]

タートルグラフィクスによって単純でない図形を描くプログラムを一つ作成せよ。その際、次の a〜d の条件を満たすようにせよ。

  • a) タートルを3つ以上用いて図形を描く
  • b) 図形の大きさや角度などに変数を活用する
  • c) 複数の色を用いる
  • d) 数学関数・乱数などを利用する

提出は以下の3つを含むこと

  • あ) プログラム
  • い) どのような図形が描かれるかの説明 (言葉で説明しても画像を用いてもよい)
  • う) 満たした条件と、それぞれをどのように満たしたかの説明 (a であれば、各タートルの役割、b は各変数の役割、など)

注意:

  • ・プログラムは一つにまとめた方が望ましいが、条件ごとに別々のものを作成してもよい。
  • 図形が「単純」かどうかは主観で判断せよ。
  • 全ての条件を満たすことが望ましい。
  • Turtleクラスのfd,bk,rt,ltなどのメソッドの引数は整数でなければいけない(教科書p.12)ので、実数を与える場合にはキャスト演算子(教科書pp.30-31)を用いなければいけないことに注意せよ。例えば m.fd(10*Math.cos(1)) はエラーになるので m.fd((int)(10*Math.cos(1))) のようにする。

[2-2]

図形の形状を変更するために上で作成したプログラムを変更することを考える。上の b) に関して、変数を活用することでプログラムの変更が容易になったかどうかについて自分の考えを述べよ。

(例えば、具体的な変更(例えば5角形を8角形にするなど)を想定し、変数を活用した場合・しなかった場合の変更箇所を比較すると考えやすいだろう。)

[2-3]

上の[2-1]のプログラムから、教科書にある次の文法規則があてはまる場所を1つずつ探し、どのようにあてはまるかを説明せよ。

  • a) new 【クラス名】() [p.9]
  • b) 【変数名】 = 【式】; [p.9]
  • c) 【型名】【変数名】; [p.9]
  • d) 【型名】【変数名】 = 【初期値を表す式】; [p.9]
  • e) 【オブジェクト式】.【インスタンスメソッド名】(【引数式1】,...,【引数式n】) [p.10]
  • f) new 【クラス名】(【引数式1】,...,【引数式n】) [p.13]
  • g) 【オブジェクト式】.【インスタンス変数名】 [p.18]
  • h) 【クラス名】.【クラス変数名】 [p.24]
  • i) 【クラス名】.【クラスメソッド名】(【引数式1】,...,【引数式n】) [p.24]

  • 【 】は教科書で四角囲みで書かれている。
  • 例えば a であれば、リスト2.1の5行目の「f=new TurtleFrame();」の「new TurtleFrame()」の部分があてはまり、【クラス名】は「TurtleFrame」になっている、と答えればよい。

第3課題 制御構造・配列

[3-1]

タートルグラフィクスによって図形を描くプログラムを一つ作成せよ。その際、次の条件を満たすようにせよ。

  • a) 2重あるいはそれ以上にネストした繰り返しを行う
  • b) 配列を活用する

提出は以下の3つを含むこと

  • あ) プログラム
  • い) どのような図形が描かれるかの説明 (言葉で説明しても画像を用いてもよい)
  • う) 満たした条件と、それぞれをどのように満たしたかの説明 (a であれば、各繰り返しが何に対応するか、b は配列のプログラム中での役割、など)

注意:

  • プログラムは一つにまとめた方が望ましいが、条件ごとに別々のものを作成してもよい。
  • 全ての条件を満たすことが望ましい。

[3-2]

第2回課題で作成したプログラムを見直して、

  • (1) 同じ手順を繰り返しているところ
  • (2) 似たような値のために多数の変数を使用しているところ

を探せ。もしあれば、それぞれについて「どのような手順を繰り返しているか」「どのような値のために多数の変数を使用しているか」を述べよ。さらに、 (1) については for あるいは while 文を用いて、(2)については配列を用いたプログラムを作り、提出せよ。

(もし第2回課題ですでに、for/while文や配列を用いている場合には、そのプログラムを示し、そのように述ればよい。)
講評
  • (3a) 「配列を利用したプログラム」の中には実際には配列が必要でないものもいくつかありました。
    典型的なものとしては、配列のi番目は繰り返しのi回目の間しか使われていない、というものです。例えば次のようなコードでは繰り返し1回ごとにタ一トルを作りhm[i]に代入し、表示し、hm[i]を使った処理をしています。しかしhm[i]の値は、i+1以降では使われていません。 
    Turtle[] hm[N] = new Turtle[N];
for (int i = 0; i < N; i++) {
  hm[i] = new Turtle(...);
  f.add(hm[i]);
  ...hm[i]だけを使って描画...
}
...以降hmを使わない処理...
    このような場合、次のように書き換えると配列を使わずとも同じ処理ができます: 
    Turtle m;
for (int i = 0; i < N; i++) {
  m = new Turtle(...);
  f.add(m);
  ...mを使って描画...
}
    逆に言えば、配列が本当に役に立つのは、i回目の繰り返しが終わった後にもhm[i]の値を使う必要があるケースだと言えます。
  • (3b) [3-2]で示されたプログラムが「すでに第2課題でfor文や配列を使っていて、それを示した」ものか「第2課題をfor文や配列を使って書き直したものか」がはっきりと分からないものがありました。

第4回課題 クラスメソッドの利用・素数の計算

(駒場祭期間中は情報教育棟が閉館する予定があるので注意せよ。)

[4-1]

第3回課題において作成したプログラムを、クラスメソッドを使って整理せよ。複雑な処理を行うプログラムは、いくつかの部分に分けた方が作りやすいし、理解もしやすい。また、似たような処理を何回も行っている場合には、その処理内容を1つのメソッドとして定義しておくことで、同じ操作を何回も書くことを防げる。 提出は以下を含むこと:
  • あ) クラスメソッドを使って整理し直したプログラム
  • い) 第3回課題において作成したプログラム
  • う) 上の あ) のプログラムで定義されているメソッド全てについて、以下のことを説明せよ:
    1. メソッドの名前
    2. どのような値を用いているか
    3. それぞれの値の名前
    4. それぞれの値の型
    5. どのような計算あるいは処理をしているか
    6. 答えの型
    (資料の1.1.1の1〜6に対応している)
注意:
  • 第3回課題において複数のプログラムを作成している場合には、その中の1つを選べばよい。(が2つ以上に対して行っても構わない。)
  • [追記] 第3回課題で作成したプログラムがあまりに単純で、クラスメソッドを利用する余地がない場合には、「第3回課題で作成したプログラム」を発展させたものを作り、それを元にクラスメソッドによる書き換えを行ってよい。
  • メソッドとして定義すべき部分は様々である。例えば、比較的単純な計算(2乗を計算する、距離を計算する)などから、複雑な操作(タートルm1,m2の中点にタートルm3を移動させる、半径rの正n角形を描く)などまである。
  • 複雑な操作/計算をするメソッドが、より細かな操作/計算をするメソッドを呼び出すことも多い。
  • できるだけ「分かりやすい」メソッドの名前や引数名をつけるように心掛けよ。例えば、正n角形を描く場合には、「seitakakukei」あるいは「drawRegularPolygon」などとする。
  • プログラムの中にできるだけ多くのコメントを書き込め。メソッドに分けて整理をしたとしても、そのメソッドが何をするものかが読みとれなければ、プログラムを理解することはできない。

[4-2] 素数の計算

資料に示したアルゴリズムを参考にして「N以下の素数の個数と、その中の最大の素数を表示するプログラム」を作成し、アルゴリズムによる速度の違いを比較せよ。
  • 資料2.4.1〜2.4.3に紹介されている3つのアルゴリズムを参考にせよ。2つ以上のアルゴリズムを実行できるようにすることが望ましい。
  • 資料に紹介した以外のアルゴリズムを用いても構わない。ただしその場合は、アルゴリズムの完全な説明を付けるか、参考にした文献等を明示せよ。説明も出典もないアルゴリズムは受け付けない。
  • 個々のアルゴリズムが計算に要した時間を計測せよ。時間の計測方法は資料ページの Timer.java を参考にせよ。
  • Nが 10,100,1000,1万,10万のときの個々のアルゴリズムの実行時間を測り、各アルゴリズムの速さを比較せよ。
  • フェルマーのテストをする場合には、「テストの回数」と「誤認率(素数でないものを素数と判定してしまう確率)」の関係がどうなっているかを調べてみよ。
  • 余力があれば、int型のかわりにlong型を使ったプログラムを作り、より大きな素数を計算するプログラムを作成せよ。
  • さらに余力があれば java.math.BigDecimal クラスを使ってさらにより大きな素数を計算するプログラムを作成せよ。
  • 「非常に大きなN以下の最大の素数(らしい数)を1つ」求める場合には、どの方法が適しているかを考察せよ。Nが109 (10億)程度、 1018 (100京) 程度、 1030 程度の場合はどうか?

提出は以下の3つを含むこと

  • あ) 作成したプログラム
  • い) プログラムがどのアルゴリズム(複数可)を用いているかの説明。また、工夫した点についての説明。
  • う) 実行結果 (どのような条件で測ったかとその結果)
  • え) 考察

第5回課題 オブジェクト指向によるプログラムの設計

(冬休み中は情報教育棟が閉館する予定があるので注意せよ。)

[5-1] 継承によってクラス定義を拡張する機能を活用したプログラムを設計し作成せよ

ただし、ここでは継承によって「異なる動作/計算をするオブジェクトを同様に扱えること」を活用していることを条件とする。このようなプログラムを1から設計するのは初学者には難しいので、次のどちらかの方法でおおまかな設計を決めることにする。
  • 第8回配布資料で紹介した2つのプログラムの設計に従う。もちろん、それを元にした上で独自の機能を加えてもよい。
  • 独自のプログラムの設計を考え、教員・TAの確認を受ける。「このように継承を使ったプログラムを作りたい」というアイデアがあれば、その段階で教員・TAに相談する。教員・TAはそれが「活用」になっているかを判断し、助言する。確認は、メール・掲示板を通して受けることとする。(確認を受けずに独自のプログラムを提出した場合、題意を満たしていないため評価の対象外となる可能性がある。)
提出は以下を含むこと:
  • あ) プログラムの全体の目的 (何をするプログラムか)
  • い) 全体的に特に工夫した点。
  • う) プログラムの機能 (具体的にどんなことができるのか)
  • え) どのような機能のために継承を活用したか (異なる動作/計算をするモノは何だったか。それらはどのクラスに対応しているのか。どんな操作/計算をするメソッドが再定義されたのか。)
  • お) クラスの構成 (どのようなクラスがあり、それがどのような機能に対応しているか。各クラスにはどのようなメソッドがあり、それがどのような機能や働きに対応しているか。)
  • か) プログラム
  • き) プログラムの使い方
  • く) 考祭 (継承・メソッドの再定義の機能を使わない場合、どのような問題が起きるか)
注意:
  • 第8回配布資料で紹介したプログラムをもとにする場合でも、上の あ〜く 全てを書くこと。
  • できるだけ「分かりやすい」クラス・メソッド・変数名をつけるように心掛けよ。
  • プログラムにはできるだけ多くのコメントを付けよ。メソッドに分けて整理をしたとしても、そのメソッドが何をするものかが読みとれなければ、プログラムを理解することはできない。
  • 添付ファイルとして提出する場合は、1つのファイルして(つまり1回で)提出することが望ましい。

第6回課題 再帰を使ったプログラム

(情報教育棟システム更新にともなう開館日程に注意せよ。)

以下の[6-1]・[6-2]のどちらかを提出せよ。

[6-1] 再帰的なメソッド呼び出しを利用してフラクタル図形を描くプログラムを作成し、再帰を用いない場合と比較せよ

  • フラクタル図形としては第11回資料に載せたもののほかに、独自に考案したものでも構わない。
  • 第11回資料のTreeクラスをそのまま提出してはいけない。
提出は以下を含むこと:
  • あ) 全体的に特に工夫した点。
  • い) 再帰によって何故そのような図形が描けるかの説明
  • う) プログラム
  • え) プログラムの使い方
  • お) 再帰を用いない場合との比較。(再帰を用いずに同じ図形を描くプログラムを作るとしたら、どのようなものになるか。 (実際のプログラムを示すとよいかも知れない。) 図形の形状を変更をすることを考えた場合、変数の値の変更だけで済むか/プログラム自体を変更しなければいけないか、等々の観点から比較せよ。)

[6-2] 再帰的なデータ構造を定義し、それを利用するプログラムを作成せよ

どのようなデータ構造を定義し、どのように利用するかは自由とする。ただし、第11回資料をそのまま提出してはいけない。例えば以下のようなものが考えられる:
  • いままでに作ったプログラムで配列を用いていた部分をリストに置き換えたもの:
    • 描画エディタで「図形要素の配列」を用いていたところを、「図形要素のリスト」に
    • 「タートルの配列」を用いていたところを「タートルのリスト」に
    ことや、
  • 「木構造」や「グラフ構造」といった、より複雑なデータ構造を使ったプログラム。
提出は以下を含むこと:
  • あ) 全体的に特に工夫した点。
  • い) どのようなデータ構造を作成したか、それが「再帰的」なデータ構造になっていること、そのデータ構造の操作をどのように定義したかの説明
  • う) プログラム
  • え) プログラムの使い方
  • お) 再帰的データ構造を用いない場合との比較。(再帰的データ構造を用いずに、同じ動作をするプログラムを作るとしたら、どのようなものになるか。 (実際のプログラムを示すとよいかも知れない。) 再帰的データ構造と配列を比較した場合に、どのような利害得失があるか、など。)
注意:
  • できるだけ「分かりやすい」クラス・メソッド・変数名をつけるように心掛けよ。
  • プログラムにはできるだけ多くのコメントを付けよ。メソッドに分けて整理をしたとしても、そのメソッドが何をするものかが読みとれなければ、プログラムを理解することはできない。
  • 添付ファイルとして提出する場合は、1つのファイルして(つまり1回で)提出することが望ましい。

評価

全体の50%になる。

参考情報

計算機プログラミングI (2003年度冬学期)