我以错误的方式解决了 Project Euler #15。为什么这样做？

Question

# 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

这解决了问题，尽管我的电脑花了一个多小时。我手工制作了一个 3x3 网格，作为在生产中检查解决方案的一种方式。

事后研究，我发现了这个二项式系数：

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

但即使研究了一个小时如何计算这些，我仍然不知道如何手动计算，更不用说通过 Ruby。

Answer 1

我刚才在 Ruby 解决了这个问题。

我不知道它是如何工作的，但它给出了正确的答案。

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

Answer 2

n个事物长度r的重复组合次数等于(n + r - 1; r)。请参阅 this website（标题为 "Combinations with Repetition" 的部分）了解原因。

在你的代码中，r和n是一样的，所以你可以把这个写成(2n - 1; n)，也就是a.repeated_combination(a.length).to_a.lengthreturns。在这种特殊情况下，将此值乘以 2 得到 (2n; n)（因为对于所有整数 x，(2x - 1; x) * 2 等于 (2x; x)），这是正确答案。

Answer 3

@Brad 是对的（或几乎是对的——不确定）。这就是为什么。对于 nxn 网格（即 n 行和 n 列），从左上角到右下角的每条路径都有 n-1 向下移动和 n-1 向右移动。此类路径的数量等于 select 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”网格。我希望这种解释上的差异也解释了为什么 Brad 的答案对应于我的 n=21 案例。

我以错误的方式解决了 Project Euler #15。为什么这样做？

I solved Project Euler #15 the wrong way. Why did this work?

ruby

binomial-coefficients