プロジェクトオイラー問523

https://projecteuler.net/problem=523
プロジェクトオイラー問523


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