--> Archiwum Forum
Pirix [ ! KB ! Góry górą ]
Szybkie mnożenie wielomianów - problem:(
Witam!
Mam problem z takim zadankiem:
Ja wyliczyć współczynniki e, f, g wielomianu gx^2 + fx + e = (ax + b)*(cx + d) znając współczynniki a, b, c, d używając tylko trzech mnożeń?
Znaczek "^" oznacza podniesienie do potęgi.
Jeśli mógłbym użyć czterech mnożeń zadanie jest banalnie proste, ale przy trzech mnożeniach już tak nie jest.
X-Cody [ Zabójca z Liberty City ]
Nie umie pomoc inaczej niz ^^up^^ a zrobic :)
sparrhawk [ Mówca Umarłych ]
Hm, nie wiem, czy dobrze zrozumiałem, ale zadanie robi się w pamięci i nie wiem o jakich mnożeniach tu mowa.
g = ac
f = ad + bc
e - bd
Pirix [ ! KB ! Góry górą ]
sparrhawk ---> no wlaśnie w tym rzecz, że zrobiłeś cztery mnożenia:
1) a*c
2) a*d
3) b*c
4) b*d
I mowa właśnie o mnożeniach współczynników, które wyszczególniłem wyżej.
Z tego co udało mi się zorientować to trzeba zmienić reprezentacje wielomianu z reprezentacji za pomocą współczynników na reprezentacje za pomocą wartości w punktach, dokonać przekształceń i wrócić do pierwotnej reprezentacji wielomianu(czyli za pomocą współczynników).
Lambda [ Legionista ]
W(0) = e = bd mnożenie 1
W(1) = (a + b)(c + d) = g + f + e mnożenie 2
ac + ad + bc + bd = g + f + bd
ac + ad + bc = g + f *
W(-1) = (-a + b)(-c + d) = g - f + e mnożenie 3
ac - ad - bc + bd = g - f + e
ac - ad - bc = g - f **
* i ** dają razem
g = ac
f = ad + bc
symbolicznie, to tych mnoeżeń to tu jest więcej, ale gdyby to rachować na wartościach to niby 3. tylko na cholerę komu takie "ułatwienie"?
Pirix [ ! KB ! Góry górą ]
Lambda----> Dzięki wielkie! Takie zadanie wymyślił sobie prowadzący algorytmy i struktury danych u mnie na uczelni. Jeszcze raz dzieki!