Re: [問題] 請問關於遞迴的問題(求講解)(補圖)

[Violation (茶葉很苦)]

※ 引述《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://www.ptt.cc/bbs/Ruby/M.1398585243.A.418.html
推 timeregorge:真的是感謝您的回應！！有另外一個問題想請教
→ timeregorge:這邊陸地的計算方式是假設四周圍都是陸地,在第一個點
→ timeregorge:假設往左移動一格好了,他會在移動後的那個點再一次往
→ timeregorge:四周圍的八個方向再次進行計數,直到碰到水為止嗎？
→ Violation:是的，它會計算到直到碰到水或是遇到已經算過的地
推 timeregorge:原來如此,真的非常感謝您的講解!