Background
McCarthy is a famous theorician of computer science. In his work, he defined a recursive function, called f91, that takes as input a positive integer N and returns a positive integer defined as follows:
- If N ≤ 100, then f91(N) = f91(f91(N+11));
- If N ≥ 101, then f91(N) = N-10.
The Problem
Write a program, that computes McCarthy's f91.
Input
The input tests will consist of a series of positive integers, each integer is at most 1,000,000. There will be at most 250,000 test cases. Each number is on a line on its own. The end of the input is reached when the number 0 is met. The number 0 shall not be considered as part of the test set.
Output
The program shall output each result on a line by its own, following the format given in the sample output.
Sample Input
500
91
0
Sample Output
f91(500) = 490
f91(91) = 91
解題思考
這一題並不難,直接照著題目定義,用遞迴寫也可以 AC。
不過若是仔細分析下來,其實可以發現:當 N 小於等於 100 時,f91(N) 必等於 91。
總而言之,這題其實連遞迴都不需要用,只需要一個 if 條件判別就行了。
參考解答(C++)
#include <iostream> using namespace std; int main(void) { while (1) { unsigned int n; cin >> n; if (n == 0) { break; } if (n <= 100) { // 若 n 小於 100, f91(n) 必等於 91 cout << "f91(" << n << ") = 91" << endl; } else { cout << "f91(" << n << ") = " << n - 10 << endl; } } #ifndef ONLINE_JUDGE system("pause"); #endif return 0; }
3 回覆:
這題當初寫的時候,簡單到我不知道怎麼說了XD
是沒錯
不過這題還比不上 11172 那題那麼簡單XD
若沒想到<100的都是91
就不簡單了
張貼留言