Как пройти M * N сетку в KDB - PullRequest
Новая
       40

Как пройти M * N сетку в KDB

0 голосов
/ 30 января 2019

Как пройти сетку m * n в Qlang, вы можете перемещаться вверх, вниз или по диагонали.чтобы узнать, сколько возможных путей достижения конечной точки.

Как показано ниже: 

                  0
                  |
           ------- ------
          |       |       |
      ( 0 1)    (1 1)         (1 0) 
         |         .          |
   ------ -----            ------ -----
  |            |   .      |            |
( 0 1)        (1 0)       ( 1 1)        (2 0)   
.... 
(2 2)        .....................   (2 2)

1 Ответ

0 голосов
/ 31 января 2019

Один из способов сделать это с помощью .z.s для рекурсивного вызова начальной функции с разными аргументами и суммированием для получения общего числа путей. 

f:{
  // When you reach a wall, there is only one way to corner so return valid path
  if[any 1=(x;y);:1];
  // Otherwise spawn 3 paths - one up, one right and one diagonally
  :.z.s[x-1;y] + .z.s[x;y-1] + .z.s[x-1;y-1] 
}

q)f[2;2]
3
q)f[2;3]
5
q)f[3;3]
13

Если вы путешествуете по краям, а не по квадратамвы можете изменить первую строку на: 

if[any 0=(x;y);:1];

Решение в закрытой форме - это просто найти Delannoy Number , который может быть реализован примерно так, когда вы путешествуете по краям. 

d:{
  k:1+min(x;y);
  f:{prd 1+til x};
  comb:{[f;m;n] f[m] div f[n]*f[m-n]}[f];
  (sum/) (2 xexp til k) * prd (x;y) comb/:\: til k
 }

q)d[3;3]
63f

Это намного быстрее для больших плат, так как я думаю, что сложность первого решения O (3 ^ m + n), в то время как сложность второго O (m * n) 

q)\t f[7;7]
13
q)\t f[10;10]
1924
q)\t d[7;7]
0
q)\t d[100;100]
1
...