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

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

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

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

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

Попытка установки

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

Источник

4 ответа

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

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

Итак, есть 3 вещи, на которые стоит обратить внимание:

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

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

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

или, если хотите, в виде связного списка чисел [x_mult|sum]: [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" как должное, сохранив первые 7 в другом месте. Кроме того, поскольку индекс напрямую зависит от длины списка, полиномы, такие как будет иметь очень неэффективное представление.

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

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

ура

Andres

Источник

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

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

#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);
}
Источник

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

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

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

Вы можете использовать Boost.uBLAS для матричных операций.

Источник

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

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

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

class Polynomial
{
   list<nodes> termList;
}; 

class Node
{
   list<SubNodes> subnodelist;

};

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

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

Источник
Другие вопросы по тегам