解決遞歸序列

最近我一直在解決谷歌Foobar的一些挑戰，爲了好玩，現在我已經被困在其中一個超過4天了。它是關於定義如下遞歸函數：解決遞歸序列

R(0) = 1 
R(1) = 1 
R(2) = 2 
R(2n) = R(n) + R(n + 1) + n (for n > 1) 
R(2n + 1) = R(n - 1) + R(n) + 1 (for n >= 1)

的挑戰是寫一個函數answer(str_S)其中str_S是一個整數S，它返回最大n使得R(n) = S的底數爲10的字符串表示。如果沒有這樣的n，則返回「無」。另外，S將是一個不大於10^25的正整數。

我已經調查了很多關於遞歸函數和關於解決遞歸關係，但沒有運氣。我輸出了前500個號碼，我發現每個號碼都沒有關係。我使用下面的代碼，它使用遞歸，所以當數字開始變大時它變得非常慢。

def getNumberOfZombits(time): 
    if time == 0 or time == 1: 
     return 1 

    elif time == 2: 
     return 2 

    else: 
     if time % 2 == 0: 
      newTime = time/2 
      return getNumberOfZombits(newTime) + getNumberOfZombits(newTime+1) + newTime 

     else: 
      newTime = time/2 # integer, so rounds down 
      return getNumberOfZombits(newTime-1) + getNumberOfZombits(newTime) + 1

所面臨的挑戰還包括一些測試用例所以，在這裏，他們是：

Test cases 
========== 

Inputs: 
    (string) str_S = "7" 
Output: 
    (string) "4" 

Inputs: 
    (string) str_S = "100" 
Output: 
    (string) "None"

我不知道如果我需要解決的遞推關係到任何東西簡單，但因爲有一個甚至一個用於奇數，我覺得很難做到（我還沒有在學校中瞭解到它，所以我對這個主題的所有知識都來自互聯網文章）。

所以，在所有指導我完成這個挑戰任何幫助將受到歡迎:)

來源

2014-12-04 Gonçalo Santos

我認爲你必須知道一些先進的數學和使用快速矩陣求冪。 – 2014-12-04 19:49:41

這可能有助於：http://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python – 2014-12-04 21:14:39

@LambdaFairy也許就是這樣吧！我認爲這不會有太大的區別，但事實證明，這要比以前快得多！謝謝！我現在試着用它來實現它，我會告訴你它是否做到了這一點：D – 2014-12-04 22:12:27

，而不是試圖用數學簡化這個功能，我簡化了Python中的算法。正如@LambdaFairy所建議的那樣，我在getNumberOfZombits（time）函數中實現了記憶。此優化加快了功能很多。

然後，我轉到下一步，嘗試看看這個兔子的輸入是什麼。我之前通過觀察它的情節分析了函數，並且我知道偶數數字先得到更高的輸出，並且在奇數達到相同的水平之後纔得到更高的輸出。由於我們需要輸出的最高輸入，所以我首先需要在偶數中搜索，然後在奇數中搜索。如你所見，奇數總是比偶數獲得更多的時間才能達到相同的輸出。 Plot of the function

問題是我們無法搜索每次增加1的數字（它太慢了）。我做了什麼來解決這個問題就是實現一個類似二進制搜索的算法。首先，我將搜索偶數（使用二進制搜索算法），直到找到一個答案或者我沒有更多數字搜索。然後，我對奇數進行了同樣的處理（再次使用二進制搜索算法），如果找到了答案，我用它替換了以前的任何答案（因爲它必然比前一個答案更大）。

我有我用來解決這個源代碼，所以如果有人需要它，我不介意分享吧:)

來源

2015-01-03 22:17:27

解決這一難題的關鍵是使用二進制搜索。從序列發生器可以看到，它們依賴於大致n/2的遞歸，因此計算R（N）需要大約2 * log2（N）遞歸調用;當然，你需要爲奇數和偶數做到這一點。

這不算太壞，但你需要弄清楚哪裏可以找到能夠給你輸入的N。爲了做到這一點，我首先實現了對N的上下界的搜索。我用2的冪乘上N，直到我有N和2N分別爲每個序列（奇數和偶數）形成下限和上限。

有了這些界限，我就可以在它們之間進行二分搜索，快速找到N的值，或者它的不存在。

來源

2015-10-04 10:19:35 Sean

解決遞歸序列

回答

相關問題