我是 Java 新手,我是否正在嘗試實作一種遞回方法來查找"n choose k"。
但是,我遇到了一個問題。
public class App {
public static void main(String[] args) throws Exception {
int n = 3;
int k = 2;
int result = combRecursion(n, k);
System.out.println(result);
}
private static int combRecursion(int n, int k) {
if (k == 0) {
return 1;
} else {
return (combRecursion(n - 1, k - 1) combRecursion(n - 1, k));
}
}
輸出: 此行的多次重復:
at App.combRecursion(App.java:14)
uj5u.com熱心網友回復:
只有當大于或等于 時,才可以k
從一組專案中挑選專案。n
n
k
您需要通過呼叫切斷沒有結果的遞回分支,combRecursion(n - 1, k)
這不會減少樣本中的專案數量。
當您需要創建遞回方法時,它應該始終包含兩個部分:
基本情況- 表示一組邊緣情況,即預先知道結果的瑣碎場景。如果遞回方法遇到基本情況(傳遞給方法的引數匹配基本情況的條件之一),遞回終止。在此任務中,基本情況將表示完全發現源串列并且位置等于其大小(無效索引)的情況。
遞回案例- 進行遞回呼叫和主要邏輯所在的解決方案的一部分。
您的遞回案例是正確的:它產生了兩個遞回執行分支(一個將“選擇”當前專案,第二個將“拒絕”它)。
但是在基本情況下,您已經錯過了上面提到的場景,我們需要解決這些情況:
n
不夠大 (k > n
),因此無法獲取k
專案。并且回傳值將是0
(或者您可能會拋出例外而不是回傳值)。k == 0
結果應該是1
(總是可以拿走0
物品,而且只有一種方法可以做到——不要選擇任何東西)。- 何時- 正如@akuzminykh指出
k == n
的那樣,只有一種方法可以構建組合。回傳值將是1
請注意,因為您的目標是熟悉遞回(我很確定您將其作為練習),所以無需在解決方案中模仿數學公式,請使用純邏輯。
以下是如何實作它:
private static int combRecursion(int n, int k) {
if (k > n) return 0; // base case - impossible to construct a combination
if (n == k || k == 0) return 1; // base case - a combination was found
// recursive case
return combRecursion(n - 1, k - 1) combRecursion(n - 1, k);
}
main()
- 演示
public static void main(String[] args) {
System.out.println(combRecursion(3, 2));
System.out.println(combRecursion(5, 2));
}
輸出
3 // pick 2 item from the set of 3 items
10 // pick 2 item from the set of 5 items
uj5u.com熱心網友回復:
您的基本案例應該包括n == k || k == 0
“n 選擇 k”才能正確實施。這樣,兩個呼叫最終都會終止(即使您當前的實作效率相當低,因為它具有指數運行時間)。更好的實作將使用公式n!/k!/(n-k)!
或乘法公式在線性時間內運行:
int factorial(int n) {
int res = 1;
for (; n > 1; n--) {
res *= n;
}
return res
}
int choose(int n, int k) {
return factorial(n)/factorial(k)/factorial(n-k);
}
進一步優化這個留給讀者練習(提示:一個 for 回圈就足夠了)。
uj5u.com熱心網友回復:
在您撰寫的遞回方法中,k
該引數將確定結束遞回的基本情況。
您的基本情況僅檢查k
s 值,并且您的右遞回呼叫不斷進行遞回呼叫,其中k
保持不變,并且其嵌套的遞回呼叫將依次執行相同的操作,無休止地產生沒有結束的右遞回呼叫。
那個遞回呼叫就是給你一個StackOverflowError
.
您應該將其重寫為:
int choose(int n, int k) {
if (k == 0) return 1;
return (n * choose(n - 1, k - 1)) / k;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/caozuo/470930.html
下一篇:函式遞回