每个测试输入包含1个测试用例 输入只有一行,一个正整数N 1 <= N <= 1000
输出一个浮点数,精确到小数点后四位数字,表示剩余马匹数量的数学期望
1 2
1.0000 1.5000
用的暴力求解,思路:数组array大小为马的个数,里面存放了每匹马的速度,不考虑马速度相等的情况。array = [1,2,3] 表示速度为1的马在最前面,速度为2的马在中间,速度为3的马在最后面,这种情况对应着:三匹马在场上,速度最快的马在最前面,速度最慢的马在最后面, 速度在中间的马位置在中间,则最最终剩下3匹马。 三匹马在场上位置的其他情况还有: [1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1],分别剩下2、2、2、1、1匹马。 当有n匹马则排列所有可能的情况,对每一种情况求剩下的马的数量。本来想用高中的学的那点组合数学求个递推式或者直接一个解表达式,发现数学功底不够... 代码如下,solve()求出每种排列,remain()函数求每种排列剩下的马的数量:
import java.util.*;
public class Main{
static int count = 0;
public static int remain(int[] array){
int max = array[0];
int remain_num = 0;
for(int i = 0; i < array.length; ++i){
if(max <= array[i]){
max = array[i];
++remain_num;//这匹马会留下
}
}
return remain_num;
}
public static void swap(int[] array,int i, int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void solve(int[] array, int idx){
if(idx == array.length - 1){
count += remain(array);
return ;
}
for(int i = idx; i < array.length; ++i){
swap(array, idx, i);
solve(array, idx + 1);
swap(array,idx,i);
}
}
public static void main(String[] arg){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int num = sc.nextInt();
int[] array = new int[num];
for(int i = 0; i < num; ++i){
array[i] = i + 1;
}
solve(array,0);
double res = count*1.0;
for(int j = 0; j < array.length; ++j){
res = res/array[j];
}
String str = String.format("%.4f", res);
System.out.println(str);
count = 0;
}
}
}
int main() { int n; cin >> n; double horse[n + 1]; horse[0] = 0; for (int i = 1; i <= n; i++) { horse[i] = 0; for (int j = 0; j < i; j++) horse[i] += (horse[j] + 1) / i; } printf("%.4lf", horse[n]); return 0; }
/*
后面速度快的马一定能追上前面速度慢的马。
n匹马的情况,当第一匹马是最快的时候,概率是1/n,这个时候期望是f(n-1)+1
当不是最快的时候,第一匹马一定能被追上,所以期望还是f(n-1),概率是(n-1)/n
即f(n) = (1/n)(f(n-1)+1)+(n-1)/n*(f(n-1)) 整理得 f(n) = 1/n+f(n-1)
*/
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); double res; int i=0; try{ i = in.nextInt(); } catch(Exception e) { i = 0; } res = run(i); System.out.println(String.format("%.4f",res)); } private static double run(inti) { if(i == 1) return1; return1/(double)i+run(i-1); }
}
#include <bits/stdc++.h>#include <iomanip>using namespace std;int main(){intn;while(cin>>n){double res=0;for(double i =0;i<n;i++){res += 1.0/(i+1);}cout<<fixed<<setprecision(4)<<res<<endl;}}
#include <iostream> #include <vector> #include <stdio.h> using namespace std; int main(){ int n; while(cin>>n){ vector<float> dp(n + 1); dp[0] = 0; dp[1] = 1; float pl = 0.5; for(int i = 2; i <= n; i++){ dp[i] = pl + dp[i - 1]; pl = (float)(i) / (i + 1) * pl; } printf("%.4f\n", dp[n]); } return 0; }
#include <bits/stdc++.h> #include <stdio.h> using namespace std; int main(){ int N; while(cin>>N){ double res = 1; for(double i=2;i<=N;++i){ res += 1.0/i; } cout<<fixed<<setprecision(4)<<res<<endl; } return 0; }
import java.util.HashMap; import java.util.Scanner; import java.text.DecimalFormat; public class Main{ public static void main(String[] args){ int n = new Scanner(System.in).nextInt(); HashMap<Integer, Double> resultMap = new HashMap<>(); double result = expectHorses(n, resultMap); DecimalFormat formatter = new DecimalFormat("0.0000"); System.out.println(formatter.format(result)); } public static double expectHorses(int n, HashMap<Integer, Double> resultMap) { if (resultMap.get(n) != null) return resultMap.get(n); if (n == 0 || n == 1) { resultMap.put(n, Double.valueOf(n)); return n; } double horses = 0; for(int i = 0; i < n; i++) { horses += (expectHorses(i, resultMap) + 1.0) / n; } resultMap.put(n, horses); return horses; } }
也可以用dp的思路做:如果总共4匹马,第4匹马的期望就是(最快的马排在最前面的时候,3匹马的期望+1)+(最快的排在第二的时候,2匹马的期望+1,最快的排在第三的时候,1匹马的期望+1)+(排在最后的时候,0匹马的期望+1)。
总共有n匹马,就可以动态规划地推出f(n)
代码如下:
#include <iostream> #include <vector> using namespace std; vector<double> f(1, 0); int main(){ int n; while(cin >> n){ if(f.size() >= n + 1){ printf("%.4f\n", f[n]); continue; } for(int i = f.size(); i <= n; ++i){ double tmp = 0; for(int j = 0; j < i; ++j){ tmp += 1 + f[j]; } tmp /= i; f.push_back(tmp); } printf("%.4f\n", f[n]); } return 0; }
importjava.util.*; publicclassMain{ publicstaticvoidmain(String[]args){ Scanner in = newScanner(System.in); while(in.hasNextInt()){ intn = in.nextInt(); doubleexpect = 0; for(inti=1; i<=n; i++){ expect += 1.0/i; } System.out.printf("%.4f\n",expect); } } } |
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
int n;
while(cin>>n){
float *e=new float[n+1];
e[0]=0;
for(int i=1;i<n+1;i++){
e[i]=0;
for(int j=0;j<i;j++){
e[i]+=(e[j]+1);
}
e[i]=e[i]/i;
}
cout<<setiosflags(ios::fixed)<<setprecision(4)<<e[n]<<endl;
delete []e;
}
return 0;
}
#include <iostream> #include <vector> using namespace std; double process(int n) { if (n < 1) { return 0.0; } vector<double> dp(n + 1, 0.0); dp[1] = 1.0; for (int i = 2; i <= n; ++i) { for (int j = 0; j < i; ++j) { dp[i] += (1 + dp[j]) / i; } } return dp[n]; } int main() { int n; while (cin >> n) { printf("%.4f\n", process(n)); } return 0; }