事前にC言語による乱数発生の基礎を読んでおくこと。

サイコロによる乱数発生

サイコロをN 回投げたときに1が何回出たかをシミュレーションし、 平均が1/6に近くなることを確かめよ。

• N = 6000(1/10), 30000(半分), 60000(全て)として以下のように比べよ。

  (出力例)
  {1,...,6} men no saikoro
   6000 kai no Hyohon Heikin = 0.151167 (Rironchi 0.166667)
  30000 kai no Hyohon Heikin = 0.166100 (Rironchi 0.166667)
  60000 kai no Hyohon Heikin = 0.167950 (Rironchi 0.166667)
  

• サイコロが6面体だけではなく、 FACE面出るものに対応できるように一般化せよ。ただし、FACE は自然数とする。

乱数表の作成

下記のようなフォーマットで乱数表を作成せよ。 ただし、以下のとおりにすること。

• 2重ループを使用すること。
• 0から9までの1桁の乱数を生成し、2桁ずつ並べ、その後には空白を入れること。
• 縦に10桁、横に10桁書くこと。

--------------------
     乱数表
--------------------
 1 | 86 26 72 03 71 
 2 | 98 49 84 26 67 
 3 | 90 71 99 53 56 
 4 | 94 31 01 41 41 
 5 | 24 06 38 15 57 
 6 | 25 70 67 02 05 
 7 | 99 02 10 45 19 
 8 | 63 37 07 61 21 
 9 | 85 66 63 36 54 
10 | 25 42 75 32 04 
--------------------

モンテカルロ法 (面積の計算)

[0,1]x[0,1]に2次元の乱数をN点とる。 つまり、{(x_1,y_1),...,(x_N,y_N)}を考える。 N点のうち以下の割合を計算せよ。

