来考验坛友们的数学水平了（答案已公布在52楼，71楼补充了图）

天下何人 · 发表于 2024-7-20 22:43

本帖最后由天下何人于 2024-7-20 22:48 编辑

想了想，如果第一步(1012，2)就碰到敌人的话确实无法确定哪边有缺口，改进一下

第一次测第1列，第二次测中间1012列，确定第1列到第1012列之间能不能成立斜线，能成立就二分左边，不能就二分右边，比前面的方法多一次，13次

ryanghj · 发表于 2024-7-20 22:44

isengrin 发表于 2024-7-20 22:40
比如这样

那个是走到第二行，我箭头稍微多了一点而已，不是走到第三行

横着移动是不怕遇到坏人的，因为相当于瞬移

—— 来自 Xiaomi 2308CPXD0C, Android 14上的 S1Next-鹅版 v2.5.2-play

snarc1 · 发表于 2024-7-20 22:45

本帖最后由 snarc1 于 2024-7-20 22:46 编辑

3次，注意每一列最多有一个坏人，这个问题的关键是找到一个确定的坏人，然后绕到他的那一列的下一行，一直沿着这一列走就行了。第一次尝试从【1，1】下到【2，1】，然后往右边一直走，一次就可以探查到第一行的坏人，假定这个坏人是【2，p】，接下来的问题就是如何走到【3，p】，然后向下一直走到【2024，p】，从【2，p-1】或者【2，p+1】的向下，最坏的情况就是这两个中有一个是坏人，如若不然，则直接通关，所以最坏的情况3次解决。（【2，1】是坏人的情况不影响3次的结果，为了上面的流畅性省略掉）

isengrin · 发表于 2024-7-20 22:47

ryanghj 发表于 2024-7-20 22:44
那个是走到第二行，我箭头稍微多了一点而已，不是走到第三行

横着移动是不怕遇到坏人的，因为相当于瞬移 ...

不是，从你那个图来看，你从11行下到第12行的时候，不能保证那个格子不是坏人

ryanghj · 发表于 2024-7-20 22:48

isengrin 发表于 2024-7-20 22:47
不是，从你那个图来看，你从11行下到第12行的时候，不能保证那个格子不是坏人 ...

每行只有一个坏人啊

那箭头是从10下到11

1-10 10-11 11-底，是这么个顺序

—— 来自 Xiaomi 2308CPXD0C, Android 14上的 S1Next-鹅版 v2.5.2-play

isengrin · 发表于 2024-7-20 22:50

ryanghj 发表于 2024-7-20 22:48
每行只有一个坏人啊那箭头是从10下到11

1-10 10-11 11-底，是这么个顺序

那你从11行如何到12行

cjtk · 发表于 2024-7-20 22:52

本帖最后由 cjtk 于 2024-7-20 22:55 编辑

二楼的题错了，是 2024行 2023列 2022个敌人

实际上用一个小一点的就行，明白道理加大棋盘也是一样的，
假设10行9列8个敌人
第二行敌人一定在第一列或者最后一列，如果在别的地方碰到用楼上的办法绕过去，n=3结束
然后这里假设第一列碰到敌人，那么就按这个感觉一行一行的左右探索标志x的地方

S	S	S	S	S	S	S	S	S
o	x	x	x	x	x	x	x	x
	?	x	x	x	x	x	x	x
		?	x	x	x	x	x	x
			?	x	x	x	x	x
				?	x	x	x	x
					?	x	x	x
						?	x	x
							?	x
G	G	G	G	G	G	G	G	G

o是之前碰到的敌人，?是敌人可能的地方，如果都走完了就直接到最后一列了，游戏结束
如果是中间碰到了一个敌人，那就可以直接绕过去了, 图里按y走就行

S	S	S	S	S	S	S	S	S
o	x	x	x	x	x	x	x	x
	?	x	x	x	x	x	x	x
y	y	y	o
y
y
y
y
y
G	G	G	G	G	G	G	G	G

不管在哪一行碰到都可以绕过去然后回到第一列直达终点

rick343 · 发表于 2024-7-20 22:53

本帖最后由 rick343 于 2024-7-20 23:17 编辑

好吧，这个方法有问题

前两步确定两边坏人的位置。
第三步从一列出发，在①和②之间那行转弯。
遇到3以后挑一个合适的区间重复第三步

