[编程题]随机的机器人
- 热度指数：1047 时间限制：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)
用的随机。多试几次就过了。迭代次数越大越准，但超过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)
给一个简单的解法：
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)
参考自：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)
百度解释：在概率论和统计学中，数学期望(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)
//思路：利用三维数组
// 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)
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)
//利用仿真思想实习，会有一点点偏差
#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)
//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)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
