我需要計(jì)算從原點(diǎn)到點(diǎn) (n,0) 的路徑數(shù)，其中 n>0 并且移動(dòng)次數(shù)必須恰好為 2*n。我只能移動(dòng)(x + 1, y) [→], (x, y + 1) [↑],(x - 1, y + 1) [-], (x + 1, y - 1) [&], or ( x + 1, y + 1) [%]。限制是：[-] 和 [&] 從不以任何順序直接相鄰。[↑] 和 [→] 從不以任何順序直接相鄰。[↑] 和 [%] 從不以任何順序直接相鄰。程序需要顯示所有的移動(dòng)（x>0 & y>0）。示例：對(duì)于 n = 7,(7) = 416449 我無(wú)法讓它顯示正確答案。 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貢獻(xiàn)1773條經(jīng)驗(yàn) 獲得超3個(gè)贊
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));
}
我認(rèn)為“？” 可以用“(x+y)/2<2*n-pasi”代替嗎？
慕姐4208626
TA貢獻(xiàn)1852條經(jīng)驗(yàn) 獲得超7個(gè)贊
通常，此類(lèi)問(wèn)題可以通過(guò)純遞歸解決，而無(wú)需static變量。只需計(jì)算每個(gè)可能的延續(xù)的路徑數(shù)。在給定的約束下到達(dá)所需的目的地后，將完整路徑的數(shù)量增加 1 ( return 1;)，否則通過(guò)返回 0 來(lái)中斷遞歸。
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;
}
為每個(gè)可能的方向?qū)懸粋€(gè)類(lèi)似的方法，考慮到它的合法延續(xù)。
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;
}
...
最后，考慮到當(dāng)節(jié)點(diǎn)到目的地的距離大于剩余移動(dòng)次數(shù)時(shí)，訪問(wèn)節(jié)點(diǎn)不會(huì)產(chǎn)生完整路徑，您可以顯著提高性能。我在現(xiàn)場(chǎng)留下了一個(gè)問(wèn)號(hào)，這是您添加適當(dāng)條件來(lái)檢查這一點(diǎn)的好地方。
添加回答
舉報(bào)
0/150
提交
取消