c++ - 使用栈编写序列T(n) = T(n/2) + T(n/2) + n的程序；T(1) = 1

Question

#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");
}

我可以轻松地使用递归来解决它，但问题要求我使用堆栈。我的代码显示错误的输出。我不确定我该怎么做，所以有人可以帮我解决吗？

标签： c++

Answer 1

每个新值都需要一个接近堆栈一半的值。例如，T(100) 需要知道 T(50)，您需要保留值以便以后使用它们。

问题是：你如何获得一个接近堆栈一半的值而不丢失它上面的所有值？堆栈不是随机访问，因此您不能只抓取您想要的项目。

要从堆栈中检索一个值，您需要弹出高于所需值的所有值，读取该值，然后将所有这些值推回。那么，您将临时弹出的所有值存储在哪里？好吧，您可以使用堆栈。

如果您正在计算 T(n)，那么堆栈的顶部是 T(n-1)，而 T(n/2) 是堆栈顶部下方的 n/2 个项目。所以要得到它，我们需要从堆栈中删除 i-1 - n/2 个值，从堆栈顶部获取我们想要的值，然后将所有这些值放回去。

在这里试试：https ://onlinegdb.com/ByhQ-R9DI

#include <iostream>
#include <stack>

std::stack<int> results;

int retrieve(int howfardown)
{
    if (howfardown == 0)
        return results.top();

    int value;
    std::stack<int> temp;

    for (int i=0; i<howfardown; i++)
    {
        temp.push(results.top());
        results.pop();
    }

    value = results.top();

    for (int i=0; i<howfardown; i++)
    {
        results.push(temp.top());
        temp.pop();
    }

    return value;
}

int main(int argc, char *argv[])
{
    results.push(1);

    // The top of the stack is now T(1)

    int n;
    if (argc==2)
        n = atoi(argv[1]);
    if (n<1)
        n = 1;

    // n now has a value (n=1 if there was a problem getting the value)

    for(int i=2; i<=n; i++)
    {
        std::cout << "The top of the stack is T(" << i-1 << ") = " << results.top() << "\n";
        std::cout << "The stack is " << i-1 << " items deep\n";
        std::cout << "T(" << i/2 << ") = " << i-1 - i/2 << " item down the stack\n"; 

        int prev_value = retrieve(i-1 - i/2);
        std::cout << "T(" << i << "/2) = T(" << i/2 << ") = " << prev_value << "\n"; 

        int value = prev_value + prev_value + i;
        std::cout << "T(" << i << ") = T(" << i/2 << ") + T(" << i/2 << ") + " << i << " = " << value << "\n"; 

        results.push(value);
        std::cout << "Push T(" << i << ") onto the stack\n\n"; 
    }

    // so print out the top of the stack

    std::cout << "T(" << n << ") = " << results.top() << "\n"; 

    return 0;
}