遞歸查找在不斷縮小的LispList中INT的索引

這裏是計算機科學系的第二年級學生，作爲遞歸練習的一部分，我們已經給LispLists一些任意問題。我被卡住了一半，所以如果任何人都可以在沒有明確地給我答案的情況下指向正確的方向，那會很好。遞歸查找在不斷縮小的LispList中INT的索引

我需要找到在LispList listToCheck的intToFind每個實例的位置 - 唯一的條件是：

沒有額外的參數可以用來
它必須遞歸地完成

對於每個一個誰沒有遇到LispLists - 他們沒有索引，你可以叫他們的唯一方法是：

.isEmpty（）返回布爾
。頭（）第0位置返回元件
.tail（）返回不是頭部
.cons（值）增加價值， '頭' 的位置 - 換檔一切一跌

還有一個方法，我寫了以前稱：

recursiveCountLength（列表）返回傳遞的LispList的長度的整數。

我一直在測試上的名單是：[2,3,4,2,5,12,2,5]，所以我在尋找的結果是[0， 3,6] - 與出路，這裏就是我這麼遠（我後試圖解釋）：

public static LispList<Integer> 
    recursivePositions(LispList<Integer> listToCheck, int intToFind) 
{ 
    if(listToCheck.isEmpty()) return listToCheck; 
    else { 
    // go through the array in its entirety once through, 
    // do everything else 'on the way back up' 
    LispList<Integer> positions = recursivePositions(listToCheck.tail(), intToFind); 

    //get the current length and current head 
    int currentInt  = listToCheck.head(); 
    int currentLength = recursiveCountLength(listToCheck); 

    //if a match is found, add the current length of the list to the list 
    if(currentInt == intToFind) return positions.cons(currentLength); 
    else return positions; 
    } 
}

我目前的理論是，在每次遇到數組的長度是我們正在尋找的int（在這種情況下是2）從列表的原始長度（在本例中爲8）中減去將給我們索引。

第一情況與8的長度（8-8 =索引的0，因此索引現在[0]），
下爲5的長度發生（8-5 =索引3，因此索引現在[0,3]），
最後發生在長度爲2（8-2 =索引6，因此索引現在[0,3,6]）。

唯一的問題是，我不知道如何得到一個靜態'8' - 這讓我得出結論，我完全以錯誤的方式接近這一點。有人在這裏有任何提示嗎？任何幫助將非常感激。

來源

2014-10-18 PookageHayes

你寫的這個方法是有效的「一個額外的參數」，只是實現的功能，而不是深度跟蹤整數。你可以使用它嗎？你是否應該使用它？ – 2014-10-18 18:13:30

你得到一個職位列表。對於每個遞歸步驟，我都會更新這個返回的列表。這不是如何將它寫入「真正的」Lisp，而是以某種「純粹」的Lisp寫成...... – 2014-10-18 19:19:17

澄清：a LispList只是一個單鏈表（用於區分雙鏈接的Java LinkedList）。

通常情況下，您需要使用助手將信息載入遞歸調用，例如當前位置和已找到的位置（當前部分結果）。

LispList<Integer> positions (final int item, final LispList<Integer> list) { 
    return positionsAux(item, list, 0, new LispList<Integer>()); 
} 

private LispList<Integer> positionsAux (final int item, 
             final LispList<Integer> list, 
             final int position, 
             final LispList<Integer> result) { 
    if (list.isEmpty()) { 
     return result.reverse(); 
    } 
    if (list.head().intValue() == item) { 
     result = result.cons(position); 
    } 
    return positionsAux(item, list.tail(), position + 1, result); 
}

如果這不被允許，則需要將結果向後推送。如果您認爲遞歸調用返回了list.tail()的正確結果，則需要在每個找到的位置上加1以獲得list的正確結果。然後，如果當前元素匹配，則結果爲cons 0。這個版本比第一個效率低，因爲您遍歷了輸入列表中每個元素的當前結果列表（因此它是O（n＆middot; m）而不是O（n），其中n是輸入列表的長度和m結果列表的長度）。

LispList<Integer> positions (final int item, final LispList<Integer> list) { 
    if (list.isEmpty()) { 
     return new LispList<Integer>(); 
    } 
    final LispList<Integer> tailResult = positions(item, list.tail()); 
    final LispList<Integer> result = tailResult.addToEach(1); 
    if (list.head().intValue() == item) { 
     return result.cons(0); 
    } else { 
     return result; 
    } 
}

實施第二reverse()的第一個版本，並addToEach(int)就留給讀者做練習。

來源

2014-10-19 11:34:48 Svante

您至少需要3個參數。可以肯定，添加更多的參數是可以的，因爲他允許使用幫助器方法（因爲否則，你可以讓你的方法調用具有更多參數的幫助器方法）。

最簡單的方法遞歸：

public static LispList<Integer> positions(LispList<Integer> list, Integer key, Integer position){ 
    if (list.isEmpty()) return LispList.empty(); 

    if (list.head().equals(key)) return positions(list.tail(), key, position+1).cons(position); 

    return positions(list.tail(), key, position+1); 
}

來源

2014-10-19 13:18:15 TheDream

遞歸查找在不斷縮小的LispList中INT的索引

回答

相關問題