ここから本文です

1からnの文字がランダムに並んでおります。 これをもっとも手数のかからな...

1からnの文字がランダムに並んでおります。


これをもっとも手数のかからない順番で

昇順に並べ替えるとき。
手数の期待値はいくらでありましょうか。

※手数※
ある1つの数をその位置から別の位置に挿入を1手とする。
(交換は2手とする)



例・・・・・・
n=3

132
この場合2を真ん中へ入れると123となるから最小は1手

123・・・・0手
132・・・・1手
213・・・・1手
231・・・・1手
312・・・・1手
321・・・・2手

期待値は6/6=1手

補足バブルソートのようなものでありましょうか。
そうするとn(n-1)/2通り必要であられますから期待値はn(n-1)/4ということで在りましょうか。しかしn=3に該当しません様な。。。

興味深い数列
http://oeis.org/A126065

エクセルによりますと期待値は
n=1から順序で。
0 0.5 1 1.58333 2.20833 2.85972 3.53472 4.22966 4.94065
0.5ずつの差からちょうっとずつ勢いが強くなる。
どんな関数への漸近が可能でありましょう。。。

閲覧数:
207
回答数:
1

違反報告

ベストアンサーに選ばれた回答

edu********さん

2014/1/106:10:48

勝手に並べろよ。年末から新年の多忙な時期にくだらねぇ質問するなよ。

質問した人からのコメント

2014/1/3 21:07:12

降参 日々の生活ではストレスの発散の場が見当たらず、education_knowingさんのようにあらゆる質問に不毛な難癖をつけて回ります様な「無差別暴言癖」を患っておられます方は、知恵袋にも一定数の方がおられます。

せっせと頑張ってストレス発散に励んでおられる辺り、回答内容の割にはお暇だということがバレておりますね……

゚+.(・∀・)゚+.゚


さて、念の為こちらの質問は自分用に保存致しましておきますものと致します。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる