使用 std::stack 将 Hermite 多项式递归转换为解

Question

Hermite 多项式由以下公式定义，其中 n>0 且 x 为实数：

我已经使用递归定义了一个解决方案：

int hermitPolynomial(int n, int x){
    if(n == 0){
        return 1;
    }
    if (n == 1){
        return x*2;
    }
    return 2*x*hermitPolynomial(n-1,x) + 2*(n-1)*hermitPolynomial(n-2,x);
}

如何使用堆栈将函数转换为迭代解决方案？另外，使用堆栈将递归转换为迭代函数的基础知识是什么？

我设法将难度较低的递归（如斐波那契）转换为迭代堆栈解决方案。

这是我尝试过的解决方案，但我没有想到一种方法来跟踪“2x”和“2(n-1)”：

int hermitPolynomialIter(int n, int x){
    std::stack<int> s;
    int result = 0;
    s.push(n);
    while(!s.empty()){
        int temp = s.top(); s.pop();
        if(temp == 1){
            result+=1;
        }
        else if(temp == 2){
            result+=2*x;
        }
        else{
            s.push(temp-1);
            s.push(temp-2);
        }
    }
    return result;
}

Answer 1

提示：

请注意，递归公式根据两个先前的评估（即 Hn-1 和 Hn-2）表示 Hn。因此，您可以仅使用两个保存这些评估的变量（设 H1 和 H2）来执行它，并在您增加 n.

时移动它们

循环体为

H0= 2 * X * H1 + 2 * (N-1) * H2;
H2= H1;
H1= H0;
N++;

以下不变量将成立：H1 = Hn-1 and H2 = Hn-2，对于所有迭代。

我让你找出变量 H0、H1 和 H2 应该如何初始化（考虑 N=2）。

Answer 2

首先，让我注意到recurrence formula是

H_n(x) = 2xH_{n-1}(x) - 2(n-1)H_{n-2}(x)

（注意减号）。

这是一个解决方案，以及计算 x=1 和 x=2 处的第一个多项式的小测试。

#include <stack>
#include <iostream>

int hermitePolynomial(int n, int x)
{
  std::stack<int> s;
  if (n == 0)
    {
      return 1;
    }
  else if (n == 1)
    {
      return 2 * x;
    }
  else
    {
      s.push(1);
      s.push(2 * x);
      for (int k = 2; k <= n; ++k)
    {
      auto hermite_k_minus_1 = s.top();
      s.pop();
      auto hermite_k_minus_2 = s.top();
      s.pop();
      auto hermite_k = 2 * x * hermite_k_minus_1 - 2 * (k - 1) * hermite_k_minus_2;
      s.push(hermite_k_minus_1);
      s.push(hermite_k);
    }
      return s.top();
    }
}

int main()
{
  for (const int x : { 1, 2 })
    {
      std::cout << "Polynomials at x = " << x << std::endl;
      for (int i = 0; i < 5; ++i)
    std::cout << "H_" << i << "(" << x << ") = " << hermitePolynomial(i, x) << std::endl;
    }

  return 0;
}

看到了Live on Coliru.

主要思想是循环迭代计算第 k 个多项式，并将最后 2 个多项式保存在堆栈中，即索引 k-1 和 k-2 的多项式。

使用 std::stack 将 Hermite 多项式递归转换为解

Transforming Hermite Polynomial Recursion to a solution using std::stack

c++

algorithm

recursion

stack