从原点到点的路径数

Question

我需要计算从原点到点 (n,0) 的路径数，其中 n>0 并且移动次数必须恰好为 2*n。我只能移动

(x + 1, y) [→], (x, y + 1) [↑],(x - 1, y + 1) [-], (x + 1, y - 1) [&], or ( x + 1, y + 1) [%]。

限制是：

[-] 和 [&] 从不以任何顺序直接相邻。

[↑] 和 [→] 从不以任何顺序直接相邻。

[↑] 和 [%] 从不以任何顺序直接相邻。

程序需要显示所有的移动（x>0 & y>0）。示例：对于 n = 7,(7) = 416449 我无法让它显示正确答案。

    package algo;

public class Test {

static int k = 0;

public static int calcul(int x, int y, int n, int pasi, int p, int[] num) {

    if (x ==n && y == 0 && pasi == 2 * n ) {

        {

            for(int i=1;i<=2*n;i++)

                System.out.print(num[i]);

            System.out.println(" ");

            k = k + 1;

        }

    } else if (pasi < 2 * n && x >= 0 && y >= 0) {

        if (num[pasi] != 2) {

            num[pasi + 1] = 1;

            calcul(x + 1, y, n, pasi + 1, 1, num);

        }

        if (num[pasi] != 1 && num[pasi] != 6) {

            num[pasi + 1] = 2;

            calcul(x, y + 1, n, pasi + 1, 2, num);

        }

        if (num[pasi] != 5) {

            num[pasi + 1] = 4;

            calcul(x - 1, y + 1, n, pasi + 1, 4, num);

        }

        if (num[pasi] != 4) {

            num[pasi + 1] = 5;

            calcul(x + 1, y - 1, n, pasi + 1, 5, num);

        }

        if (num[pasi] != 2) {

            num[pasi + 1] = 6;

            calcul(x + 1, y + 1, n, pasi + 1, 6, num);

        }

    }

    return k;

}

public static void main(String[] args) {

    int n = 3;

    int[] num = new int[n * 2 + 1];

    int q = calcul(0, 0, 2, 0, 0, num);

    System.out.println("paths:" + q);

}

}

Answer 1

private static boolean isPossibleOrigin(int x, int y, int n, int pasi) {&nbsp; &nbsp; return x >= 0 && y >= 0 && pasi < 2 * n && (x+y)/2<2*n-pasi;}public static int calcul(int x, int y, int n) {&nbsp; &nbsp; if (x == n && y == 0 ) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else if (isPossibleOrigin(x, y, n, 0)) {&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right(x+1, y, n,1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + up(x, y+1, n, 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + leftup(x-1, y+1, n, 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightdown(x+1, y-1, n, 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightup(x+1, y+1, n, 1);&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}public static int right(int x, int y, int n, int pasi) {&nbsp; &nbsp; if (x == n && y == 0 && pasi == 2 * n) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else if (isPossibleOrigin(x, y, n, pasi)) {&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right(x+1, y, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + leftup(x-1, y+1, n, pasi+1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightdown(x+1, y-1, n, pasi+1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightup(x+1, y+1, n,pasi+ 1);&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}public static int leftup(int x, int y, int n, int pasi) {&nbsp; &nbsp; if (x == n && y == 0 && pasi == 2 * n) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else if (isPossibleOrigin(x, y, n, pasi)) {&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right(x+1, y, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + leftup(x-1, y+1, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + up(x,y+1,n,pasi+1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightup(x+1, y+1, n,pasi+ 1);&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}public static int rightup(int x, int y, int n, int pasi) {&nbsp; &nbsp; if (x == n && y == 0 && pasi == 2 * n) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else if (isPossibleOrigin(x, y, n, pasi)) {&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right(x+1, y, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + leftup(x-1, y+1, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; +rightdown(x+1, y-1, n, pasi+1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightup(x+1, y+1, n,pasi+ 1);&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}public static int up(int x, int y, int n, int pasi) {&nbsp; &nbsp; if (x == n && y == 0 && pasi == 2 * n) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else if (isPossibleOrigin(x, y, n, pasi)) {&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; +up(x, y+1, n, pasi+1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + leftup(x-1, y+1, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+rightdown(x+1, y-1, n, pasi+1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ;&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}public static int rightdown(int x, int y, int n, int pasi) {&nbsp; &nbsp; if (x == n && y == 0 && pasi == 2 * n) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else if (isPossibleOrigin(x, y, n, pasi)) {&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right(x+1, y, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+rightdown(x+1, y-1, n, pasi+1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + up(x,y+1,n,pasi+1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightup(x+1, y+1, n, pasi + 1);&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}public static void main(String[] args) {System.out.println("Paths:"+calcul(0, 0, 1));}我认为“？” 可以用“(x+y)/2<2*n-pasi”代替吗？

Answer 2

通常，此类问题可以通过纯递归解决，而无需static变量。只需计算每个可能的延续的路径数。在给定的约束下到达所需的目的地后，将完整路径的数量增加 1 ( return 1;)，否则通过返回 0 来中断递归。private static boolean isPossibleOrigin(int x, int y, int n, int pasi) {&nbsp; &nbsp; return x >= 0 && y >= 0 && pasi < 2 * n && ?;}public static int calcul(int x, int y, int n) {&nbsp; &nbsp; if (x == n && y == 0 && n == 0) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else if (isPossibleOrigin(x, y, n, 0)) {&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right(x, y, n, 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + up(x, y, n, 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + leftup(x, y, n, 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightdown(x, y, n, 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightup(x, y, n, 1);&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}为每个可能的方向写一个类似的方法，考虑到它的合法延续。public static int right(int x, int y, int n, int pasi) {&nbsp; &nbsp; x = x+1;&nbsp; &nbsp; if (x == n && y == 0 && pasi == 2 * n) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else if (isPossibleOrigin(x, y, n, pasi)) {&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right(x, y, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + leftup(x, y, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightdown(x, y, n, pasi + 1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + rightup(x, y, n, pasi + 1);&nbsp; &nbsp; }&nbsp; &nbsp; return 0;}...最后，考虑到当节点到目的地的距离大于剩余移动次数时，访问节点不会产生完整路径，您可以显着提高性能。我在现场留下了一个问号，这是您添加适当条件来检查这一点的好地方。