当前位置:   article > 正文

[数据结构习题]用栈实现递归函数的非递归运算_递归函数的非递归计算

递归函数的非递归计算

 题目来源:王道23数据结构,3.3.6,综合应用题03

非王道书教材内答案解法!

 整体思路:

    从前往后计算解题,我们可以创建一个两个元素的栈,用于保存Pn-1(x)与Pn-2(x),初始化为栈底元素P0(x),栈顶元素P1(x)。根据这两个可以往后得出P3(x),P4(x)。。。每次计算时依次弹出站内元素,并用变量记录下来,计算完后便可抛弃Pn-2(x),将Pn-1(x)压入栈底,再将Pn(x)压入栈顶。整体思路就是将从后往前(n-0)的递归解题变为从前往后(0-n)的循环解题。代码如下

  1. #include<iostream>
  2. using namespace std;
  3. struct stack {
  4. int arr[2] = {0,0};
  5. int top=-1;
  6. }; // 大小为2的辅助栈
  7. bool push(struct stack &s ,int x) {
  8. s.arr[++s.top] = x;
  9. return true;
  10. } // 入栈操作
  11. bool pop(struct stack &s , int& x) {
  12. x = s.arr[s.top--];
  13. return true;
  14. } // 出栈操作
  15. int func_p(int x, int n) {
  16. if (n == 0)
  17. return 1;// n=1时直接返回1
  18. struct stack s;// 创建一个辅助栈
  19. int val1 = 0, val2 = 0, val3 = 0;
  20. push(s,1);
  21. push(s,2 * x); // 将1,2x依次压入栈
  22. // 当n>1的时候执行此循环
  23. for (int i = 2; i <= n; i++) {
  24. pop(s,val1); // 弹出Pn-1(x)
  25. pop(s,val2); // 弹出Pn-2(x)
  26. push(s,val1); // 再将原Pn-1(x)压入栈中,为下一次循环做准备
  27. val3 = 2 * x * val1 - 2 * (i - 1) * val2; // 求出Pn(x)
  28. push(s,val3); // 将目前Pn(x)压入栈中
  29. }
  30. int res=0;
  31. pop(s,res); // 此时栈顶元素即为Pn(x)
  32. return res;
  33. }

执行检验结果:

  1. int main() {
  2. cout << "请输入x与n" << endl;
  3. int x, n;
  4. cin >> x >> n;
  5. cout << func_p(x, n) << endl;// x,n
  6. system("pause");
  7. return 0;
  8. }

我们测试输入x=2,n=3,稿纸手算结果如下

 代码运行结果为

结果正确! 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/952490
推荐阅读
相关标签
  

闽ICP备14008679号