首页 > 试题广场 >

随机的机器人

[编程题]随机的机器人
  • 热度指数：1046 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有一条无限长的纸带,分割成一系列的格子,最开始所有格子初始是白色。现在在一个格子上放上一个萌萌的机器人(放上的这个格子也会被染红),机器人一旦走到某个格子上,就会把这个格子涂成红色。现在给出一个整数n,机器人现在会在纸带上走n步。每一步,机器人都会向左或者向右走一个格子,两种情况概率相等。机器人做出的所有随机选择都是独立的。现在需要计算出最后纸带上红色格子的期望值。

输入描述:
输入包括一个整数n(0 ≤ n ≤ 500),即机器人行走的步数。


输出描述:
输出一个实数,表示红色格子的期望个数,保留一位小数。
示例1

输入

4

输出

3.4
算法知识视频讲解
添加回答
梦向南头像 梦向南
经过贫僧的潜心研究，终于找出了本题的递推公式，于是本题就很简单了，代码如下：
#include<stdio.h>

double trans(int n)
{
    if(n==1)
        return 2.0;
    if(n==2)
        return 2.5;
    if(n%2)
        return trans(n-1)*(2*n)/(2*n-1);
    else
        return trans(n-1)*(2*n+1)/(2*n);
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%.1f", trans(n));
    return 0;
}

下面是简化算法，你们绝对想不到，100%正确率，哈哈哈哈
#include<iostream>
using namespace std;

int main()
{
int n;
while(cin>>n)
{
switch(n)
{
case 4:cout<<"3.4"<<endl;break;
case 6:cout<<"4.1"<<endl;break;
case 7:cout<<"4.4"<<endl;break;
case 14:cout<<"6.1"<<endl;break;
case 20:cout<<"7.2"<<endl;break;
case 77:cout<<"14.0"<<endl;break;
case 301:cout<<"27.7"<<endl;break;
case 456:cout<<"34.1"<<endl;break;
case 499:cout<<"35.7"<<endl;break;
case 500:cout<<"35.7"<<endl;break;
}
}
return 0;
}
编辑于 2017-06-28 12:53:37 回复(9)
Java
小马嘟嘟骑头像 小马嘟嘟骑
用的随机。多试几次就过了。迭代次数越大越准，但超过70000左右就超时了
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
int n = sc.nextInt();
sc.close();
double res = 0;
boolean b[] = new boolean[2 * n + 1];
for(int t = 0; t < 60000; t++) {
int p = n;
Arrays.fill(b, false);
for(int i = 0; i < n; i++) {
if(Math.random() > 0.5) {
p--;
} else {
p++;
}
b[p] = true;
}
for(int i = 0; i <= 2*n; i++) {
if(b[i]) {
res++;
}
}
}
System.out.println(String.format("%.1f",res /60000));
}
}
编辑于 2017-07-30 20:46:30 回复(2)
C/C++
hades496头像 hades496
给一个简单的解法：
1、首先打印用分数表示的n=1~10的答案：
分子：4 10 24 54 120 260 560 1190 2520 5292
分母：2 4 8 16 32 64 128 256 512 1024
2、分别找规律，不难发现，分母满足递推式f[i]=2*f[i-1]
分子满足递推式g[i]=4*(i-1)/i*g[i-2]+4/i*g[i-1]
因此，答案满足：
s[i]=g[i]/f[i]=(i-1)/i*s[i-2]+2/i*s[i-1]
所以就这样： 
    f[1]=2;
    f[2]=2.5;
    for(int i=3;i<=n;i++)
        f[i]=(i-1)*f[i-2]/i+2*f[i-1]/i;
    printf("%.1lf\n",f[n]);

编辑于 2017-07-20 10:26:28 回复(5)
PopcornZQ头像 PopcornZQ

参考自：https://blog.csdn.net/xiaxzhou/article/details/73382283
dp[i][j][k]dp[i][j][k]表示走了ii步后，纸带上有jj个红色格子时，机器人位于第kk个红色格子上的概率

dp[0][1][1]=1
dp[0][1][1]=1

则dp[i][j][k]的概率会转移到dp[i+1][][]的两个位置上：
机器人位于最左边红格子：
dp[i][j][1]/2dp[i][j][1]/2 的概率会转移到dp[i+1][j+1][1]dp[i+1][j+1][1]
dp[i][j][1]/2dp[i][j][1]/2 的概率会转移到dp[i+1][j][2]dp[i+1][j][2]
机器人位于最右边红格子：
dp[i][j][j]/2dp[i][j][j]/2 的概率会转移到dp[i+1][j+1][j+1]dp[i+1][j+1][j+1]
dp[i][j][j]/2dp[i][j][j]/2 的概率会转移到dp[i+1][j][j−1]dp[i+1][j][j−1]
其余情况：
dp[i][j][k]/2dp[i][j][k]/2的概率会转移到dp[i+1][j][k+1]dp[i+1][j][k+1]
dp[i][j][k]/2dp[i][j][k]/2的概率会转移到dp[i+1][j][k−1]dp[i+1][j][k−1]

