我需要计算从原点到点 (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);}}
2 回答
慕容3067478
TA贡献1773条经验 获得超3个赞
private static boolean isPossibleOrigin(int x, int y, int n, int pasi) {
return x >= 0 && y >= 0 && pasi < 2 * n && (x+y)/2<2*n-pasi;
}
public static int calcul(int x, int y, int n) {
if (x == n && y == 0 ) {
return 1;
} else if (isPossibleOrigin(x, y, n, 0)) {
return
right(x+1, y, n,1)
+ up(x, y+1, n, 1)
+ leftup(x-1, y+1, n, 1)
+ rightdown(x+1, y-1, n, 1)
+ rightup(x+1, y+1, n, 1);
}
return 0;
}
public static int right(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x+1, y, n, pasi + 1)
+ leftup(x-1, y+1, n, pasi+1)
+ rightdown(x+1, y-1, n, pasi+1)
+ rightup(x+1, y+1, n,pasi+ 1);
}
return 0;
}
public static int leftup(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x+1, y, n, pasi + 1)
+ leftup(x-1, y+1, n, pasi + 1)
+ up(x,y+1,n,pasi+1)
+ rightup(x+1, y+1, n,pasi+ 1);
}
return 0;
}
public static int rightup(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x+1, y, n, pasi + 1)
+ leftup(x-1, y+1, n, pasi + 1)
+rightdown(x+1, y-1, n, pasi+1)
+ rightup(x+1, y+1, n,pasi+ 1);
}
return 0;
}
public static int up(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
+up(x, y+1, n, pasi+1)
+ leftup(x-1, y+1, n, pasi + 1)
+rightdown(x+1, y-1, n, pasi+1)
;
}
return 0;
}
public static int rightdown(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x+1, y, n, pasi + 1)
+rightdown(x+1, y-1, n, pasi+1)
+ up(x,y+1,n,pasi+1)
+ rightup(x+1, y+1, n, pasi + 1);
}
return 0;
}
public static void main(String[] args) {
System.out.println("Paths:"+calcul(0, 0, 1));
}
我认为“？” 可以用“(x+y)/2<2*n-pasi”代替吗？
慕姐4208626
TA贡献1852条经验 获得超7个赞
通常，此类问题可以通过纯递归解决，而无需static变量。只需计算每个可能的延续的路径数。在给定的约束下到达所需的目的地后，将完整路径的数量增加 1 ( return 1;)，否则通过返回 0 来中断递归。
private static boolean isPossibleOrigin(int x, int y, int n, int pasi) {
return x >= 0 && y >= 0 && pasi < 2 * n && ?;
}
public static int calcul(int x, int y, int n) {
if (x == n && y == 0 && n == 0) {
return 1;
} else if (isPossibleOrigin(x, y, n, 0)) {
return
right(x, y, n, 1)
+ up(x, y, n, 1)
+ leftup(x, y, n, 1)
+ rightdown(x, y, n, 1)
+ rightup(x, y, n, 1);
}
return 0;
}
为每个可能的方向写一个类似的方法，考虑到它的合法延续。
public static int right(int x, int y, int n, int pasi) {
x = x+1;
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x, y, n, pasi + 1)
+ leftup(x, y, n, pasi + 1)
+ rightdown(x, y, n, pasi + 1)
+ rightup(x, y, n, pasi + 1);
}
return 0;
}
...
最后，考虑到当节点到目的地的距离大于剩余移动次数时，访问节点不会产生完整路径，您可以显着提高性能。我在现场留下了一个问号，这是您添加适当条件来检查这一点的好地方。
添加回答
举报
0/150
提交
取消