2

我一直在尝试使用 Chris Pine 的《学习编程》一书来学习 Ruby。在读到第 10 章和使用的示例之前，我实际上很兴奋。现在，仅这一章和它的例子就完全消除了我继续读这本书的所有兴奋。在这个例子中，我完全不知道它是如何尝试计算瓷砖的，或者当方法是使用continent_size world, x,y 的属性定义时，为什么他使用world [y],[x]？我不确定这个例子中的递归是如何工作的。有人可以对这个例子有更多的了解吗？作者实际上试图做什么？

M = 'land'
o = 'water'

world = [
  [o,o,o,o,o,M,o,o,o,o,o],
  [o,o,o,o,M,M,o,o,o,o,o],
  [o,o,o,o,o,M,o,o,M,M,o],
  [o,o,o,M,o,M,o,o,o,M,o],
  [o,o,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,M,M,M,M,o,o,o],
  [M,M,M,M,M,M,M,M,M,M,M],
  [o,o,o,M,M,o,M,M,M,o,o],
  [o,o,o,o,o,o,M,M,o,o,o],
  [o,M,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,o,M,o,o,o,o,o]]

def continent_size world, x ,y

  if x < 0 or x > 10 or y < 0 or y > 10
    return 0
  end

  if world[y][x] != 'land'
    return 0
  end

  size = 1
  world [y][x] = 'counted land'

  size = size + continent_size(world, x-1, y-1)
  size = size + continent_size(world, x , y-1)
  size = size + continent_size(world, x+1, y-1)
  size = size + continent_size(world, x-1, y )
  size = size + continent_size(world, x+1, y )
  size = size + continent_size(world, x-1, y+1)
  size = size + continent_size(world, x , y+1)
  size = size + continent_size(world, x+1, y+1)
  size

end

puts continent_size(world, 5, 5)
4

7 回答 7

2

这称为洪水填充。它所做的是计算连接到初始起点的所有“土地”的大小。请注意，它并没有计算所有的“土地”符号，只是那些因为水而无法到达的符号。

洪水填充是一种称为深度优先搜索的形式，它是一种遍历图形（此处为离散“地图”）的方法。可以这样概括：

  1. 访问当前位置/图形节点，计数并将其标记为已访问
  2. 检查所有连接的节点（这里，任何向上、向下、向左或向右），如果它们未被访问并且它们是陆地，则递归地访问它们

他可能会做 y, x 的原因如下：二维数组的逻辑格式首先按行组织，然后按列组织。可以将行视为 y 轴，将列视为 x。

于 2013-05-31T02:06:03.297 回答
1

当我在书中解决这个问题时，我也注意到了调用 world 时 x & y 的换位。我在 Pragmatic Programmer 的网站上查看了勘误表中是否列出了该内容，但事实并非如此。

我认为这是错字并将它们翻转为x，y。无论哪种方式，代码都可以工作。

这并不重要，因为 5,5 的起点是任意的，并且代码将检查 x,y（或 y,x）周围的所有八个图块，直到它到达数组/世界的“边缘”。

于 2013-06-01T19:47:17.310 回答
0

我还注意到 Pine 代码中 x 和 y 的转置。
我认为推理可能是他安排了“世界”阵列，以便每一行都有一个子阵列。“world”后面的方括号中的第一个数字（world[0]）是指世界中元素（子数组）的索引。由于这些是垂直堆叠的，因此它是您的 y 轴。第二个括号内的数字 (world[0][5]) 指的是子数组中的元素。它们水平运行，因此第二个数字指的是您的 x 轴。编写方法以获取参数 x 然后参数 y 允许您以传统的 (x,y) 格式输入起始位置，而在方法中，变量被转置以完成任务。我认为。不过，我对此完全陌生。

此外，如果有人对此练习的扩展版本有一个干净的解决方案，其中大陆“与世界边缘接壤”，我很乐意看到它

于 2014-08-01T00:02:41.313 回答
0

当世界的顶端全是“o”时，救援方法似乎仍然失败。解决这个问题的一个简单方法是编写一个条件来检查坐标 (x,y) 是否在边界之外（即在 0 或 world.length-1 之外），如果满足该条件则返回 0。

于 2014-06-08T23:46:31.080 回答
0

我对解决它的方式感到很肮脏，我在这里寻找更好的答案。我创建了一个新变量 E = 'edge'，并将任何触及地图边缘的字符更改为 E。然后我将这段代码添加到continent_size 方法的顶部：

if world[y][x] == 'edge'
        return 1
    end

有用。：/

于 2014-06-07T08:38:54.840 回答
0

从其他答案退后几步，这里的递归是从 insidecontinent_size调用八次continent_size。

因此，该方法在其内部被调用了八次。

但是......这八个内部方法中的每一个都调用continent_size了另外八次。

等等等等。

绕开它是疯狂的，但是当你这样做时，感觉就像你可以看到黑客帝国。虽然很简短。

我偶然发现了这个问题，以寻求有关任务扩展位的帮助（如果您的“探索者”之一从世界边缘掉下，如何避免错误）。

我最终通过救援解决了这个问题：

# If it's off the edge of the world, it's as good as water
square = world[y][x] rescue 'o'

if square != 'Land'
  return 0
end

我不知道这是否是最好的方法，但对我来说似乎很优雅。

于 2013-10-31T22:19:52.917 回答
0

我也花了一些时间来理解这个例子。起初，我试图解决这样的任务：

  if ( world[y] > world[y].length  || world[x] > world[x].length ) || ( world[y] < world[y].length || world[x] < world[x].length )
    return 0 
  end

但我不断收到“数组的未定义方法”>“的错误”

然后我意识到解决方案可能是调节“x”和“y”，如果它们大于数组（10）或小于（0）：

if x > 10 || x < 0 || y > 10 || y < 0
  return 0
end

这里的问题是它适用于这种特定大小的数组......如果世界大于 10 - 程序会将它遇到的每个“土地”计为 0。

所以我想这只是半解决方案......

于 2016-03-22T17:48:57.053 回答