愚钝兔子 · 发表于 2024-7-20 22:54

本帖最后由愚钝兔子于 2024-7-20 22:59 编辑

？每一列最多有一个坏人，那找到第一行和第二行的坏人以后不就绕过第一行的坏人可以无脑往下了

是我想岔了吗
--------------
哈哈果然是想简单了

骷髅兵 · 发表于 2024-7-20 22:54

天下何人发表于 2024-7-20 22:15
因为列数比敌人数多1，二分后肯定有一边是无法排成斜线

比如第一步探中间1012，(1012，1013)是敌人，所以 ...

你画一下就知道，刚好一个45度斜线上随机缺一个口子，哪有什么斜率不同

，相当于你从上方发射粒子碰撞一堵有一个随机位置缺口的隐藏的墙，每次碰到墙粒子死亡探出墙上一个点，由于墙的缺口位置随机生成并固定不变，所以这粒子的移动轨迹和你如何知道这隐藏墙上的缺口在哪里毫无关系，这问题求的也不是最理想情况，是粒子100%成功率穿过缺口的最低尝试次数。

Hydro · 发表于 2024-7-20 22:55

snarc1 发表于 2024-7-20 22:45
3次，注意每一列最多有一个坏人，这个问题的关键是找到一个确定的坏人，然后绕到他的那一列的下一行，一直 ...

(2, p+1)是坏人而(2, p-1)不可达怎么办，e.g. p=1

今井莉莎 · 发表于 2024-7-20 22:58

提示: 作者被禁止或删除内容自动屏蔽

snarc1 · 发表于 2024-7-20 22:58

Hydro 发表于 2024-7-20 22:55
(2, p+1)是坏人而(2, p-1)不可达怎么办，e.g. p=1

不存在不可达的情况，注意一行只有一个坏人，如果从左边下不去就从最右侧的出发向向左走到坏人的旁边向下

Hydro · 发表于 2024-7-20 23:02

今井莉莎发表于 2024-7-20 22:58
公布答案吧，答案就是3次，其实6楼的哥们已经画图做出来这题的一半了，采取如下策略，从第1行的最右边开始 ...

“直到发现阶梯断掉的部分”的最差情况不是阶梯有2022个坏人长吗，最小稳定尝试数怎么是3
我看错题了？?

秋月孝三 · 发表于 2024-7-20 23:05

Hydro 发表于 2024-7-20 23:02
“直到发现阶梯断掉的部分”的最差情况不是阶梯有2022个坏人长吗，最小稳定尝试数怎么是3
我看错题了？? ...

只要不踩到坏人就可以一直走，不消耗尝试次数

isengrin · 发表于 2024-7-20 23:05

今井莉莎发表于 2024-7-20 22:58
公布答案吧，答案就是3次，其实6楼的哥们已经画图做出来这题的一半了，采取如下策略，从第1行的最右边开始 ...

遍历的时候每行都是一次尝试啊，不能把“以此法遍历每一行的格子”算作一次尝试

Hydro · 发表于 2024-7-20 23:06

snarc1 发表于 2024-7-20 22:58
不存在不可达的情况，注意一行只有一个坏人，如果从左边下不去就从最右侧的出发向向左走到坏人的旁边向下 ...

52楼答案，从右侧开始扫，"第2行的坏人在最左边1列"的情况，它在数组边缘，绕过它只有一个方向，这就是最差的阶梯形情形，也是"罐子模型"的情况

isengrin · 发表于 2024-7-20 23:07

秋月孝三发表于 2024-7-20 23:05
只要不踩到坏人就可以一直走，不消耗尝试次数

注意是每一行，最差情况是每行都要遇一次坏人

cjtk · 发表于 2024-7-20 23:07

Hydro 发表于 2024-7-20 23:06
52楼答案，从右侧开始扫，"第2行的坏人在最左边1列"的情况，它在数组边缘，绕过它只有一个方向，这就是最 ...

你看一下我47楼的表格

愚钝兔子 · 发表于 2024-7-20 23:09

Hydro 发表于 2024-7-20 23:02
“直到发现阶梯断掉的部分”的最差情况不是阶梯有2022个坏人长吗，最小稳定尝试数怎么是3
我看错题了？? ...

