Using stack to write write the program of the sequence T(n) = T(n/2) + T(n/2) + n; T(1) = 1

[thanhquan1704]

#include <iostream>
#include <stack>
using namespace std;
int my_sequence(int n)
{
stack<long> mystack;
mystack.push(0);
mystack.push(1);
for (int i = 1; i <= n; i++)
{
int a = mystack.top();
mystack.pop();
int b = mystack.top();
mystack.pop();
int c = a / 2 + b / 2 + n;

mystack.push(a);
mystack.push(c);
}
return mystack.top();
}
int main()
{
for (int i = 1; i <= 10; i++)
{
cout << i << '\t' << my_sequence(i) << endl;
}
system("pause");
}


Here is my code but the output is wrong. Can anybody help me to solve it? Thank you!

[salem c]

Please use https://www.cplusplus.com/articles/jEywvCM9/ when posting code.

Are you sure it's a stack and not a vector?

> T(n) = T(n/2) + T(n/2) + n; T(1) = 1
Because this is most easily implemented with a vector, because it says
T[n] = T[n/2] + T[n/2] + n;

With a stack, you've written
T[n] = T[n-1]/2 + T[n-2]/2 + n;

[keskiverto]

Furthermore:

T(n/2) + T(n/2) + n = 2 * T(n/2) + n

[edit] The T is recursive.
Example: T(7) needs T(3) and T(3) needs T(1).
If we follow the recursion, we find sequence 7, 3, 1.
However, the value of T(7) accumulates a sum from sequence 1, 3, 7.

Programming has two sides: (1) understand the problem and (2) express it in language's syntax.

[lastchance]

@thanquan1704, are you sure that you meant that sort of "stack"?

I guess I'm probably thinking the same way as @Keskiverto.

#include <iostream>
using namespace std;

int T( int n )
{
   return n <= 1 ? 1 : 2 * T( n / 2 ) + n;
}

int main()
{
   int n;
   cout << "Input n: ";   cin >> n;
   cout << "T(" << n << ") = " << T( n ) << '\n';
}

Input n: 7
T(7) = 17

[ne555]

a recursive function may be converted to an iterative one by using a stack
think on how a function call works:
- store the program counter(PC) into the stack
- push the parameters of the function into the stack
- change the PC to the address of the function
- the function retrieve its parameters from the stack
- do whatever it has to do
- retrieves the PC from the stack
- push the return value onto the stack
- writes the PC so it returns to the caller
you may see this by doing a backtrace on your debugger.

def T(n):
   if n == 1:  //base case
      return 1
   else:  //recursive case
      return T(n//2) + T(n//2) + n

def emulating_recursion(n):
   s = stack new
   s push: n //push the parameter
   result = 0
   s empty? whileFalse: //function "body"
      x = s top //retrieve the parameter
      s pop
      if x == 1: //base case
         result += 1
      else: //recursive case
         result += x
         s push: x/2 //recursion T(n/2)
         s push: x/2
   return result

now, I cheated there
instead of pushing the return value, I simply add it to `result', and may only do that because your recursion only invokes addition

here's an implementation where it pushes the return value, using a flag to differentiate them from parameters
https://stackoverflow.com/questions/9831666/how-can-you-emulate-recursion-with-a-stack

[lastchance]

I prefer recursion, but did you mean this?

#include <iostream>
#include <stack>
using namespace std;

int main()
{
   int n;
   cout << "Input n: ";   cin >> n;
   stack<int> S;
   while ( n > 1 )
   {
      S.push( n );
      n /= 2;
   }
   int result = 1;
   while ( !S.empty() )
   {
       result = 2 * result + S.top();
       S.pop();
   }   
   cout << "T = " << result << '\n';
}

Input n: 7
T = 17

Here's an alternative (which I don't like as much):

#include <iostream>
#include <stack>
using namespace std;

int main()
{
   int n;
   cout << "Input n: ";   cin >> n;
   stack<int> S;
   S.push( n );
   int result = 0;
   while ( !S.empty() )
   {
      n = S.top();
      S.pop();
      result += n;
      if ( n > 1 ) { S.push( n / 2 );   S.push( n /2 ); }
   }   
   cout << "T = " << result << '\n';
}