|
例えば３冊のファイルが本棚にランダムに並んでいる時、
適当なファイルを左端に移動する方法を繰り返して、元の順番になるまでの 最短の手順を考える。 A,B,C :0回 A,C,B->B,A,C->A,B,C:2回 B,A,C->A,B,C:1回 B,C,A->A,B,C:1回 C,A,B->B,C,A->A,B,C:2回 C,B,A->B,C,A->A,B,C:2回 以上よりすべての順列では0+2+1+1+2+2=8回の移動が対応し 任意の配列では8/3!=4/3回の手順で元の順番に戻せることが期待できる。 では ５冊のファイルがランダムに並んでいるとした場合 上記の方法で元に順番に並ばせるための手順はいくつになるでしょうか？ また１０冊ではどうか？ 解答
123
1回...213,231...2
2回...213-132,231-321,312...3
これを基本に考えればいいはずも...よくわからず ^^;
・上記サイトのらすかる様の素敵な(実はよくわかってない ^^;)もの Orz〜
n冊のファイルの並べ方で、最終的に右端に来るべきk冊が
左→右の順（間に他のファイルが入ってよい）になっているのは n!/k!通りなので、 右端のちょうどk冊が左→右の順になっているのは n!/k!-n!/(k+1)!通り *ここが肝だと思うもよく理解できてなかと...^^;
右端のちょうどk冊が左→右の順になっているとき 最短の手順はn-k回なので、 最短の手順の合計は Σ[k=1〜n-1]{n!/k!-n!/(k+1)!}(n-k) =(n!/1!-n!/2!)(n-1) +(n!/2!-n!/3!)(n-2) +(n!/3!-n!/4!)(n-3) +… +(n!/(n-1)!-n!/n!)(n-(n-1)) =(n!/1!)(n-1)-n!/2!-n!/3!-n!/4!-…-n!/(n-1)!-(n!/n!)(n-(n-1)) =(n!)(n+1)-n!/0!-n!/1!-n!/2!-n!/3!-n!/4!-…-n!/(n-1)!-n!/n! =(n+1)!-n!Σ[k=0〜n]1/k! =(n+1)!-n!{[en!]/n!} =(n+1)!-[en!] よって回数の期待値は {(n+1)!-[en!]}/n! =n+1-[en!]/n! *熟読玩味ぃ〜^^;☆
|
- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用
コメント（0）
