Problem 523

Problem 523 「初めてのソート その1」 †

リストをソートする以下のアルゴリズムについて考えよう:

1. リストの1番目からスタートし, 順番に隣り合った要素のペアをチェックしていく.
2. もし隣り合った要素が順番通りでなければ:
   a. リストの1番目にそのペアの小さい方の要素を移動する.
   b. ステップ1から作業を再開する.
3. 全てのペアが順番通りになった時, 停止する.

例えば, リスト { 4 1 3 2 } は以下のようにしてソートされる:

4 1 3 2 (4 と 1 が順番どおりでないのでリストの1番目に 1 を移動する)
1 4 3 2 (4 と 3 が順番どおりでないのでリストの1番目に 3 を移動する)
3 1 4 2 (3 と 1 が順番どおりでないのでリストの1番目に 1 を移動する)
1 3 4 2 (4 と 2 が順番どおりでないのでリストの1番目に 2 を移動する)
2 1 3 4 (2 と 1 が順番どおりでないのでリストの1番目に 1 を移動する)
1 2 3 4 (これでリストはソートされた)

リスト L をソートする際に実行されるステップ 2a の回数を F(L) としよう. 例えば, F({ 4 1 3 2 }) = 5 となる.

整数 { 1,2, ..., n } からなるすべての順列 P における F(P) の期待値を E(n) としよう.
E(4) = 3.25, E(10) = 115.725 が与えられている.

E(30) を求めよ. 回答を小数点以下2桁までとなるよう四捨五入して答えよ.

最新の20件

アクセス数

合計：868 今日：1 昨日：4