fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <stack>
  4. using namespace std;
  5. // parameters
  6.  
  7. struct Call {
  8.     int n;
  9.     int a, b, c, d; // local variables
  10.     int cur_loc; // location of next statement to be executed
  11.  
  12. };
  13.  
  14. int G(int n) {
  15.     Call initial_call;
  16.     initial_call.n = n;
  17.     initial_call.cur_loc = 0;
  18.  
  19.     stack<Call> st;
  20.     st.push(initial_call);
  21.     int last_ret_val = 0; // Return value of last finished call
  22.     while (!st.empty()) {
  23.         Call& call = st.top();
  24.         if (call.cur_loc == 0) {
  25.             if (call.n <= 1) {
  26.                 // Call finished, save return value and pop stack
  27.                 last_ret_val = 1;
  28.                 st.pop();
  29.             }
  30.             else {
  31.                 // Make new child call F(n-1) and push to stack
  32.                 Call new_call;
  33.                 new_call.cur_loc = 0;
  34.                 new_call.n = call.n - 1;
  35.                 st.push(new_call);
  36.                 // Update current location inside parent call
  37.                 call.cur_loc = 1;
  38.  
  39.  
  40.             }
  41.  
  42.         }
  43.         else if (call.cur_loc == 1) {
  44.             // Do required computations
  45.             call.a = call.n + last_ret_val;
  46.             // Make new child call F(n/2) and push to stack
  47.             Call new_call;
  48.             new_call.cur_loc = 0;
  49.             new_call.n = call.n / 2;
  50.             st.push(new_call);
  51.             // Update current location inside parent call
  52.             call.cur_loc = 2;
  53.  
  54.         }
  55.  
  56.         else if (call.cur_loc == 2) {
  57.             // Do required computations
  58.             call.b = call.n * last_ret_val;
  59.             call.c = call.n - 2 - (call.a + call.b) % 2;
  60.             Call new_call;
  61.             new_call.cur_loc = 0;
  62.             new_call.n = call.c;
  63.             st.push(new_call);
  64.             // Update current location inside parent call
  65.             call.cur_loc = 3;
  66.         }
  67.         else if (call.cur_loc == 3) {
  68.             // Do required computations
  69.             call.d = last_ret_val;
  70.             // Call finished, save return value and pop stack
  71.             last_ret_val = call.a + call.b + call.d;
  72.             st.pop();
  73.  
  74.         }
  75.     }
  76.     return last_ret_val;
  77. }
  78.  
  79.  
  80. int main()
  81. {
  82.     cout << "Result: " << G(3) << endl;
  83.     return 0;
  84. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Result: 13
https://ideone.com/cmm2yy
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!