Mnożenie wielomianów

pytanie zadane 24 kwietnia 2018 w Matematyka, fizyka, logika przez gab12345 Nowicjusz (120 p.)

Dzień dobry, muszę napisać algorytm do mnożenia wielomianów w sage math (python). Ale kompletnie nie wiem od czego zacząć, czy trzeba wykorzystać algorytm Strassena? Bardzo proszę o pomoc

1 odpowiedź

odpowiedź 24 kwietnia 2018 przez k222 Nałogowiec (30,150 p.)

NIe wiem do końca jak ty tam masz te wielomiany zapisane ale weźmy najprostszy sposób, czyli masz je zapisane w dwóch tablicach t1, t2 takich, że numer indeksu to potęga przy x a wartość w tablicy to współczynnik przy x (domuślnie wszędzie 0). Wystarczy więc zrobić trzecią tablicę t3 o wielkości równej sumie wielkości dwóch danych, a następnie bierzesz dwie komórki o współrzędnych i,j (z tablic t1, t2) wartości w tych komórkach mnożysz i otrzymaną wartość dodajesz do wartości w komórce o numerze i+j w tablicy t3> Jeśli tak pomnożysz każdą komórkę przez każdą w tablicach t1 t2 to w tablicy t3 otrzymasz "wielomian" będący ilorazem dwóch danych.

komentarz 24 kwietnia 2018 przez gab12345 Nowicjusz (120 p.)

Bardzo dziękuję za odpowiedź, ale czy mógłbyś napisać przykładowy algorytm takiego mnożenia wielomianów. Dopiero zaczynam pracę z sage math i nie za bardzo wiem jak pisać takie algorytmy.

komentarz 24 kwietnia 2018 przez k222 Nałogowiec (30,150 p.)

Sory, ale tutaj już nie pomogę, bo ani z pythonem ani sage math nie miałem zbytnio styczności, wiem tylko że się da w pythonie bo są tam tablice

komentarz 24 kwietnia 2018 przez Irrichi Użytkownik (640 p.)

@gab12345,

Wydaje mi się, że w pythonie powinno wyglądać to tak:

W1=[1,2,3,4]
W2=[5,4,3,2,1]
W3=[]

for i in range(0,len(W1)+len(W2)-1):
  W3.append(0)

for i in range(0,len(W1)):
  for j in range(0,len(W2)):
    W3[i+j]=W3[i+j]+W1[i]*W2[j]

print(W3)

Gdzie w tablice W1 i W2 wpisujesz wielomian tak, aby W1[k] było współczynnikiem wielomianu przy x do k-tej potęgi. W moim przykładzie te wielomiany to 1+2x+3x^2+4x^3 i 5+4x+3x^2+2x^3+x^4.

Wynik zapisany w tablicy W3 należy odczytać w ten sam sposób. W tym przypadku jest to 4 x^7 + 11 x^6 + 20 x^5 + 30 x^4 + 40 x^3 + 26 x^2 + 14 x + 5.

komentarz 24 kwietnia 2018 przez gab12345 Nowicjusz (120 p.)

Dziękuję ratujesz mi życie
a czy da się tak zrobić, żeby na końcu był wyświetlany wielomian, a nie tylko jego współczynniki?

komentarz 24 kwietnia 2018 przez Irrichi Użytkownik (640 p.)

W1=[1,2,3,4]
W2=[5,4,3,2,1]
W3=[]
 
for i in range(0,len(W1)+len(W2)-1):
  W3.append(0)
 
for i in range(0,len(W1)):
  for j in range(0,len(W2)):
    W3[i+j]=W3[i+j]+W1[i]*W2[j]
 
print(W3)

for i in range(len(W3)-1,-1,-1):
  if(i!=0):
    print(str(W3[i])+"x^"+str(i)+" + ",end='')
  if(i==0):
    print(W3[0])

komentarz 25 kwietnia 2018 przez gab12345 Nowicjusz (120 p.)

wyrzuca taki błąd:

 File "<ipython-input-2-e38574fd9a51>", line 16
    print(str(W3[i])+"x^"+str(i)+" + ",end='')
                                          ^
SyntaxError: invalid syntax

komentarz 25 kwietnia 2018 przez Irrichi Użytkownik (640 p.)

To spróbuj tak:

W1=[1,2,3,4]
W2=[5,4,3,2,1]
W3=[]
  
for i in range(0,len(W1)+len(W2)-1):
  W3.append(0)
  
for i in range(0,len(W1)):
  for j in range(0,len(W2)):
    W3[i+j]=W3[i+j]+W1[i]*W2[j]
  
print(W3)
 
for i in range(len(W3)-1,-1,-1):
  if(i!=0):
    print str(W3[i])+"x^"+str(i)+" + ",
  if(i==0):
    print(W3[0])