Làm thế nào để lưu trữ đa thức?

Question

Các số nguyên có thể được sử dụng để lưu trữ các số riêng lẻ, nhưng không thể sử dụng các biểu thức toán học. Ví dụ, cho phép nói rằng tôi có các biểu hiện:

6x^2 + 5x + 3

Làm thế nào tôi lưu trữ các đa thức? Tôi có thể tạo đối tượng của riêng mình, nhưng tôi không thấy làm thế nào tôi có thể đại diện cho đa thức thông qua dữ liệu thành viên. Tôi không muốn tạo ra một hàm để đánh giá một đối số được truyền vào bởi vì tôi không chỉ cần đánh giá nó, mà còn cần phải thao tác biểu thức.

Là một tùy chọn duy nhất của vector hoặc có giải pháp thích hợp hơn không?

Answer 1

Cách đơn giản nhưng không hiệu quả là lưu trữ dưới dạng danh sách các hệ số. Ví dụ: đa thức trong câu hỏi sẽ trông giống như sau:

[6, 5, 3] 

Nếu cụm từ bị thiếu, hãy đặt số 0 vào vị trí của nó. Ví dụ, các đa thức 2x^3 - 4x + 7 sẽ được biểu diễn như thế này:

[2, 0, -4, 7] 

Các bậc của đa thức được đưa ra bởi chiều dài của một danh sách trừ. Biểu diễn này có một bất lợi nghiêm trọng: đối với các đa thức thưa thớt, danh sách sẽ chứa rất nhiều số không.

Biểu diễn hợp lý hơn về danh sách thuật ngữ đa thức thưa thớt là danh sách các thuật ngữ không đồng nhất, trong đó mỗi thuật ngữ là danh sách chứa thứ tự của cụm từ và hệ số của đơn hàng đó; mức độ đa thức được đưa ra theo thứ tự của thuật ngữ đầu tiên. Ví dụ, đa thức x^100+2x^2+1 sẽ được đại diện bởi danh sách này:

[[100, 1], [2, 2], [0, 1]] 

Là một ví dụ về cách hữu ích đại diện này là, cuốn sách SICP xây dựng một đơn giản nhưng rất hiệu quả symbolic algebra system sử dụng các đại diện thứ hai cho đa thức mô tả ở trên.

Answer 2

Danh sách không phải là tùy chọn duy nhất.

Bạn có thể sử dụng bản đồ (từ điển) lập bản đồ số mũ cho hệ số tương ứng.

Sử dụng bản đồ, ví dụ của bạn sẽ là

{2: 6, 1: 5, 0: 3} 

Một danh sách (hệ số, số mũ) cặp là khá chuẩn. Nếu bạn biết đa thức của bạn dày đặc, nghĩa là tất cả các vị trí số mũ là các số nguyên nhỏ trong khoảng 0 đến một số mũ nhỏ nhất, bạn có thể sử dụng mảng, như tôi thấy Óscar Lopez vừa mới đăng. :)

Answer 3

Vector/mảng là lựa chọn hiển nhiên. Tùy thuộc vào loại biểu thức bạn có thể xem xét một số loại vectơ thưa thớt (tùy chỉnh được thực hiện, tức là dựa trên từ điển hoặc thậm chí danh sách được liên kết nếu các biểu thức của bạn có 2-3 hệ số khác 0 x^100 + x).

Trong cả hai trường hợp hiển thị thông qua lớp/giao diện tùy chỉnh sẽ có lợi như bạn có thể thay thế triển khai sau này. Bạn có thể muốn cung cấp các hoạt động chuẩn (+, -, *, bằng) nếu bạn có kế hoạch viết nhiều mã thao tác biểu thức.

Answer 4

Bạn cần lưu trữ hai điều:

1. Mức độ đa thức của bạn (ví dụ: "3")
2. Một danh sách có chứa mỗi hệ số (ví dụ: "{3, 0, 2}")

Trong tiêu chuẩn C++, "std :: vector <>" và "std :: list <>" có thể thực hiện cả hai.

Answer 5

Bạn có thể biểu thị các biểu thức dưới dạng Cây biểu thức. Xem ví dụ .NET Expression Trees.

Điều này cho phép biểu thức phức tạp hơn nhiều so với đa thức đơn giản và các biểu thức đó cũng có thể sử dụng nhiều biến.

Trong .NET bạn có thể thao tác cây biểu thức dưới dạng cây và bạn có thể đánh giá nó như một hàm.

 Expression<Func<double,double>> polynomial = x => (x * x + 2 * x - 1); 
     double result = polynomial.Compile()(23.0); 

Answer 6

Chỉ lưu các hệ số trong mảng hoặc véc tơ. Ví dụ: trong C++ nếu bạn chỉ sử dụng hệ số nguyên, bạn có thể sử dụng std::vector<int> hoặc cho số thực, std::vector<double>. Sau đó, bạn chỉ cần đẩy các hệ số theo thứ tự và truy cập chúng theo số mũ thay đổi.

Ví dụ (một lần nữa trong C++), để lưu trữ 5 * x^3 + 9 * x - 2 bạn có thể làm:

std::vector<int> poly; 
    poly.push_back(-2); // x^0, acceesed with poly[0] 
    poly.push_back(9); // x^1, accessed with poly[1] 
    poly.push_back(0); // x^2, etc 
    poly.push_back(5); // x^3, etc 

Nếu bạn có lớn, thưa thớt, đa thức, thì có lẽ bạn muốn muốn sử dụng bản đồ thay vì vectơ. Nếu bạn có độ dài có kích thước cố định, thì bạn có thể sử dụng một mảng chiều dài cố định thay vì một vectơ.

Tôi đã sử dụng C++ làm ví dụ, nhưng cùng một lược đồ này có thể được sử dụng bằng bất kỳ ngôn ngữ nào.

Answer 7

Bạn cũng có thể biến nó thành reverse Polish notation:

6x^2 + 5x + 3 -> x 2^6 * x 5 * + 3 +

đâu x và con số này " đẩy "lên một ngăn xếp và các hoạt động (^, *, +) lấy hai giá trị cao nhất từ ​​ngăn xếp và thay thế chúng bằng kết quả của hoạt động. Cuối cùng, bạn nhận được giá trị kết quả trên stack.

Trong biểu mẫu này, thật dễ dàng để tính toán các biểu thức phức tạp tùy ý.

Biểu diễn này cũng gần với biểu diễn cây của các biểu thức trong đó các nút cây không phải lá đại diện cho các phép toán và chức năng và các nút lá dành cho các hằng số và các biến.

Điều tốt về cây là bạn cũng có thể dễ dàng đánh giá các biểu thức và bạn cũng có thể làm những việc như phân biệt biểu tượng trên chúng. Cả hai đều có tính chất đệ quy.

Answer 8

Phương pháp tiếp cận hướng đối tượng sẽ nói rằng Đa thức là tập hợp các Monome, và một Monomial gói gọn một hệ số và lũy thừa với nhau.

Cách tiếp cận này hoạt động khi khi bạn có một đa thức như thế này:

y(x) = x^1000 + 1 

Một cách tiếp cận đó gắn liền với một cấu trúc dữ liệu đến một trật tự đa thức sẽ là khủng khiếp lãng phí đối với trường hợp bệnh lý này.