现有一个 m*n 的矩阵，矩阵外围一周的点的值是已知的，矩阵当中每个点的值都是上下左右四个点的平均值，请求出每个点的值。
xlvecle · 2014-11-24 18:52:17 +08:00 · 3405 次点击这是一个创建于 3653 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
picasso250 2014-11-24 19:11:23 +08:00
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. |
 |
2
kokdemo 2014-11-24 19:24:22 +08:00
感觉就是一层层的向内收缩吧
|
 |
3
xlvecle OP @picasso250 谢谢，但是我用递归操作起来发现并不是是很容易实现，最后会陷入互相等待，不知道有没有什么具体的意见
|
 |
5
miaoever 2014-11-24 19:51:51 +08:00
这是在做滤波么
|
 |
6
ruoyu0088 2014-11-24 19:53:12 +08:00
解线性方程组。
|
 |
7
hahastudio 2014-11-24 20:09:25 +08:00
我觉得解方程逃不掉
递归的话，需要有一个真能直接算出来的点作为 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; 这两个你都无法直接算出，只能寄希望于矩阵 |
|
8
xlvecle OP @hahastudio 说道点子上了，解方程逃不掉，可是目前思路不明确
|
|
10
kokdemo 2014-11-24 21:08:49 +08:00
@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，…… 直到这一圈被连接在一起 然后继续算下个矩形 |
 |
11
zzutmebwd 2014-11-24 21:12:15 +08:00
回去看线性代数书吧。。。忘光了
|
 |
13
akfish 2014-11-24 22:53:25 +08:00
不就是解线性方程组嘛，根据题目条件构造系数矩阵A很容易，然后高斯消元，搞定。
|
 |
14
1r5b6rRCaViA78f6 2014-11-25 01:11:09 +08:00 via Android
2m+2n+4个线性方程组解mn个未知数 你确定？
|
|
15
1r5b6rRCaViA78f6 2014-11-25 01:19:19 +08:00 via Android
额 搞错了 应该是mn个方程组 用个mn*mn的矩阵进行求逆？
|
|
16
picasso250 2014-11-25 10:10:35 +08:00
@xlvecle 这个不是递归，是解方程组。
|
|
17
ruoyu0088 2014-11-25 15:05:25 +08:00
可以用迭代法，或者用稀疏矩阵解方程，下面是程序：
http://nbviewer.ipython.org/github/ruoyu0088/openbooks/blob/master/average_matrix.ipynb |
Select Language