现有一个 m*n 的矩阵，矩阵外围一周的点的值是已知的，矩阵当中每个点的值都是上下左右四个点的平均值，请求出每个点的值。

[xlvecle]

[picasso250]

For a given point [i,j], we could write down it's expression,
v[i,j] = (v[i-1,j] + v[i+1, j] + v[i, j-1] + v[i, j+1]) / 4.
If all the 4 points' value is known, we could calculate the value of v[i,j]. This condition is the base condition, 3x3 matrix.

In general, we could write down (m-2)*(n-2) equations about all unknown points, hence we could solve that system of linear equations.

For us coder, we just need to make another matrix and solve it.

[kokdemo]

感觉就是一层层的向内收缩吧

[xlvecle]

@picasso250 谢谢，但是我用递归操作起来发现并不是是很容易实现，最后会陷入互相等待，不知道有没有什么具体的意见

[xlvecle]

@kokdemo 本身我也感觉收缩就行了，但是递归到最后出不来，该怎么搞

[miaoever]

这是在做滤波么

[ruoyu0088]

解线性方程组。

[hahastudio]

我觉得解方程逃不掉
递归的话，需要有一个真能直接算出来的点作为 trigger，才有可能带起整个栈
比如，一个 4×3 的矩阵：
1, 2, 3, 4
2, ?, ?, 4
3, 3, 3, 4

a[1][1] = a[1][2] / 2 + 7/2;
a[1][2] = a[1][1] / 2 + 5;

这两个你都无法直接算出，只能寄希望于矩阵

[xlvecle]

@hahastudio 说道点子上了，解方程逃不掉，可是目前思路不明确

[xlvecle]

@miaoever 嗯，双线性插值什么的

[kokdemo]

@xlvecle 对于m*n的矩阵
可以先确定 0，0 ；m，0；0，n；m，n四个点的值。
然后就可以求出1，0；0，1；m-1，0；m，1；1，n；0；n-1；m-1，n；n-1；m
八个点，然后继续算2，3，……
直到这一圈被连接在一起

然后继续算下个矩形

[zzutmebwd]

回去看线性代数书吧。。。忘光了

[xlvecle]

@kokdemo 周围一圈的值都是确定的，它们不是周围点的平均值，所以1,1就没法直接求出来，往里面走比较困难。

[akfish]

不就是解线性方程组嘛，根据题目条件构造系数矩阵A很容易，然后高斯消元，搞定。

[1r5b6rRCaViA78f6]

2m+2n+4个线性方程组解mn个未知数 你确定？

[1r5b6rRCaViA78f6]

额 搞错了 应该是mn个方程组 用个mn*mn的矩阵进行求逆？

[picasso250]

@xlvecle 这个不是递归，是解方程组。

[ruoyu0088]

可以用迭代法，或者用稀疏矩阵解方程，下面是程序：

http://nbviewer.ipython.org/github/ruoyu0088/openbooks/blob/master/average_matrix.ipynb

[xlvecle]

@ruoyu0088 受教了，谢谢