有一个岛，用方阵nxn表示。
岛上的一个人站在任何给定的坐标 (x,y) 上。他可以在岛上向右、向左、向上、向下一步向任何方向移动。如果他走出岛，他就会死。
让岛屿表示为 (0,0) 到 (n-1,n-1)（即 nxn 矩阵），并且人站在给定的坐标 (x,y) 处。他被允许在岛上移动 n 步（沿着矩阵）。他在岛上走了 n 步后死亡的概率是多少？
使用编程技术找到概率的方法应该是什么？
我有一个数学方法，但我不知道它是否正确。这里是：
结果的总数是n^n。要计算可能导致该人死亡的结果数量：
对于四个方向中的每一个，检查多少步可以导致他走出矩阵。然后，应用高中概率公式。例如，假设他可以采取的总步数是 5；(x, y) = (2,1) [索引从 0 开始]。因此，他需要在北目录中采取 3 步。掉出岛。将它们保持在一个组中：（NNN）并将其他 2 个步骤作为 4 个选择中的任何一个，我们有公式：4*4*3。同样，对于其他 3 个方向。最后，概率=（计算出的死亡结果之和）/（总结果）
这是一个谷歌面试问题。
TL;DR：递归。（或者“数学归纳法”，如果你很势利的话。）
（在下文中，“he is dead after he walks non the island”被假定为“他在少于或等于n步数后死亡”。如果您将其理解为“他在恰好有n步数后死亡”，答案将是略有不同。我将在最后简要讨论。）
我们有一个矩阵，其中每个单元格中的值表示如果我们从该单元格开始逐步NxN死亡的概率。n
考虑逐步死亡的概率0。显然，这0.0适用于岛内的每个位置，以及岛外的1.0任何地方。
逐步死亡的概率是1多少？你有四个方向可以移动，概率相等。所以对于每个细胞，你取它的四个邻居，找出它们逐步死亡的概率0，然后将它们平均在一起。（如果一个邻居在矩阵之外，你认为它的概率是1.0。）
类似地，k从给定单元开始逐步死亡的概率是k-1从其相邻单元开始逐步死亡的概率的平均值。
Python代码：
from itertools import product as prod
def prob_death(island_size, steps):
if island_size < 1 or steps < 0: raise ValueError
new_prob = [[0. for i in range(island_size)] for j in range(island_size)]
if steps == 0:
return new_prob
old_prob = prob_death(island_size, steps - 1)
directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
for (i, j, direction) in prod(range(island_size), range(island_size), directions):
neighbor_i = i + direction[0]
neighbor_j = j + direction[1]
if neighbor_i >= 0 and neighbor_i < island_size and \
neighbor_j >= 0 and neighbor_j < island_size:
prob_death_this_way = old_prob[neighbor_i][neighbor_j]
else: # neighbor is outside the island
prob_death_this_way = 1.
new_prob[i][j] += 0.25* prob_death_this_way
return new_prob
现在，让我们测试一下：（mpr只是一个很好地打印矩阵的函数）
>>> mpr(prob_death(5, 0))
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
不出所料：如果你从岛内开始，你不能在 0 步内死亡。
>>> mpr(prob_death(5,1))
0.500000 0.250000 0.250000 0.250000 0.500000
0.250000 0.000000 0.000000 0.000000 0.250000
0.250000 0.000000 0.000000 0.000000 0.250000
0.250000 0.000000 0.000000 0.000000 0.250000
0.500000 0.250000 0.250000 0.250000 0.500000
这是我们所期望的。如果您从角落牢房开始，您有0.5可能在 1 步内死亡：您的 4 个邻居中有 2 个在岛外。如果你从边缘开始，只有 1 个邻居在外面，所以你的死亡概率是0.25。在其他任何地方，所有邻居都在岛内，因此在 1 步内死亡的概率为0.0。
>>> mpr(prob_death(5, 5))
0.806641 0.666016 0.622070 0.666016 0.806641
0.666016 0.437500 0.349609 0.437500 0.666016
0.622070 0.349609 0.261719 0.349609 0.622070
0.666016 0.437500 0.349609 0.437500 0.666016
0.806641 0.666016 0.622070 0.666016 0.806641
5 个步骤中死亡的概率。我无法验证确切的值，但它看起来是正确的：角落的死亡概率最高，边缘略低，并且向内稳步下降。
这解决了在少于或等于n步骤中死亡的问题。
现在，要找到精确 n步数中的死亡概率： 让在小于或等于n从 开始的步数内死亡的概率(x,y)记为P(x,y,n)。那么在精确n步骤中死亡的概率是存活n-1步骤的概率乘以在n第 th 步骤中死亡的概率，假设我们存活了n-1步骤：(1-P(x,y,n-1))*(P(x,y,n) - P(x,y,n-1))。（我不太确定这个公式；如果我错了，请纠正我。）
首先，从第 0 步中出现在平方 (x, y) 中的概率的矩阵开始。让我们用一个 4x4 矩阵来模拟它。假设这个人从 (1, 2) 开始：
After 0 steps:
0.00% 0.00% 0.00% 0.00%
0.00% 0.00% 100.00% 0.00%
0.00% 0.00% 0.00% 0.00%
0.00% 0.00% 0.00% 0.00%
outside: 0.00%
----
After 1 steps:
0.00% 0.00% 25.00% 0.00%
0.00% 25.00% 0.00% 25.00%
0.00% 0.00% 25.00% 0.00%
0.00% 0.00% 0.00% 0.00%
outside: 0.00%
----
After 2 steps:
0.00% 12.50% 0.00% 12.50%
6.25% 0.00% 25.00% 0.00%
0.00% 12.50% 0.00% 12.50%
0.00% 0.00% 6.25% 0.00%
outside: 12.50%
----
After 3 steps:
4.69% 0.00% 12.50% 0.00%
0.00% 14.06% 0.00% 12.50%
4.69% 0.00% 14.06% 0.00%
0.00% 4.69% 0.00% 4.69%
outside: 28.12%
----
After 4 steps:
0.00% 7.81% 0.00% 6.25%
5.86% 0.00% 13.28% 0.00%
0.00% 9.38% 0.00% 7.81%
2.34% 0.00% 5.86% 0.00%
outside: 41.41%
----
这是一个计算这个的python程序：
class Table:
def __init__(self, n, outside=0):
self.T = [[0]*n for i in xrange(n)]
self.outside = outside
def add(self, i, j, value):
n = len(self.T)
if 0<=i<n and 0<=j<n:
self.T[i][j] += value
else:
self.outside += value
def make_next(self):
n = len(self.T)
Q = Table(n, self.outside)
for i in xrange(n):
for j in xrange(n):
value = self.T[i][j] / 4.0
Q.add(i-1, j, value)
Q.add(i+1, j, value)
Q.add(i, j-1, value)
Q.add(i, j+1, value)
return Q
def __repr__(self):
return '\n'.join(' '.join(
'{:6.2f}%'.format(item*100)
for item in line)
for line in self.T) + \
'\noutside: {}'.format('{:6.2f}%'.format(self.outside*100))
N = 4
T = Table(N)
T.add(1, 2, 1)
for k in xrange(N+1):
print 'After {} steps:'.format(k)
print T
print '----'
T = T.make_next()
这是一个非常复杂和细致入微的问题——我怀疑面试官的目标不是听到你想出答案，而是看你如何解决问题。
问题变成了一个边上有n 个方格的棋盘，一个棋子显然是随机放置的，它必须移动n 个空格，每转一圈都在一个明显随机的基本方向上移动。因此，棋子离开棋盘的概率不仅与棋盘的大小有关，还与棋子的位置有关。由于任何离开棋盘的动作也算作离开棋盘，因此棋子所走的路径也是相关的。
对于 2×2 网格，棋子有 2/7 的概率留在棋盘上（四个路径留在棋盘上，总共 14 个路径，与四个可能的起点中的哪一个无关）。
对于 3×3 网格，如果棋子从角落开始，则棋子有 2/11 的概率留在棋盘上（16 条路径留在棋盘上，总共 88 条路径）。如果它从一侧开始，它有 3/11 的概率（24 条路径保持打开）。如果它从中心开始，它有 9/22 的概率（36 条路径保持打开）。由于棋子有 4/9 的概率从角或边开始，1/9 的概率从中心开始，它留在棋盘上的总概率是 (2/11 + 3/11) × 4/9 + 9/22 × 1/9 = 0.247。
4×4 网格变得（显然）更加复杂，但可能值得注意的是网格确实符合一种模式：
2×2：
- - 1 - -
- 2 - 2 -
1 - 2 - 1
- 2 - 2 -
- - 1 - -
3×3：
- - - 1 - - -
- - 3 - 3 - -
- 3 - 9 - 3 -
1 - 9 - 9 - 1
- 3 - 9 - 3 -
- - 3 - 3 - -
- - - 1 - - -
我从 4×4 网格开始，但不，谢谢。起始广场似乎有 36 条通往它的路径，实际上识别它们是很乏味的。在任何情况下，棋子都从图案的中心开始，我们可以根据需要绘制棋盘。
然而，显然有一个模式，它相当大声地表明存在数学对称性，但我既没有时间也没有耐心去解决它。每个极点都有一条路径，下一组端点有n条路径，下一组似乎有n 2条路径。我怀疑我在计算 4×4 网格的最里面的一组端点时犯了一个错误，但如果我没有， 36 = n(n - 1) 2，这强烈暗示了环的模式。
无论如何，正如我所说，这个问题非常复杂，几乎可以肯定的是，你的方法受到了评判，而不是你的回答能力。不过，这是一个有趣的练习。
方法应依赖概率公式 - 有利案例数/案例总数
给定坐标 (x,y) 和步骤 - n 用户可以采取的步骤总数 -
第 1 步 - 4 种方式 第 2 步 - 4 * 3（假设他不能后退） 第 3 步 - 4* 3^2 ... 。 ... ... nth step - 4*3^(n-1) Arthmetic Progression 将给出总步数。
Farovable 案例 - 即跨越边界 - 递归函数在所有 4 个方向上递归，并且每当矩阵边界被跨越时增加变量计数。
将两者分开以获得答案。
感谢 Anubhav C 提供了上述出色的解决方案，这对于阐明问题的解决方案非常有帮助。我认为使用 0.25 作为概率（上面提到的）可能会产生误导和错误！如果我们看一下概率#dead_cases/#total_possible_moves，结果会有所不同。
考虑以下用于查找死亡/幸存案例的代码：
def winLoss_stat(N, steps):
newStats = [[[0, 0, 0] for i in range(N)] for j in range(N)]
if steps==0:
newStats = [[[1, 0, 0] for i in range(N)] for j in range(N)]
return newStats
oldStats = winLoss_stat(N, steps-1)
for i in range(N):
for j in range(N):
for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
indX = i + d[0]
indY = j + d[1]
if indX >=0 and indX < N and indY >= 0 and indY<N:
newStats[i][j][0] += oldStats[indX][indY][0]
newStats[i][j][1] += oldStats[indX][indY][1]
newStats[i][j][2] += oldStats[indX][indY][2]
else:
newStats[i][j][1] += 1
if steps==1:
newStats[i][j][2] = 1
return newStats
(or equivalently, for one step (using dfs - recursive):
class winLoss:
def __init__(self, N):
self.win = 0
self.loss = 0
self.N = N
def winLoss(self, x, y, n):
if x < 0 or y < 0 or x >= self.N or y >= self.N:
self.loss += 1
return
if n == 0:
self.win += 1
return
self.winLoss(x - 1, y, n-1)
self.winLoss(x, y - 1, n-1)
self.winLoss(x+1, y, n-1)
self.winLoss(x, y+1, n-1)
wl = winLoss(n)
wl.winLoss(i, j, n)
for any i,j start point and n (size of square)
)
The winLoss_stat returns three values for starting point at each square i, j:
[numbers of survive cases, numbers of die cases before or at k steps, numbers of death exactly at step k]
The results are as the following for n=4 (4X4), steps=4:
0 1 2 3
0 [58, 24, 12] [93, 34, 18] [93, 34, 18] [58, 24, 12]
1 [93, 34, 18] [150, 46, 28] [150, 46, 28] [93, 34, 18]
2 [93, 34, 18] [150, 46, 28] [150, 46, 28] [93, 34, 18]
3 [58, 24, 12] [93, 34, 18] [93, 34, 18] [58, 24, 12]
This translates to the following probabilities for
1. death before or at k steps:
0 1 2 3
0 0.292683 0.267717 0.267717 0.292683
1 0.267717 0.234694 0.234694 0.267717
2 0.267717 0.234694 0.234694 0.267717
3 0.292683 0.267717 0.267717 0.292683
2. death exactly at k steps:
0 1 2 3
0 0.146341 0.141732 0.141732 0.146341
1 0.141732 0.142857 0.142857 0.141732
2 0.141732 0.142857 0.142857 0.141732
3 0.146341 0.141732 0.141732 0.146341
The results can be verified by looking at the numbers of win-loss from step 1 to 3 for n=3:
winLoss_stat(3, 1)
0 1 2
0 [2, 2, 1] [3, 1, 1] [2, 2, 1]
1 [3, 1, 1] [4, 0, 0] [3, 1, 1]
2 [2, 2, 1] [3, 1, 1] [2, 2, 1]
winLoss_stat(3, 2)
0 1 2
0 [6, 4, 2] [8, 5, 2] [6, 4, 2]
1 [8, 5, 2] [12, 4, 4] [8, 5, 2]
2 [6, 4, 2] [8, 5, 2] [6, 4, 2]
winLoss_stat(3, 3)
0 1 2
0 [16, 12, 4] [24, 13, 8] [16, 12, 4]
1 [24, 13, 8] [32, 20, 8] [24, 13, 8]
2 [16, 12, 4] [24, 13, 8] [16, 12, 4]