Tính Tổng / Hiệu / Tích / Thương 2 đa Thức - Dạy Nhau Học Trang chủ » Cộng 2 đa Thức Bằng Danh Sách Liên Kết đơn » Tính Tổng / Hiệu / Tích / Thương 2 đa Thức - Dạy Nhau Học Có thể bạn quan tâm Cộng 2 đa Thức đồng Dạng Cổng 2 Học Viện Cán Bộ Công 2jj Cổng 2 Kcn Vân Trung Cổng 2 Khu Công Nghiệp Vân Trung Tính Tổng / Hiệu / Tích / Thương 2 đa thức programming c++ tcm (Người bí ẩn) February 28, 2022, 7:29am #1 Hi mọi người, Mình có 1 đề bài như sau: Nhập vào 2 đa thức rồi tính tổng, hiệu, tích, thương của 2 đa thức đó, kết quả trả về là 1 đa thức mới. Yêu cầu: Phải xuất ra đầy đủ định dạng của 1 đa thức. ĐA THỨC CÓ DẠNG: a0 * x^0 + a1 * x^1 + a2 * x^2 + … + an * x^n Dữ liệu trong đa thức sẽ có: Số bậc cao nhất của đa thức (n). Danh sách các hệ số của đa thức (từ a0 --> an). Yêu cầu: Phải xuất ra theo đúng định dạng. vd: Đa thức 1: 1 + 2 * x^1 + 3 * x^2 Đa thức 2: 4 + 5 * x^1 + 6 * x^2 + 7 * x ^ 3 => Đa thức 1 + Đa thức 2 = 5 + 7 * x^1 + 9 * x^2 + 7 * x^3 => Đa thức 1 - Đa thức 2 = -3 - 3 * x^1 - 3 * x^2 - 7 * x^3 => Đa thức 1 * Đa thức 2 = 4 + 13 * x^1 + 28 * x^2 + 34 * x^3 + 32 * x^4 + 21 * x^5. => Đa thức 1 / Đa thức 2: Tự nháp. Tình hình là mình chỉ mới làm được mỗi phép Cộng và Trừ, còn Tích và Thương thì thấy nó hơi khó khó sao ấy. Nên phiền mọi người có thể cho mình 1 chút gợi ý về 2 phép Nhân và Chia được không ? Hoặc là cho mình 1 cái “sườn” code cũng được và giải thích … blah blah … Đây là Source Code phép Cộng / Trừ 2 Đa thức: http://codepad.org/PTIFTOiO /* Bài 1: Nhập vào 2 đa thức rồi tính tổng, hiệu, tích, thương của 2 đa thức đó, kết quả trả về là 1 đa thức mới. Yêu cầu: Phải xuất ra đầy đủ định dạng của 1 đa thức. ĐA THỨC CÓ DẠNG: a0 * x^0 + a1 * x^1 + a2 * x^2 + ... + an * x^n Dữ liệu trong đa thức sẽ có: - Số bậc cao nhất của đa thức (n). - Danh sách các hệ số của đa thức (từ a0 --> an). */ typedef struct dathuc DT; struct dathuc { int bac; double *heso; }; std::istream& operator >> (std::istream &is, DT *x) { do { std::cout << "\nNhap so bac cua da thuc: "; is >> x->bac; if (x->bac < 1) std::cout << "\nSo bac cua da thuc khong hop le.\n"; } while (x->bac < 1); std::cout << "\nNhap cac he so (a0 -> an):\n"; x->heso = new double[x->bac + 1]; for (int i = 0; i <= x->bac; ++i) { std::cout << "\nHe so a" << i << ": "; is >> x->heso[i]; } return is; } std::ostream& operator << (std::ostream &os, DT *x) { int count = 0; os << x->heso[0]; x->heso[1] < 0 ? os << " - " << x->heso[1] * -1 << " * x" : os << " + " << x->heso[1] << " * x"; for (int i = 2; i <= x->bac; ++i, ++count) { x->heso[i] < 0 ? os << " - " << x->heso[i] * -1 << " * x^" << i : os << " + " << x->heso[i] << " * x^" << i; } os << std::endl; return os; } DT* Tong2DaThuc(DT *x, DT *y) { int Max = x->bac > y->bac ? x->bac : y->bac; int Min = x->bac < y->bac ? x->bac : y->bac; DT *kq = new DT; kq->bac = Max; kq->heso = new double[kq->bac + 1]; for (int i = 0; i <= Min; ++i) { kq->heso[i] = x->heso[i] + y->heso[i]; } if (Max == x->bac) { for (int i = Min + 1; i <= Max; ++i) { kq->heso[i] = x->heso[i]; } } else { for (int i = Min + 1; i <= Max; ++i) { kq->heso[i] = y->heso[i]; } } return kq; } DT* Hieu2DaThuc(DT *x, DT *y) { int Max = x->bac > y->bac ? x->bac : y->bac; int Min = x->bac < y->bac ? x->bac : y->bac; DT *kq = new DT; kq->bac = Max; kq->heso = new double[kq->bac + 1]; for (int i = 0; i <= Min; ++i) { kq->heso[i] = x->heso[i] - y->heso[i]; } if (Max == x->bac) { for (int i = Min + 1; i <= Max; ++i) { kq->heso[i] = x->heso[i]; } } else { for (int i = Min + 1; i <= Max; ++i) { kq->heso[i] = 0 - y->heso[i]; } } return kq; } int main() { DT *x = new DT; std::cout << "\n\t------------ NHAP DA THUC 1 ------------\t\n"; std::cin >> x; std::cout << x; DT *y = new DT; std::cout << "\n\t------------ NHAP DA THUC 2 ------------\t\n"; std::cin >> y; std::cout << y; std::cout << "\n\t----------------------------------------\t\n"; std::cout << "\nTong 2 da thuc tren: " << Tong2DaThuc(x, y) << std::endl; std::cout << "\nHieu 2 da thuc tren: " << Hieu2DaThuc(x, y) << std::endl; delete x; delete y; system("pause"); return 0; } Cảm ơn mọi người nhiều nhé Gio (Gió) October 3, 2016, 10:58am #2 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 3 Likes tcm (Người bí ẩn) October 3, 2016, 11:29am #3 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ả tntxtnt () October 3, 2016, 10:08pm #4 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 7x3 + 6x2 + 5x + 4 chia 3x2 + 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)*(x3-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 4x2/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)*(x2-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 6 Likes tcm (Người bí ẩn) October 5, 2016, 1:53pm #5 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 tntxtnt () October 5, 2016, 5:15pm #6 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 a0 coef[1] tương ứng với a1 … coef[10] tương ứng với a10 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 đó. 3 Likes tcm (Người bí ẩn) October 5, 2016, 10:54pm #7 tntxtnt: 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; } tntxtnt () October 6, 2016, 1:00am #8 lấy giấy ra nhân đi sẽ thấy, đừng có lười (5x3 + 4x2 + 3x + 2) * (7x2 + 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. 3 Likes tcm (Người bí ẩn) October 6, 2016, 9:59am #9 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 Gio (Gió) October 6, 2016, 11:03am #10 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; } 6 Likes tcm (Người bí ẩn) October 6, 2016, 12:57pm #11 Gio: 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 Gio (Gió) October 6, 2016, 1:17pm #12 fill chức năng trong này là gán tất cả heso=0 Khi nhân 2 đa thức aixi * bjxj = ai*bjxi+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]) 4 Likes tcm (Người bí ẩn) October 6, 2016, 1:34pm #13 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 Gio: kq->heso[i+j] += x->heso[i]*y->heso[j]; Thanks anh nhiều ! Manh_Nguyen4 (Mạnh Nguyễn) December 20, 2019, 10:12am #14 DaThuc tich(DaThuc a, DaThuc b) { DaThuc s; s.bac = a.bac + b.bac; for (int i = 0; i <= a.bac + b.bac; i++) { s.heso[i] = 0; for (int j = 0; j <= i; j++) s.heso[i] += a.heso[j] * b.heso[i - j]; } return s; } 4 Likes Nobita1 (.) December 26, 2019, 7:17am #15 đây là hướng dẫn mình code nhân 2 đa thức bằng linklist bạn có thể tham khảo nhé: manhcntt21/Data-structure-and-Algorithm/blob/master/linklist_stack/list.cpp #include <stdio.h> #include <stdlib.h> #include "list.h" #include <bits/stdc++.h> list_datatype *list; int number_element = 0; void init_list() { list = (list_datatype*)malloc(sizeof(list_datatype)); list->first = NULL; list->last = NULL; } void insert_head_node(int x) { Node *newnode = (Node*)malloc(sizeof(Node)); newnode->data = x; if(list->first == NULL) { list->first = newnode; list->last = newnode; number_element++; This file has been truncated. show original 1 Like DayNhauHoc's Discord Học C++ Free? Click Blog Dạy Nhau Học Tự Học Lập Trình 83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao? Từ khóa » Cộng 2 đa Thức Bằng Danh Sách Liên Kết đơn Biểu Diễn đa Thức Bằng Danh Sách Liên Kết | VnCoding Xử Lý đa Thức Bằng Danh Sách Liên Kết - TaiLieu.VN Thao Tác đa Thức Bằng Danh Sách Liên Kết đơn - Diễn Đàn Tin Học Cộng đa Thức 2 Biến Bằng Danh Sách Liên Kết [Linked List] - Cộng Hai đa Thức Dùng Danh Sách Kiên Kết đơn. Thuật Toán Cộng đa Thức Bằng Danh Sách Liên Kết đơn - D10cn4 Xử Lý đa Thức Bằng Danh Sách Liên Kết | PDF - Scribd Xử Lý đa Thức Bằng Danh Sách Liên Kết - TailieuXANH Biểu Diễn đa Thức Bằng Danh Sách Liên Kết đơn (linked_list) C++ Dễ ... Danh Sách Liên Kết đơn Trong C++ | TopDev Xu Ly Da Thuc Bang Danh Sach Lien Ket Ppt Converted - StuDocu [PDF] BÀI 2 DANH SÁCH - Topica Đề Thi Tham Khảo Môn Cấu Trúc Dữ Liệu Và Giải Thuật 27 | Xemtailieu
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?