Re: [问题] 请问关于递回的问题(求讲解)(补图)

楼主: Violation (茶叶很苦)   2014-04-27 15:54:00
※ 引述《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)
作者: timeregorge (Nick)   2014-04-27 21:38:00
真的是感谢您的回应!!有另外一个问题想请教这边陆地的计算方式是假设四周围都是陆地,在第一个点假设往左移动一格好了,他会在移动后的那个点再一次往四周围的八个方向再次进行计数,直到碰到水为止吗?
楼主: Violation (茶叶很苦)   2014-04-27 21:49:00
是的,它会计算到直到碰到水或是遇到已经算过的地
作者: timeregorge (Nick)   2014-04-27 22:15:00
原来如此,真的非常感谢您的讲解!

Links booklink

Contact Us: admin [ a t ] ucptt.com