計算機プログラミングI 第8回 素数を見つけるアルゴリズム 継承とインスタンスメソッド クラスの設計 オブジェクトに機能を加える オブジェクトの機能を変更 クラスの設計 計算機プログラミングI (増原) 2003年度

2からnが素数かどうかを 判定するのに必要な計算回数 単純な方法: iが素数かどうか2～(n-1) で割ってみる→約i回の計算 iが2からnまで調べる→2+3+…+n=約n2回の計算 エラトステネスのふるい i番目が素数→n/i回の計算 i=2からn-1まで全て素数だったとしてn/2 + n/3+…+n/(n-1) < an log(n) 回の計算 (素数の存在確率を無視) ただし大きさnの配列が必要 フェルマーのテスト(単純) 1回のテストは ai の計算→i回の掛け算 iが2からnまで各b回テスト→ 約 bn2 回の計算 フェルマーのテスト(工夫) aiの計算 =ai/2の計算+1回 =(ai/4の計算+1回)+1回=… =a0の計算+1回+・・・+1回 =約 log(i)回 iが2からnまで各b回テスト 合計 bn log(n)回以下の計算 確率的 計算機プログラミングI (増原) 2003年度

計算量 定数を無視して考えたものを「計算量」という 2からnが素数かどうか 単純な方法: 約n2回 エラトステネスのふるい 約 n log(n) 回 大きさnの配列が必要 フェルマーのテスト(単純): 約 bn2 回 フェルマーのテスト(工夫): 約 bn log(n)回 定数を無視して考えたものを「計算量」という O(n2), O(n log(n))のように書く おおまかな計算時間 (とメモリの量)を比べるため 例: 非常に大きな素数を見つけたい場合 計算機プログラミングI (増原) 2003年度

n2回とn log(n)回の違い 計算機プログラミングI (増原) 2003年度

最大のメルセンヌ素数 分散コンピューティングで栄誉ある大発見を (ZDNN 2001/12/17) ……コンピュータを使って，これまでに発見された中で世界最大の素数を発見した。……メルセンヌ素数と呼ばれる特殊なタイプの素数を発見するプロジェクトに参加……発見した素数は，2の1346万6917乗マイナス1，桁数は405万3946桁にもなる。 メルセンヌ素数は，「2のp乗マイナス1（pは普通の素数）」という特殊なタイプの素数を研究していたフランスの修道士，Marin Mersenne（1588～1648）にちなんで名付けられた。 メルセンヌ素数は普通の素数よりもはるかに珍しい。これまでのところ，39のメルセンヌ素数が発見されている……発見した数値がメルセンヌ素数であることを確認するのに42日間かかった。その後研究者がワークステーション1台を使って，3週間かけて確認作業を行った。http://www.zdnet.co.jp/news/0112/17/e_distributed.html 40番目のメルセンヌ素数の発見! (2003/12/3) 値は 220,996,011-1 桁数は6,320,430桁 http://www.mersenne.org/ 計算機プログラミングI (増原) 2003年度

継承とインスタンスメソッド オブジェクトに機能を加えたい! だけど、いままでのプログラムは変えたくない! だからといってプログラムのコピーもしたくない!  継承を使って新しいクラスを作る 新しいインスタンス変数を追加する 新しいインスタンスメソッドを追加する オブジェクトの機能を変更したい! だけど(以下略)  継承を使って新しいクラスを作る すでにあるインスタンスメソッドを再定義する 計算機プログラミングI (増原) 2003年度

例題: タートルでn角形を描く いままでのTurtleオブジェクトができること 前進(fd)・回転(lt)等の指示を受ける Turtleオブジェクトに「長さlのn角形を描け」という 指示が出せたなら・・・ Turtle m = new Turtle(); m.polygon(100,5); // 1辺100の5角形 でも… Turtleクラスは変更したくない Turtle.javaのコピーを作るのは面倒 計算機プログラミングI (増原) 2003年度

例題: タートルでn角形を描く Turtle クラスを拡張して、Houseクラスを定義する Houseクラスにインスタンスメソッドを追加する 「n角形を描く」polygon 「家の形を描く」house  Houseオブジェクトに対しては、fd, lt 等の他に 追加された polygon, house メソッドも 呼び出せる ※Houseオブジェクトを使っていない プログラムには影響がない! 計算機プログラミングI (増原) 2003年度

