fork download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4.  
  5. int F(int n) {
  6.     // Location 0
  7.     if (n <= 0) return 0;
  8.     if (n == 1) return 1;
  9.  
  10.     int x = F(n - 3);
  11.     // Location 1
  12.     int y = F(n / 2);
  13.     // Location 2
  14.     int z = x * y;
  15.     // Location 3
  16.     return n + z;
  17. }
  18.  
  19. struct Call {
  20.     int n;
  21.     int x, y, z;
  22.     int cur_loc;
  23. };
  24.  
  25. int G(int n)  {
  26.     stack<Call> st;
  27.     Call initialCall;
  28.     initialCall.n = n;
  29.     initialCall.cur_loc  = 0;
  30.     st.push(initialCall);
  31.     int last_ret_val = 0;
  32.     while(!st.empty()) {
  33.         Call& cur = st.top();
  34.         if(cur.cur_loc  == 0) {
  35.             if(cur.n <= 0) {
  36.                 last_ret_val = 0;
  37.                 st.pop();
  38.             }
  39.             else if(cur.n == 1) {
  40.                 last_ret_val = 1;
  41.                 st.pop();
  42.             }
  43.             else {
  44.                   // Make new child call F(n-1) and push to stack
  45.                   Call new_call;
  46.                   new_call.cur_loc = 0;
  47.                   new_call.n = cur.n - 3;
  48.                   st.push(new_call);
  49.                   cur.cur_loc = 1;
  50.             }
  51.         }
  52.         else if(cur.cur_loc == 1) {
  53.             cur.x = last_ret_val;
  54.             Call new_call;
  55.             new_call.cur_loc = 0;
  56.             new_call.n = cur.n / 2;
  57.             st.push(new_call);
  58.             cur.cur_loc = 2;
  59.  
  60.         }
  61.         else if(cur.cur_loc == 2) {
  62.             cur.y = last_ret_val; 
  63.             cur.z = cur.x * cur.y;
  64.              cur.cur_loc = 3;
  65.         }
  66.         else if(cur.cur_loc == 3) {
  67.              last_ret_val = cur.n + cur.z;
  68.             st.pop();
  69.  
  70.         }
  71.     }
  72.     return last_ret_val;
  73. }
  74.  
  75. int main()
  76. {
  77.     cout << "F(4) : " << F(4) << endl;
  78.     cout << "G(4): " << G(4) << endl;
  79.  
  80. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
F(4) : 6
G(4): 6
https://ideone.com/mfNxzH
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!