Tính Tổng / Hiệu / Tích / Thương 2 đa thức

Giải thích thì cũng khá loằng ngoằng, mình viết code bằng python rồi bạn có thể tìm hiểu trong đó.
Coi đa thức là một list F(x) = sum ( f[i]*x^i ); i= 0 -> n-1

def add(f,g):
    degree=max(len(f),len(g))
    ans=[0]*degree

    for i in range(degree):
        ans[i]=(f[i] if i<len(f) else 0)+ (
            g[i] if i<len(g) else 0)
    return ans

def sub(f,g):
    degree=max(len(f),len(g))
    ans=[0]*degree

    for i in range(degree):
        ans[i]=(f[i] if i<len(f) else 0)- (
            g[i] if i<len(g) else 0)
        
    while len(ans)>0 and ans[-1]==0: # loai he so bac cao nhat neu = 0
        ans.pop()
    return ans

def mul_n(f,n): # f(x) *(number n)
    return map(lambda i:i*n,f)

def mul_k(f,k): # return f(x)*x^k
    return [0]*k+f

def mul(f,g):
    ans=[]

    for i,v in enumerate(g):
        t=mul_k(mul_n(f,v),i)  # t=f(x)*g[i] * x^i
        ans=add(ans,t) # ans = sum (f(x) *g[i]*x^i)
    return ans

def div(f,g): # f(x)=q(x)*g(x)+r(x)
    q=[]
    while len(f)>=len(g):
        t=mul_k(mul_n([1],1.0*f[-1]/g[-1]),len(f)-len(g)) # chia 2 bac cao nhat
        q=add(q,t)
        f=sub(f,mul(t,g))
    return q,f

Python chắc em chịu anh ơi, em chỉ rành về C/C++ thôi chứ chẳng biết tẹo nào về python cả

cho code C++ chắc gì đã hiểu

http://rextester.com/ZEQEV88237

#include <iostream>
#include <map>

class Polynomial
{
public:
    Polynomial() {}
    int degree()const { return poly.empty() ? 0 : poly.rbegin()->first; }
    void   set(int degree, double coef) { poly[degree] = coef; }
    double get(int degree)const         { auto it = poly.find(degree); return it == end(poly) ? 0 : it->second; }
    Polynomial& operator+=(const Polynomial& rhs);
    Polynomial& operator-=(const Polynomial& rhs);
    Polynomial& operator*=(const Polynomial& rhs);
    Polynomial& operator/=(const Polynomial& rhs);
    Polynomial& operator%=(const Polynomial& rhs);
    Polynomial operator+(const Polynomial& rhs)const { auto ret = *this; return ret += rhs; }
    Polynomial operator-(const Polynomial& rhs)const { auto ret = *this; return ret -= rhs; }
    Polynomial operator*(const Polynomial& rhs)const { auto ret = *this; return ret *= rhs; }
    Polynomial operator/(const Polynomial& rhs)const { auto ret = *this; return ret /= rhs; }
    Polynomial operator%(const Polynomial& rhs)const { auto ret = *this; return ret %= rhs; }
    static std::pair<Polynomial,Polynomial> div(Polynomial lhs, const Polynomial& rhs);
    friend std::ostream& operator<<(std::ostream& out, const Polynomial& rhs);
private:
    std::map<int,double> poly;
};

int main()
{
    Polynomial p1;
    p1.set(0, 1);
    p1.set(1, 2);
    p1.set(2, 3);
    std::cout << "p1 = " << p1 << "\n";
    
    Polynomial p2;
    p2.set(0, 4);
    p2.set(1, 5);
    p2.set(2, 6);
    p2.set(3, 7);
    std::cout << "p2 = " << p2 << "\n\n";
    
    std::cout << "p1 + p2 = " << p1 + p2 << "\n";
    std::cout << "p1 - p2 = " << p1 - p2 << "\n";
    std::cout << "p1 * p2 = " << p1 * p2 << "\n";
    std::cout << "p1 / p2 = " << p1 / p2 << "\n";
    std::cout << "p1 % p2 = " << p1 % p2 << "\n\n";
    
    std::cout << "p2 + p1 = " << p2 + p1 << "\n";
    std::cout << "p2 - p1 = " << p2 - p1 << "\n";
    std::cout << "p2 * p1 = " << p2 * p1 << "\n";
    std::cout << "p2 / p1 = " << p2 / p1 << "\n";
    std::cout << "p2 % p1 = " << p2 % p1 << "\n";
}


