Представление полинома со связанными списками

Question

Заранее спасибо. Для моего класса C++ мне поручено представить многочлен, такой как (MyPoly= 7x^6*y^4 + 4x^4*y^5 - 8x^5*y^3 – 9x + 8), используя связанные списки и здание Node & Поли классы, чтобы помочь выразить это.

Я не знаю, как представить многочлен как с X, так и Y в связанном списке.

У меня есть идея создать связанный список, чтобы представить многочлен как 7 6 4 -> 4 4 5 -> -8 5 3 ->-9 1 0 -> 8 0 0 ->NULL

Я новичок в этом, так ли пример кода или псевдо-код будет иметь большую помощь.

Attempted setup

Я придумал этот код здесь (начальная точка), но я думаю, что это будет работать только для имеющих одну переменную, а не два (7x^6 * ... но не 7x^6 * у^4). Еще раз спасибо :).

Answer 1

Я думаю, вы можете представить полином с матрицей, не связанной списком или чем-то еще.

|X^0|x^1|x^2|x^3 
---|---|---|---|--- 
y^0| | | |  
---|---|---|---|--- 
y^1| | | | 
---|---|---|---|--- 
y^2| | | | 
---|---|---|---|--- 
y^3| | | | 

В каждой ячейке вы должны сохранять коэффициенты при x^x 'и y^y'. И вы можете легче определить операции.

Для операций с матрицами вы можете использовать Boost.uBLAS.

Answer 2

Это будет один из способов сделать это:

Вопросы проектирования:
1. Рассмотрим полиномиальных как список узлов
2. Каждый узел может состоять подузлы.

Итак, ваши определения классов будут:

class Polynomial 
{ 
    list<nodes> termList; 
}; 

class Node 
{ 
    list<SubNodes> subnodelist; 

}; 

template<class T> 
class subNode 
{ 
    int coefficient; 
    int power; 
    T variable; 
}; 

Примечание: Не тестировал код на корректность.

Answer 3

Быстрое решение не так чисто:

MyPoly = 7x^6 * у^4 + 4x^4 * у^5 - 8й^5 * у^3 - 9й +-

#include <list> 
class factor; 
class polynomial{ 
public: 
    std::list<factor> factors; 
}; 

class factor{ 
public: 
    factor()=default; 
    factor(int constant,int x_pow,int y_pow):constant(constant),x_pow(x_pow),y_pow(y_pow){} 
    int constant; 
    int x_pow; 
    int y_pow; 

}; 
int main() 
{ 
    polynomial MyPoly; 
    MyPoly.factors.emplace_back(7,6,4); 
    MyPoly.factors.emplace_back(4,4,5); 
    MyPoly.factors.emplace_back(8,5,3); 
    MyPoly.factors.emplace_back(9,1,0); 
    MyPoly.factors.emplace_back(8,0,0); 
} 

Answer 4

Вы думаете, или вам разрешено работать с полиномами Horner's representation? Это не только более эффективный способ вычисления значений полиномов, но во многих случаях может привести к более разреженной структуре данных. Например, Полином:

эквивалентно следующему выражению:

Так есть 3 вещи, чтобы отметить:

• На самом деле одна замечательная вещь этой схемы (хотя и не имеет прямого отношения к вашему вопросу) заключается в том, что ее расчет равен er, так как вы сохраняете много размножений.
• Индекс полиномом непосредственно зависит от длины выражения
• Все элементы в выражении являются isomorph, независимо от степени. Это справедливо и для каждой реальности.

Так что в этом повезло случае Полином я выбрал может быть очень легко и эффективно хранить в виде следующего списка/массива:

[7, 5, 1, -4, 1, 8, 1, -7]

или если вы хотите, как связанный список [ x_mult | сумма] номера: [7 | 5] -> [1 | 4] -> [1 | 8] -> [1 | -7]

тогда вы знаете, что элементы с четными индексами умножаются по x и добавляется к следующему элементу, схема довольно проста.

#include <iostream> 
using namespace std; 

int main() 
{ 
    // the x you want to calculate 
    int x = 1; 
    // the horner-representation of your polynom 
    int A[8] {7, 5, 1, -4, 1, 8, 1, -7}; 
    int partial; 
    int result = 1; 
    // run calculations following horner-schema 
    for (int i = 0; i < 8; i++) { 
    if (i%2==0){ 
     partial = A[i]*x; // this mult. is only needed at i=0 
     result *= partial; 
    } else{ 
     partial = A[i]; 
     result += partial; 
    } 
    } 
    cout << "x=" << x << ", p(x)=" << result << endl; 
    return 0; 
} 

• Вопросы: Вы могли бы значительно улучшить производительность и использование памяти, если подавить нечетные индексы, и принять «1» 's, как должное, хранение первых 7 в другом месте. Кроме того, поскольку индекс напрямую зависит от длины списка, такие полиномы, как , будут иметь очень неэффективное представление.

• Временное решение для проблемы с памятью: Возможным обходным путем будет наследовать ваш ListElement как ExpandedListElement, так что числа в его контейнерах не рассматриваются в качестве факторов, но, как количества повторений. Таким образом, ExpandedListElement [1000 | a] будет означать, что в вашем списке есть тысяча ListElements, которые выглядят следующим образом: [1 | a]. Таким образом, пример x^1000 + 3 имеет два элемента: ExpandedListElement [999 | 0] -> ListElement [1 | 3]. Вам также понадобится метод для выполнения цикла, который я опускаю (если вам нужно это обходное решение, дайте мне знать, и я опубликую его).

Я не тестировал его широко, но я предполагаю, что это хороший подход и для двух или более переменных. Я также оставил остальную часть деталей реализации OO, но основные DS и операции там и должны быть легко встроены в классы. Если вы попробуете, дайте мне знать, как это работает!

Приветствия

Andres