首页 > 试题广场 >

赛马

[编程题]赛马
  • 热度指数：3066 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长的时间后，赛道上剩余的马匹数量的数学期望是多少

输入描述:
每个测试输入包含1个测试用例
输入只有一行，一个正整数N
1 <= N <= 1000


输出描述:
输出一个浮点数，精确到小数点后四位数字，表示剩余马匹数量的数学期望
示例1

输入

1
2

输出

1.0000
1.5000
算法知识视频讲解
添加回答
xttty头像 xttty
马的速度不同，则一定能由大到小排列。假设是a1＞a2＞……＞an 那么a1在任何位置都可以存活 a2必须在a1后面才可以存活，因为路是无限长，所以概率是1/2 a3同理需要在a1和a2后面才能活，概率就是1/3 以此类推，期望是: 1+1/2+1/3+.....+1/n
发表于 2017-03-02 19:35:10 回复(6)
星辰大宇头像 星辰大宇

用的暴力求解，思路：数组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;
        }
    }
}
发表于 2017-03-20 16:53:49 回复(3)
布白头像 布白
概率论学得好就不用看了 =  =、
提供一种更程序员的递归思路：
有 n 匹马时，跑得最快的马在每个位置上的概率都是 1/n，当最快的这匹马落在位置 j (1 <= j <= n) 上时，前面的马全要死，后面的马全追不上这批最快的马进而退化成 (n - j) 匹马的期望问题，递推公式：hosre[n] = 1/n * (hosre[n - j] + 1)，(1 <= j <= n)。 
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;
}

编辑于 2018-03-15 19:37:53 回复(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);
    }
}
编辑于 2017-03-11 23:00:22 回复(1)
Hmmmmmmm_y头像 Hmmmmmmm_y 

	#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;





	     }





	 }

编辑于 2018-08-09 16:40:49 回复(0)
牛客1763773号头像 牛客1763773号
//动态规划
#include <string.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
intmain(){
    intn;
    cin >> n;
    vector<double> a;
    a.push_back(1.0);
    doublecurrrent = 0.0;
    for(inti = 2; i <= n; i++){
        currrent += a[i - 2];
        doubleinput = (currrent / i) + 1;
        a.push_back(input);
    }
    printf("%.4f", a[n-1]);
    return0;
}
发表于 2017-09-01 10:08:11 回复(0)
AA应SL头像 AA应SL
马的速度不同。假设是a1＞a2＞……＞an 。由于路无限长，所以速度快的一定会超过前面速度慢的。那么a1在任何位置都可以存活 a2必须在a1后面才可以存活，a3同理在a1,a2后才能存活，P（a3)=1/3;因为a3有三种情况，在a1前，a1,a2中间，a2后面。以此类推。a4为1/4；
发表于 2017-03-08 13:02:53 回复(0)
这个好玩吗？头像 这个好玩吗？
// 调和级数

#include <cstdio>

int main() {
    int n;
    while( scanf( "%d", &n ) != EOF ) {
        double sum = 0.0;
        for( int i = 1; i <= n; i++ ) {
            sum = sum + 1.0 / i;
        }
        printf( "%.4lf\n", sum );
    }
    return 0;
}

发表于 2017-03-05 15:25:46 回复(0)
制霸216头像 制霸216
速度最大的马无论在什么位置都可以不被淘汰，所以速度最大的马存活的概率是1，然后速度第二大的马只有在速度最大的马后面才能存活，只有在它前后两种情况，所以存活的概率是1/2，同理，速度第三大的马有三种排列情况（不考虑前面两匹马的排列），存活概率是1/3,依次类推，所以最后的情况就是1+1/2+1/3+......1/n。注意不是通过每种排列情况计算能存活下来的马的数量，而是根据每匹马能存活的概率计算。
发表于 2017-03-09 22:37:23 回复(2)
一叶秋头像 一叶秋 
#include <iostream>

using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	double ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans += 1.0 / i;
	}
	printf("%.4f\n", ans);
	return 0;
}

编辑于 2017-03-01 20:03:17 回复(0)
hahaheha头像 hahaheha 

#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;
}


发表于 2022-09-03 22:30:17 回复(0)
Jerry1127头像 Jerry1127 
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	a := float64(n)
	ans := 0.0
	for i := 1.0; i <= a; i++ {
		ans += float64(1.0 / i)
	}

	fmt.Println(ans)
}

发表于 2022-03-25 16:33:36 回复(0)
Hedgerow头像 Hedgerow 
#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;
}
任一马匹只有被后面的马匹追上才会被淘汰。在比赛时长无限且路无限长的条件下，设s1>s2>s3>...>sn，对于s1存活概率为1（无论位于哪，在某一时刻它总会追上前面一匹马），s2只有在s1后面才能存活，所以1/2的概率（前或后），以此类推，即求1+1/2+1/3+...+1/n的值保留四位即可。使用fixed()补零和setprecision(4)保留四位小数。
注：使用double保存最后结果可全A，用float只能过96%，好像是n=962的时候输出大了0.0001。double的精度更高一点。
发表于 2021-03-31 01:23:02 回复(0)
Ozaaa头像 Ozaaa
使用递归的方法做的 
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;
    }
}

编辑于 2019-08-16 19:58:12 回复(0)
佘溪源头像 佘溪源

也可以用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;
}
发表于 2019-08-02 19:46:07 回复(0)
牛客933099号头像 牛客933099号
直接考虑排在最前面的马，其速度最大的概率为1/n, 非最大的概率为(1-1/n)
设f(n)为n匹马时的期望
则若最前一匹马速度最大最后一定会留下
则f(n) = 1/n*(f(n-1) + 1) + (1-1/n) * f(n-1)
化简后为f(n) = f(n-1) + 1/n;
代码如下：
 
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);
        }
    }
}
发表于 2019-06-04 23:04:42 回复(0)
Mr.Lin_头像 Mr.Lin_
n=input()
p=0.0
for i in range(0,n):
    p+=1.0/(i+1)
print "%.4f"%p
发表于 2019-03-17 13:59:03 回复(0)
Dongxiaoyu头像 Dongxiaoyu
#include <iostream>
usingnamespacestd;
 
intmain()
{
    intn;
    while(cin >> n)
    {
        floatans;
        for(floati=1; i<=n && i<=10000; i++)
            ans += (1/i);
        printf("%.4f",ans);
    }
}
96%的通过率，求大神解答为什么，最后输出差0.0001

发表于 2018-09-22 17:06:18 回复(0)
雨落虹头像 雨落虹 

	#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;





	}

发表于 2018-09-06 17:35:49 回复(0)
liaoming头像 liaoming 
#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;
}

发表于 2018-08-15 15:38:19 回复(0)
提交观点

问题信息

C++工程师 2017 网易互娱 排序 递归 Java工程师 网易雷火
上传者：小小
难度：
37条回答 5528浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号