赞
踩
题目来源:王道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)的循环解题。代码如下
- #include<iostream>
- using namespace std;
-
- struct stack {
- int arr[2] = {0,0};
- int top=-1;
- }; // 大小为2的辅助栈
-
- bool push(struct stack &s ,int x) {
- s.arr[++s.top] = x;
- return true;
- } // 入栈操作
-
- bool pop(struct stack &s , int& x) {
- x = s.arr[s.top--];
- return true;
- } // 出栈操作
-
- int func_p(int x, int n) {
-
- if (n == 0)
- return 1;// n=1时直接返回1
-
- struct stack s;// 创建一个辅助栈
- int val1 = 0, val2 = 0, val3 = 0;
- push(s,1);
- push(s,2 * x); // 将1,2x依次压入栈
-
- // 当n>1的时候执行此循环
- for (int i = 2; i <= n; i++) {
- pop(s,val1); // 弹出Pn-1(x)
- pop(s,val2); // 弹出Pn-2(x)
- push(s,val1); // 再将原Pn-1(x)压入栈中,为下一次循环做准备
- val3 = 2 * x * val1 - 2 * (i - 1) * val2; // 求出Pn(x)
- push(s,val3); // 将目前Pn(x)压入栈中
- }
- int res=0;
- pop(s,res); // 此时栈顶元素即为Pn(x)
- return res;
- }

执行检验结果:
- int main() {
- cout << "请输入x与n" << endl;
- int x, n;
- cin >> x >> n;
- cout << func_p(x, n) << endl;// x,n
-
- system("pause");
- return 0;
- }
我们测试输入x=2,n=3,稿纸手算结果如下
代码运行结果为
结果正确!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。