我大概懂了。因为最坏情况一定是坏人排成一个阶梯并在随机位置插入一个空白列。你是可以预判这个最坏情况下坏人的位置并不去触碰它的。停在前一格就可以去扭头去下一行了。
当你经过了空白列后坏人会比你的预判提前一格出现，所以你会撞上坏人，从而就知道坏人的旁边一列就是空白列

snarc1 · 发表于 2024-7-20 23:09

Hydro 发表于 2024-7-20 23:06
52楼答案，从右侧开始扫，"第2行的坏人在最左边1列"的情况，它在数组边缘，绕过它只有一个方向，这就是最 ...

题目里有个条件是可以往回走

今井莉莎 · 发表于 2024-7-20 23:10

提示: 作者被禁止或删除内容自动屏蔽

新人马甲2 · 发表于 2024-7-20 23:10

本帖最后由新人马甲2 于 2024-7-20 23:17 编辑

这应该是个概率题，每移动一行有1/2023概率返回起始点然后尝试次数+1，需要求的是最多可以尝试失败多少次（答案是2022次）

但是理论上确实有若干种分布让憨豆永远无法抵达最后一行，也就是坏人的分布呈连续的，第一个坏人在第一行的比如说最左边，最后一个坏人在最后一行的最右边，而憨豆的移动只能是上下左右移动，在这种分布下憨豆穿过坏人阵列抵达最后一行的可能性是0
哦2022个坏人，2023列，还有一列是空的，那没错啊，最多可以失败2022次，那n就是2023？

秋月孝三 · 发表于 2024-7-20 23:11

本帖最后由秋月孝三于 2024-7-20 23:12 编辑

isengrin 发表于 2024-7-20 23:07
注意是每一行，最差情况是每行都要遇一次坏人

不需要的。假设第二行坏人在(2,1)，那么当最坏情况下探索第三行(3,3)~(3,2023)都没踩到坏人的时候就肯定知道坏人在(3,2)了（因为列限制，所以不可能是(3,1)），不需要真踩一下(3,2)。后面的行都是一个道理

Hydro · 发表于 2024-7-20 23:12

cjtk 发表于 2024-7-20 23:07
你看一下我47楼的表格

"然后这里假设第一列碰到敌人，那么就按这个感觉一行一行的左右探索标志x的地方"
这不是最差情况就是尝试了2022次把坏人全撞出来了吗，最小稳定尝试数是2023啊....?

cjtk · 发表于 2024-7-20 23:15

Hydro 发表于 2024-7-20 23:12
"然后这里假设第一列碰到敌人，那么就按这个感觉一行一行的左右探索标志x的地方"
这不是最差情况就是尝试 ...

x的地方没有敌人啊

snarc1 · 发表于 2024-7-20 23:15

Hydro 发表于 2024-7-20 23:12
"然后这里假设第一列碰到敌人，那么就按这个感觉一行一行的左右探索标志x的地方"
这不是最差情况就是尝试 ...

坏人有可能在n个位置，如果我n-1次都没碰到他，那么他在的位置不就确定了吗，不需要真的去碰他

今井莉莎 · 发表于 2024-7-20 23:15

提示: 作者被禁止或删除内容自动屏蔽

圣堂刺客 · 发表于 2024-7-20 23:18

幻想风靡_ 发表于 2024-7-20 21:20
二分。
阶梯式的话，行之差一定等于列之差，中间一共2022行，2023列，取1，1012和2023后肯定有个区间不满 ...

二分法的话走完二等分点就走四等分点了，最边上的其实不用走的，然后每次的等分点都得尝试两次

cjtk · 发表于 2024-7-20 23:20

Hydro 发表于 2024-7-20 23:12
"然后这里假设第一列碰到敌人，那么就按这个感觉一行一行的左右探索标志x的地方"
这不是最差情况就是尝试 ...

只走x，别走？的地方

今井莉莎 · 发表于 2024-7-20 23:28

提示: 作者被禁止或删除内容自动屏蔽

新人马甲2 · 发表于 2024-7-20 23:36

但是想了想，也可能遇到坏人在最边上但是并非阶梯分布的情况，照阶梯策略走法在第一次遇到坏人的特定一侧走还是有可能再次遇到坏人，所以还是有种情况下n等于4？

圣堂刺客 · 发表于 2024-7-20 23:36

本帖最后由圣堂刺客于 2024-7-20 23:42 编辑

答案还是很好理解，就是想不到，这种题是真的好题，其实也不叫想不到，是容易陷入自我的思维陷阱（比如二分法），并且对此深信不疑，而不去考虑更好的策略。

