1楼. 一个长度为1米的圆环,上面有n个点平均分布,2≤n≤1000,每个点被随机标记为0或1。
现有一机器人,会随机告诉你一个点的标记,然后你可以
①要求机器人是否改变该点的标记。
②要求机器人告诉下一个顺时针或逆时针的点的标记
机器人执行②以后,重复以上过程,但机器人每执行一次步骤②则记录你移动距离。你可以在任意时刻停止并回答n是多少。
请设计一个方案,能正确回答n且期望移动距离最小。
gf10025 2-15 09:10 4楼. 2里面的顺逆能不能自己选择啊?比如这次要机器人告诉顺时针的下一个,下次要机器人告诉逆时针的下一个……
劎子仙跡 2-22 12:15 回复(1) 5楼. 最保险的做法是,先把起点标记设为1,再一直顺时针走,把接下来遇到的998个标记全都设为1,第999个标记改为0。此时整个圆环只有机器人所在的位置是0。接着继续顺时针走,接着遇到的第n个标记是0,那么这个圆环就有n个点。不过如果点数太少的话,绕几百圈好像也不太划算()
贴吧用户_53E1EEN 2-22 21:10 回复(1) 6楼. 刚刚又想到一个方案。接下来我会用“前进”和“调头”来描述机器人移动。
先将起点标记设为1,引入变量m=1,
===分割线===
然后前进m步,中途遇到的标记都设为1,之后再前进一个标记设为0,
接着调头,然后一边前进一遍检查路过的标记,
如果在经过2m个标记之前,发现接下来第n个标记是0,那么n就是最终点数。
如果接下来2m个标记都是1,那就将m乘2,回到分割线位置继续执行。
这种方法的移动距离,最好情况是2圈,最坏情况是5圈,期望移动距离大致是三圈半
贴吧用户_53E1EEN 2-22 21:55 回复(2) 9楼. 先逆逆逆时针旋转移动17个点,终点设为1,其他点(包括起点)都设为0;
然后顺顺顺时针旋转,若在移动x(2<=x<=17)个点后遇到1,则n=x;
若没遇到,则继续顺顺顺时针旋转移动(113+1)-17=97个点,终点设为1,其他点都设为0;
然后逆逆逆时针旋转,若在移动x(18<=x<=113)点后遇到1,则n=x;
若没遇到,则继续逆逆逆时针旋转移动(459+1)-113=347个点,终点设为1,其他点都设为0;
然后顺顺顺时针旋转,若在移动x(114<=x<=459)个点后遇到1,则n=x;
若没遇到,则继续顺顺顺时针旋转移动1000-459=541个点,终点设为1,其他点都设为0;
最后顺时针或逆时针旋转均可,若在移动x(460<=x<=1000)点后遇到1,则n=x;
距离期望为3.3531
wyx8904wyx8904 3-5 19:10 回复 10楼. 若题目表述的意思是,人随着被告知的数字运动,那就太复杂了,提供最佳解的思路:
开局设为1,顺时针第二个0,我站在0这个点,中间有0-998个数字。
此时设(1,0)序列为模版A1
第三个数字:
为0时,继续顺时针,x≥3,设模版A2序列为(1,0,0)
为1时,则设为0,并且记录实时模版B,序列为(1),从A1模版开始比较,得知与模版A1的第一个数字相同,继续顺时针,
第四个数字:
为0时,与模版A1完全吻合,【对于1000总量而言,此时概率是否值得回头验证!!!或者继续顺时针运动,重复两次,则大大增加回头验证的价值,对于模版A1,一定是继续顺时针,甚至需要重复三次,可能才值得回头】。
我认为最优解一定是与所得信息同步递进的,即提前计算出对于个数n,在2-1000以内的平均分布,对于二段循环(即有两个数字的循环,需要重复多少次,值得回头验证),对于三段循环,需要重复多少次,值得回头验证,制成表格,然后依据实际情况依表行动,即为最优解。
若要算出期望,则需要对每种可能进行【步数和概率的统计】,是复杂的运算。
此题有误 3-24 15:26 回复