1 
# Starting in the top left corner of a 2×2 grid, 
# and only being able to move to the right and down, 
# there are exactly 6 routes to the bottom right corner.
# How many such routes are there through a 20×20 grid?


def lattice_paths
  a = (0..19).to_a
  puts a.repeated_combination(a.length).to_a.length * 2
end

lattice_paths

私のコンピューターには1時間以上かかりましたが、これで解決しました。実稼働環境でソリューションを確認する方法として、手動で 3x3 グリッドを作成しました。

事後調査を行ったところ、次の二項係数にたどり着きました。 

f(n)=(2n-1; n)

しかし、これらを計算する方法を 1 時間研究した後でも、Ruby ではなく、手動で計算する方法がわかりません。

4

3 に答える 3

2

@Bradの右（またはほぼ右 - わからない）。理由は次のとおりです。nxnグリッド (つまり、n行と列) の場合n、左上から右下への各パスは下n-1にn-1移動し、右に移動します。このようなパスの数は、全移動n-1から右移動 (または下移動)を選択する方法の数に等しくなります。2*(n-1)

(total moves)!/(right moves)!*(total moves - right moves)!
  #=> (total moves)!/(right moves)!**2
  #=> (2*(n-1))!/(n-1)!**2

の場合n=20、これは次のとおりです。

38!/19!**2

の場合n=21:

40!/20!**2

これは@Bradの答えです。にはn=3、次のものがあります。

4!/2!**2 #=> 6

パス。質問には、「2x2」グリッドには6つのパスがあると記載されているため、それを「3x3」グリッドと見なす必要があります.この解釈の違いは、ブラッドの答えが私のn=21ケースに対応する理由も説明していると思います.

于 2015-11-23T05:53:56.287 に答える
2

物の長さrの組み合わせの繰り返し数nは に等しい(n + r - 1; r)。理由については、この Web サイト(「組み合わせと繰り返し」というタイトルのセクション)を参照してください。

あなたのコードでrは、 は と同じなのでn、これを と書くことができます。(2n - 1; n)これがa.repeated_combination(a.length).to_a.length返されます。この値に 2 を掛ける(2n; n)と、この特定のケースで得られます (はすべての整数に対して(2x - 1; x) * 2等しいため)。これが正しい答えです。(2x; x)x

于 2015-11-23T04:10:28.640 に答える
1

少し前にRubyでこれを解決しました。

それがどのように機能するかはわかりませんが、正しい答えが得られます。

puts (1..40).inject(:*) / (1..20).inject(:*) ** 2

于 2015-11-23T03:46:07.577 に答える