約n 2 回の計算

計算機プログラミングI
第8回
• 素数を見つけるアルゴリズム
• 継承とインスタンスメソッド
–オブジェクトに機能を加える
–オブジェクトの機能を変更
• クラスの設計
1
計算機プログラミング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)回以下の計算
– 確率的
2
計算機プログラミングI (増原) 2003年度
計算量
2からnが素数かどうか
• 単純な方法: 約n2回
• エラトステネスのふるい
–約 n log(n) 回
–大きさnの配列が必要
• フェルマーのテスト(単純):
約 bn2 回
• フェルマーのテスト(工夫):
約 bn log(n)回
• 定数を無視して考えた
ものを「計算量」という
– O(n2), O(n log(n))のよう
に書く
– おおまかな計算時間
(とメモリの量)を比べる
ため
– 例: 非常に大きな素数を
見つけたい場合
3
計算機プログラミングI (増原) 2003年度
n2回とn log(n)回の違い
9E+15
8E+15
7E+15
6E+15
5E+15
4E+15
3E+15
2E+15
1E+15
0
n*n
n log(n)
0
2E+07
4E+07
6E+07
8E+07
1E+08
4
計算機プログラミング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/1
7/e_distributed.html
40番目のメルセンヌ素数の発見!
(2003/12/3)
値は 220,996,011-1
桁数は6,320,430桁
http://www.mersenne.org/
5
計算機プログラミングI (増原) 2003年度
継承とインスタンスメソッド
• オブジェクトに機能を加えたい!
だけど、いままでのプログラムは変えたくない!
だからといってプログラムのコピーもしたくない!
 継承を使って新しいクラスを作る
新しいインスタンス変数を追加する
新しいインスタンスメソッドを追加する
• オブジェクトの機能を変更したい! だけど(以下略)
 継承を使って新しいクラスを作る
すでにあるインスタンスメソッドを再定義する
6
計算機プログラミングI (増原) 2003年度
例題: タートルでn角形を描く
• いままでのTurtleオブジェクトができること
–前進(fd)・回転(lt)等の指示を受ける
• Turtleオブジェクトに「長さlのn角形を描け」という
指示が出せたなら・・・
Turtle m = new Turtle();
m.polygon(100,5); // 1辺100の5角形
• でも…
–Turtleクラスは変更したくない
–Turtle.javaのコピーを作るのは面倒
7
計算機プログラミングI (増原) 2003年度
例題: タートルでn角形を描く
• Turtle クラスを拡張して、Houseクラスを定義する
• Houseクラスにインスタンスメソッドを追加する
–「n角形を描く」polygon
–「家の形を描く」house
 Houseオブジェクトに対しては、fd, lt 等の他に
