n番目をソートするときはn-1番目まではソートされています。
n-1番目までのソート回数はn-1番までのソート回数の期待値です。
4つの場合
[1,2,3,4]
[1,2,4,3]
[1,3,4,2]
[2,3,4,1]
のソート回数+長さ3の場合のソート回数の期待値を集計していき4で割れば答えが出ます。
後はこれを30まで繰り返すだけです。
答えは小数点以下3桁でだしてますので目視で修正してください。
30の場合30通りだけ検討すれば終わりです。
ソートのシミュレーションはstd::listを使えばかなり早くなると思うが配列で手抜き。
計算時間2分。
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include <iomanip>
long double calc(int len,int n){
int ds[31]={0};
long double c1=0;
int add=0;
for(int i=1;i<=len;i++){
if(i==n)add=1;
ds[i]=i+add;
}
ds[len]=n;
bool isSort=false;
//for(int i=1;i<=len;i++)printf("%d ",ds[i]);
while(isSort==false){
//
//printf("\n");
for(int i=1;i<len;i++){
if(ds[i]>ds[i+1]){
int t=ds[i+1];
int dell=0;
for(int j=len;j>1;j--){
if(j==i+1)dell=1;
ds[j]=ds[j-dell];
}
ds[1]=t;
c1+=1.0;
break;
}
if(i+1==len)isSort=true;
}
}
return c1;
}
int main(){
long double memo[31]={0};
memo[1]=0;
memo[2]=0.5;
memo[3]=1.5;
for(int j=4;j<=30;j++){
long double sum=0;
for(int i=1;i<=j;i++){
long double t=calc(j,i);
sum+=memo[j-1]+t;
//std::cout<<","<<t<<"\n";
}
memo[j]=sum/j;
std::cout<<std::fixed<<std::setprecision(3)<<j<<" "<<memo[j]<<"\n";
}
}
最終更新:2015年10月10日 07:43