平成27年度 後期 理学部数学科 計算機数学概論 脇先生

11/19
計算機数学概論
脇 隼人
九州大学 マス・フォア・インダストリ研究所
2015-11-19
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「11/19 の講義・演習」にこの資料を掲載
1 / 15
11/19
JAVA の初歩 5
前回の課題について
今回も良くできていました
ただ, 提出数が減りました. また白紙の提出もありました.
http://webct.kyushu-u.ac.jp にアクセスできなかったせ
いでしょうか?
目標
配列について
配列
変数を番号をつけてまとめたもの ≈ ベクトル
計算機で実現するデータ構造
2 / 15
11/19
配列
例 : 5 教科の平均点を出力するプログラム (Unsued array)
public class average{
public static void main(String[] args){
int japaneselang, math, science, socialstudy, english;
double ave;
japaneselang = 63; math
= 94; science = 83;
socialstudy = 75; english = 83;
ave = japaneselang + math + science + socialstudy + english;
ave = (double)ave/5.0;
System.out.println("Kokugo =
System.out.println("Sugaku =
System.out.println("Rika
=
System.out.println("Shakai =
System.out.println("Eigo
=
System.out.println("Average=
"+japaneselang);
"+math);
"+science);
"+socialstudy);
"+english);
"+ave);
}
}
3 / 15
11/19
例 : 5 教科の平均点を出力するプログラム (Used array)
public class average{
public static void main(String[] args){
int [] points;
double ave;
points = new int[5];
points[0] = 63; points[1] = 94; points[2] = 83;
points[3] = 75; points[4] = 83;
ave = (points[0] + points[1] + points[2] + points[3] + points[4]
System.out.println("Kokugo =
System.out.println("Sugaku =
System.out.println("Rika
=
System.out.println("Shakai =
System.out.println("Eigo
=
System.out.println("Average=
"+points[0]);
"+points[1]);
"+points[2]);
"+points[3]);
"+points[4]);
"+ave);
}
}
4 / 15
11/19
配列の宣言と確保
int [] points;
points = new int[5];
説明
1 行目 points という名前の int 型の配列を宣言
2 行目 メモリ上に int 型の変数 5 つ確保
注意
int[] points = new int[5]; とまとめてよい
5 は配列の長さ. 0 より小さい値を指定するとコンパイル時に
エラーになる
java.lang.NegativeArraySizeException
5 / 15
11/19
配列の各要素を参照
points[0] = 63; points[1] = 94; points[2] = 83;
points[3] = 75; points[4] = 83;
説明
1–2 行目 points の各要素に値を代入
注意
配列の番号を添え字 (index) と呼ぶ.
添え字は 0 から始まり, 4 (=5-1) でおわり
4 より大きい添え字を指定すると実行時にエラーになる
java.lang.ArrayIndexOutOfBoundsException
6 / 15
11/19
配列の宣言と代入
int[] points = {63, 94, 83, 75, 83};
説明
1 行目 points という int 型の配列を宣言して, 各要素に値
を代入
注意
配列に代入するために, プログラムの途中で points = {63,
94, 83, 75, 83}; はできない
7 / 15
11/19
配列の各要素に値を代入
ave = (points[0] + points[1]
System.out.println("Kokugo =
System.out.println("Sugaku =
System.out.println("Rika
=
System.out.println("Shakai =
System.out.println("Eigo
=
+ points[2] + points[3] + p
"+points[0]);
"+points[1]);
"+points[2]);
"+points[3]);
"+points[4]);
説明
1 行目 points の各要素から平均を計算
2–6 行目 points の各要素を出力
注意
points[0] で配列 points の 1 番目の要素が参照できる
points[3] で配列 points の 4 番目の要素が参照できる
8 / 15
11/19
for 文を使ってもっと簡単に書ける
int sum = 0;
for(int i=0; i<5; i++){
sum = sum + points[i];
}
ave = (double)sum/5.0;
説明
2–4 行目 配列 points の各要素を足し算
5 行目 int 型の変数 sum を double 型に変換して割り算
注意
添え字を変数として for 文で計算している. これはよく使う!
配列の長さは, points.length と配列の名前.length とする
と参照できる.
ave = (double)sum/points.length; の場合は, 型変換は
必須
9 / 15
11/19
課題 1 : 正の整数 N をキーボードから入力して, 以下を満たす配
列 array を作成する:
長さ N,
各要素には, 1 から 6 までの擬似乱数で生成される整数値が
代入されている.
この配列 array に対して, 以下を出力するプログラムを提出しな
さい. ファイル名は statistics.java としなさい.
配列 array の全要素
配列 array の標本平均 E , すなわち
N
1 ∑
E=
array[k]
N
k=1
配列 array の標本分散 S, すなわち
1 ∑
(array[k] − E )2
N −1
N
S=
k=1
10 / 15
11/19
課題 1 の出力例
$ java statistics
Input a positive integer :10
array[0] = 2
array[1] = 1
(中略)
array[8] = 5
array[9] = 3
E = 3.1
S = 2.7666666666666666
11 / 15
11/19
課題 2 : 正の整数 N をキーボードから入力して, 以下を満たす配
列 array を作成する:
長さ N,
各要素には, 1 から 5N までの擬似乱数で生成される整数値が
代入されている.
この配列 array に対して, 以下を出力するプログラムを提出しな
さい. ファイル名は findmax.java としなさい.
配列 array の全要素
配列 array の中で一番値の大きい要素の添字 index とその
要素の値 array[index]
12 / 15
11/19
課題 2 の出力例
$ java findmax
Input a positive integer :10
array[0] = 30
array[1] = 2
(中略)
array[7] = 49
array[8] = 34
array[9] = 13
Max : array[7] = 49
13 / 15
11/19
課題 2 のヒント 1 : S = {a1 , . . . , am } に対して m = max S を求
めたい. まず次に気づくこと:
数列 mk (k = 1, . . . , n) を次のように定める:
m1 = a1 , mk+1 = max{mk , ak+1 } (k = 1, . . . , n − 1)
(1)
この時, mn = m である 2 .
次に (1) を JAVA 言語でどう実現するか考える.
最大値を変数 int max に格納する. わざわざ mk のための配
列を作らないで mk の値を max に代入する.
m1 = a1 は, max = array[0] に対応
max{mk , ak+1 } は二つの要素の大きさを比較. もし max >
array[k] なら最大値は max, そうでなければ, ...
(k = 1, . . . , n − 1) とあるから...
1
2
参考にしないほうがよいかも
mk が {a1 , . . . , ak } の最大値であることを数学的帰納法で示せばよい.
14 / 15
11/19
課題の提出先
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「11/19 の課題」をクリック
期限は, 11/19 PM 11:59 です
15 / 15
11/19
11/26
計算機数学概論
脇 隼人
九州大学 マス・フォア・インダストリ研究所
2015-11-26
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「11/26 の講義・演習」にこの資料を掲載
1 / 15
11/19
11/26
findmax について
最大値を取る添字を見つける I
for(int k=0; k<N; k++){
max = Math.max(max,array[k]);
}
for(int j=0; j<N; j++){
if(array[j] == max){
J = j;
}
}
コメント
N 回の比較で済むところを 2N 回比較しているので, もう少
し賢い方法を使いましょう
Math.max を使うと添字まで見つけられません
2 / 15
11/19
11/26
最大値を取る添字を見つける II
for(int i=0; i<N; i++){
if(max>points[i]){
max = max;
}else{
max = points[i];
}
}
int x = 0;
for(int i = 0; i<N; i++){
if(points[i]==max){
x=i;
}
}
コメント
これも, 無駄な比較を N 回やっています
if 文において, 何もしないところは書かなくても構いません
3 / 15
11/19
11/26
最大値を取る添字を見つける III
for(int i=0; i<N; i++){
B = true;
for(int k=0; k<N; k++){
if (points[i]<points[k]){
B = false;
}
}
if (B){
System.out.println("Max : Array["+i+"] = "+points[i]);
}
}
コメント
N 2 回の比較で最大値を探している
多分, 添字を見つけることができなかったので, 無駄な比較を
して添字まで探している
4 / 15
11/19
11/26
最大値を取る添字を全て見つける
int [] array = new int [N];
int [] maxiarray;
int max = 0;
int j;
maxiarray = new int [N];
j = 0;
for(int i=0; i<N; i++){
array[i] = (int)(Math.random()*5*N)+1;
System.out.println("array["+i+"] = "+array[i]);
if(max < array[i]){
max = array[i];
maxiarray = new int [N];
maxiarray[0] = i;
j = 0;
}
else if(max == array[i]){
j = j+1;
maxiarray[j] = i;
}
}
コメント
最大を取る添字が複数個ある場合を想定したプログラム
5 / 15
11/19
11/26
JAVA の初歩 6
目標
二次元配列について
二次元配列
行列のようなもの
一次元配列の復習
int [] array = new int [N]; は
array[0] array[1] array[2] array[3]
int
int
int
int
...
array[N-1]
int
6 / 15
11/19
11/26
二次元配列
例 : 2 × 3 の行列の各要素の総和を計算
public class sumM{
public static void main(String[] args){
int [][] matrix = new int[2][3];
matrix[0][0] = 1; matrix[0][1] = -3; matrix[0][2] = 2;
matrix[1][0] = 4; matrix[1][1] = 1; matrix[1][2] = -1;
for(int i=0; i<2; i++){
for(int j=0; j<3; j++){
System.out.println("matrix["+i+"]["+j+"]="+matrix[i][j])
}
}
int sum = 0;
for(int i=0; i<2; i++){
for(int j=0; j<3; j++){
sum = sum + matrix[i][j];
}
}
System.out.println("sum = "+sum);
}
7 / 15
}
11/19
11/26
配列の宣言と確保
int [][] matrix = new int[2][3];
説明
1 行目 2 × 3 の二次元配列 matrix を宣言. 各要素は整数型
注意
二次元配列は行列に相当する. この場合,
(
)
m11 m12 m13
M=
, where mij ∈ Z
m21 m22 m23
に相当
ただし, 添字の始まりは 0 であることに注意
8 / 15
11/19
11/26
配列の各要素を参照
matrix[0][0] = 1; matrix[0][1] = -3; matrix[0][2] = 2;
matrix[1][0] = 4; matrix[1][1] = 1; matrix[1][2] = -1;
説明
1–2 行目 matrix の各要素に値を代入
注意
次のように宣言と代入をまとめても良い
int [][] matrix = {
{ 1, -3, 2},
{ 4, 1, -1},
};
上記で書く場合は, {} の対応に注意すること
配列同様, プログラムの途中で,
matrix = {
{ 1, -3, 2},
{ 4, 1, -1},
};
とはできない.
9 / 15
11/19
11/26
配列の各要素に値を代入
for(int i=0; i<2; i++){
for(int j=0; j<3; j++){
System.out.println("matrix["+i+"]["+j+"]="+matri
}
}
int sum = 0;
for(int i=0; i<2; i++){
for(int j=0; j<3; j++){
sum = sum + matrix[i][j];
}
}
System.out.println("sum = "+sum);
説明
1–5 行目 matrix の各要素を出力
6–12 行目 matrix の各要素を総和を計算
注意
二重 for 文を使っていることに注意 (i と j) の有効範囲にも
注目)
10 / 15
11/19
11/26
課題 1 : 正の整数 N をキーボードから入力して, 以下を満たす二
次元配列 matrix を作成する:
長さ N × N,
各要素には, −1 以上 1 未満の擬似乱数で生成される浮動小数
点数 1 が代入されている.
この配列 matrix に対して, 以下を出力するプログラムを提出しな
さい. ファイル名は compmat.java としなさい.
二次元配列配列 matrix の全要素
二次元配列配列 matrix を行列 M = (mij )1≤i,j≤N とみなして,
n1 =
N ∑
N
∑
i=1 j=1
v
u N N
u∑ ∑
|mij | and n2 = t
mij2
i=1 j=1
ヒント
Math.abs が絶対値, Math.sqrt が平方根
1
double のこと
11 / 15
11/19
11/26
課題 2 の出力例
$ java compmat
Input a positive integer :3
matrix[0][0]=0.34064437644708856
matrix[0][1]=-0.43628759302949827
matrix[0][2]=0.5066400548104204
matrix[1][0]=0.3225752629191847
matrix[1][1]=-0.3144773090430606
matrix[1][2]=-0.8903180980737053
matrix[2][0]=0.31829218960236005
matrix[2][1]=-0.6441572598720473
matrix[2][2]=0.0683225030029877
v1 = 1.285024712393592
v2 = 0.7875933555173698
12 / 15
11/19
11/26
課題 2 : 正の整数 N をキーボードから入力して, 以下を満たす二
次元配列 matrix を作成する:
長さ N × N,
各要素には, −5 から 4 までの擬似乱数 2 で生成される整数値
が代入されている.
この配列 matrix に対して, 以下を出力するプログラムを提出しな
さい. ファイル名は mulmat.java としなさい.
二次元配列配列 matrix の全要素
二次元配列配列 matrix を行列 M とみなして, 行列積
M × M T . ここで M T は行列 M の転置行列である.
ヒント
行列積 M × M T を要素ごとに書き下すと, for 文をどう使え
ば良いか見えるはず
2
ちょっと細かいけれど Math.random() で生成されるのは, 0 以上 1未満 の
浮動小数点数だから
13 / 15
11/19
11/26
課題 2 の出力例
$ java mulmat
Input a positive integer :3
matrix[0][0]=-3
matrix[0][1]=-2
matrix[0][2]=-2
matrix[1][0]=3
matrix[1][1]=2
matrix[1][2]=-1
matrix[2][0]=2
matrix[2][1]=0
matrix[2][2]=3
mmt[0][0]=17
mmt[0][1]=-11
mmt[0][2]=-12
(中略)
mmt[2][1]=3
mmt[2][2]=13
14 / 15
11/19
11/26
課題の提出先
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「11/26 の課題」をクリック
期限は, 11/26 PM 11:59 です
15 / 15
計算機数学概論
脇 隼人
九州大学 マス・フォア・インダストリ研究所
2015-12-03
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「12/3 の講義・演習」にこの資料を掲載
1/1
11/26 の課題について
M × M T の計算 : K = MM T として, K の各要素を kij , M の各
要素を mij とおくと
kij =
n
∑
mik mjk (1 ≤ i, j, ≤ n)
k=1
である. これを各 i, j についけ計算するだけ
M × MT
mmt[i][j] = 0;
for(int k=0; k<N; k++){
mmt[i][j] = mmt[i][j] + matrix[i][k]*matrix[j][k];
}
2/1
11/26 の課題について
その他
while 文使っている人がいましたが, サイズが決まっているの
で for 文が良いかも
Math.random から整数値や [0, 1) 以外の浮動小数点数を生成
するのに手間取っている人がいましたが,
int matrix[i][j] = (int)(10*Math.random()-5);
や
double matrix[i][j] = 2*math.random()-1;
で十分です.
3/1
JAVA の初歩 7
目標
メソッドについて
メソッド
関数・写像のようなもの
大切なのは, 「おまじない」と定義域・値域
プログラムの中で書いた手続きの共通項を見つけ出して, 抽
象化してプログラムを簡素にするために必須となる知識
「おまじない」さえわかれば, 簡単に使いこなせるはず
4/1
メソッド
例 : 身長, 体重から BMI を計算する
double height = 1.70, weight = 65.0;
double bmi = weight/(height*height);
System.out.println("Your BMI = "+bmi);
if(bmi > 21.0){
System.out.println("Your BMI is bigger than the standard.");
}else if(bmi < 17.0){
System.out.println("Your BMI is smaller than the standard.");
}else{
System.out.println("Your BMI is in standard.");
}
コメント
BMI の計算は, f (height, weight) = bmi という関数とみな
せる
そのあとの手続きも, bmi の値を代入すれば実行できる
5/1
メソッドの例 1
public class bmi{
public static double ComputeBMI(double height, double weight){
double bmi = weight/(height*height);
return bmi;
}
public static void main(String[] args){
double height = 1.70, weight = 65.0;
double bmi = ComputeBMI(height, weight);
}
}
コメント
2 行目 ∼ 5 行目 与えられた height と weight をが与えられると,
bmi を求めるメソッド ComputeBMI の定義
8 行目 ComputeBMI を利用した計算
6/1
メソッドの書き方
public static (返り値) (関数名)(引数 1, 引数 2, ...){
(手続き)
return ...;
}
戻り値 double の値を返すメソッドなら double と書く.
int の値を返すなら int と書く. また, メソッドの最
後は, return を書いて何を返すか明示する
関数名 半角英数字で記述する. f とか g など一文字よりも,
ある程度何をするメソッドなのか分かる名前を書く
と良い
引数 引数を書くときは, 変数の型と変数を合わせて書く
こと
7/1
例 1 : f : R × R → R, (x, y ) → z
public static double examplef(double x, double y){
double z;
(手続き)
return z;
}
例 2 : g : R × Z → Z, (x, y ) → z
public static int exampleg(double x, int y){
int z;
(手続き)
return z;
}
例 3 : 入力 double x に対して, x の値出力するメソッド
public static void exampleh(double x){
System.out.println("x = "+x);
}
何も返さない場合は返り値を void とし, return を書かない
8/1
例 4 : 引数として配列も O.K.
public static double exampleI(double [] vector){
double z = 0.0;
for(int i=0; i<vector.length; i++){
z = z + vector[i];
}
return (z/vector.length);
}
例 5 : 10/29 の課題 : 円周率の近似
public static double Machin(){
double m = 4*Math.atan(1.0/5.0) - Math.atan(1.0/239.0);
return (4*m);
}
9/1
例 6 : bmi の後半
public static void message(double bmi){
System.out.println("Your BMI = "+bmi);
if(bmi > 21.0){
System.out.println("Your BMI is bigger than the standard.
}else if(bmi < 17.0){
System.out.println("Your BMI is smaller than the standard
}else{
System.out.println("Your BMI is in standard.");
}
}
10 / 1
課題 1 : (おみくじ) 10 回おみくじを引くプログラムを作成した
い. そのために下記のプログラムを作成した. この中でおみくじ
の出力 1 をメソッド message として記述して, プログラムを完成
させ提出しなさい.
課題 1 の主要部分
public class Omikuji10{
public static void main(String[] args){
double d;
for(int i=0; i<10; i++){
d = Math.random();
message(d);
}
}
}
なお, 以下の条件を満たすこと:
d の値は出力させなくて良い 2
ファイル名は Omikuji10.java とすること
1
2
10/22 の課題 1 に記載している
10/22 の課題 1 と異なる
11 / 1
課題 2 : (Collatz の問題) 正の整数 n に対して次の操作を適用
する:
(操作) : n が偶数なら n/2 とする. n が奇数なら 3n + 1 とする
与えられた n に対して (操作) を繰り返し適用すると 5 × 260 まで
の n であれば必ず 1 になることが知られている 3 .
与えられた n に対して, 初めて 1 になるまでに要した (操作) の回
数を f (n) とする. キーボードから入力された n に対して f (n) を出
力するプログラムを提出しなさい. なお以下の条件を満たすこと:
「入力された n に対して, f (n) を戻り値とする」メソッドを
作ること. メソッド名はなんでも良い
ファイル名は, collatz.java とすること
(必須ではないが, 興味があれば)n = 1 ∼ 105 までの様々な n
に対して試すこと
3
https://en.wikipedia.org/wiki/Collatz_conjecture
12 / 1
課題の提出先
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「12/3 の課題」をクリック
期限は, 12/3 PM 11:59 です
13 / 1
12/3
12/10
計算機数学概論
脇 隼人
九州大学 マス・フォア・インダストリ研究所
2015-12-10
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「12/10 の講義・演習」にこの資料を掲載
1 / 13
12/3
12/10
12/3 の課題について
コメント : 返り値があるメソッドなら, main でも返り値を受け
取る変数を用意する
あまり良くない例
public static int f(int n){
int N = 0;
(中略)
return N;
}
public static void main(String[] args){
(中略)
f(n);
}
8 行目は
int count = f(n);
とした方が良い.
2 / 13
12/3
12/10
コメント (続き) : メソッドで利用する変数と main で利用する
変数の関係
何が出力されるでしょう? 5 でしょうか 15 でしょうか?
public static void function(int n){
n = n + 10;
}
public static void main(String[] args){
int n = 5;
function(n);
System.out.println("n="+n);
}
メソッドで利用される変数はメソッドの中だけで有効
なお「main から function を呼び出す」という
3 / 13
12/3
12/10
JAVA の初歩 8
目標
ファイルの入出力について
数値実験などに必須となる技術
「こんなこともできる」ということを知る・経験することが
大切
JAVA だけでなくたいていのプログラム言語で利用出来る
csv ファイル
カンマで区切られた表
1 つの行 (レコード) に, 1 つ以上の要素 (フィールド) がある
各レコードは, 同じ数のフィールドで構成される
4 / 13
12/3
12/10
ファイルからの入力
例 : 10 回の課題 (1 回 10 点満点) から各学生の講義に対する評
定を決めたい
初めの列は名前, 次の列からは, 各回の課題の点数
評定は 90 点以上 (A), 80 点以上 90 点未満 (B), 70 点以上 80
点未満 (C), 60 点以上 70 点未満 (D), 60 点未満 (F)
10 回の課題の各点数をまとめたファイル : data.csv
Student1,9,10,2,10,7,1,3,6,10,10
Student2,2,10,10,5,9,2,5,10,8,10
Student3,7,1,9,10,7,8,8,4,7,2
...(中略)...
Student98,1,10,7,10,2,10,8,6,5,3
Student99,8,3,1,8,7,8,7,5,4,9
Student100,4,9,8,9,6,7,10,5,1,9
注意
学生に対応する行の点の合計が, その学生の合計点
例えば, Student2 の合計点は 71 点で C
5 / 13
12/3
12/10
getGrade.java (これは web からダウンロードできる)
public class getGrade{
public static void main(String [] args){
int M = 100; int N = 11;
String [][] stringArray = new String[M][N];
int
[][] points
= new int[M][N-1];
String []
names
= new String[M];
readFile(stringArray);
separateP(stringArray, points);
separateS(stringArray, names);
}
(中略)
}
コメント : csv ファイルの読み込み部分 readFile はこちらで作
成済み
8 行目 二次元配列 points には学生の各課題の成績が記録.
points[i][j] は (i+1) 番目の学生の (j+1) 回目の
課題の成績が記録. 配列の長さは 100×10
9 行目 配列 names には学生の名前を記録. names[i] は
(i+1) 番目の学生の名前が記録. 配列の長さは 100
6 / 13
12/3
12/10
課題 1 : getGrade.java にある points を使って評定 A, B, C,
D, F の数を出力するプログラムを完成させ提出しなさい. なお,
(意味のある) メソッドを作ることを推奨するが, 作らなくて
もよい.
余裕があれば, 最高得点やその学生, 最低得点やその学生, 平
均点などを出力させるなど, いろいろと工夫しなさい.
data.csv は改変してはいけない.
getGrade.java は課題のページに掲載している.
出力例 (ただし, 数はデタラメ)
A : 10
B : 30
C : 20
D : 10
F : 5
Max : 100 (Student73)
Min : 15 (Student4)
Average : 55.5
7 / 13
12/3
12/10
ファイルへ出力
例 : (Collatz の続き) 前回の課題で入力された n に対して 1 にな
るための (操作) の回数 F (n) を求めるプログラム collatz.java
を作成した. n = 1 ∼ 1000 に対してこの F (n) を collatz.csv と
いうファイルに書き出すプログラム collatz2.java を作成し
たい.
collatz2.java というプログラムでは, collatz.csv を書き
出すメソッドを用意した.
csv ファイルを書き出すメソッド
void writeVals(int [] array)
array に n = 1 から n = 1000 までの F (n) を記録させると
writeVals(array); で collatz.csv が作成できる.
8 / 13
12/3
12/10
課題 2 : 課題のページに掲載している collatz2.java を完成さ
せて提出しなさい. さらに, gnuplot を使って 1 , 横軸 n 縦軸 F (n)
となるグラフをプロットして, collatz.png というファイルを作
成して提出しなさい.
余力があれば : n = 1 から n = 1000 までの
G (n) = “n が 1 になるまでのに生成される数の中での最大数”
と定めて, 課題 2 と同様に横軸 n 縦軸 G (n) のグラフを作成しなさ
い. 例えば,
10 → 5 → 16 → 8 → 4 → 2 → 1 ∴ G (10) = 16
となる. また
H(k) = “F (n) = k となる n の個数”
に対して課題 2 と同様に横軸 n 縦軸 H(n) のグラフを作成するの
も面白いかもしれない.
1
次のページを参照
9 / 13
12/3
12/10
Gnuplot の使い方
使い方の詳細は, 「Gnuplot」,「gnuplot」などで検索する
csv をグラフに表示
1 ターミナルで, 「gnuplot」とタイプ
2 「set datafile separator ","」 とタイプ
3 「plot "collatz.csv" w lp」とタイプすると, グラフが
表示
グラフを collatz.png で保存
「set terminal png 」とタイプ
2 「set output "collatz.png"」 とタイプ
3 「plot "collatz.csv" w lp」とタイプすると,
collatz.png が生成される
4 再度「set output」とすると, グラフを表示する
なお, gnuplot を終了するには「quit」
1
10 / 13
12/3
12/10
注意 1 : gnuplot を起動すると, 以下の画面になるかもしれない
が, 「キャンセル」を押してください.
11 / 13
12/3
12/10
注意 2 :
私有の Mac には gnuplot が入っていないと思うので, 各自検
索してインストールしてください.
難しいと思うので, iMac にログインして作業すると良いと思
います.
12 / 13
12/3
12/10
課題の提出先
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「12/10 の課題」をクリック
期限は, 12/10 PM 11:59 です
13 / 13
計算機数学概論
脇 隼人
九州大学 マス・フォア・インダストリ研究所
2015-12-17
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「12/17 の講義・演習」にこの資料を掲載
1/1
12/10 の課題について
{{\tt getGrade.java}}
int M = 100; int N = 11;
String [][] stringArray = new String[M][N];
int
[][] points
= new int[M][N-1];;
String []
names
= new String[M];
(中略)
int[] sum = new int[100];
for(int i=0; i<100; i++){
for(int j=0; j<10; j++){
sum[i] = sum[i] + points[i][j];
}
}
(以下略)
コメント
i<100 や j<10 は i<M や j<N-1 などと書いた方が間違いが少
ない
2/1
無限ループするプログラム
int m = 0;
for(int n=1; n<1000; n++){
m = 0;
while(n != 1){
if(n % 2 == 0){
n = n/2;
}else{
n = 2*n + 1;
}
m = m + 1;
}
}
無限ループする理由
for 文にある n が while 文の中で最終的に n= 1 になる
n++しても n= 2 で for 文で n= 1 になる
これの繰り返し=無限ループ
3/1
getGrade.java の結果
A : 0
B : 0
C : 4
D : 24
F : 72
MAX : Student61 : 76
MIN : Student60 : 33
Ave : 53.78
4/1
Figure : F (n) のプロット図
5/1
Figure : G (n) のプロット図
6/1
再帰的アルゴリズム
目標
再帰的アルゴリズムを知り, 簡単なものを実装する
メソッドを利用
数学的帰納法と同じ考え
JAVA だけでなくたいていのプログラム言語で利用出来る
再帰 (さいき) アルゴリズム
手続きの記述の中で, それ自身への参照があらわれる手続き
再帰呼び出し, 再帰プログラミングなどと呼ばれる技法
7/1
階乗の計算
例 1 : n! = n · (n − 1) · (n − 2) · · · 2 · 1 の · · · を丁寧に書くと
{
1
(n = 1)
n! =
n · (n − 1)! (n > 1)
となる
この定義は再帰的になっている
注目すべき点は, 定義自身だけでなく終了する条件もある
階乗 n! を計算する再帰的アルゴリズム
public static int factorial(int n){
int val;
if(n == 1){
val = 1;
}else{
val = n * factorial(n-1);
}
return val;
}
8/1
フィボナッチ数列
例2 :
{
F (n) =
1
(n = 1, 2)
F (n − 1) + F (n − 2) (n ≥ 3)
この定義も再帰的になっている & 定義自身だけでなく終了
する条件もある
フィボナッチ数列 F (n) を計算する再帰的アルゴリズム
public static int fib(int n){
int val;
if(n == 1 || n == 2){
val = 1;
}else{
val = fib(n-1) + fib(n-2);
}
return val;
}
9/1
fibonacci.java
ダウンロードして, 27 行目の int N = 5; の数字を
N = 10 ∼ 45 に変えて自分で動かしなさい
fibonacci.java には, 再帰を使う計算と使わない計算の 2
種類のメソッドが実装されている
N = 45 くらいにすると 2 つのメソッドの違いがわかる
2 つのメソッドの違い
fib(n) は再帰を使う
fib2(n) は再帰を使わない
計算時間に差が出る. fib2(n) の方が速い
なぜでしょう?
10 / 1
理由 : 2 つのメソッドで要する足し算の回数の違い
fib2(n) では, n − 2 回 ∴ 計 43 回
fib(n) では, G (n) 回かかるとすると,
G (n) = G (n − 1) + G (n − 2) + 1
⇒ (G (n) + 1) = (G (n − 1) + 1) + (G (n − 2) + 1)
∴ G (n) + 1 自身がフィボナッチ数列である
F (45) = 1134903170 なので, fib2(n) と比べ物にならないほ
ど足し算をたくさんする
11 / 1
計算量 (あるいは, 計算の複雑さ) : ざっくりとして定義
計算機の数理モデルにおいて, 入力に対して手続きが要する
最大ステップ数
ここでは,
入力が n
手続きがフィボナッチ数列を求めるメソッド
最大ステップ数が足し算の回数
に対応
参考書 : アルゴリズムや計算量に興味があれば次の書籍を推薦
アルゴリズムイントロダクション
計算理論の基礎
The Art of Computer Programming
12 / 1
再帰を使う時・使わない時
再帰を使う
再帰を使うと簡単に書ける場合
再帰を使わない
再帰を使うと計算時間が膨大になることがある
再帰を使わなくても書ける場合
13 / 1
課題 1 : (組み合わせの数) 非負の整数 n, k に対して次のように
定義する:

( ) 
(
)1(
) (n = k, k = 0)
n
n−1
n−1
=
+
(それ以外)

k
k −1
k
( )
( )
入力した n に対して, n0 から nn を全て列挙するプログラムを提
出しなさい. なお以下の条件を満たすこと:
(n )
k を再帰的アルゴリズムで求めること
ファイル名は combination.java とすること
もし, 余裕があれば, 再帰を使わないアルゴリズムと比べてみると
良い.
14 / 1
課題 2 : (Euclid の互除法) 二つの自然数 a, b (a ≥ b) の最大公約
数 GCD(a, b) を求める. なお, GCD(a, 0) = a と定める. a を b で
割った時の余りを r とおくと,
GCD(a, b) = GCD(b, r )
が成り立つ. Euclid の互除法を再帰を使うメソッドと再帰を使わ
ないメソッドの二つをプログラムして euclidean.java として提
出しなさい. また,
GCD(1826, 1742), GCD(783049, 152963),
GCD(1134903170, 701408733) を求めてコメント欄に書きな
さい,
15 / 1
課題 2 の続き : Euclid の互除法の手続きは以下のとおり:
1
入力 a, b (a ≥ b)
2
もし b = 0 ならば, a を最大公約数として出力
3
b ̸= 0 であれば, a ← b, b ← r (ただし r は a を b で割った時
の余り) として, 2 に戻る.
注意 : ペア a, b は左くる数字が必ず右にくる数字より大きいか
等しい
16 / 1
課題の提出先
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「12/17 の課題」をクリック
期限は, 12/17 PM 11:59 です
17 / 1
計算機数学概論
脇 隼人
九州大学 マス・フォア・インダストリ研究所
2016-01-07
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「1/7 の講義・演習」にこの資料を掲載
1/1
12/17 の課題について
euclidean.java : 非再帰アルゴリズムで苦戦していたようで
すが, 次のように書くと正しく動きます
非再帰なユークリッドの互除法
public static int gcd1(int a, int b){
int tmp;
while(b != 0){
/* a を b に, b を a%b に入れ替える */
tmp = a % b;
a = b;
b = tmp;
}
return a;
}
2/1
アルゴリズムの実装
目標
アルゴリズムを考えて JAVA で実装する
アルゴリズムと擬似コード
解決したい問題からいきなりコンピュータ言語で実装して計
算することは難しい
問題の理解して解決するためのアルゴリズムを考える
アルゴリズムをコンピュータ言語で実現するためには, ま
ず擬似コードで記述する
擬似コードで書けると (簡単な) アルゴリズムはコンピュータ
言語で実装しやすくなる
さらにアルゴリズムの解析 (最悪どれくらい計算コストがか
かるかなど) もできる
3/1
ソート (整列)
問題 : N 個の整数を小さい順に並び替える
考え方 :
コンピュータ言語で実現するためには, 入力と出力を定義し
なければならない
入力 : N 個の整数 a1 , . . . , aN
出力 : ai1 ≤ ai2 ≤ · · · ≤ aiN となるように a1 , . . . , aN を並び替える
例 : a1 = 5, a2 = 3, a3 = 6, a4 = 7, a5 = 1 ならば,
a5 ≤ a2 ≤ a1 ≤ a3 ≤ a4 の順に出力する
要素の並び替えることをソート (整列) するという
4/1
ソートのアルゴリズム : たくさんある
挿入ソート
バブルソート (単純交換法)
マージソート
クイックソートなど
挿入ソート : これでソートできることの証明や計算量の解析は
しない
a[1] から a[k-1] までがソートされていると仮定する. a[k]
を a[1] から a[k] までソートされるように挿入する
これで a[1] から a[k] までソートされている
これを k=2 から N まで繰り返す
5/1
挿入ソートの例
1
5 3 6 7 1 「ソート済みの要素に下線」
2
5 3 6 7 1 → 3 5 6 7 1 「3 の位置を探す」
3
3 5 6 7 1 → 3 5 6 7 1 「6 の位置を探す」
4
3 5 6 7 1 → 3 5 6 7 1 「7 の位置を探す」
5
3 5 6 7 1 → 1 3 5 6 7 「1 の位置を探す」
6
1 3 5 6 7 「終了」
InsertionSort の擬似コード?
for k = 2 to N
/* a[1] から a[k-1] までソート済み */
a[1] から a[k] が小さい順に並ぶように a[k] を挿入する;
end
コメント : これではまだ不十分. もう少し詳しく書く必要がある
6/1
InsertionSort の擬似コード
for k = 2 to N
key = a[k]; i = k-1;
while i > 0 かつ a[i] > key
a[i+1] = a[i];
i = i - 1;
end
a[i+1] = key;
end
挿入ソートの例 (最後の反復)
3 5 6 7 1 → 1 3 5 6 7 「1 の位置を探す」
擬似コードでは k=5, key = a[5] = 1, i = 4
i > 0 かつ a[4] > key なので, a[5] = 7, i = 3 となる
i > 0 かつ a[3] > key なので, a[4] = 6, i = 2 となる
i > 0 かつ a[2] > key なので, a[3] = 5, i = 1 となる
i > 0 かつ a[1] > key なので, a[2] = 3, i = 0 となる
while を抜ける. a[1] = 1 となる
7/1
バブルソート : これでソートできることの証明や計算量の解析
はしない
1 番目の要素と 2 番目の要素を比較して, 大小関係が逆であ
れば交換する
2 番目の要素と 3 番目の要素を比較して, 大小関係が逆であ
れば交換する
これを (N − 1) 番目と N 番目まで行う. これで N 番目の要素
は一番大きい要素になる
次に同じことを (N − 1) 番目の要素まで行う. これで (N − 1)
番目の要素は二番目に大きい要素になる
これを繰り返すと, 1 番目から N 番目まで小さい順に並ぶ
8/1
バブルソートの例
1
53671
2
53671→35671
3
35671
4
35671
5
3 5 6 7 1 → 3 5 6 1 7 「一番目に大きい 7 が a5 」
6
35617
7
35617
8
3 5 6 1 7 → 3 5 1 6 7「二番目に大きい 6 が a4 」
9
35167
10
3 5 1 6 7 → 3 1 5 6 7「三番目に大きい 5 が a3 」
11
35167
12
3 1 5 6 7「四番目に大きい 3a2 」
13
1 3 5 6 7 「終了」
9/1
バブルソート (擬似コード) :
bubbleSort
for i = 1 to N-1
for j = 1 to N - i
if a[j] > a[j+1]
swap(a[j], a[j+1]); /* a[j] と a[j+1] を交換 */
end
end
end
注意 :
swap は自分で考えましょう
擬似コードはアルゴリズムを理解しやすくしたもの
JAVA や, C 言語, C++に似ているが必ずしも同じではない.
例えば配列の添字に注意
10 / 1
課題 : sort.java というファイルを作って, その中で挿入ソー
トとバブルソートを記述して提出しなさい.
数列 {an }N
n=1 は整数型の配列で 1 から 1000 までの乱数で生
成しなさい
N を 200, 400, 600, 800, 1000 として, 挿入ソートやバブル
ソートでどれくらい時間がかかるか計測して, コメント欄に
書きなさい
時間の計測の仕方
一番簡単なのは, time コマンドの利用 (user time)
time java sort で, 出力される user time がプログラム自
体の実行にかかった時間
11 / 1
時間の計測の仕方 (続き)
1/1000 秒の測り方
long start = System.nanoTime();
(手続き)
long end = System.nanoTime();
System.out.println((end - start) / 1000000f + "ms");
これで (手続き) の要する時間を計測できる
コメント : 実は 1/1000 秒まで正確に計測しなくても良い
12 / 1
配列に関する注意 : 次のコードでは array の値は何になるで
しょうか?
public static void nothing(int [] array){
array[0] = 35;
array[1] = 45;
}
public static void main(String [] args){
int [] array = new int [2];
array[0] = 1; array[1] = 2;
System.out.println("array[0] = "+array[0]);
System.out.println("array[1] = "+array[1]);
nothing(array);
System.out.println("array[0] = "+array[0]);
System.out.println("array[1] = "+array[1]);
}
13 / 1
配列に関する注意の続き : 出力は以下の通りである
array[0]
array[1]
array[0]
array[1]
=
=
=
=
1
2
35
45
コメント :
配列の場合, メソッド内での変更はメソッドが終了しても
残ってしまう
乱数で発生させたソート前の配列は複製しておいたほうが
よい
14 / 1
課題の提出先
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「1/7 の課題」をクリック
期限は, 1/7 PM 11:59 です
15 / 1
1/7
1/21
計算機数学概論
脇 隼人
九州大学 マス・フォア・インダストリ研究所
2016-01-21·28
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「1/21 の講義・演習」にこの資料を掲載
1 / 16
1/7
1/21
アルゴリズムの実装
目標
アルゴリズムを考えて今までの知識を使って JAVA で実装
する
プログラムを書いてシミュレーションすることで, 問題の背
後にある数理を知る
構成論的な証明だとプログラムで実現して確認することがで
きることもある, ことを知る
テーマ :
今回と 1/28 の時間を使って課題に取り組む
確率論, 数値解析, 整数問題などが題材
アルゴリズムが複雑だと思った時は, ノートに擬似コードを
一度書いてみる
興味を持った課題については各自掘り下げてみる
2 / 16
1/7
1/21
課題 1 : コインを投げて表ならば 1, 裏ならば 0 としてこの操作
を繰り返して記録する. 初めて 0, 1 のパターン a = a1 a2 . . . ak が
出る時間 Na とする. 例えば
01001010101100010101110 . . .
で, あれば N00 = 4, N10 = 3, N101 = 7 である. 表の出る確率を
1/2 裏の出る確率を 1/2 として, a = 00, 01, 10, 11 の 4 パターンの
期待値を計算したい. ここでは, それをシミュレーションで近似的
に求めることにする. ファイル名は binsequence.java として提
出しなさい.
1 回の試行でコインを投げる回数 1000 とする
これを 10000 回実行する
各回で Na を求めて平均を出力する
(余力があれば) 表が出る確率を変えたり, a の列を変えて計
算しなさい
3 / 16
1/7
1/21
∫
b
f (x) dx を台形の面積の和で近似
課題 2 : (複合台形則) S :=
a
y
y = f (x)
f (xj−1 )
f (xj )
T
a = x0
x1
xj−1
xj
xn−1 b = xn
h = (b − a)/n として, xj = a + jh (j = 0, . . . , n)
台形 T の面積
(f (xj−1 ) + f (xj ))h
台形 T の面積 =
2
台形を全て足す
n
∑
(f (xj−1 ) + f (xj ))h
S(n) :=
2
j=1
x
4 / 16
1/7
1/21
課題 2 の続き : 以下の二つの積分を複合台形則を利用して値を
求めなさい. ファイル名は trapezoid.java にして提出すること.
以下の二つの積分を求めなさい:
∫ 1
(1)
S1 =
0
∫
(2)
1
dx,
1+x
1
e πx sin(πx) dx
S2 =
0
n = 2k として, k = 1, . . . , 10 に対する誤差 |S − S(n)| を全て
出力させなさい 1 .
f (x) の関数値の計算をメソッドとして用意するとプログラム
が楽になるかも
1
余力があれば, n を変化させると誤差がどれくらい変化するか推測してコメ
ント欄に記入しなさい
5 / 16
1/7
1/21
課題 3 : (行列の掛け算) 下記に従って n × n 行列 A, B の掛け算
を行うプログラムを提出しなさい. ファイル名は matmul.java と
すること.
A, B の各要素は-1 以上 1 未満の擬似乱数で生成される浮動
小数点数とする
積 AB を計算するのにかかる時間を出力しなさい 2
2
余力があれば, n を 100, 500, 1000, 1500, 2000 と変化させると計測時間がど
のように変化するかコメント欄に記入しなさい
6 / 16
1/7
1/21
課題 4 : (不思議な 4 桁) 入力 N を 4 桁の正の整数とする. 操作
g は「N の 4 桁を並び替えてできる最大数と最小数の差を返す 」
とする. この操作を
N → g (N) → g (g (N)) → g (g (g (N))) → · · ·
と繰り返すとどうなるか確認するプログラムを書き提出しなさい.
ファイル名は, gcomp.java とすること. また
N として, N = 1111, 2222, . . . , 9999 以外を入力としなさい
N が 3 桁の場合は千の位に 0 を補って 4 桁の整数にすること.
例えば N = 381 ならば,
g (381) = g (0381) = 8310 − 0138 = 8172 である.
(余力があれば) 5 桁, 6 桁など桁を増やして同様の操作を適用
するとどうなるか確認せよ.
7 / 16
1/7
1/21
課題 5 : (中間値の定理)
中間値の定理
連続関数 f : R → R と区間 [a, b] に対して, もし f (a)f (b) < 0 なら
ば f (c) = 0 となる c が開区間 (a, b) に存在する.
中間値の定理の証明の概要
∞
次の点列 {an }∞
n=1 と {bn }n=1 を構成した:
a = a1 ≤ a2 ≤ · · · ≤ an ≤ · · · ≤ c ≤ · · · ≤ bn ≤ · · · ≤ b2 ≤ b1 = b
この時
{
an =
{
bn =
(
an−1 +bn−1
2
if f
an−1
o.w.
an−1 +bn−1
2
if f
bn−1
o.w.
(
an−1 +bn−1
2
an−1 +bn−1
2
)
<0
, (n = 2, 3, . . . , )
)
>0
ただし f (a) < 0, f (b) > 0 を仮定している
limn→∞ an = limn→∞ bn = c が成り立つ
(n = 2, 3, . . . , )
8 / 16
1/7
1/21
課題 5 の続き 中間値の定理の証明をヒントに, 以下の方程式の解
のうち区間 I に入っている解を求めるプログラムを書いて提出し
なさい.
(1)
f (x) = x 3 − 3x + 3 = 0, I = [−3, 0]
(2)
f (x) = tanh(x) + 0.2x + 0.3 = 0, I = [−1, 1]
なお,
ファイル名は bisection.java とすること
無限回の反復は不可能なので, 十分小さい ϵ > 0 に対して
bn − an < ϵ となれば反復を終了して解 3 を出力させなさい
ϵ は 10−6 から 10−8 くらいで良い
tanh(x) は Math.tanh(x) で計算できる
3
出力すべき解は an あるいは bn でよい
9 / 16
1/7
1/21
課題 6 : (1 次元ランダムウォーク) x(t) を点 Q の時刻 t での数
直線上の位置とし, x(0) = 0 と定める. 確率 p で表, 確率 1 − p で
裏が出るコインが一枚あるとする. x(t) に対して x(t + 1) を次の
様に定める:
{
x(t) + 1 (コインが表の時)
x(t + 1) =
x(t) − 1 (コインが裏の時)
この操作を (無限回) 繰り返すと点 Q はいつか原点 0 に戻ってく
るだろうか.
10 / 16
1/7
1/21
Figure: p = 0.5 & 100 回の操作
11 / 16
1/7
1/21
Figure: p = 0.5 & 10000 回の操作
12 / 16
1/7
1/21
Figure: p = 0.8 & 100 回の操作
13 / 16
1/7
1/21
Figure: p = 0.8 & 10000 回の操作
14 / 16
1/7
1/21
課題 6 の続き : これを調べるために, 次のプログラムを作成して
提出しなさい. 名前は randwalk.java とすること:
確率 p を入力して, 1000 回ランダムウォークを発生させて,
P(p) =
原点に帰ってきた回数
1000
で, 点 Q が原点に返ってくる確率を P(p) で近似して, これを
出力する
1 回のランダムウォークで「無限回の操作」を実施すること
は不可能なので, 「100000 回の操作」にする.
p を変えて P(p) の値を調べなさい. 特に p がどの値だと必ず
帰ってくるか予想しなさい 4 .
4
余力があれば調べたり, 自分で考えたりして p を特定して証明しなさい
15 / 16
1/7
1/21
課題の提出先
URL : http://bb9.iii.kyushu-u.ac.jp
上記から, 「計算機数学概論」を選択
「コンテンツ」→「1/21・1/28 の課題」をクリック
期限は, 1/28 PM 11:59 です
16 / 16