追加された polygon, house メソッドも
呼び出せる
※Houseオブジェクトを使っていない
プログラムには影響がない!
8
計算機プログラミング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にはない
メソッドもある
9
計算機プログラミング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);
fd(s);
rt(30);
polygon(3,s);
lt(30); bk(s);
}
}
Turtleに機能を追加した
クラスを作ると宣言
追加される機能
(メソッド)
自分自身を使って
n角形を描く
自分自身を使って
家の形を描く
10
計算機プログラミング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);
fd(s);
rt(30);
polygon(3,s);
lt(30); bk(s);
文法:
“static” が無い以
}
外はクラスメソッドと同じ
}
例:m.polygon(50,3)を実行
→mに対して「多角形を描け」
→ このメソッドが実行
自分自身(=m)に対する
メソッドの実行
→m.fd(s)と同じ
→ mが前進
自分自身(=m)に対する
メソッドの実行
追加したメソッドも実行可
11
計算機プログラミング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辺を描く
・・・
次に「進め」と言われたら
• まだ進むべきか?
• 何度曲がるか?
• 何歩進むか?
12
計算機プログラミングI (増原) 2003年度
例題2: n角形を分割して描く亀
• 各Turtleが「1辺の長さがいくつの」「何角形」を
「何番目の辺」まで描いたかを覚える必要がある
→ インスタンス変数
• Turtleを拡張してStepperクラスを作る
– インスタンス変数を定義する
• 1辺の長さ
• 何角形か
• 何番目の辺まで描いたか
オブジェクトに
状態を持たせる
– 「1ステップ進め」インスタンスメソッドを定義
• 全ての辺を描き終えたか? まだだったら
• 前進・回転して
• 「何番目の辺まで描いたか」を1増やす
13
計算機プログラミング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);
j=j+1;
if(++j == n)
if(j==n) ...
return JUST_FIN;
と同じ
return NOT_FIN;
}
public void reset() { j = 0; }
計算機プログラミングI (増原) 2003年度
}
インスタンス
変数の宣言
自分がいま
• 何角形を描いているのか
• 1辺の長さ
• 何番目の辺を描いているのか
を覚える
• ローカル変数と同様に
• 値をとり出す
• 値をしまう
ことができる
• オブジェクトごとに用意される
→ 前回のメソッド実行時に
しまわれた値が
そのまま残っている
14
6.4 インスタンス変数
public class Stepper extends
public Turtle{
class T62{
自分がいま
public int n;
public static void main(String[]
args){
• 何角形を描いているのか
TurtleFrame f = new TurtleFrame();
public int size;
• 1辺の長さ
Stepper m1 = new Stepper();
f.add(m1);
private int j = 0;
Stepper m2 = =new
f.add(m2);
• 何番目の辺を描いているのか
public static final int ALREADY_FIN
0; Stepper();
m1.n = 4;
= 100;
public static final int JUST_FIN
= 1; m1.sizeを覚える
m2.n = =3;2; m2.size = 100;
public static final int NOT_FIN
...
public int step()
• ローカル変数と同様に
{
• 値をとり出す
if(j >= n)
• 値をしまう
return ALREADY_FIN;
ことができる
fd(size);
rt(360/n);
• オブジェクトごとに用意される
j=j+1;
if(++j
(++j == n)
if(j==n) ... → 前回のメソッド実行時に
return JUST_FIN;
しまわれた値が
と同じ
return NOT_FIN;
そのまま残っている
}
public void reset() { j = 0; }
15
計算機プログラミングI (増原) 2003年度
}
6.5 コンストラクタ
• インスタンス変数=オブジェクトごとにある状態
• オブジェクトを作る(new)と、初期化をする (例:インスタンス変数に適
当な値をしまう)
これを一体化したい!
 コンストラクタ
• オブジェクトが作られたときに実行されるメソッド
• 文法: クラス名(引数の型引数の名前, ...) { 文; ... }
(メソッド定義に似ている。違うのは返り値の型が無い点と名前)
• 継承とコンストラクタ
– 子クラスのコンストラクタから親クラスのコンストラクタを呼び出す
super(引数, 引数, ...);
– 子クラスのコンストラクタは、一番初めにこれをしなければいけない
– 省略すると「引数の無いコンストラクタ」が自動的に呼び出される
– しかし親クラスが「引数の無いコンストラクタ」を定義していないとエラー
16
計算機プログラミングI (増原) 2003年度
コンストラクタの実例
コンストラクタの
定義
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) {
Stepper
super(x,
super(x, y,
y, angle);
angle);
this.n = n;
this.size = size;
}
...
public int step() {
if(j >= n)
return ALREADY_FIN;
...
Stepper[] hm = new Stepper[10];
for(int i = 0 ; i < 10; i++){
}
hm[i] = new Stepper(i *
hm[i].setColor(c[i % c.length]);
f.add(hm[i]);
1. Stepperオブジェクトが作られる
2. コンストラクタが実行される
計算機プログラミングI (増原) 2003年度
親クラスの
コンストラクタを実行
... new Turtle(x,y,angle)
のときと同様
50 + 25,150,0, n[i], size[i]);
17
例題3: 点線を描く亀
• Turtleオブジェクトがfdしたときに点線を描かせた
い! でも Turtle クラスは変更したくない!
 継承とインスタンスメソッドの再定義
• 例:
polygon(5,50)
polygon(5,50)
Tensen
違い: fdメソッドを
点線を描きながら進むように
再定義している
計算機プログラミングI (増原) 2003年度
House
18
例題3: 点線を描く亀
点線を描く亀を作るには
• Houseクラスの子クラスTensenクラスを定義する
• Tensenクラスにfdメソッドを定義する―― 再定義という
• そのメソッド中でペンを上げ下げしながらn進む
polygon(5,50)
polygon(5,50)
Tensen
House
19
計算機プログラミングI (増原) 2003年度
点線で多角形を描く
public class Tensen extends House{
int psize = 4;
1. main から実行が始まる
(略: コンストラクタ)
2. Tensenオブジェクトが
public void fd(int s){
作られる
長さsの点線を描く
3. Tensenオブジェクトの
}
ploygonメソッドを呼び出す
}
public static void main(String[] args){
(略: TurtleFrameの生成)
4. ploygonメソッドは
Tensen m = new Tensen();
n角形を描く。その際、
(略)
Tensenオブジェクトの
m.polygon(5, 50);
fdは点線を描くように
}
再定義されているので、
n角形は点線で描かれる。
20
計算機プログラミングI (増原) 2003年度
親クラスから
継承したpolygonを
実行
点線で多角形を描く
public class Tensen extends House{
public class House
再定義された
int psize = 4;
extends Turtle {
fdが実行
(略: コンストラクタ)
public void polygon(int n, int s){
public void fd(int s){
int a = 360/n;
長さsの点線を描く
for(int j = 0; j < n; j++){
}
fd(s);
ここから
rt(a);
スタート
自身のfdを
public static void main(…){
}
呼び出し
(略: TurtleFrameの生成)
}
オブジェクト
Tensen m = new Tensen();
}
を作る
(略)
メソッド
m.polygon(5, 50);
Tensen
呼び出し
}
}
polygon
fd
21
計算機プログラミングI (増原) 2003年度
点線で多角形を描く
public class Tensen extends House{
再定義された
int psize = 4;
fdが実行
(略: コンストラクタ)
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);
}
}
}
Ten
結果: 点線で5角形が描かれる
22
計算機プログラミングI (増原) 2003年度
点線で多角形を描くしくみ
Turtleクラス
fd(s):
実線を描きながら前進
rt(a):
右回転 Houseクラス
fd(s):
…
継承
(実線を描きながら前進)
polygon(n,s):
fdを使って多角形を描く
• Tensenオブジェクトへのpolygonメ
ソッドの呼び出しは、親クラスの継
承された定義の実行になる
• polygonメソッド中でのfdメソッドの
呼び出しは、Tensenオブジェクトへ
のメソッド呼び出しなので、再定義
されたfdが実行される
Tensenクラス
fd(s):
点線を描きながら前進
polygon(n,s):
継承
(fdを使って多角形を描く)
…
計算機プログラミングI (増原) 2003年度
所属
Tensen
23
親クラスのメソッドを使う方法
• メソッドを再定義すると、
親クラスのメソッド定義が使えなくなる
例: Tensenオブジェクトのfdメソッド
• メソッド中で
super . メソッド名(引数, ...)
のようにメソッドを呼び出すと、
親クラスのメソッドを実行できる
例: Tensenオブジェクトのfdメソッド中で
super.fd(psize)
とすると、Turtleクラスに定義された
本来のfdメソッドが実行される
24
計算機プログラミングI (増原) 2003年度
点線を描くしくみ
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);
}
}
}
25
計算機プログラミングI (増原) 2003年度
点線を描くしくみ
public class Tensen extends House{
int psize = 4;
(略: コンストラクタ)
public void fd(int s){
長さsの点線を描く
}
public void fd(int s){
}
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);
int k, len;
public static voidfor(k
main(…){
= 0, len = 0 ; len + }psize <= s; k++, len+= psize){
(略: TurtleFrameの生成)
if(k % 2 == 0) down();}else up();
Tensen m = new Tensen();
super.fd(psize); }
(略)
ペンを交互に上げ
}
m.polygon(5, 50);
down();
下ろししながら、
}
}
super.fd(s - len);
psizeづつ前進する
super . メソッド名(引数式, …) 親クラスのメソッドを呼び出す
26
計算機プログラミングI (増原) 2003年度
点線を描くしくみ
Turtleクラス
fd(s):
実線を描きながら前進
rt(a):
右回転 Houseクラス
fd(s):
…
継承
(実線を描きながら前進)
polygon(n,s):
fdを使って多角形を描く
• Tensenオブジェクトのfdメソッドを
呼び出すと、再定義されたメソッド
が実行される
• 再定義されたメソッド中の
super.fd(psize)は親クラスのfdメ
ソッドを実行する。結果、Turtleク
ラスのfdメソッドが実行され、実線
が描かれる
Tensenクラス
fd(s):
ペンを上下させながら
super.fd(psize)を呼び出し
polygon(n,s):
継承
(fdを使って多角形を描く)
… 計算機プログラミングI (増原) 2003年度
所属
Tensen
27
まとめると・・・
Turtleクラス
fd(s):
実線を描きながら前進
rt(a):
右回転 Houseクラス
fd(s):
…
継承
(実線を描きながら前進)
polygon(n,s):
fdを使って多角形を描く
Tensenクラス
fd(s):
ペンを上下させながら
super.fd(psize)を呼び出し
polygon(n,s):
継承
(fdを使って多角形を描く)
… 計算機プログラミングI (増原) 2003年度
polygon
fd
所属
Tensen
28
クラスの拡張
class House extends Turtle { … } のようなとき
• Houseは子クラスまたはサブクラス
• Turtleは親クラスまたはスーパークラス
• Houseオブジェクトは、Turtleオブジェクトが持っている全
てのメソッドを持つ (例: fd)
• Houseオブジェクトは、Turtleオブジェクトのかわりに使え
る (例: TurtleFrameオブジェクトに add できる)
Turtle m = new House(); ということが可能!
• HouseオブジェクトはTurtleオブジェクトと違った
動きをするかも知れない(例: fdの再定義)
29
計算機プログラミング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);
}
…
}
30
計算機プログラミングI (増原) 2003年度

Download Report