情報基礎II (第1回)

情報基礎Ⅱ/基礎工学Ⅲ
(第12回)
月曜4限
担当:北川 晃
例題:疑似乱数列の発生
混合型合同法を用いて,乱数の初期値より,
擬似乱数列を生成するプログラムを作れ.
考え方:
1. 初期値
2.
を読み込む.
を計算し, で割ったあまりを計算する.
3. あまりを次の乱数として,
とおく.
4. さらに次の乱数を計算する.
  2 ,   12869, c  6925
15
プログラミング演習
疑似乱数列を発生させるプログラムを用いて,
六面サイコロの出目を生成するプログラムを作れ.
考え方
• 混合型合同法では,0≦x<μの乱数が得られる.
• 得られた乱数をμで割れば,[0,1)の乱数が得られる.
• [0,1)の規格化乱数が得られれば,これに(b-a)
をかけてaを加えることで,[a,b)の乱数が得られる.
• 実数で得られる乱数列を整数化する.
サイコロの出目:出力例
サイコロの出目の発生:プログラム例
Dim mu As Integer = 2 ^ 15
Sub Main()
Console.Title = "乱数の発生"
Dim x, x_dice As Integer, n As Integer = 100
Console.WriteLine("xの初期値(0-32768)を入力して下さい")
Console.Write("x0=")
一様乱数を生成する関数
x = Console.ReadLine()
For i As Integer = 1 To n
x_dice = Fix(6 * uni_rnd(x) / mu + 1)
If i Mod 10 <> 0 Then
Console.Write("{0,5}", x_dice)
1≦x<7の
Else
Console.WriteLine("{0,5}", x_dice) 実数列を生成
End If
x = uni_rnd(x)
Next
xを次の値に置き直す
End Sub
サイコロの出目の発生:プログラム例(つづき)
Function uni_rnd(x) As Single
Dim lambda, c As Integer
lambda = 12869
c = 6925
x = (lambda * x + c) Mod mu
Return x
End Function
一様乱数を計算する
関数副プログラム
プログラミング演習
六面サイコロの出目に関するプログラムを用いて,
各出目の頻度を計算せよ.
ほぼ均等に
1/6=0.1666…
サイコロの出目の頻度:プログラム例
Dim mu As Integer = 2 ^ 15
各目の
Sub Main()
カウンター
Console.Title = "乱数の発生"
Dim x, x_dice, n, c1, c2, c3, c4, c5, c6 As Integer
各目の Dim p1, p2, p3, p4, p5, p6 As Single
頻度
c1 = 0 : c2 = 0 : c3 = 0 : c4 = 0 : c5 = 0 : c6 = 0
Console.WriteLine("xの初期値(0-32768)を入力して下さい")
Console.Write("x0=")
x = Console.ReadLine()
n = 1000000
試行回数
サイコロの出目の頻度:プログラム例(つづき)
For i As Integer = 1 To n
x_dice = Fix(6 * uni_rnd(x) / mu + 1)
Select Case x_dice
Case 1
c1 = c1 + 1
出目の判定
Case 2
とカウント
c2 = c2 + 1
Case 3
c3 = c3 + 1
Case 4
c4 = c4 + 1
Case 5
c5 = c5 + 1
Case 6
c6 = c6 + 1
End Select
x = uni_rnd(x)
Next
サイコロの出目の頻度:プログラム例(つづき)
p1 = c1 / n
Console.WriteLine("1の確率は{0}",
p2 = c2 / n
Console.WriteLine("2の確率は{0}",
p3 = c3 / n
Console.WriteLine("3の確率は{0}",
p4 = c4 / n
Console.WriteLine("4の確率は{0}",
p5 = c5 / n
Console.WriteLine("5の確率は{0}",
p6 = c6 / n
Console.WriteLine("6の確率は{0}",
End Sub
p1)
p2)
p3)
p4)
p5)
p6)
出目の頻度
と表示
サイコロの出目の頻度:プログラム例(つづき)
Function uni_rnd(x) As Single
Dim lambda, c As Integer
lambda = 12869
c = 6925
x = (lambda * x + c) Mod mu
Return x
End Function
一様乱数を計算する
関数副プログラム
プログラミング演習
y
1
-1≦x<1,-1≦y<1の
範囲に無作為にn個の点を打ち,
そのうち単位円内部にある点の
1
O
数をncとする.nc/nの値を計算せよ.
モンテカルロ法
考え方:
• 領域は対称なので,第一象限だけを考えればよい.
• 乱数により各点を計算し,x2+y2≦1ならばncを1だけ増やす.
• 各領域に点が打たれる頻度が,面積に比例するので…
x
モンテカルロ法:出力例
モンテカルロ法:プログラム例(つづき)
Dim mu As Integer = 2 ^ 15
Sub Main()
Console.Title = "モンテカルロ法による円周率の計算"
Dim c, n, x, y As Integer
Console.WriteLine("繰り返し回数nを入力してください")
Console.Write("n=")
n = Console.ReadLine()
x = 0
y = 2000
c = 0
初期値は固定した
円の中にある数のカウンター
座標の計算
For i As Integer = 1 To n
x = uni_rnd(x)
y = uni_rnd(y)
If (x / mu) ^ 2 + (y / mu) ^ 2 <= 1 Then c = c + 1
Next
座標が円の中にあるか判定
モンテカルロ法:プログラム例(つづき)
Console.WriteLine("π={0}", 4 * c / n)
End Sub
Function uni_rnd(x) As Single
Dim lambda, c As Integer
lambda = 12869
c = 6925
x = (lambda * x + c) Mod mu
Return x
End Function
計算値の書き出し
論理型変数
•「真」もしくは「偽」に関する情報処理を扱う.
•処理規則は論理代数(ブール代数)に従う.
•論理定数:真を’True’で,偽を’False’で表し,
これ以外の値は取らない.
論理演算子
• a = True
• b = False
• c = a And b
• d = Not b
•
•
•
•
•
Not
And
Or
=
<>
(
(
(
(
(
)
)
)
)
 )
