Lecture on Programming I 6/21
Menu Menu
先週の復習
Java の動かし方Java による Turtle Graphics
来週
来週6/28は、自習とします。足りない人には問題を用意しておくので、解いてみて下さい。
Typing の練習
今日も typing の練習をすること (20分)結果をscript でメールすること。
整形した結果を、
Subject: Report on Programming I 6/21-typist
というサブジェクトで、kono@ie.u-ryukyu.ac.jp までメールを出すこと。
% rsh pw006 "Mail -s 'Report on Programming I 6/21-typist' kono@ie.u-ryukyu.ac.jp" < typescript
ランダムな配列を作る
public static int [] random_array (int n) {
int i,j;
list = new int [n];
for(i=0;i<n;i++) list[i] = -1;
for(i=0;i<n;i++) {
j = (int)(java.lang.Math.random()*n);
while (list[j] != -1) {
j = (++j<n)?j:0;
}
list[j]=i;
}
return list;
}
このままでは、動かない( Perl と違う...)。テスト用のクラスを作って動かそう。
java.lang.Math.random() を Java のリファレンス Java 1.1.1 Reference から調べてみよう。
解の性質を調べる
random_array は、本当にランダムか? これをグラフィカルに表示する方法を考え実装せよ。また、ランダムでない場合は、その理由について考察し、その解決方法を示せ。
それを並べ換える (バブルソート)
隣どおしを比較して、小さい方を前に移す
それをすべての配列に繰り返し適用する
public static int [] buble_sort (int list[],int n) {
int i,j;
for(i=0;i<n;i++) {
for(j=1;j<n;j++) {
if (list[i]>list[j]) {
int k;
k = list[j];
list[j] = list[i];
list[i] = k;
}
}
}
return list;
}
100個の要素を並べ換える(sort)するのに何回ループを回るのだろうか?
このようにデータを扱う手順を「アルゴリズム」という。プログラムは、データ構造とアルゴリズムの組み合わせである。
テストプログラム を参考にして、sort にかかる時間を調べてみよう。
配列だけでプログラムできるか?
できる。
計算機の限界 => Turing Machine
人間ができる計算の限界
Turing Machine とは?
無限の長さの配列(メモリ) + 有限状態機械(CPU)
配列だけでプログラムするな!
オブジェクトあるいは、構造体を使って、より立体的なデータ構造を作り、それを使ってプログラムすること。
配列が多くでてくるプログラムは、設計が悪いと考えて良い。
データ構造を考えることによって、プログラムの見通しが良くなる。自然に、効率の良いアルゴリズムとなる。
Btree を作ってみる
整列したデータ構造を漸時的に(incremental)作成したい場合、データ構造を柔軟に変更したい場合は、木構造を用いると良い。ここでは木構造のうち、特に、二分木を扱う。木の一つの要素は、
その場所の値 右の木 左の木の三つの属性を持つ。これを配列、
[値、左、右」で表そう。
根 二分木の基(root) 葉 リーフ(leaf)ともいう。木の一番端 幹 ノード(node)ともいう。木の構成要素Btree (二分木)を使って、並べ換え(sort)を作ってみよう。
Btree.java ここでは、木を深さ優先にたどっている。
これに対して、浅いところから順にたどる方法を幅優先(Breadth First)という。
Btree のGraphicalな表示
二分木を図で表示するには、上から順に表示すれば良い。それは、幅優先に木をたどることになる。一つの実装法は、
一つのレベルのノードのリスト(配列)を作ることである。これから、
次のレベルのノードのリストを作ることは容易だ。これを繰り返すことにより、幅優先アルゴリズムを作ることができる。
Breadth first walk する時の、一段前のlevelを取っておくことにより、Btree を Applet 上で Graphical に示すプログラムを書け。
Breadth First Walk を、Vector を使って実装せよ。また、それを使って、木構造を文字的に表現するプログラムを記述せよ。
1
2 3 4
5 6 7 8
9 10
木構造を表示するためには、ノードの値を記述する必要がある。
(*) Btree を Depth first の方法で、Graphical に表示する方法に付いても考察してみよ。(ヒント: 2パス (2 pass )という、木を二回渡り歩く方法を使うと良いかも知れない)
Vector の使い方
Vector には整数は格納できないらしい。それを示すエラーメッセージを出すプログラムを示せ。それを乗り越える方法にはどんな方法があるか。(ヒント class Integerを使う)
Enumerator の使い方
(*) Btree を Breadth walk する Enumerator を作成せよ。
Test プログラム
BtreeTest.java 長さ n の入力を格納するのに、どの程度の計算が必要だろうか?データとして、最初から順序がそろっている場合、最初はまったくの逆順になっている場合を考えてみよう。
try/catch
public static void main (String args[]) {
Btree t;
int size;
if (args.length==0) {
System.out.print("Need an integer argument as size. \n");
return;
}
try {
size = Integer.parseInt(args[0]);
} catch (Exception e) {
System.out.print("Need an integer argument as size. \n");
return;
}
if (size<=0) {
System.out.print("An argument should be greater than 0. \n");
return;
}
...
入力のチェックが重要。
Object の作り方
走る車を表すオブジェクトを作ることを考えよう。ここでは、
車の速度 v
車のハンドルの方向 direction
を考えることにする。これらをオブジェクトの状態として持つclass Car
を作成せよ。
これらの代わりに、
アクセスの位置 pedal
エンジンの力 power
車の重さ weight
車の加速 accelaration
などを使うオブジェクトclass DetailedCar を作成せよ。
Runnable
例題RunningOval を参考にして、線を書く代わりに、自走する Car を作ってみよ。Applet を Runnable にして、Car に forward() のようなメッセージを送るようにすると良いかも知れない。
四角いコースを走るCar、丸いコースを走るCarのプログラムを作成せよ。
速度も時間で変化するように作ってみよう。
Manual の見方
三角形を描くために必要なclass とmethod のマニュアルを探す手順を記述せよ。
基本的な制御
class Car, class DetailedCar で、単位時間(1sec)あたりの車の位置を計算するメソッドを、これらのclass に付け加えたい。必要なインスタンス変数を付け加えて、このメソッドを完成しせよ。このクラスを使って、車の10秒間の動きをシミュレーションするプログラムを作成せよ。for, while, do-while の三種類のループを使う版を作成せよ。
継承の使い方
Detailed Car を Car を継承する形で作成してみよ。
String の使い方
Car に運転者の名前と、持ち主の名前という属性を付け加える。Car に、持ち主以外が運転すると文句を言う機能を付けてみよう。
文字と数字の変換
Applet のGraphics を使って、この車の運転手の名前、スピード、位置などを表示する方法を示せ。
try catch の使い方
制限速度を越えると Exception を投げるように Car を改造したい。制限速度を越えた場合はどのようにすべきか? Runnable の例題にその処理をtry/catch を使って付け加えよ。
宿題
以上の問題をSubject: Report on Programming I 6/14というサブジェクトで、来週までに提出すること。