1. (0,0)を中心とした半径1の円の第1象限の部分に入る割合。
   この割合は、1/4の円の面積と考えることができ、理論的にはπ/4である。 このことから、この割合を4倍するとπの近似となることがわかる。 Nを大きくしてπが近似されることを 例えば出力を以下のようにせよ。

   1000 Kai
   Wariai = 0.787000 (rironchi  = 0.785398
   pi no kinji = 3.148000 (pi = 3.141593)
   

   (解答)
2. y_i< x_i^k となるものの割合。ただし、k=1,2,…, 5 として与えておく。
   この割合は、は積分∫x^k dx = 1/(k+1) と等しい。 例えば、出力を以下のようにせよ。 (解答)

   1000000 Kai
   x^1 no sekbun = 0.500404,  (Sekibun no Rironchi = 0.500000)
   x^2 no sekbun = 0.333478,  (Sekibun no Rironchi = 0.333333)
   x^3 no sekbun = 0.250468,  (Sekibun no Rironchi = 0.250000)
   x^4 no sekbun = 0.200415,  (Sekibun no Rironchi = 0.200000)
   x^5 no sekbun = 0.166984,  (Sekibun no Rironchi = 0.166667)
   

1. 以下の出力のように、0〜1000の数値を乱数として選び、ユーザが当てるプログラムを作成せよ。 (解答)

   0から1000までの数値を1つ固定しました(Xとします)
   X を当ててください
   適当に0から1000までの数値を入れてください：500
   それよりも小さいです
   適当に0から1000までの数値を入れてください：250
   それよりも小さいです
   適当に0から1000までの数値を入れてください：125
   それよりも小さいです
   適当に0から1000までの数値を入れてください：63
   それよりも小さいです
   適当に0から1000までの数値を入れてください：32
   それよりも大きいです
   適当に0から1000までの数値を入れてください：45
   それよりも小さいです
   適当に0から1000までの数値を入れてください：40
   その数値(40)です。当てるのに7回かかっています
   

2. 上記のプログラムを改良して、範囲を指示してくれるプログラムを作成せよ。 (解答)

   0から1000までの数値を1つ固定しました(Xとします)
   X を当ててください
   適当に0から1000までの数値を入れてください(平均は500.0)：500
   それよりも大きいです
   適当に501から1000までの数値を入れてください(平均は750.5)：750
   それよりも小さいです
   適当に501から749までの数値を入れてください(平均は625.0)：625
   それよりも大きいです
   適当に626から749までの数値を入れてください(平均は687.5)：687
   それよりも大きいです
   適当に688から749までの数値を入れてください(平均は718.5)：718
   それよりも大きいです
   適当に719から749までの数値を入れてください(平均は734.0)：734
   その数値(734)です。当てるのに6回かかっています
   

下記のような、透明傘の上に雨を降らせるプログラムを作成せよ。

• 傘の部分は 三角形の描画問題 を使って書くこと。
• 傘の真上の雨は、傘の幅と同じ大きさの正方形の領域に関して、 以下の方法で描画する：
  • 雨がある確率を0.2、雨がない確率を0.8として 雨があれば「*」雨なければ「 」とする。

 *
          *
*  *  *
 *    *   *
      *
   * * *
**  *

  *
 *   *
   * *
     *
    * *
   *   *
  *     *
 *       *
***********
     *
     *
     *
     *
     *   *
      ***

くじ引きの公平性のチェック

自然数 n,k を n≧2, 1≦ k < n とする。 n人の中からk人を当たりとする公正な方法として以下を考える。

1. くじを引く順番を決定するためにn人がくじ {1,…,n} を非復元抽出で抽出する。
2. 上記の順番に {1,…,n+1} を非復元抽出で引いて、 残りの1枚の番号 X を決定する。
3. 当たりを {X+1,…,X+k} 番の番号を 引いた人と決定する。 ただし、当たりの番号が最後の番号 n+1 までいってしまうと 1番に返って当たりを決める。

出力例：
10人から3人を選ぶ試行を 1000000回実験
( 1)  300759回当選(割合0.300759) 理論値=0.300000
( 2)  299398回当選(割合0.299398) 理論値=0.300000
( 3)  299946回当選(割合0.299946) 理論値=0.300000
( 4)  299630回当選(割合0.299630) 理論値=0.300000
( 5)  299479回当選(割合0.299479) 理論値=0.300000
( 6)  300223回当選(割合0.300223) 理論値=0.300000
( 7)  300380回当選(割合0.300380) 理論値=0.300000
( 8)  300594回当選(割合0.300594) 理論値=0.300000
( 9)  299022回当選(割合0.299022) 理論値=0.300000
(10)  300569回当選(割合0.300569) 理論値=0.300000

硬貨投げの待ち時間(簡単)

• 硬貨を投げて表が出るまでの回数を出力するプログラムを作成せよ。 ( 解答)

• 硬貨を投げて表が出るまでの回数を1000回の試行を行って その平均を出力するプログラムを作成せよ。 ( 解答)

硬貨投げの待ち時間

硬貨を投げ続けて表か裏を記録し、 あるパターンが現れるまでの投げた回数(待ち時間と言う)を考える。 例えば、パターンが「裏裏」であり、「表表裏裏表...」と出ると 待ち時間は4と数える。待ち時間は確率的に変化するが(確率変数となる)

• 「表裏」がでるまでの待ち時間の平均と
• 「表表」がでるまでの待ち時間の平均

• 「表裏」がでるまでの待ち時間の平均=4
• 「表表」がでるまでの待ち時間の平均=6

• 「表裏」がでるまでの待ち時間の平均=1/(p*(1-p))
• 「表表」がでるまでの待ち時間の平均=(1+p)/p^2

1. 表と裏は1/2の確率で出る公平な硬貨を考える。
   1. 表が出るまでの平均待ち時間は2であることを数学的に示せ。
   2. 「表裏」と「表表」の平均待ち時間は等しいように思われるが、 そうでない理由を述べよ(分からなくとも直感的に説明することを試みよ) また、「表裏」と「表表」の平均待ち時間はそれぞれ4,6であることを示せ。 ( 解答)
2. 公平な硬貨を「表裏」と「表表」が出るまでそれぞれ 1000回繰り返して、平均をとることにより確率(相対頻度)を出力せよ。
3. 表が向く確率pを黄金数の逆数としたときにも同じ事を行え。

参考文献：ブロム他著, 確率論へようこそ, 丸善出版, 2005年, 6ページ, 第1.4節

出力例：
10000 Kai  no shiko, prob. P = 0.500000
heikin (10) = 3.953400 Rironchi (4.000000)
heikin (11) = 6.047900 Rironchi (6.000000)

10000 Kai  no shiko, prob. P = 0.618034
heikin (10) = 4.246600 Rironchi (4.236068)
heikin (11) = 4.239100 Rironchi (4.236068)

(関数を使わない解答) (関数を使った解答)

硬貨投げの度数分布

5枚の硬貨を1000回投げ、表の出た回数を記録する。 このときの度数分布を出力し、その平均と分散を求めよ。 また、平均と分散の理論値も出力してみよ。

5 Ko no Coin wo 1000 Kai  Nage mashita
0       33
1       166
2       314
3       307
4       142
5       38
Heikin 2.473000 Rironchi = 2.500000
Bunsan 1.291271, Rironchi =1.250000

前問と同様に 5個のサイコロを6*6*6*6*6回投げ、1の出た回数を記録する。 このときの度数分布を出力し、その平均と分散を求めよ。 また、平均と分散の理論値も出力してみよ。 なお、5個とも1が出る確率を考えながら サイコロを6*6*6*6*6回投げる意味を書け。

(解答)

サイコロによるポーカー

(ポーカーの問題) のと同じく以下のようにポーカーをする。ただし、5枚のカードを サイコロを5回投げて決めることにする(1,..,6の数字だけ決めてマークは考えない)

• それらの値が全て等しければ「5カードです。」
• 上記ではなく、どれか4つの値が等しければ「4カードです。」
• 上記ではなく、どれか3つの値が等しく、他の2つは別の値として等し い場合「フルハウスです。」
• 上記ではなく、どれか3つの値が等しく、他の2つは異なる値の場合 「3カードです。」
• 上記ではなく、2つの値が2組だけ等しければ「2ペアです。」
• 上記ではなく、2つの値が1組だけ等しければ「1ペアです。」
• すべて異なれば「すべて異なります。」

1. N 回繰り返して、それぞれの回数をN で割った標本平均を求めよ。 N は define 文で書き、N を100 や10000で実行してみよ。
2. それぞれの確率が 1.0/1296, 25.0/1296, 25.0/648, 25.0/162, 25.0/108, 25.0/54, 5.0/54 であることが知られている(できるならば数学的にチェックせよ)。 この確率とプログラムの出力と比較せよ。 Nの大きさと精度に関して述べよ。

出力例：
(0) ハイカード(すべてばらばら)
(1) 1ペア
(2) 2ペア
(3) 3カード
(4) フルハウス
(5) 4カード
(6) 5カード

サイコロ投げでのポーカー(10000回)
(0)  922         0.092200 prob(0.092593)
(1) 4609         0.460900 prob(0.462963)
(2) 2353         0.235300 prob(0.231481)
(3) 1498         0.149800 prob(0.154321)
(4)  381         0.038100 prob(0.038580)
(5)  230         0.023000 prob(0.019290)
(6)    7         0.000700 prob(0.000772)

サイコロの目が全て出るまでの回数

サイコロを投げ続けて、1から6が全て出るまでの回数を出力するプログラム を作成せよ。 ただし、以下のように1から6まで、出た目を配列で表現すること。

• サイコロの目が出ていない→0
• サイコロの目が出た→1

出力例：
0 0 1 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0
0 1 1 0 1 0
0 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 1
10回かかりました

旅人の問題

ある旅人が4つの都市A,B,C,Dを訪れたいと思った。 まずどれかでたらめに選んで訪れる。例えば最初にAを選んだなら、次に B,C,Dを同じ確率で選ぶ。次にBを選んだなら、今度はA,C,Dのなかから選ぶ。 (彼は忘れっぽいので、そのときにはもうAに言ってしまったことを憶えていない。) 次に3つのなかから選んで、と続ける。旅人が4つの都市を全て訪れるのに必要な数 Nの平均を求めよ。
参考文献：ブロム他著, 確率論へようこそ, 丸善出版, 2005年, 3ページ, 第1.2節

1. 上記の問題の設定のまま、何回かかったかをシミュレーションせよ。

   出力例：
   8回かかりました
   

   ( 解答)
2. 回数の情報と何回かかったかを以下のように表示するプログラムを作成せよ。 なお、4桁の0,1の数字は都市 A,B,C,D に関して0は未訪問、1は訪問を表現しており、左の括弧に囲まれている数字はステップ数とする。 ( 解答)

   出力例：
   (1) 0 1 0 0
   (2) 0 1 1 0
   (3) 0 1 1 1
   (4) 0 1 1 1
   (5) 0 1 1 1
   (6) 1 1 1 1
   6回かかりました
   

3. 未訪問の都市訪れることを成功(S)、そうでないことを失敗(F)とする。 今の位置と成功、失敗がが分かるように追加せよ。 ( 解答)

   出力例：
   (1) 0 1 0 0    2 S
   (2) 0 1 0 1    4 S
   (3) 0 1 1 1    3 S
   (4) 0 1 1 1    4 F
   (5) 0 1 1 1    2 F
   (6) 0 1 1 1    4 F
   (7) 1 1 1 1    1 S
   7回かかりました
   

4. 以下の関数を作成して上記のプログラムを書き変えよ。 ( 解答)
   • 次の都市を現在の都市以外からランダムに選ぶ関数 int next_choose(int current_city)
   • 現在の回数 itmes、訪問リスト visited[]、都市 chk_city 今の訪問状態((3) 0 1 0 1 のようなもの)を表示する関数 void print_status(int itimes, int visited[], int chk_city)
   • 現在のところどれだけの都市を訪問したかの数を返す関数 int sum_visited(int visited[])

5. 全ての都市を訪れる試行をMAX_TRIAL回行いたい。

   #define MAX_TRIAL 5 // 実験の回数
   

   として、旅人が4つの都市を全て訪れるのに必要な数Nについて MAX_TRIAL回繰り返すプログラムを作成せよ。 ただし、1回の試行において何回かかったかを試行毎に出力するようにせよ。 ( 解答)

   (1)  9回かかりました
   (2)  7回かかりました
   (3)  5回かかりました
   (4)  6回かかりました
   

6. 前の問題に関して、MAX_TRIAL を増やしてデータをとり、 標本平均と分散を表示するプログラムを作成せよ。 ( 解答)

   Toshi no kazu = 4, Kaisu = 10000
   Heikin = 6.526300 (Rironchi =6.500000)
   Bunsan = 6.985908 (Rironchi =6.750000)
   

   なお、上記の「Rironchi」はNに関して期待値 E(N)と分散 V(N) を それぞれ計算したものであるが、都市の数を CITY とすると 一般的には以下が知られており、ここではそれを用いた。

     E(N) = (CITY -1)*(1+1/2+…+1/(CITY-1)) + 1
     V(N) = (CITY -1)*Σ_{2≦i≦CITY-1} (i-1)/(CITY -i)^2
   

   ただし、上記の事柄を数学的に考察する必要はない。
7. 前の問題に関して、最小値、最大値を調べ、 その範囲で何回実行されたかヒストグラムを求めよ。 ( 解答)

   Toshi no kazu = 4, Kaisu = 1000
   Heikin = 6.557000 (Rironchi =6.500000)
   Bunsan = 6.648751 (Rironchi =6.750000)
   min = 4 max = 20
   4:       212
   5:       218
   6:       179
   7:       124
   8:       76
   9:       69
   10:      46
   11:      28
   12:      13
   13:      8
   14:      9
   15:      8
   16:      5
   17:      0
   18:      3
   19:      0
   20:      2