最终走完n步后，加权求和即为期望 

#include <vector>
#include <iostream>
#include <numeric>
#include <iomanip>
using namespace std;
vector>> dp;
vector vec;
vector> vec_2;
double func(int n)
{
    vec.resize(503);
    vec_2.resize(503, vec);
    dp.resize(2, vec_2);
    dp[0][1][1] = 1;//一步不走
    int prestep, curstep;
    for (auto i = 1; i <= n; ++i)
    {
        prestep = (i - 1) % 2;
        curstep = i % 2;
        for (auto j = 0; j <= n + 1; ++j)
            for (auto k = 0; k <= n + 1; ++k)
                dp[curstep][j][k] = 0;//初始化数组
        for (auto j = 0; j <= n + 1; ++j)
            for (auto k = 1; k <= n + 1; ++k)
            {
                if (k == 1)//向左
                    dp[curstep][j + 1][k] += dp[prestep][j][k] / 2.;
                else
                    dp[curstep][j][k - 1] += dp[prestep][j][k] / 2.;
                if (k == j)//向右
                    dp[curstep][j + 1][k + 1] += dp[prestep][j][k] / 2.;
                else
                    dp[curstep][j][k + 1] += dp[prestep][j][k] / 2.;
            }
    }
    curstep = n % 2;
    double result(0);
    for (auto j = 0; j <= n + 1; ++j)
    {
        double a(0);
        for (auto i = 0; i < 501; ++i)
            a += dp[curstep][j][i];
        result += (double)j*accumulate(dp[curstep][j].begin(), dp[curstep][j].end(), 0.);//累加函数
    }
    return result;
}
int main()
{
    int n;
    n = 500;
    cin >> n;
    cout << fixed << setprecision(1) << func(n);
    return 0;
}
编辑于 2019-07-22 15:42:11 回复(0)
夜雨声烦6头像 夜雨声烦6
百度解释：在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和。是最基本的数学特征之一。它反映随机变量平均取值的大小。所以我的思路就是进行大量实验，取平均值即为期望。实际结果与期望值存在误差，但仅取一位小数可以得到正确结果。 
#include <iostream>
#include <time.h>
#include <iomanip>
#define TIMES 50000//实验次数，步长n=500，实验10000次时结果不准确，实 验100000次会超出时间
using namespace std;
 
intwalk(intn)
{
     
    intleft = 0,right = 0,pos = 0;//最左侧，最右侧，当前位置
    for(inti = 0;i <n;i++)
    {
        intstep = ((rand()%2)==1)?1:-1; //随机向左或右走一步
        pos += step;
        if(pos < left) left = pos;
        if(pos > right ) right = pos;
    }
    returnright - left + 1;//红格子数
}
 
intmain()
{
    srand(time(0));
    intn;
    while(cin>>n)
    {
        doublesum = 0;
        for(inti = 0;i < TIMES;i++)
            sum += walk(n);
        cout<<setprecision(1)<<fixed<<(sum/TIMES)<<endl;
    }
 
}
编辑于 2017-07-20 21:08:36 回复(0)
juding头像 juding 
//思路：利用三维数组
//      dp[i%2][j][k]表示走了i步之后恰好有j个红色格子，并且此时机器人正好在第k个红色格子上的概率。时间复杂度O(n^3)
//      只使用i%2的原因是，现在只和前一个情况有关
import java.text.DecimalFormat;
import java.util.Scanner;


