#c #algorithm #recursion #stack
Вопрос:
Многочлены Эрмита определяются следующими формулами, где 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);
}
Как функция может быть преобразована в итеративное решение с использованием стека? Также каковы основы преобразования рекурсии в итеративную функцию с использованием стека?
Мне удалось преобразовать менее сложные рекурсии(например, Фибоначчи) в итеративное решение стека.
Это решение, которое я пробовал, но я не придумал, как отслеживать «2 x» и «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 resu<
}
Комментарии:
1. почему вы хотите использовать стек? Итерационное решение-это просто цикл
2. @463035818_is_not_a_number в основном для практики использования стеков. Но также существуют языки(например, python), которые имеют ограничение глубины рекурсии, и из-за этого в некоторых случаях итерация лучше. Спасибо!
3. часть практики стеков состоит в том, чтобы научиться, когда их использовать, а когда нет. Вы превращаете что-то относительно простое во что-то относительно сложное. Просто говорю. Если вся цель этого состоит в том, чтобы попрактиковаться
std::stack, вам, возможно, следует упомянуть об этом в вопросе4. Я попробовал, но, извините, я действительно не понимаю, как здесь уместится стопка. Похоже, вы хотите использовать стек для отслеживания последних двух предыдущих результатов, но тогда цикл
while(!s.empty())не имеет смысла. На каждой итерации вы добавляете последние два значения обратно в стек, поэтому он никогда не бывает пустым5. fwiw, последний ответ использует стек как (сложный) способ хранения двух последних предыдущих результатов, и это то, что я ожидал найти в вашем коде в первую очередь. Это способ сделать это, но все же моя рекомендация применима: имейте в виду, что единственная причина использования стека здесь-практика использования стека
Ответ №1:
Подсказка:
Обратите внимание, что рекурсивная формула выражает Hn в терминах двух предыдущих оценок (а именно Hn-1 «и Hn-2 «). Следовательно, вы можете выполнить это, используя только две переменные, которые содержат эти оценки (пусть 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 ).
Ответ №2:
Прежде всего, позвольте мне заметить, что формула повторения является
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;
}
Посмотрите это в прямом эфире на Колиру.
Основная идея заключается в том, что вы повторяете цикл для вычисления k-го многочлена и сохраняете в стеке 2 последних многочлена, т. е. многочлен для индексов k-1 и k-2.