作者Violation (茶叶很苦)
看板Ruby
标题Re: [问题] 请问关於递回的问题(求讲解)(补图)
时间Sun Apr 27 15:54:00 2014
※ 引述《timeregorge (vincent)》之铭言：
: http://imgur.com/JrrL7NU
: 小弟练习一个例题
: 这个例题的目的是计算陆地的尺寸
: 但不重复计算
: 我左看右看完全不知道他到底是如何计算的
: 或是为什麽在if那边要用[y] [x] != 'land'
: 等等的
: 请问有人可以完整的帮我解释一下吗？
: 谢谢您！
这例题还蛮有趣的。
首先 contient_size 函式包含了 world, x, y 这三个参数，
表示它会读入一个地图跟一组 (x, y) 座标，之所以会需要这组座标，
是因为此函式并不是计算地图的"全部"陆地尺寸，而是计算在给定的座标上，
所存在的"相连"陆地尺寸。举例来说 contient_size(world, 5, 5) 就是计算
在 (5, 5) 座标上的相连陆地尺寸。
问题麻烦的地方就在於如何计算"相连"的陆地，这边的做法是采用递回，
最常用来介绍递回的例子就是费式数列：
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n - 1) + Fib(n - 2)
藉由把 Fib(n) 分解成 Fib(n - 1) + Fib(n - 2)，直到 n == 0 或 1 再加总起来。
计算相连的陆地的算法也是类似，假设想计算 (x, y) 座标的陆地，可以先算出周围
陆地的尺寸，再把结果跟它本身加总起来：
(x - 1, y + 1) | (x, y + 1) | (x + 1, y + 1)
-------------------------------------------------
(x - 1, y) | 0 or 1 | (x + 1, y)
-------------------------------------------------
(x - 1, y - 1) | (x - 1, y - 1) | (x + 1, y - 1)
所以下面这个判断的意思就可以理解了，在计算周围的陆地尺寸时，
如果发现输入的座标不是 'land' 时，就直接回传 0 ，表示此座标并没有相连的陆地。
if world[x][y] != 'land'
return 0
end
若为 'land' 则会先给 size = 1，表示目前座标本身为一单位的陆地，然後利用递回
去计算它相邻座标所在的相连陆地大小，最後再把结果跟 size 加总。
但递回时会发生重复计算的情况，为了避免重复计算，
在 size = 1 之後要加上 world[x][y] = 'counted land'，
表示目前座标的陆地已经被计算过，这样 if world[x][y] != 'land'
会直接回传 0 ，不再继续计算下去。
整个程式的思路大概就是这样。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.192.212.108
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Ruby/M.1398585243.A.418.html
1F：推 timeregorge:真的是感谢您的回应！！有另外一个问题想请教 04/27 21:38
2F：→ timeregorge:这边陆地的计算方式是假设四周围都是陆地,在第一个点 04/27 21:39
3F：→ timeregorge:假设往左移动一格好了,他会在移动後的那个点再一次往 04/27 21:40
4F：→ timeregorge:四周围的八个方向再次进行计数,直到碰到水为止吗？ 04/27 21:41
5F：→ Violation:是的，它会计算到直到碰到水或是遇到已经算过的地 04/27 21:49
6F：推 timeregorge:原来如此,真的非常感谢您的讲解! 04/27 22:15