std::ostream& operator<<(std::ostream& out, const Polynomial& rhs)
{
    if (!rhs.degree()) return out << 0;
    auto kv = rhs.poly.begin();
    out << kv->second << "*x^" << kv->first;
    while (++kv != end(rhs.poly)) out << " + " << kv->second << "*x^" << kv->first;
    return out;
}

Polynomial& Polynomial::operator+=(const Polynomial& rhs)
{
    for (auto const& kv : rhs.poly) poly[kv.first] += kv.second;
    return *this;
}

Polynomial& Polynomial::operator-=(const Polynomial& rhs)
{
    for (auto const& kv : rhs.poly) poly[kv.first] -= kv.second;
    return *this;
}

Polynomial& Polynomial::operator*=(const Polynomial& rhs)
{
    decltype(poly) p;
    for (auto const& kv1 : poly) for (auto const& kv2 : rhs.poly)
        p[kv1.first + kv2.first] += kv1.second * kv2.second;
    poly.swap(p);
    return *this;
}

std::pair<Polynomial,Polynomial> Polynomial::div(Polynomial remainder, const Polynomial& divisor)
{
    Polynomial quotient;
    while (remainder.degree() >= divisor.degree())
    {
        int    deg  = remainder.degree() - divisor.degree();
        double coef = remainder.poly.rbegin()->second / divisor.poly.rbegin()->second;
        for (auto const& kv : divisor.poly) remainder.poly[kv.first + deg] -= kv.second * coef;
        quotient.poly[deg] = coef;
        remainder.poly.erase(std::prev(end(remainder.poly)));
    }
    return {quotient,remainder};
}

Polynomial& Polynomial::operator/=(const Polynomial& rhs)
{
    auto qr = div(*this, rhs);
    poly.swap(qr.first.poly);
    return *this;
}

Polynomial& Polynomial::operator%=(const Polynomial& rhs)
{
    auto qr = div(*this, rhs);
    poly.swap(qr.second.poly);
    return *this;
}

đa thức = tổng các đơn thức

bậc của đa thức là bậc của đơn thức có bậc lớn nhất

phép nhân đơn giản chỉ là 2 cái vòng for nhân các đơn thức với nhau nhau, rồi nhớ chỉnh bậc cho đúng: 2 đơn thức nhân với nhau tạo ra đơn thức mới, hệ số bằng tích 2 hệ số cũ, bậc bằng tổng 2 bậc cũ.

phép chia thì tính từ từ: lấy hệ số của đơn thức bậc cao nhất trong vế trái chia cho hệ số của đơn thức bậc cao nhất bên vế phải, ra được hệ số của 1 đơn thức trong thương (quotient), rồi phải lấy đa thức bị chia (dividend) trừ đi tích của đơn thức này với đa thức chia (divisor). Lập lại tới khi nào đa thức bị chia có bậc bé hơn đa thức chia là được. Lúc này đa thức bị chia chính là phần dư (remainder) của phép chia đa thức.

vd
7x³ + 6x² + 5x + 4 chia 3x² + 2x + 1

vì bậc của đa thức bị chia là 3 > bậc của đa thức chia là 2:

• lấy hệ số 7 chia cho hệ số 3 ta có kết quả đơn thức của thương: (7/3)*(x^3-2) = 7x/3.
• lấy (7x/3) nhân với đa thức chia, trừ vô đa thức bị chia, đa thức bị chia còn 4x²/3 + 8x/3 + 4

vì bậc của đa thức bị chia là 2 = bậc của đa thức chia là 2:

• lấy hệ số 4/3 chia cho hệ số 3 ta có kết quả đơn thức của thương: (4/9)*(x^2-2) = 4/9.
• lấy (4/9) nhân với đa thức chia, trừ vô đa thức bị chia, đa thức bị chia còn 16x/9 + 32/9

vì bậc của đa thức bị chia là 1 < bậc của đa thức chia là 2 => dừng. Kết quả thương là 7x/3 + 4/9, phần dư là 16x/9 + 32/9

Anh @tntxtnt code dễ hiểu tí được không nhỉ, em chưa học OOP, this, … này nọ cơ mà

Chỉ được dùng struct, con trỏ, mảng, … trở xuống thôi