:否定
:論理積
:論理和
:論理等価
:論理非等価
論理演算子
書き方
結果が真になるための条件
Not X
X And Y
X Or Y
X = Y
X <> Y
Xが真でない
X,Yが共に真
X,Yの少なくとも一方が真
XとYが共に真,または共に偽
XとYの内の一方が真で,他方が偽
上記以外のときは,結果が偽
例題:論理代数による演算処理
Dim a, b, c, d, e, f, g, h As Boolean
a = True
b = False
aに「真」を,bに
「偽」を代入する
c = a
d = Not a
cにaの値を,
dにbの否定を代入する
e
f
g
h
=
=
=
=
a
a
a
a
And b
Or b
= b
<> b
g = (a = b)と書いてもよい
一つ目の“=”は「代入」を,
二つ目は「論理等価」を
表していることに注意
Console.WriteLine("a={0,6}",
Console.WriteLine("c={0,6}",
Console.WriteLine("e={0,6}",
Console.WriteLine("g={0,6}",
a)
c)
e)
g)
:
:
:
:
C:
D:
E:
真
偽
偽
F:
真
G:
偽
H:
真
Console.WriteLine("b={0,6}",
Console.WriteLine("d={0,6}",
Console.WriteLine("f={0,6}",
Console.WriteLine("h={0,6}",
b)
d)
f)
h)
論理代数による演算処理:出力例
A:
B:
C:
D:
E:
真
偽
真
偽
偽
F:
真
G:
偽
H:
真
例題:真理値表
論理式
a  b  c 
の真理値表を与えるプログラムを作れ.
真理値表:
変数の取り得るすべての値の組み合わせに対し,
論理式がとる値を表にしたもの.
例:a∧bの真理値表
a
b
ab
真
真
偽
偽
真
偽
真
偽
真
偽
偽
偽
真理値表:出力例
要素の数を
指定しない
真理値表:プログラム例
Dim v() As Boolean = {True, False}
配列に初期値を
代入する場合
Console.WriteLine("
a
b
c result")
Console.WriteLine("------------------------------------")
For i As Integer = 0 To 1
For j As Integer = 0 To 1
For k As Integer = 0 To 1
Console.WriteLine(" {0,8} {1,8} {2,8} {3,8}", _
v(i), v(j), v(k), v(i) And Not (v(j) Or v(k)))
Next
Next
a bc
a, b, c
Next


例題:エラトステネスのふるい
n までの素数を求めて出力するプログラムを作れ.
アルゴリズム:エラトステネスのふるい
•2の倍数(2自身を除く)に全部印をつける.
•3の倍数(3自身を除く)に全部印をつける.
•5の倍数(5自身を除く)に全部印をつける.
•…
• n まで全部の倍数に印をつけたとき,
印がつかないで残っている数は,
どの数の倍数でもないから素数である.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17…