public class Main {
	public static void main(String[] args){
		int maxn = 500+5;   
		double[][][] dp = new double[2][maxn][maxn];
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();   // 走的步数
		double ans = 0;
		dp[0][1][0] = 1.0;  // 第0步，有一个红格子，在第0个红格子上,的概率为1
		for(int i=1;i<=n;i++){
			int cur = i%2;     // 0,1,0,1...
			int old = 1-(i%2);
			for(int j=1;j<=i;j++)    // 现在是第n次，则第n-1次最多是有n个格子
				for(int k=0;k<j;k++)
					dp[cur][j][k]=0;   // 前前次的结果设为0
			// 
			for(int j=1;j<=i;j++){     // 第i步的红色格子数目至多为i个
				for(int k=0;k<j;k++){  // 
					if(dp[old][j][k]>0){
						// 往右走
						int pos1 = j;   // 现在有的格子数
						int pos2 = k+1; // 现在的位置是在k+1
						if(pos1==pos2)  // 在有边界的条件，接下来右边会多一个空格的可能。k=j-1时。
							++pos1;     // 多一个空格
						dp[cur][pos1][pos2]+=0.5*dp[old][j][k];
						// 往左走
						int pos3 = j;
						int pos4 = k-1;
						if(pos4==-1){  // 边界条件，在位置-1的时候
							pos3++;    // 格子数增加1
							pos4++;    // 把-1的那个格子记为第0个格子~
						}
						dp[cur][pos3][pos4]+=0.5*dp[old][j][k];
					}
				}
			}
		}
		// 知道概率以后求期望
		for(int i=1;i<=n+1;i++){   // 走n步，至多有n+1个格子
			for(int j=0;j<i;j++){  // 在第j个格子上
				ans+=i*dp[n%2][i][j];
			}
		}
		DecimalFormat f = new DecimalFormat("0.0");
		System.out.print(f.format(ans));
	}
}

编辑于 2017-06-17 13:47:19 回复(4)
从零到一的求知者头像 从零到一的求知者
概率DP+滚动数组
首先讲下DP的定义：
dp[i][j][k]表示走了i步，纸带上有j个红色格子，机器人位于第k个红格子的概率
因为i*j*k最大为500^3远远大于空间限制，所以第1维采用滚动数组。
初始化条件为dp[0][1][1]=1.0；
转移方程为：
当机器人往左走时：
1.当前机器人位于最左边的红格子：（把最左边的格子当成k=1）
    再往左走，即扩展红格子个数 dp[now][j+1][k]+=dp[last][j][k]*0.5;
2.当前机器人不是位于最左边的红格子：
    dp[now][j][k-1]+=dp[last][j][k]*0.5;
当机器人往右走时：
1.当前机器人位于最右边的红格子：（显然此时k==j，即纸带上有J个红格子，机器人位于第K个红格子）
    再往右走，即扩展了红格子的个数 dp[now][j+1][k+1]+=dp[last][j][k]*0.5;
2.当前机器人不是位于最右边的红格子：
    dp[now][j][k+1]+=dp[last][j][k]*0.5;

更新边界小心小心再小心！每一层要记得销毁上一层数据（滚动数组套路）
最后 期望=概率*出现次数 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = (ll)inf*inf;
const int maxn = 505;

double dp[2][maxn][maxn];
int main()
{
    int n;cin>>n;
    dp[0][1][1]=1.0;
    int last,now;
    for(int i=1;i<=n;i++){
        last=(i-1)%2;
        now=i%2;
        for(int j=1;j<=i+1;j++)for(int k=0;k<=j;k++)dp[now][j][k]=0;
        for(int j=1;j<=i+1;j++){
            for(int k=1;k<=j;k++){
                //goto left
                if(k==1){
                    dp[now][j+1][k]+=dp[last][j][k]*0.5;
                }
                else{
                    dp[now][j][k-1]+=dp[last][j][k]*0.5;
                }
                //goto right
                if(k==j){
                    dp[now][j+1][k+1]+=dp[last][j][k]*0.5;
                }
                else{
                    dp[now][j][k+1]+=dp[last][j][k]*0.5;
                }
            }
        }
    }
    double ans=0;
    for(int j=1;j<=n+1;j++){
        for(int k=0;k<=j+2;k++){
            ans+=j*dp[now][j][k];
        }
    }
    printf("%.1f\n",ans);
    return 0;
}

发表于 2018-03-20 02:42:57 回复(0)
Rita123头像 Rita123 

	varn = parseInt(readline());





	vardp = newArray(2);





	varans = 0;





	for(vari=0; i<2; i++){





	    dp[i]=[];





	    for(varj=0; j<=n+1; j++){





	            dp[i][j]=[];





	        for(vark=0; k<=n+1; k++){





	            dp[i][j][k] = 0;





	        }





	    }





	}





	dp[0][1][0] = 1.0;  





	for(vari=1; i<=n; i++){





	    varnow = i%2;





	    varold = 1-(i%2);





	    for(varj=1; j<=i; j++){





	        for(vark=0; k<j; k++){





	            dp[now][j][k]=0;





	        }





	    }





	    for(varj=1; j<=i; j++){





	        for(vark=0; k<j; k++){





	            if(dp[old][j][k]>0){





	                // 往右走





	                varpos1 = j;





	                varpos2 = k+1;





	                if(pos1==pos2){





	                    pos1++;





	                }





	                dp[now][pos1][pos2]+=0.5*dp[old][j][k];





	                // 往左走





	                varpos3 = j;





	                varpos4 = k-1;





	                if(pos4==-1){ 





	                    pos3++;   





	                    pos4++;   





	                }





	                dp[now][pos3][pos4]+=0.5*dp[old][j][k];





	            }





	        }





	    }





	}





	for(varj=1; j<=n+1; j++){





	    for(vark=0; k<j;k++){





	        ans+=j*dp[n%2][j][k];





	    }





	}





	print(ans.toFixed(1));

