计算板上最短路径的数量

Question

我正在尝试创建一个程序来查找 nxn 板上的最短路径数。这应该使用二叉树递归。它需要两个数字来表示棋盘上某个方块的位置，以及 returns 指定方块与左上角之间不同的最短路径的数量。而且你只能上下左右移动。

  0 1 2 3 4 5 6 7 8 
0 . . . . . . . . .
1 . . . . . . . . .
2 . . . . . . . . .
3 . . . . . . . . .
4 . . . . . . x . .
5 . . . . . . . . .
6 . . . . . . . . .

在这种情况下，x 位于第 4 行第 6 列。程序应计算最短路径的数量。显然，如果 x 在一条边上，那么只有一条最短路径。

(check-expect (shortest 0 0) 0)
(check-expect (shortest 0 1) 1) 
(check-expect (shortest 1 0) 1) 
(check-expect (shortest 1 1) 2) 
(check-expect (shortest 1 2) 3) 
(check-expect (shortest 2 1) 3) 
(check-expect (shortest 2 2) 6) 
(check-expect (shortest 2 3) 10) 
(check-expect (shortest 2 7) 36) 
(check-expect (shortest 6 5) 462)

我相信我真的很接近，但在其他情况下我遇到了问题：

(define (shortest x y)
  (cond
    [(= x y 0) 0]
    [(or (zero? y) (zero? x)) 1]
    [else (+ 1 (shortest (sub1 x) y)
               (shortest x (sub1 y)))]))

我以为 else 中会有一个 if 语句，但我不确定要测试什么。

在 ISL+ 中，这不应该有任何助手、lambda、局部变量等。任何帮助都会很棒。

Answer 1

据我所知，如果您将第 4 行从

更改为

 [else (+ 1 (shortest (sub1 x) y)

到

 [else (+ (shortest (sub1 x) y)

该功能应按要求运行。所以...

(define (shortest x y)
  (cond
    [(= x y 0) 0]
    [(or (zero? y) (zero? x)) 1]
    [else (+ (shortest (sub1 x) y)
             (shortest x (sub1 y)))]))

else 中不需要 ifs。

计算板上最短路径的数量

Count number of shortest paths on a board

scheme

racket