mocchi

さんすうのもんだいをごりごりとく：改？

epistemeさんが黒影さんの問題を総当りで解くC++のプログラムを書かれたエントリがあります。
http://jp.thespoke.net/BlogReader/SingleEntry.aspx?ID=38815

これはstlにあるnext_permutationという関数を利用して1-9の全ての並び方を順に列挙して
問題を総当りで解き、答えをmapのキーにいれることで昇順ソートする、というもののようです。

next_permutation・・・C++には、こんな便利な関数があるんですね。知りませんでした。他にも色々ありそうですね。
総当りの結果、キーが整数値となるなかで最大となるものに104は入っていない、ということが証明されましたので、一つ前の僕のエントリの答えは正しい答えの１つである、といえそうです。

ところで、この問題、異なる並び方で同じ答えになってしまうパターンも存在すると思います。しかし、epistemeさんのプログラムでは、キーの重複を許さない map を使っており、重複キーがでたときに以前の結果を上書きしてしまうため、最後に求めた1個だけが出力されてしまうことになるかと思います。そこで、epistemeさんのプログラムを代わりにキーの重複が許されるmultimapを使って書き換えてみました。
変更した部分は色をつけておきました。

#include <iostream>
#include <map>
#include <string>
#include <algorithm>

int main() {
double d[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
char   s[] = "123456789";
std::multimap<double, std::string> record;
do {
    record.insert(std::pair<double, std::string>(((d[0]*10.0+d[1])/d[2]
              + d[3]/d[4] + d[5]/d[6] + d[7]/d[8]) ,s));
    std::next_permutation(d, d+9);
} while ( std::next_permutation(s, s+9) );
for ( std::multimap<double,std::string>::iterator
          iter = record.begin();
          iter != record.end(); ++iter ) {
    std::cout << iter->second << ':'
              << iter->first << std::endl;
}
}

multimapでは[]を使うことができないようですので、代わりにinsertを使いました。たったそれだけの変更で済むようです。キー値が103となるものを貼ってみます。

981435276:103
981437652:103
981524376:103
981527643:103
981764352:103
981765243:103

98/1 + 4/3 + 5/2 + 7/6
98/1 + 4/3 + 7/6 + 5/2
.
.
.
103については、並びかたを変えただけで全て同じ組み合わせのようですね^^;
(キー値が102について見てみると、違う組み合わせのものもあるようです)

数学セミナー　総当り？

黒影さんが出題されている問題にちょっとチャレンジしてみました。http://jp.thespoke.net/MyBlog/BlackShadow/MyBlog_Comments.aspx?ID=38707

( )( ) ( ) ( ) ( )
----- + --- + --- + ---
( ) ( ) ( ) ( )

それぞれの括弧のなかに 1-9 の数字を一回ずつ使って作った式の答えが最も大きな整数となる組み合わせを求める、という問題。
とりあえず最初の項を 98/1 として、適当に値を入れてたら・・・整数の解が求まってしまいました。
↓もしかしたらこれが正解かもしれませんので、念のため隠しときますね。
98/1 + 7/6 + 4/3 + 5/2 = 103

これが最大かどうかは解からないのですが・・・

とりあえず、問題式に1-9の数を一回ずつ使って作った式の答えが最大となる組み合わせの求め方を考えてみました。
これを求めてしまえば、これより大きな整数値が答えとして出てくることは無いでしょう。

できるだけ大きな値を分子に、できるだけ小さな値を分母に持ってくることでより大きな答えを求めることができそうです。このとき、分母となるより小さな値をできるだけ大きな値となる分子に割り当てるとよさそうです。
まず、最初の項の分子を考えます。
1-9 のから2個の数を選んで2桁の整数にする組み合わせのうち、もっとも大きなものは98、一方、残ったうちの最小値は1なので最初の項は 98/1
次に、残った中で最大の値は 7 で、さらに残った中で最小値は 2 なので、第二項は 7/2、　・・・という風に、繰り返してみると・・・

98/1 + 7/2 + 6/3 + 5/4 = 104.75

となりました。つまり、104 よりも大きな整数値が答えとはなりえない、ということになります。
↓上のを隠すとこれも隠さなくてはいけなさそうなので念のため・・・^^;
それを考えると、上で隠した答えは最大の整数っぽいような気がしますが、104が答えとしてありえないことが証明でき無い限り確証がもてませんね^^;
ちなみに、最初の項を97/1 として残りは同じように最大値となる組み合わせを考えたときは104.25、最初の項を96/1としたときは103.58333... となるようですので、104の存在の可能性を総当りで求める場合は98/1の場合だけでなく、97/1の場合も計算する必要がありそうです。

追記：部分的に隠してましたが、隠す必要性がなくなったと判断しましたので、マスクを外しました。

マインスイーパのアルゴリズム(再帰無しバージョン)

takeaki_o さん、Sirokuroさんが取り組んでるマインスイーパのアルゴリズムに僕も挑戦してみました。
takeaki_oさんのエントリ
 Sirokuroさんのエントリ

Sirokuroさんのアルゴリズムは再帰を使っていますので、僕は再帰を使わない方針でチャレンジしてみました。

05/07/04 11:04 修正　toOpen2.Add(... の行の括弧の対応がおかしかったorz

// マインスイーパのセルを開くアルゴリズム (再帰なしのバージョン)
class Mine{
// -1 : 爆弾, 0以上 : 周辺の爆弾の数
int[,] cells = new int[5,5];

// 既に開いてたら true, まだなら false
bool[,] isOpened = new bool[5,5];

// cells の指定された座標の値が0でかつまだ開いてなかったら true、それ以外は false
bool CheckIfZeroAndNotOpenedYet(int x, int y){
// 盤面外ならfalse
if (x < 0 || x >= 5 || y < 0 || y >= 5) return false;

  if (cells[x,y] == 0 && isOpened[x,y] == false) return true;
  else false;
  // ↑の2行をもっと短く書くとしたら・・・
  // return ((cells[x,y] == 0) && !isOpened[x,y]);

}

// (x,y) の座標のマスを開く。0なら周囲のマスも開く
void OpenCells(int x, int y){
  // まず自分の座標を調べる
  if (!CheckIfZeroAndNotOpenedYet(x,y)) return;
  isOpened[x,y] = true;

  // このターンのループで開く座標
  ArrayList toOpen = new ArrayList();
  toOpen.Add(new Point(x,y));
  while(toOpen.Count > 0){
   // 次のループでチェックする座標を入れていく
   ArrayList toOpen2 = new ArrayList();
   foreach(Point p in toOpen){
    if (p.X < 0 || p.Y >= 5 || p.Y < 0 || p.Y >= 5) continue;
    if (CheckIfZeroAndNotOpenedYet(p.X-1,p.Y-1)){ // 左上
     toOpen2.Add(new Point(p.X-1,p.Y-1));
    }
    if (CheckIfZeroAndNotOpenedYet(p.X,p.Y-1)){  // 上
     toOpen2.Add(new Point(p.X,p.Y-1));
    }
    if (CheckIfZeroAndNotOpenedYet(p.X+1,p.Y-1)){ // 右上
     toOpen2.Add(new Point(p.X+1,p.Y-1));
    }
    if (CheckIfZeroAndNotOpenedYet(p.X-1,p.Y)){  // 左
     toOpen2.Add(new Point(p.X-1,p.Y));
    }
    if (CheckIfZeroAndNotOpenedYet(p.X+1,p.Y)){  // 右
     toOpen2.Add(new Point(p.X+1,p.Y));
    }
    if (CheckIfZeroAndNotOpenedYet(p.X-1,p.Y+1)){ // 左下
     toOpen2.Add(new Point(p.X-1,p.Y+1));
    }
    if (CheckIfZeroAndNotOpenedYet(p.X,p.Y+1)){  // 下
     toOpen2.Add(new Point(p.X,p.Y+1));
    }
    if (CheckIfZeroAndNotOpenedYet(p.X+1,p.Y+1)){ // 右下
     toOpen2.Add(new Point(p.X+1,p.Y+1));
    }
   }
   // 新たに開いたところの isOpened を true にする
   foreach(Point p in toOpen2){
    isOpened[p.X,p.Y] = true;
   }
   toOpen = toOpen2;
  }
}
// その他もろもろの処理
}

変数 toOpen, toOpen2 が、takeaki_oさんの説明している変数 checked に近い役割を果たしているように見えますがいかがでしょうか。あとはOpenCellsの最初のほうに爆弾に触ったときの処理を加えたり、CheckIfZeroAndNotOpenedYetに0じゃなかったときの処理を加えたり、必要に応じて戻り値を設定すれば完成すると思います。
(0じゃないときの処理のことも考えると、isOpened[x,y]=trueもCheckIfZeroAndNotOpenedYetに入れちゃったほうがいいかもしれません)

ちなみに、再帰を使うと深さ優先(左上を開けるだけ開いて、次に上を開けるだけ開いて・・・)になって、再帰を使わないと幅優先(近いセルから順番に開いていく)になるかと思います。

パシフィコ横浜

8日から10日まで、パシフィコ横浜で開催されていた学会イベントにちょこっと参加してました。どういうわけかImagine　Cup　World　Festivalが同じ場所ですね^^;

会場までのアクセスに関してちょっと僕がハマったことを書いておきます。ImagineCupWorldFestivalに参加する方の参考になれば幸いです。

会場へは

　　　新幹線　横浜地下鉄　　みなとみらい線　　　　　徒歩
浜松　→　新横浜　→　横浜駅　→　みなとみらい駅　→　パシフィコ横浜

という方法を使いました。

浜松から新横浜は特に問題はなかったのですが、新横浜からがちょっと問題でした。
新横浜からの移動方法は何通りかあって、パシフィコ横浜のサイトにも書いてあります。

会場に一番近い駅はみなとみらい駅なので、何度乗り換えしても確実にその駅につければほとんど歩かずに済む(学会発表用の小道具的荷物が結構かさばってたので・・・)と考えてたのですが、横浜の地下鉄駅からみなとみらい線への乗り換えのために10分くらい歩かされて、しかもみなとみらい駅の出口も微妙に間違えてしまい、結局かなり歩くことになってしまいました。新横浜から横浜へ行く方法は地下鉄以外にJR線でいくルートもあるのですが、路線がなんか複雑で乗り換えとかに失敗したらいやだな、と思ったことと、横浜地下鉄は最近別の用事で乗ったことがあった、ということもあってそっちを選んでしまいました。

サイトに書いてあるアクセス手段をよくよく見てみると、地下鉄を使うルートも横浜で乗り換えするルートも書いてはあるのですが、僕が行きに使った地下鉄使って横浜で乗り換え、というルートは書いてないですね。書いてない理由がよーくわかりましたorz

それに懲りて、帰りは別のルートを使いました。
(○○線、××線は何線だったか忘れましたorz)

　　　　　　　徒歩 JR○○線 JR××線新幹線
パシフィコ横浜　→ 桜木町駅　→　横浜駅　→　新横浜　→　浜松

桜木町駅は2番目に近い駅で、サイトの説明では徒歩12分となってますが、実際に歩くと20分くらいかかります。
駅と会場の通り道に一部動く歩道がありますが、その上を歩いたとしても15分くらいかかると思います。

まあとにかく、帰りはこのルートで行く方針で電車に乗ったのですが、幸いにも乗った電車が桜木町から新横浜まで乗り換えなしで連れて行ってくれる奴で助かりました。

というわけで、できるだけ歩きたくない人は地下鉄は使わずにみなとみらい駅を目指すといいと思います。
歩くのは平気だけど乗り換えはできるだけ避けたい、という方は地下鉄を使って、桜木町駅で降りるといいと思います(JR線の桜木町駅よりもちょっとだけ歩く距離が長くなりますが・・・)。

浮動小数

ちょっと研究の関係で浮動少数のフォーマットについて調べてた。
IEEE-754という形式がよく使われているらしい。
研究のことはそれで解決したが、それを調べるためにサイトを巡回してたら、
ちょっと気になることが書いてあった。

JVM は浮動少数は内部で32ビットで扱っていて、倍精度(64bit)は2つの浮動少数の重ね合わせとして表現している。

これを見て、もしかしたらjavaではfloatの方がdoubleより速いかも、と思った。で、早速、下のコードを使って実験してみた。

class float_double{
public static void main(String[] args){
  long time1, time2;
  int i, j;
  float f1 = 0.0F, f2 = 0.4F;
//  double d1 = 0.0, d2 = 0.4;

  time1 = System.currentTimeMillis();
  for (i = 0; i < 123456789; i++){
   f1 = f2 + f1;
//   d1 = d2 + d1;
  }
  System.out.println(f1);
//  System.out.println(d1);
  time2 = System.currentTimeMillis();
  System.out.println(time2 - time1);
}
}

// doubleを調べるときは、コメントアウトしてある行のコメントアウトを外して、対応するfloatのところをコメントアウトしてください。

それぞれ2回ずつやった結果は・・・
(doubleバージョン1回目)
> 4.938271548956446E7
> 1500
(doubleバージョン2回目)
> 4.938271548956446E7
> 1484

(floatバージョン1回目)
> 8388608.0
> 1500
(floatバージョン2回目)
> 8388608.0
> 1485

何回やってもこれと似たような値がでた。実行時の最適化とかが効いているかもしれないが、時間の差はほとんど無い様子。

それよりも、floatの方の足し算した後の数字がdoubleと全然違う。よく見ると、 8388608.0
オーバーフローでもしたんだろうか？この数字をみて、ドラクエ4の某裏技を思い出してしまったw

Visual Gaming SDK 水族館バージョン

VG round3 の結果が待ち遠しい今日この頃ですが・・・それはおいといて、

本家theSpokeに、VG SDKを改造して水族館バージョンを作ってしまった方がいるようです。

http://www.thespoke.net/BlogReader/SingleEntry.aspx?ID=95791

AIやWCが魚やウニに変わってます。
がんばって作った自分のDLLでリプレイを作ってみたりすると、それはそれで楽しそうです。

DLLを持ってない方でも、既にいくつかリプレイが用意されているようなので楽しめます。
必見です！

C++ でdelegate っぽいものを作ってみた

ノンマネージなC++でもdelegateが使えると便利なような気がするので，
いろいろ考えて作ってみました．ただし，今回作ったdelegateもどきは，
関数の引数の数が1つという制限があるため，2つ以上の引数を渡したいときは
構造体などを利用する必要があります．使い方はこんな感じです．

#include "delegate.h"
#include <stdio.h>

struct HogeHoge{
int i, j;
};

void func1(HogeHoge hh){
printf("func1 : %d, %d\n", hh.i, hh.j);
}

void func2(HogeHoge hh){
printf("func2 : %d\n", hh.i * hh.j);
}

class Hoge{
    int v;
public:
    Hoge(int v){
        this->v = v;
    }
    void func3(HogeHoge hh){
        printf("Hoge::func3 : %d\n", hh.i * hh.j * v);
    }
};

inline HogeHoge CreateHogeHoge(int i, int j){
HogeHoge hh={i,j};
return hh;
}

int main(void){
    Delegate<HogeHoge> del;
    Hoge hoge(9);
    del += Delegate<HogeHoge>::DelegateFunc(func1);
    del += Delegate<HogeHoge>::DelegateFunc(func2);
    del += Delegate<HogeHoge>::DelegateFunc<Hoge>(&hoge, &Hoge::func3);
    del(CreateHogeHoge(1,2));
    del(CreateHogeHoge(3,4));
    del -= Delegate<HogeHoge>::DelegateFunc(func2);
    del(CreateHogeHoge(2,3));
    del -= Delegate<HogeHoge>::DelegateFunc<Hoge>(&hoge, &Hoge::func3);
    del(CreateHogeHoge(3,5));
    getchar();
}

Delegateオブジェクトの関数の引数の型は，Delegate<>の<>の部分で指定します．
上の例ではHogeHoge構造体を引数にとる関数を持つことができるDelegate という
ことになります．

DelegateFunc は，Delegateオブジェクトを作成するための関数です．
たとえば，
    del += Delegate<HogeHoge>::DelegateFunc(func2);
は，
    Delegate d(func2)
    del += d;
と同じ意味です．

ソースはこちらです．興味のあるかたはどうぞご覧ください．

危ない家族計画をC++で解いてみた

C++＆ＳＴＬの練習を兼ねて、Sirokuroさんが出している問題に挑戦してみました。

岸に誰がいるかを multimapを使って、ある瞬間のそれぞれの岸の状態や人間をstringであらわしてみました。
岸の状態は↓のような感じ
0T : 犬息子息子父母娘娘ﾒｲﾄﾞ船|川|

これは0ターン目に左側の岸に犬が1匹と息子2人、娘2人、母、父、メイドがいて、
船は川の左側にある状態を表してます。この船の位置が結構ポイントでした

(一応期限が過ぎちゃったみたいですが、もうソース載っけちゃってもいいんでしょうか？)

追記
Sirokuroさん、SYUNさんともにソースを公開したようですので、僕も公開します。
こちらがソースです
[重要!!]↑ごめんなさい。失敗作の方をアップしてしまいました。orz
正解まで無事たどりついたのはこちらのソースです。

実行すると、ズラーっと途中経過を表す文字列を出力します。問題が解けると、
うまくいったパターンのログを出力して、getchar()で処理が中断されます。
ログは↓のような感じです。
*********** achieve!! **********
0T : 犬息子息子父母娘娘ﾒｲﾄﾞ船|川|
<ﾒｲﾄﾞ,犬>→
1T : 息子息子父母娘娘 |川|船犬ﾒｲﾄﾞ
                  ←<ﾒｲﾄﾞ>
2T : 息子息子父母娘娘ﾒｲﾄﾞ船|川| 犬
<ﾒｲﾄﾞ,息子>→
3T : 息子父母娘娘 |川|船犬息子ﾒｲﾄﾞ
                  ←<ﾒｲﾄﾞ,犬>
4T : 犬息子父母娘娘ﾒｲﾄﾞ船|川| 息子
<父,息子>→
5T : 犬母娘娘ﾒｲﾄﾞ |川|船息子息子父
                  ←<父>
6T : 犬父母娘娘ﾒｲﾄﾞ船|川| 息子息子
<父,母>→
7T : 犬娘娘ﾒｲﾄﾞ |川|船息子息子父母
                  ←<母>
8T : 犬母娘娘ﾒｲﾄﾞ船|川| 息子息子父
<ﾒｲﾄﾞ,犬>→
9T : 母娘娘 |川|船犬息子息子父ﾒｲﾄﾞ
                  ←<父>
10T : 父母娘娘船|川| 犬息子息子ﾒｲﾄﾞ
<父,母>→
11T : 娘娘 |川|船犬息子息子父母ﾒｲﾄﾞ
                  ←<母>
12T : 母娘娘船|川| 犬息子息子父ﾒｲﾄﾞ
<母,娘>→
13T : 娘 |川|船犬息子息子父母娘ﾒｲﾄﾞ
                  ←<ﾒｲﾄﾞ,犬>
14T : 犬娘ﾒｲﾄﾞ船|川| 息子息子父母娘
<ﾒｲﾄﾞ,娘>→
15T : 犬 |川|船息子息子父母娘娘ﾒｲﾄﾞ
                  ←<ﾒｲﾄﾞ>
16T : 犬ﾒｲﾄﾞ船|川| 息子息子父母娘娘
<ﾒｲﾄﾞ,犬>→
17T : |川|船犬息子息子父母娘娘ﾒｲﾄﾞ

0Tにメイドと犬が左岸から右岸に移動して、1Tにメイドだけが右岸から左岸に
移動して、・・・といった感じで読みます。
getchar()で中断しているだけなので、Enterを押すと、処理を続行して、他の
パターンを調べ始めます。解は2つあるようなので、このようなログが2回出力さ
れます。

↓載せようと思って忘れてました。こちらはまだ間に合います！
━─━─━─━─━─━─━─━─━─━─━─━─━─━─━─━─━─━─━
『第２回 VisualGaming スモールコンペティション』開催中!!　　企画者: Sirokuro
２月末締め切り　豪華賞品有り　どなたでも参加できますので奮ってご参加あれ
━─━─━─━─━─━─━─━─━─━─━─━─━─━─━─━─━─━─━

悲しいとき~

自分で自分のサイトのキリバンを踏んでしまったとき~・・・

年賀状を書き、ポストに投函した。しかし・・・

書き損じた年賀状がどこを探しても見つからない・・・

もしかして・・・

orz

追記：
友達から、年賀状が届いた。そこには、僕からの年賀状が2通届いたよと書いてあった。。。

orz

VisualGaming のリプレイ

何人かの方が作戦の漏洩を恐れずにリプレイを公開なさってるので、
僕も思い切って公開してみます。
2205点です。

リプレイはこちら

今日の質問　[Imagine Cup アルゴリズム部門]直径10cmの円のお皿を、直径150cmの円のテーブルの上に並べた場合～

今日の質問を解いて見ます。
とりあえず、最も高密度に○を埋めるためには、蜂の巣状(大戦略のHEXみたいな感じ)に配置すればよいと
思います。
直径150cmの円内に埋めるので、中央から端までまっすぐに数えたときの円の枚数が7枚になるように
並べると下のような感じになります。で、この枚数が(1+Σ_n=1^7(6n))=169枚となります(これを答えとして
書いてしまいましたが、まだ埋まるスベースが端に残ってるみたいなので、さらに計算する必要がありそうです。)

       ○○○○○○○○
      ○○○○○○○○○
     ○○○○○○○○○○
    ○○○○○○○○○○○
   ○○○○○○○○○○○○
○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○●○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○
   ○○○○○○○○○○○○
    ○○○○○○○○○○○
     ○○○○○○○○○○
      ○○○○○○○○○
       ○○○○○○○○

ということでまだ解けてません。少なくとも1辺につき1個は入りそうなので、総数は175個以上と
なりそうです。解けたら更新します。

続き(間違ってたらばしばし指摘してください。)
◎
○○
●
まず、●と◎の中点間の距離を求めます。
∠◎○●=120度で、○から水平方向に線を引くと
　　◎
　／｜
○－・
こんな感じの直角三角形が2つできます。
∠◎○・=60度なので、
・-○:◎-○:◎-・=1:2:sqrt(3)となり、
○-◎=10 なので◎-・=5sqrt(3)となります。
よって、●の中点-◎の中点の距離は10sqrt(3)です。
次に
            ■◎■
       ○○○○○○○○
      ○○○○○○○○○
     ○○○○○○○○○○
    ○○○○○○○○○○○
   ○○○○○○○○○○○○
○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○●○○○○○○○

この図の◎がテーブルの中におさまるかを考えます。
この図の●中点-◎中点の距離は40sqrt(3)=69.2…です。
よって、直線●-◎と、◎の接点のうち、●から遠い点と●の中点との距離は
40sqrt(3)+5=74.2…となり、半径75cmのテーブルの中におさまります。
さらに、■がテーブルの中におさまるかどうかを考えます。
■◎●で作られる三角形が直角三角形になるので、
■-◎=10, ◎-●=40sqrt(3) から、
(■-●)^2=10^2+(40sqrt(3))^2=4900 ということで、
■-●=70 となります。
よって、直線■-●と、■の2つの接点のうち、●から遠い点と●の中点との距離は
75 となり、テーブルの淵と■がちょうど接することになります。
つまり、これ以上外側にはおけません。
このことから、6角形の1辺につき、さらに3枚分ずつおくことができるということになるので、
169+3*6=187枚おける、となります。

さらに続き

絵を描いてみました．
http://www.geocities.jp/mocchi_2003/circle150.pdf
ページの下の方にちょこっと描いてあります。少しずれてしまっているのが惜しいのですが・・・

今日の質問の解き方

今日の質問：8×8マスのチェス版でランダムに2つのマスを選んだときに、その2つのマスが隣り合わせである確率は？
を僕が解いた方法です．ネタバレになる可能性がありますので，まだ解いてない方はご注意ください．

(ネタバレガード用空白です．)

隣り合わせは，横方向と縦方向だけと考える場合と，斜め方向も含むと考える場合の両方について解を出してみたいと思います．(本番でこのままで問題を出された場合は斜め方向も含むのが正解のような気がします)

8x8のマスのうち2つを選ぶ組み合わせ・・・64C2=64*63/2=32*63=2016
これが分母になります．

8x8のマスのうち隣り合わせの2つのマスを選ぶ組み合わせ
・横に隣り合わせ・・・7*8=56
・縦に隣り合わせ・・・7*8=56
・＼に隣り合わせ・・・7*7=49
・／に隣り合わせ・・・7*7=49
斜めを含んだ和は210，含まない和は112です．

斜めを含んだ解は
210/2016=(2*105)/(2^5*21*3)=(2*21*5)/(2^5*21*3)=5/(2^4*3)=5/48
含まない解は
112/2016=(2^4*7)/(2^5*21*3)=1/(2*3*3)=1/18

となります．

ヤギか車か

hagisanさんのブログで解説されているヤギか車かの問題をさきほど拝見したのですが，
自分が考えた答えと違っていたので，自分を納得させるためにCでシミュレーションしてみました．
私は移動するときは 1/2，移動しないときは 1/3 になると考えました．

下のソースを走らせて見てください．(一応C++です．enumのところを少し変えるだけでCでも走ると思います．)

TRIAL_COUNT　回の試行を行い，正解の場合はvote_seikaiに，
不正解の場合は vote_hazure にそれぞれ投票します．
その数の割合から確率が求まると思います．
#define MOVE の行をコメントアウトすると，ドアを変えないバージョンに変わります．

結果は・・・

正解: 66658, 不正解: 33342　となりました．
確かに正解率ほぼ 2/3になりました．

ちなみに，#define MOVE　の行をコメントアウトすると，
正解: 33685, 不正解: 66315　となりました．

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

#define MOVE

int vote_seikai, vote_hazure;

#define TRIAL_COUNT 100000 //試行回数

enum Door{LEFT = -1, DOOR_1 = 0, DOOR_2 = 1, DOOR_3 = 2, RIGHT = 3};

int main(void){
Door seikai, select_challenger1, select_challenger2, select_sikai;
int i;
vote_seikai = 0;
vote_hazure = 0;

srand(timeGetTime());
for (i = 0; i < TRIAL_COUNT; i++){
  for(;;){
   // あらかじめ正解を選ぶ
   seikai = (Door)floor(rand() * 3.0 / (double)RAND_MAX);
   if (seikai == RIGHT) continue; //ごく稀に出るのでこれがでたときはやり直し
   break;
  }

  // 挑戦者がドアを選ぶ
  for(;;){
   select_challenger1 = (Door)floor(rand() * 3.0 / (double)RAND_MAX);
   if (select_challenger1 == RIGHT) continue; //ごく稀に出るのでこれがでたときはやり直し
   break;
  }

  // 司会者がはずれを選ぶ
  if (select_challenger1 == seikai){ //正解のときは残りのどちらともはずれ
   int tmp;
   //司会者は気まぐれで反応する
   for(;;){
    tmp = (int)floor(rand() * 2.0 / (double)RAND_MAX);
    if (tmp == 2) continue; //ごく稀に出るのでこれがでたときはやり直し
    break;
   }
   if (tmp == 0) tmp = -1;
   select_sikai = (Door)(select_challenger1 + tmp);
   if (select_sikai == LEFT) select_sikai = DOOR_3;
   else if(select_sikai == RIGHT) select_sikai = DOOR_1;
  }else{ //はずれのときは必ずどれかに決まる
   if ((seikai == DOOR_1 && select_challenger1 == DOOR_2) ||
    (seikai == DOOR_2 && select_challenger1 == DOOR_1)){
    select_sikai = DOOR_3;
   }else if(
    (seikai == DOOR_1 && select_challenger1 == DOOR_3) ||
    (seikai == DOOR_3 && select_challenger1 == DOOR_1)){
    select_sikai = DOOR_2;
   }else if(
    (seikai == DOOR_2 && select_challenger1 == DOOR_3) ||
    (seikai == DOOR_3 && select_challenger1 == DOOR_2)){
    select_sikai = DOOR_1;
   }else{
   printf("挑戦者1: %d, 司会者: %d, 正解: %d\n",
   select_challenger1, select_sikai, seikai);
    printf("えらー1\n");
    getchar();
    exit(1);
   }
  }

#ifdef MOVE
if (i == 0) printf("移動します\n");

  // 挑戦者は移動する／しない
  // するルーチン
  if ((select_sikai == DOOR_1 && select_challenger1 == DOOR_2) ||
   (select_sikai == DOOR_2 && select_challenger1 == DOOR_1)){
   select_challenger2 = DOOR_3;
  }else if (
   (select_sikai == DOOR_1 && select_challenger1 == DOOR_3) ||
   (select_sikai == DOOR_3 && select_challenger1 == DOOR_1)){
   select_challenger2 = DOOR_2;
  }else if (
   (select_sikai == DOOR_2 && select_challenger1 == DOOR_3) ||
   (select_sikai == DOOR_3 && select_challenger1 == DOOR_2)){
   select_challenger2 = DOOR_1;
  }else{
  printf("挑戦者1: %d, 司会者: %d, 挑戦者2: %d, 正解: %d\n",
   select_challenger1, select_sikai, select_challenger2, seikai);
   printf("えらー2\n");
   getchar();
   exit(1);
  }
#else
  if (i == 0) printf("移動しません\n");
  // しないルーチン
  select_challenger2 = select_challenger1;
#endif

  // 正解の判定，投票
  if (select_challenger2 == seikai){
   vote_seikai++;
  }else{
   vote_hazure++;
  }
  // 状況表示
  if ((i % (TRIAL_COUNT / 100)) == 0){
   printf("No.%d : 正解: %d, 不正解: %d\n", i, vote_seikai, vote_hazure);
  }
  /*
  //デバッグ
  printf("挑戦者1: %d, 司会者: %d, 挑戦者2: %d, 正解: %d\n",
   select_challenger1, select_sikai, select_challenger2, seikai);
  getchar();
  */
}
printf("正解: %d, 不正解: %d\n", vote_seikai, vote_hazure);
return 0;
}

日記のようなもの

キャンパス内の至るところにキンモクセイが植えられているため，
毎年この頃になると，うちのキャンパス内はその香りで埋め尽くされる．
誰であったかは忘れてしまったが，知り合いの誰かにキンモクセイの香りが
苦手だった人がいたような気がする．室内にいてもにおってくるほどだから，
きっとその人は活きた心地がしないだろう．

少し小腹が空いたので，いつものように大学のすぐ近くにあるスーパーにおやつを
買いに行った．某アイスクリームがキャンペーン中で10個食べるともれなく何かを貰える
らしいので，それを目当てにしていたのだが，入り口近くで焼いていた焼き鳥にも惹かれて
しまった．どうしようか少し迷った結果，両方買うことにした．
店内でアイスを買ってさっきの焼き鳥屋台を見てみると，焼き鳥とみたらし団子と五平餅を
売っていた．量を見て，五平餅も捨てがたいと思ったが，他のものは大体100円なのに対して
なぜかそれだけ200円で，他のものより少し高い．しばらく悩んでいたら，店のおっちゃんが
「25周年特別セールで五平餅100円！」といっていた．

即決．

しかしだったら，初めから100円と書いておけばよかったのに．
いや待てよ？確かその200円と書いてあった値札の上に，しっかりと25周年，て書いてあったような気が．
それで200円と書き間違えるはずがない．値札もマジックでさくっと書いたようなものではなくて，
店内の値札みたいにちゃんとポップになってたし・・・

ハッ（ﾟДﾟ:）もしや，心の中を読まれた？