algorithm - 2D 平面中的点与平面原点之间的不同路径数

Question

<分区>

Answer 1

这里有新答案: 在对计算表进行分析后 - 可以找到具有某些组合的路径数。

Delphi 代码(注意对于超出 Int64 范围的大数应该使用长算术):

function PathCount(x, y, N: Integer): Int64;
var
  t, Diff: Integer;
begin
  x := Abs(x); //exploit symmetry
  y := Abs(y);

  if y > x then begin  //Swap them for simplicity, exploit symmetry again
    t := x;
    x := y;
    y := t;
  end;

  Diff := N - (x + y);
  if (Diff < 0) or Odd(Diff) then
    Exit(0);  //return 0 for unavailable points

  Diff := Diff div 2;
  Result := CombinationCount(N, x + Diff) * CombinationCount(N, Diff);
end;


function CombinationCount(n, k: Integer): Int64;
var
  i: Integer;
begin
  Result := 1;
  if k > n - k then
    k := n - k;
  for i := 1 to k do
    Result := (Result * (n - i + 1)) div i;
end;

---

旧答案(用于演示)

对于合理的 N，可以使用动态规划。制作具有限制的 3d 数组 (-N/2..N/2),(-N/2..N/2),(0..N)。请记住，它的大小是 N^3(10^21 表示 1000 万个点，不切实际)。您可以利用对称性，但缩减因子仅为小常量(2 或 4)。

递归公式:

P(p, q, K) = P(p-1, q, K-1) + P(p+1, q, K-1) + P(p, q-1, K-1) + P(p, q+1, K-1)

逐层填充数组:第一步使 P(x-1,y0,1) = 1(再增加 3 个点)，依此类推... 0、1、2步后初始点的邻域:

                  0 0 1 0 0
0 0 0    0 1 0   0 2 0 2 0
0 1 0    1 0 1   1 0 4 0 1
0 0 0    0 1 0   0 2 0 2 0
                  0 0 1 0 0 

6 步动画:

完成后，P(0, 0, N) 将包含路径数。

P.S. 可能有一些组合公式。例如，我们可以在最后一条对角线 (1 2 1, 1 3 3 1, 1 4 6 4 1 ...) 中看到二项式系数 C(N,K)，下一条非零对角线包含 N * C(N, K)等等。