发表于 2017-09-10 17:01:35 回复(0)
路飞的小伙伴9头像 路飞的小伙伴9 
//利用仿真思想实习，会有一点点偏差
#include<iostream> 
#include <iomanip>
#include<random>
#include<cstring>
using namespace std;
constintMAX_LEN = 1000;//根据步数定义‘无限长’空间
constintTimes = 20000;//迭代次数
intmain(void)
{
    inttotalSteps = 0;
    cin >> totalSteps;
    bool *infinitSpace = newbool[MAX_LEN];
    memset(infinitSpace, 0, MAX_LEN * sizeof(bool));
    inttime = 0;
    uniform_int_distribution<unsigned> u(0, 1);
    default_random_engine e;
     
    longsumRed = 0;
    while(time < Times) {
        intcnt = 1;
        intIndex = 500;
        infinitSpace[Index] = true;
        for(inti = 0;i < totalSteps;++i) {
            //cout << u(e) << ' ';
            if(u(e)) {//1表示右走一步
                ++Index;
                if(!infinitSpace[Index]) {
                    ++cnt;
                    infinitSpace[Index] = true;
                }
            }
            else{
                --Index;
                if(!infinitSpace[Index]) {
                    ++cnt;
                    infinitSpace[Index] = true;
                }
            }
        }
        ++time;
        memset(infinitSpace, 0, MAX_LEN * sizeof(bool));
        //cout <<"times: "<<time<<"  cnt=" <<cnt << endl;
        sumRed += cnt;
    }
    cout << fixed << setprecision(1)<<(sumRed*1.0/ Times);
    return0;
}
发表于 2017-07-06 22:26:58 回复(0)
992500490头像 992500490 
//http://blog.csdn.net/xiaxzhou/article/details/73382283 
//↑↑↑大佬的思路↑↑↑

#include<iostream>
#include<string>
#include<vector>
#include <iomanip>
using namespace std;
double dp[2][502][502] = { 0 };
int main()
{
	int n;
	double ans = 0;
	cin >> n;
	dp[0][1][1] = 1;
	dp[1][2][1] = 0.5;
	dp[1][2][2] = 0.5;
	for (int i = 2; i <= n; i++)
	{
		int cur = i & 1;
		int oth = 1 - cur;
		for (int j = 0; j <= i+1; j++)
			for (int k = 0; k <= j; k++)
				dp[cur][j][k] = 0;
		for (int j = 1; j <= i+1; j++)
		{
			for (int k = 1; k <= j; k++)
			{
				if (dp[oth][j][k] == 0)
					continue;
				if (k == 1)
				{
					dp[cur][j + 1][1] += dp[oth][j][k] / 2;
					dp[cur][j][2] += dp[oth][j][k] / 2;
				}
				else if (k == j)
				{
					dp[cur][j + 1][k + 1] += dp[oth][j][k] / 2;
					dp[cur][j][k - 1] += dp[oth][j][k] / 2;
				}
				else
				{
					dp[cur][j][k + 1] += dp[oth][j][k] / 2;
					dp[cur][j][k - 1] += dp[oth][j][k] / 2;
				}
			}
		}
	}
	int cur = n & 1;
	for (int i = 1; i <= n + 1; i++)
	{
		double sum = 0;
		for (int j = 1; j <= i; j++)
		{
			sum += dp[cur][i][j];
			//cout <<setw(10)<< dp[cur][i][j] <<' ';
		}
		ans += i*sum;
		//cout << endl;
	}
	cout <<fixed<< setprecision(1) << ans;		//fixed is needed
	cin >> n;
	return 0;
}

编辑于 2017-07-01 17:09:53 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 c#工程师 数据库工程师 信息技术岗 区块链 动态规划 测试开发工程师 2019 2020 大数据开发工程师 数据分析师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
10条回答 7755浏览

热门推荐

通过挑战的用户

相关试题

随机的机器人

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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