tự viết đi, ko xài map cũng được, xài mảng lưu hệ số coef, vd đa thức bậc 10 thì xài mảng 11 phần tử:
coef[0] tương ứng với a₀
coef[1] tương ứng với a₁
…
coef[10] tương ứng với a₁₀

khi nhân 2 đa thức vd bậc 10 với bậc 3 thì kết quả là đa thúc bậc 13, nên tạo mảng hệ số 14 phần tử.

phép chia thì vd bậc 10 chia bậc 3 kết quả ra đa thức bậc 7, nên tạo mảng hệ số 8 phần tử, rồi chia dần dần theo cách chia tiểu học đó.

khi nhân 2 đa thức vd bậc 10 với bậc 3 thì kết quả là đa thúc bậc 13, nên tạo mảng hệ số 14 phần tử.

Great. Nhưng làm sao để tính ra từng phần tử anh?
VD: (2 + 3x)(4 + 5x + 6x^2)
Bây giờ mình muốn tính hạng tử bậc 2 chẳng hạn, thì phải nhân 2 với 6x^2, 3x với 5x. Nếu trường hợp đa thức đó dài ngoằn nghoèo nữa thì mình dùng thuật toán gì để tính nhỉ ?

Em mới làm được cái “khung” thôi

DT* Tich2DaThuc(DT *x, DT *y)
{
	DT *kq = new DT;
	kq->heso = new double[x->bac + y->bac + 1];
	for (int i = 0; i <= x->bac; ++i)
	{
		for (int j = 0; j <= y->bac; ++j)
		{
			// chưa nghĩ ra ....
		}
	}

        return kq;
}

lấy giấy ra nhân đi sẽ thấy, đừng có lười
(5x³ + 4x² + 3x + 2) * (7x² + 8x + 9) = …
nhân lần lượt từng đơn thức với nhau sẽ thấy logic của phép nhân 2 đa thức thôi.

Uhm …

Đây là hàm tính tích 2 đa thức của em.

DT* Tich2DaThuc(DT *x, DT *y)
{
	DT *kq = new DT;
	kq->bac = x->bac + y->bac;
	kq->heso = new double[kq->bac + 1];
	for (int i = 0; i <= kq->bac; ++i)
	{
		kq->heso[i] = 0;
		for (int j = 0; j <= (int)i / 2; ++j)
		{
			if (x->bac >= i && y->bac >= i)
			{
				if (i != 0)
				{
					kq->heso[i] += (x->heso[j] * y->heso[i - j]) + (y->heso[j] * x->heso[i - j]);
				}
				else
				{
					kq->heso[i] += (x->heso[j] * y->heso[i - j]);
				}
				continue;
			}
			if (y->bac >= i - j)
			{
				kq->heso[i] += (x->heso[j] * y->heso[i - j]);
				continue;
			}
			if (x->bac >= i - j)
			{
				kq->heso[i] += y->heso[j] * x->heso[i - j];
				continue;
			}
		}
	}
	return kq;
}

Nó chỉ đúng với 1 vài đa thức đơn giản, còn những đa thức phức tạp còn sai sót, mong anh @tntxtnt cố chiếu

Sao mà phức tạp thế

DT * mul(DT *x, DT *y)
{
       DT *kq=new DT;
       kq->bac=x->bac+y->bac;
       kq->heso=new double[kq->bac+1];
       fill(kq->heso,kq->heso+bac+1,0.0);
       for(int i=0;i<=x->bac;i++) for(int j=0;j<=y->bac;j++)
             kq->heso[i+j]+=x->heso[i]*y->heso[j];
       return kq;
}

Sao mà phức tạp thế

Em newbie nên code dài dòng lưa thưa lắm anh

Ôi thần linh ơi, tuyệt vời quá anh ! Cơ mà em chưa hiểu lắm về cái thuật toán anh dùng, anh có thể giải thích được không ạ ? Với cái hàm fill nữa

fill chức năng trong này là gán tất cả heso=0

Khi nhân 2 đa thức a_ixⁱ * b_jx^j = a_i*b_jx^i+j . Kết quả của phép nhân là tổng của biểu thức trên nên kết quả kq->heso[i+j] = sum(x->heso[i]*y->heso[j])

OK, sau 1 hồi suy ngẫm, em thấy cái chỗ hay nhất trong thuật toán của anh là chỗ này

kq->heso[i+j] += x->heso[i]*y->heso[j];

Thanks anh nhiều !