Массив Представление полиномов

Question

Я читал о реализации связанного списка полиномов. Он заявил,

Compare this representation with storing the same
polynomial using an array structure.
In the array we have to have keep a slot for each exponent
of x, thus if we have a polynomial of order 50 but containing
just 6 terms, then a large number of entries will be zero in
the array.

Мне было интересно, как мы представляем полином в массиве? Пожалуйста, ведите меня.

Спасибо

Answer 1

Полная реализация Java на основе многочленов на основе массива приведена здесь: http://www.cs.lmu.edu/~ray/classes/dsa/assignment/2/answers/

Основная идея заключается в том, что если у вас есть многочлен, подобный

4x^6-2x+5

, то ваш массив будет выглядеть следующим образом

   0     1    2    3    4    5    6
+----+-----+----+----+----+----+----+
| 5  |  -2 |  0 |  0 |  0 |  0 |  4 |
+----+-----+----+----+----+----+----+

То есть

• коэффициент 5 находится в слоте 0 массива (представляет 5x ^ 0)
• коэффициент -2 находится в слоте 1массива (представляющего -2x ^ 1)
• коэффициент 4 находится в слоте 6 массива (представляющего 4x ^ 6)

Вы, вероятно, можете видеть, как это представление будетрасточительно для полиномов, таких как

3x^5000 + 2

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

Answer 2

Если у вас есть полиномиальная функция, такая как

3x^4 + x^2 + 2x + 1 = 0

Вы можете представить ее в массиве как

[1 2 1 0 3]

Итак, элемент 0 - это коэффициент x ^ 0, элемент 1коэффициент х ^ 1 и так далее ...

Answer 3

обычно вы держите один элемент для каждого показателя степени, поэтому полином на самом деле:
poly[0]*x^0 + poly[1]*x^1 + ... + poly[n-1]*x^(n-1)

например. если у вас есть p(x) = 3x^5+5x^2+1, ваш массив будет:

poly[0] = 1
poly[1] = 0
poly[2] = 5
poly[3] = 0
poly[4] = 0
poly[5] = 3

Answer 4

Предположим, ваш полином

6x^50 + 4x^2 + 2x + 1

Абзац, который вы опубликовали, описывает его сохранение в массиве следующим образом:

polynomial = new array(50)  // I'm assuming all elements initialize to zero
polynomial[50] = 6
polynomial[2] = 4
polynomial[1] = 2
polynomial[0] = 1

По сути, это тратит много места таким образом. Здесь индекс массива - это «степень» x для полинома от x.