10696 f91

題目連結

題目翻譯

McCarthy 是電腦科學界知名的理論學家，他定義了一個遞迴函式 f91，輸入一個正整數 N，回傳一個正整數，定義如下：

• 若 N ≤ 100，則 f91(N) = f91(f91(N+11))
• 若 N ≥ 101，則 f91(N) = N - 10

請寫一個程式計算 McCarthy's f91。

輸入

輸入為一連串正整數，每個數最多 1,000,000，最多 250,000 筆測資，每個數字獨自一行。輸入以 0 結束，0 本身不需處理。

輸出

對每筆輸入依照範例格式輸出一行結果，格式為 f91(N) = 結果。

解題思路

直接照定義遞迴會因為測資量大（最多 25 萬筆）而效能不足，但這個函式其實有封閉解：

• 當 N ≤ 100 時，不論遞迴多少層，最後都會收斂到 91；
• 當 N ≥ 101 時，直接等於 N - 10。

因此只要用一個 O(1) 的條件判斷即可，不需要真的做遞迴呼叫。

程式碼

#Jackis666
while True:
    n=int(input())
    if n==0:
        break
    print("f91(",end="")
    print(n,end="")
    print(") = ",end="")
    if n<=100:
        print(91)
    else:
        print(n-10)