Define a function F(x).
If x=1, then F(x)=1.
If x is even, then F(x)=F(x/2).
For all other cases, F(x)=F(x−1)+F(x+1).
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input consists of only one line containing a positive integer x (1 ≤ x ≤ 2,000,000). | The output consists of only one line containing a positive integer F(x). |
| 6 | 2 |
Thought Process
You can write a recursive function for this problem. The termination condition is when N=1, return N, then write the conditions for even and odd numbers. Finally, call the recursive function with N and print the result using cout.
Sample Code－ZeroJudge E357: Recursion Practice
#include <iostream>
using namespace std;
int calc (int N)
{
if (N == 1) return 1;
if (N % 2 == 0) return calc(N/2);
else return calc(N-1)+calc(N+1);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
cout << calc(N) << endl;
}
//ZeroJudge E357
//Dr. SeanXD