n角形の描き方を知っている タートルがいたら・・・ public class T61 { public static void main(String[] args){ TurtleFrame f = new TurtleFrame( ); House m = new House( ); int s = 50; f.add(m); m.house(s); m.up( ); m.fd(s * 2); m.down( ); m.polygon(3, s / 2); m.up( ); m.fd(s); m.down( ); m.polygon(10, s / 5); } House・・・Turtleのかわりのクラス名 Turtleオブジェクトと 同じように使える Turtleにはない メソッドもある 計算機プログラミングI (増原) 2003年度

n角形の描き方を知っている タートルの定義 public class House extends Turtle { public void polygon(int n, int s){ int a = 360/n; for(int j = 0; j < n; j++){ fd(s); rt(a); } public void house(int s){ polygon(4,s); rt(30); polygon(3,s); lt(30); bk(s); Turtleに機能を追加したクラスを作ると宣言 追加される機能 (メソッド) 自分自身を使って n角形を描く 自分自身を使って 家の形を描く 計算機プログラミングI (増原) 2003年度

n角形の描き方を知っている タートルの定義 public class House extends Turtle { public void polygon(int n, int s){ int a = 360/n; for(int j = 0; j < n; j++){ fd(s); rt(a); } public void house(int s){ polygon(4,s); rt(30); polygon(3,s); lt(30); bk(s); 例:m.polygon(50,3)を実行 →mに対して「多角形を描け」 → このメソッドが実行 自分自身(=m)に対する メソッドの実行 →m.fd(s)と同じ → mが前進 自分自身(=m)に対する メソッドの実行 追加したメソッドも実行可 文法: “static” が無い以外はクラスメソッドと同じ 計算機プログラミングI (増原) 2003年度

例題2: n角形を分割して描く亀 「長さlのn角形を分割して描く」Turtle 「1ステップ進め」と言われると、n角形の1辺だけを描く 「1ステップ進め」というときに、いちいち1辺の長さや 何角形であるかを指示したくない 次に「進め」と言われたら まだ進むべきか? 何度曲がるか? 何歩進むか? Stepper m = 長さ50の5角形を描く亀; Stepper m1 = 長さ30の8角形を描く亀; m.step(); //5角形の1辺を描く m1.step(); //8角形の1辺を描く ・・・ 計算機プログラミングI (増原) 2003年度

例題2: n角形を分割して描く亀 各Turtleが「1辺の長さがいくつの」「何角形」を 「何番目の辺」まで描いたかを覚える必要がある → インスタンス変数 Turtleを拡張してStepperクラスを作る インスタンス変数を定義する 1辺の長さ 何角形か 何番目の辺まで描いたか 「1ステップ進め」インスタンスメソッドを定義 全ての辺を描き終えたか? まだだったら 前進・回転して 「何番目の辺まで描いたか」を1増やす オブジェクトに 状態を持たせる 計算機プログラミングI (増原) 2003年度

6.4 インスタンス変数 インスタンス 変数の宣言 public class Stepper extends Turtle{ public int n; public int size; private int j = 0; public static final int ALREADY_FIN = 0; public static final int JUST_FIN = 1; public static final int NOT_FIN = 2; public int step() { if(j >= n) return ALREADY_FIN; fd(size); rt(360/n); if(++j == n) return JUST_FIN; return NOT_FIN; } public void reset() { j = 0; } 自分がいま 何角形を描いているのか 1辺の長さ 何番目の辺を描いているのか を覚える ローカル変数と同様に 値をとり出す 値をしまう ことができる オブジェクトごとに用意される → 前回のメソッド実行時に しまわれた値が そのまま残っている j=j+1; if(j==n) ... と同じ 計算機プログラミングI (増原) 2003年度

6.4 インスタンス変数 public class Stepper extends Turtle{ public int n; 自分がいま public int size; private int j = 0; public static final int ALREADY_FIN = 0; public static final int JUST_FIN = 1; public static final int NOT_FIN = 2; public int step() { if(j >= n) return ALREADY_FIN; fd(size); rt(360/n); if(++j == n) return JUST_FIN; return NOT_FIN; } public void reset() { j = 0; } public class T62{ public static void main(String[] args){ TurtleFrame f = new TurtleFrame(); Stepper m1 = new Stepper(); f.add(m1); Stepper m2 = new Stepper(); f.add(m2); m1.n = 4; m1.size = 100; m2.n = 3; m2.size = 100; ... 自分がいま 何角形を描いているのか 1辺の長さ 何番目の辺を描いているのか を覚える ローカル変数と同様に 値をとり出す 値をしまう ことができる オブジェクトごとに用意される → 前回のメソッド実行時に しまわれた値が そのまま残っている j=j+1; j=j+1; if(j==n) ... と同じ (++j == n) 計算機プログラミングI (増原) 2003年度

6.5 コンストラクタ インスタンス変数=オブジェクトごとにある状態 オブジェクトを作る(new)と、初期化をする (例:インスタンス変数に適当な値をしまう) これを一体化したい!  コンストラクタ オブジェクトが作られたときに実行されるメソッド 文法: クラス名(引数の型 引数の名前, ...) { 文; ... } (メソッド定義に似ている。違うのは返り値の型が無い点と名前) 継承とコンストラクタ 子クラスのコンストラクタから親クラスのコンストラクタを呼び出す super(引数, 引数, ...); 子クラスのコンストラクタは、一番初めにこれをしなければいけない 省略すると「引数の無いコンストラクタ」が自動的に呼び出される しかし親クラスが「引数の無いコンストラクタ」を定義していないとエラー 計算機プログラミングI (増原) 2003年度

コンストラクタの実例 コンストラクタの 定義 1. Stepperオブジェクトが作られる 2. コンストラクタが実行される 親クラスの Stepper(int x, int y, int angle, int n, int size) { super(x, y, angle); this.n = n; this.size = size; } コンストラクタの 定義 public class Stepper extends Turtle{ public int n; public int size; private int j = 0; Stepper(int x, int y, int angle, int n, int size) { super(x, y, angle); this.n = n; this.size = size; } ... public int step() { if(j >= n) return ALREADY_FIN; Stepper super(x, y, angle); 親クラスの コンストラクタを実行 ... new Turtle(x,y,angle) のときと同様 Stepper[] hm = new Stepper[10]; for(int i = 0 ; i < 10; i++){ hm[i] = new Stepper(i * 50 + 25,150,0, n[i], size[i]); hm[i].setColor(c[i % c.length]); f.add(hm[i]); } new Stepper(i * 50 + 25,150,0, n[i], size[i]); 1. Stepperオブジェクトが作られる 2. コンストラクタが実行される 計算機プログラミングI (増原) 2003年度

違い: fdメソッドを 点線を描きながら進むように 例題3: 点線を描く亀 Turtleオブジェクトがfdしたときに点線を描かせたい! でも Turtle クラスは変更したくない!  継承とインスタンスメソッドの再定義 例: polygon(5,50) polygon(5,50) Tensen House 違い: fdメソッドを 点線を描きながら進むように 再定義している 計算機プログラミングI (増原) 2003年度

例題3: 点線を描く亀 点線を描く亀を作るには Houseクラスの子クラスTensenクラスを定義する Tensenクラスにfdメソッドを定義する―― 再定義という そのメソッド中でペンを上げ下げしながらn進む polygon(5,50) polygon(5,50) Tensen House 計算機プログラミングI (増原) 2003年度

点線で多角形を描く public class Tensen extends House{ int psize = 4; (略: コンストラクタ) public void fd(int s){ 長さsの点線を描く } public static void main(String[] args){ (略: TurtleFrameの生成) Tensen m = new Tensen(); (略) m.polygon(5, 50); main から実行が始まる Tensenオブジェクトが 作られる Tensenオブジェクトのploygonメソッドを呼び出す ploygonメソッドは n角形を描く。その際、Tensenオブジェクトの fdは点線を描くように 再定義されているので、 n角形は点線で描かれる。 計算機プログラミングI (増原) 2003年度

点線で多角形を描く Tensen 親クラスから 継承したpolygonを 実行 public class Tensen extends House{ int psize = 4; (略: コンストラクタ) public void fd(int s){ 長さsの点線を描く } public static void main(…){ (略: TurtleFrameの生成) Tensen m = new Tensen(); (略) m.polygon(5, 50); public class House extends Turtle { public void polygon(int n, int s){ int a = 360/n; for(int j = 0; j < n; j++){ fd(s); rt(a); } 再定義された fdが実行 ここから スタート 自身のfdを 呼び出し fd オブジェクト を作る メソッド 呼び出し polygon Tensen 計算機プログラミングI (増原) 2003年度

点線で多角形を描く Tensen 結果: 点線で5角形が描かれる public class Tensen extends House{ int psize = 4; (略: コンストラクタ) public void fd(int s){ 長さsの点線を描く } public static void main(…){ (略: TurtleFrameの生成) Tensen m = new Tensen(); (略) m.polygon(5, 50); public class House extends Turtle { public void polygon(int n, int s){ int a = 360/n; for(int j = 0; j < n; j++){ fd(s); rt(a); } 再定義された fdが実行 Tensen 結果: 点線で5角形が描かれる 計算機プログラミングI (増原) 2003年度

点線で多角形を描くしくみ Tensen Turtleクラス fd(s): 実線を描きながら前進 rt(a): 右回転 … Tensenオブジェクトへのpolygonメソッドの呼び出しは、親クラスの継承された定義の実行になる polygonメソッド中でのfdメソッドの呼び出しは、Tensenオブジェクトへのメソッド呼び出しなので、再定義されたfdが実行される extends Houseクラス fd(s): 継承 (実線を描きながら前進) polygon(n,s): fdを使って多角形を描く extends Tensenクラス fd(s): 点線を描きながら前進 polygon(n,s): 継承 (fdを使って多角形を描く) … 所属 Tensen 計算機プログラミングI (増原) 2003年度

親クラスのメソッドを使う方法 メソッドを再定義すると、 親クラスのメソッド定義が使えなくなる 例: Tensenオブジェクトのfdメソッド メソッド中で super . メソッド名(引数, ...) のようにメソッドを呼び出すと、 親クラスのメソッドを実行できる 例: Tensenオブジェクトのfdメソッド中で super.fd(psize) とすると、Turtleクラスに定義された 本来のfdメソッドが実行される 計算機プログラミングI (増原) 2003年度

? 点線を描くしくみ public class Tensen extends House{ public class House int psize = 4; (略: コンストラクタ) public void fd(int s){ 長さsの点線を描く } public static void main(…){ (略: TurtleFrameの生成) Tensen m = new Tensen(); (略) m.polygon(5, 50); public class House extends Turtle { public void polygon(int n, int s){ int a = 360/n; for(int j = 0; j < n; j++){ fd(s); rt(a); } ? 計算機プログラミングI (増原) 2003年度

点線を描くしくみ super . メソッド名(引数式, …) 親クラスのメソッドを呼び出す public class Tensen extends House{ int psize = 4; (略: コンストラクタ) public void fd(int s){ 長さsの点線を描く } public static void main(…){ (略: TurtleFrameの生成) Tensen m = new Tensen(); (略) m.polygon(5, 50); public class House extends Turtle { public void polygon(int n, int s){ int a = 360/n; for(int j = 0; j < n; j++){ fd(s); rt(a); } public void fd(int s){ int k, len; for(k = 0, len = 0 ; len + psize <= s; k++, len+= psize){ if(k % 2 == 0) down(); else up(); super.fd(psize); } down(); super.fd(s - len); ペンを交互に上げ下ろししながら、psizeづつ前進する super . メソッド名(引数式, …) 親クラスのメソッドを呼び出す 計算機プログラミングI (増原) 2003年度

点線を描くしくみ Tensen Turtleクラス fd(s): 実線を描きながら前進 rt(a): 右回転 … Tensenオブジェクトのfdメソッドを呼び出すと、再定義されたメソッドが実行される 再定義されたメソッド中のsuper.fd(psize)は親クラスのfdメソッドを実行する。結果、Turtleクラスのfdメソッドが実行され、実線が描かれる extends Houseクラス fd(s): 継承 (実線を描きながら前進) polygon(n,s): fdを使って多角形を描く extends Tensenクラス fd(s): ペンを上下させながら super.fd(psize)を呼び出し polygon(n,s): 継承 (fdを使って多角形を描く) … 所属 Tensen 計算機プログラミングI (増原) 2003年度

まとめると・・・ Tensen Turtleクラス fd(s): 実線を描きながら前進 extends rt(a): 右回転 … Houseクラス fd(s): 継承 (実線を描きながら前進) polygon(n,s): fdを使って多角形を描く polygon extends fd Tensenクラス fd(s): ペンを上下させながら super.fd(psize)を呼び出し polygon(n,s): 継承 (fdを使って多角形を描く) … 所属 Tensen 計算機プログラミングI (増原) 2003年度

クラスの拡張 class House extends Turtle { … } のようなとき Houseは 子クラス または サブクラス Houseオブジェクトは、Turtleオブジェクトが持っている全てのメソッドを持つ (例: fd) Houseオブジェクトは、Turtleオブジェクトのかわりに使える (例: TurtleFrameオブジェクトに add できる) Turtle m = new House(); ということが可能! HouseオブジェクトはTurtleオブジェクトと違った 動きをするかも知れない(例: fdの再定義) 計算機プログラミングI (増原) 2003年度

クラスの設計――Turtleクラスの解剖 public class Turtle{ public Color kameColor = Color.green; TurtlePanel f; // 表示面画 double angle; // 角度 double x, y; // 位置 double dx, dy; // sin(a),-cos(a) boolean penDown; // ペン状態 Color c = Color.black; // ペンの色 //コンストラクタ public Turtle(int x,int y, int ia) { this.x = ((double)x + 0.5); this.y = ((double)y + 0.5); setangle((double)ia *Math.PI/180.0); penDown = true; } //インスタンスメソッド public void fd(int n) { double xx = x; double yy = y; x = xx + dx * n; y = xx + dy * n; if (penDown) { f.addLineElement((int)xx, (int)yy, (int)x, (int)y, c); } kameShow(moveWait); … 計算機プログラミングI (増原) 2003年度