Как умножить 2 полинома использовать Linked List без переменной мощности? - PullRequest
Новая
       13

Как умножить 2 полинома использовать Linked List без переменной мощности?

1 голос
/ 12 октября 2011

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

class Node {
    public:
        int data; // only data, has no power
        Node* next;
};
class PolyList {
    private:
        Node* pHead;
     public:
        PolyList();
        ~PolyList();
         ............
}

Список читается файлом input.txt. Пример: 2 4 0 3 ---> Полином = (2x ^ 3 + 4x ^ 2 + 3)

Как реализовать метод умножения 2 полиномов между list1 и list2. Я ищу в Google и на этом сайте, но создается только найденный многочлен с данными, включающими переменную коэффициента и переменную степени. У моего полинома есть только коэффициент, и я не могу изменить эту структуру. Мне нужна помощь от всех. Большое спасибо.

Ответы [ 4 ]

2 голосов
/ 12 октября 2011

То, что вы хотите сделать, это свертка коэффициентов. Если у вас есть доступ к Matlab (или Octave), вы можете попробовать его: 

% Note this is Matlab, just for demonstration
p1 = [1 1];  % x + 1
p2 = [1 0];  % x
p3 = conv(p1, p2)   %x*(x + 1) => x^2 + x

% gives p3 = [1 1 0], i.e., x^2 + x

Edit: я не дал никаких подробностей о реализации этого - вы, вероятно, можете найти примеры свертки, используя связанные списки, прибегая к помощи Google.

1 голос
/ 12 октября 2011

Вы можете использовать два вложенных цикла for, чтобы умножить два списка вместе, сохранив их в другом списке: (псевдокод) 

define list3 as a new PolyList of length x + y

for each element A at index x in list1
   for each element B at index y in list2
       save list3 element at index x + y as (A * B + (element at index x + y))

Так, например, с x ^ 3 - 2x + 1 * x ^ 2 + 4 = [1, 0, -2, 1] * [0, 0, 1, 4] = [0, 0, 0, 1 , 0, 2, 1, -8, 4].

* Примечание: Ваш итоговый список может быть до в два раза размера исходной длины двух массивов, потому что, например, x ^ 3 * x ^ 3 = x ^ 6, который будет записан в шестом указателе, начиная справа. *

Также обратите внимание: Два массива должны иметь одинаковую длину, чтобы алгоритм работал правильно! Если это не предполагается созданной вами функцией, вам придется справиться с этой ситуацией.

Хороший способ выяснить, как запрограммировать такую ​​проблему, - представить точно шаги, которые вы бы предприняли для решения проблемы, записать их, а затем перевести это на язык, на котором вы использование.

1 голос
/ 12 октября 2011

Способ сделать это может быть следующим: 

list<int> multiply(list<int> l1, list<int> l2) {
  int m[l1.size() + l2.size() - 1]; // Only positive powers of l1 "augments" the powers of l2!

  for (unsigned int i = 0; i < l1.size(); i++) {
    for (unsigned int j = 0; j < l2.size(); i++) {
      m[i + j] += l1.get() * l2.get();
      l2.next();
    }
    l2.reset();
    l1.next();
  }
  list<int> to_ret;
  for (unsigned int i = 0; i < m.length; i++)
    to_ret.push_back(m[i]);
  return to_ret;
}

Вы положите коэффициент i -ой степени полученного полинома в m[i].Чтобы заполнить m, достаточно перебрать каждую пару (i, j) из [0, l1.size) x [0, l2.size) и ввести m[i + j] коэффициент, который вы умножаете на коэффициент i -я степень первого многочлена с степенью j -ой степени второго.

0 голосов
/ 12 октября 2011

Если вы хотите умножить два полинома порядка M и N, то результирующий полином будет иметь порядок M + N. Поэтому вам необходимо создать выходной связанный список, длина которого является суммой длин двух входных списков. Затем вы просто перебираете два входных списка, умножая и суммируя термины в выходной список.

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

...