今井莉莎 · 发表于 2024-7-20 23:38

提示: 作者被禁止或删除内容自动屏蔽

BRRM · 发表于 2024-7-20 23:47

本帖最后由 BRRM 于 2024-7-20 23:56 编辑

如果坏人是零散分布的，那你有很大概率用很少的步数走出去：（不一定是最少的步数）
1、随便选取一个格子向下走，碰到第一个坏人
2、向左或者右走到尽头，碰到第二个坏人
3、绕过第二个坏人走出去

这种方法最怕的就是阶梯状的排布，所以这道题的本质是在问碰到阶梯排布的坏人，有没有一种稳定的方法能用固定的步数走出去。

52楼的答案的第二种情况就是教你如何推理当前排布是否是阶梯状，如果不是，那你可以轻松地绕出去，如果是，那你总能找到一个出口出去。

黄色全都是可推理的，不需要支付任何代价的，但如果你遇到了蓝色，那你下一轮就能立即绕出去。

Hydro · 发表于 2024-7-20 23:49

cjtk 发表于 2024-7-20 23:20
只走x，别走？的地方

i see, 与其说是罐子不如说是"炸弹不会击中同一个地方两次（真的不会击中两次）"或"兔子与猎犬"

gm有n列和n-1个用于防守的子，但绕过防线的最小尝试数始终是3
一旦一列上已经存在过用于防守的子，这一列就变成了gm的死区，罐子模型假设gm不会让pl越过防线（只能从一侧突破的对角线阵型），而关键在右下角的下法（假设对角线防御棋子在i，而攻击i+1的位置）
pl一旦采取这种策略，gm要么弃子放过保持对角线（僵持），要么棋子真的在i+1，后者会导致对角线阵型不成立，被直接绕过
实际的博弈只存在在3列之间

濡鸦之羽_ · 发表于 2024-7-20 23:55

看完题目以后惊奇于这特工试错居然没有惩罚，后来发现原来是憨豆不是邦德

天下何人 · 发表于 2024-7-21 00:05

本帖最后由天下何人于 2024-7-21 00:07 编辑

骷髅兵发表于 2024-7-20 22:54
你画一下就知道，刚好一个45度斜线上随机缺一个口子，哪有什么斜率不同，相当于你从上方发射粒子碰撞一堵 ...

2024行，去掉一头一尾两行安全行是2022行，2023列，列比行多1，你告诉我怎么45度角从头连到尾

zorya · 发表于 2024-7-21 00:26

今井莉莎发表于 2024-7-20 22:58
公布答案吧，答案就是3次，其实6楼的哥们已经画图做出来这题的一半了，采取如下策略，从第1行的最右边开始 ...

你这个策略是有点问题的。
1，2两种情况没问题。
第3种情况你在中间碰到坏人还需要两次才能保证走对，所以最低次数是不超过4次。
官方的策略倒是没问题。

骷髅兵 · 发表于 2024-7-21 00:45

天下何人发表于 2024-7-21 00:05
2024行，去掉一头一尾两行安全行是2022行，2023列，列比行多1，你告诉我怎么45度角从头连到尾 ...

噢，是我眼力不好，没看清，两段45度斜线是会错开一个格子

，但斜线不完整的随机排列情况也会有，阶梯走法撞到时有可能得多花几步判断，小学数学估计搞不定吧。

		自动登录	找回密码
密码			立即注册

[读书] 来考验坛友们的数学水平了（答案已公布在52楼，71楼补充了图）

本帖子中包含更多资源

评分

本帖子中包含更多资源

今井莉莎今井莉莎当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2022-4-11 头像被屏蔽	楼主\| 发表于 2024-7-20 22:58 来自手机 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

今井莉莎今井莉莎当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2022-4-11 头像被屏蔽	楼主\| 发表于 2024-7-20 23:10 来自手机 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

今井莉莎今井莉莎当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2022-4-11 头像被屏蔽	楼主\| 发表于 2024-7-20 23:15 来自手机 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

今井莉莎今井莉莎当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2022-4-11 头像被屏蔽	楼主\| 发表于 2024-7-20 23:28 来自手机 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

今井莉莎今井莉莎当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2022-4-11 头像被屏蔽	楼主\| 发表于 2024-7-20 23:38 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报