2

私はクリス・パインの本「プログラミングを学ぶ」を使って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 を実行している可能性があります: 2D 配列の論理形式は、最初に行で編成され、次に列で編成されます。行は y 軸、列は x 軸と考えることができます。

于 2013-05-31T02:06:03.297 に答える
1

この本でこの問題に取り組んだとき、ワールドが呼び出されたときの x & y の転置にも気付きました。Pragmatic Programmer の Web サイトを調べて、これが正誤表に記載されているかどうかを確認しましたが、記載されていません。

タイプミスだと思い、x、yに反転させました。コードはどちらの方法でも機能します。

5,5 の開始点は任意であり、配列/ワールドの「エッジ」に到達するまで、コードは x、y (または y、x) の周りの 8 つのタイルすべてをチェックするため、実際には問題ではありません。

于 2013-06-01T19:47:17.310 に答える
0

私はそれを解決した方法についてかなり汚いと感じており、ここでより良い答えを探しています。新しい変数 E = 'edge' を作成し、マップの端に接するすべての文字を E に変更しました。次に、次のコードをcontinent_size メソッドの先頭に追加しました。

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

できます。:/

于 2014-06-07T08:38:54.840 に答える
0

他の回答から数歩戻って、ここでの再帰は、continent_size内から 8 回呼び出されますcontinent_size。

そのため、このメソッドは内部で 8 回呼び出されています。

しかし ... これらの 8 つの内部メソッドはそれぞれcontinent_size、さらに 8 回呼び出します。

などなど。

理解するのはばかげていますが、理解すると、マトリックスを見ることができるように感じます. 非常に簡単ですが。

タスクの拡張ビットに関するヘルプを探しているときに、この質問に出くわしました (「エクスプローラー」の 1 つが世界の端から落ちた場合にエラーを回避する方法)。

私はレスキューでこれを解決することになりました：

# 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）より小さい場合、解決策は「x」と「y」を調整することにあることに気付きました。

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

ここでの問題は、この特定のサイズの配列で機能することです...世界が10より大きい場合、プログラムは遭遇するすべての「土地」を0としてカウントします。

ということは、半解だけということでしょうか…。

于 2016-03-22T17:48:57.053 に答える