Đa thức được biểu diễn bằng danh sách tuyến tính, mỗi số hạng của nó được lưu trữ bằng kiểu Sohang được định nghĩa trong C++ như sau:
struct Sohang {
int somu; //số mũ
float heso; //hệ số
};
Danh sách các số hạng được lưu trữ bằng mảng một chiều.
Xin hướng dẫn viết các chương trình con thực hiện các yêu cầu sau:
1. Sắp xếp mảng theo thứ tự giảm dần của các trường Somu; phương pháp sắp xếp là Chèn.
2. Chuẩn hóa đa thức: mỗi số mũ chỉ xuất hiện trong đa thức 01 lần. VD:
R(x)= x^3 + x^2 + x + 2x^2 + 2x + 2
sau khi chuẩn hóa: R(x)= x^3 + 3x^2 + 3x + 2
3. Nhân đa thức.
 

" />
  • Thứ Sáu, 07/05/2010 09:25 (GMT+7)

    Xử lý đa thức bằng ngôn ngữ C++

    Câu hỏi :

    Đa thức được biểu diễn bằng danh sách tuyến tính, mỗi số hạng của nó được lưu trữ bằng kiểu Sohang được định nghĩa trong C++ như sau:
    struct Sohang {
    int somu; //số mũ
    float heso; //hệ số
    };
    Danh sách các số hạng được lưu trữ bằng mảng một chiều.
    Xin hướng dẫn viết các chương trình con thực hiện các yêu cầu sau:
    1. Sắp xếp mảng theo thứ tự giảm dần của các trường Somu; phương pháp sắp xếp là Chèn.
    2. Chuẩn hóa đa thức: mỗi số mũ chỉ xuất hiện trong đa thức 01 lần. VD:
    R(x)= x^3 + x^2 + x + 2x^2 + 2x + 2
    sau khi chuẩn hóa: R(x)= x^3 + 3x^2 + 3x + 2
    3. Nhân đa thức.
     



    Trả lời :

    1. Ý tưởng sắp xếp danh sách theo giải thuật "Insertion Sort" như sau:
     Lặp xác định vị trí đúng cho từng số hạng i (từ 0 tới n) của đa thức:
     - Lặp tìm số hạng có số mũ lớn nhất từ vị trí i tới n
     - Hoán vị nó với số hạng i
     Từ thuật giải được viết bằng ngôn ngữ tự nhiên ở trên, ta dịch nó thành hàm SortItems() được viết bằng C++ như trong mã nguồn dưới đây.

     2. Chuẩn hóa đa thức: được thực hiện thông qua 2 bước chính:
     - Sắp xếp đa thức theo thứ tự số mũ giảm dần (gọi hàm SortItems() ở bước 1).
     - Duyệt tuần tự từ đầu đến cuối đa thức để cộng các số hạng liên tiếp có cùng số mũ lại thành 1 số hạng.
     Từ thuật giải được viết bằng ngôn ngữ tự nhiên ở trên, ta dịch nó thành hàm Chuanhoa() được viết bằng C++ như trong mã nguồn dưới đây.

     3. Nhân đa thức: được thực hiện thông qua 2 bước chính.
     - Lặp nhân từng số hạng của đa thức 1 với tất cả các số hạng của đa thức 2. Kết quả được lưu vào đa thức kết quả.
     - Chuẩn hóa đa thức kết quả.
     Từ thuật giải được viết bằng ngôn ngữ tự nhiên ở trên, ta dịch nó thành hàm Nhan() được viết bằng C++ như trong mã nguồn dưới đây.
     Sau đây là qui trình điển hình để viết 1 ứng dụng C++ nhỏ demo các hàm chức năng vừa giới thiệu. 

     1. Chạy VC++ 6.0, chọn chức năng File.New để hiển thị cửa sổ New, chọn mục Project, chọn mục "Win32 Console Application", chọn thư mục chứa Project ứng dụng ở Location, nhập tên Project quản lý ứng dụng (thí dụ là Dathuc) vào textbox "Project Name", chọn button Ok để tiếp tục.
     2. Khi cửa sổ Step 1 hiển thị, đánh dấu chọn vào mục "An empty project" rồi chọn button Finish để hoàn tất việc tạo Project mới.
     3. Chọn menu File.New, chọn mục Files, chọn mục "C++ Source File", nhập tên file vào textbox "FileName" (thí dụ là dathuc), rồi chọn button Ok để mở cửa sổ tạo file này.

     4. Viết code cho file như sau:
     #include <stdio.h>
     #include <math.h>
     //định nghĩa kiểu miêu tả 1 số mũ
     typedef struct {
     float heso; //hệ số
     int somu; //số mũ
     } Sohang;
     
     //hàm sắp xếp đa thức theo thứ tự số mũ giảm dần
     void SortItems (Sohang* dathuc, int soluong) {
     //định nghĩa các biến cần dùng
     int i,j, max;
     Sohang temp;
     //Lặp xác định vị trí đúng cho từ số mũ
     for (i = 0; i < soluong-1; i++) {
     //Tìm phần tử có số mũ lớn nhất từ vị trí i
     max = i;
     for (j = i + 1; j < soluong; j++)
     if (dathuc[max].somu < dathuc[j].somu)
     max = j;
     //hoán vị phần tử có số mũ lớn nhất về vị trí i
     temp = dathuc[i];
     dathuc[i] = dathuc[max];
     dathuc[max] = temp;
     }
     }
     
     //hàm chuẩn hóa đa thức, mỗi số mũ chỉ có 1 phần tử
     int Chuanhoa (Sohang* dathuc, int soluong) {
     //định nghĩa các biến cần dùng
     int i,j;
     Sohang* temp = new Sohang[soluong];
     //sắp xếp thự tự các phần tử trong đa thức
     SortItems(dathuc,soluong);
     //Lặp việc gộp các phần tử có số mũ giống nhau
     j = 0; temp[0] = dathuc[0];
     i = 1;
     while (i < soluong)
     if (temp[j].somu == dathuc[i].somu) {
     temp[j].heso += dathuc[i].heso;
     i++;
     } else {
     j++;
     temp[j] = dathuc[i];
     i++;
     }
     //copy kết quả về dathuc gốc
     for (i =0; i <= j ; i++)
     dathuc[i] = temp[i];
     //return số phần tử trong đa thức chuẩn hóa
     delete (temp);
     return j+1;
     }
     
     //hàm in đa thức để kiểm tra
     void Indathuc(Sohang* dathuc, int soluong) {
     int i;
     for (i = 0; i < soluong; i++)
     if (dathuc[i].heso <0)
     printf("%.2fx^%d ",dathuc[i].heso, dathuc[i].somu);
     else
     printf("+ %.2fx^%d ",fabs(dathuc[i].heso), dathuc[i].somu);
     printf("\n");
     }
     
     //hàm nhân 2 đa thức
     void Nhan (Sohang* dathuc1, int soluong1, Sohang* dathuc2, int soluong2, Sohang*& dathuc3, int& soluong3) {
     //định nghĩa các biến cần dùng
     int i,j,k;
     //cấp phát bộ nhớ chứa đa thức kết quả
     dathuc3 = new Sohang[soluong1*soluong2];
     k = 0;
     //lặp nhân từng số hạng của đa thức 1
     for (i=0; i <soluong1; i++)
     //với tất cả các số hạng của đa thức 2
     for (j = 0; j <soluong2; j++) {
     dathuc3[k].somu = dathuc1[i].somu+dathuc2[j].somu;
     dathuc3[k].heso = dathuc1[i].heso*dathuc2[j].heso;
     k++;
     }
     //chuẩn hóa đa thức kết quả
     soluong3 = Chuanhoa (dathuc3,k);
     }
     
     //chương trình chính thử dùng các hàm chức năng
     void main() {
     Sohang dathuc1[] = { {1,3}, {1,2}, {1,1}, {-2,2}, {2,1},{2,0}};
     //1. thử sắp xếp và in ra để kiểm tra
     printf("Đa thức gốc là: ");
     Indathuc(dathuc1,6);
     SortItems(dathuc1,6);
     printf("Đa thức được sort là : ");
     Indathuc(dathuc1,6);
     
     Sohang dathuc2[] = { {1,3}, {1,2}, {1,1}, {-2,2}, {2,1},{2,0}};
     //2. thử chuẩn hóa đa thức và in ra để kiểm tra
     printf("Đa thức gốc là : ");
     Indathuc(dathuc2,6);
     int somu = Chuanhoa(dathuc2,6);
     printf("Đa thức được chuẩn hóa là : ");
     Indathuc(dathuc2,somu);
     
     //3. thử nhân 2 đa thức và in ra để kiểm tra
     Sohang dathuc3[] = { {1,3}, {1,2}, {1,1}, {-2,2}, {2,1},{2,0}};
     Sohang dathuc4[] = { {1,3}, {1,2}, {1,1}, {-2,2}, {2,1},{2,0}};
     Sohang* dathuc5;
     int soluong;
     Nhan(dathuc3, 6, dathuc4, 6, dathuc5, soluong);
     printf("Đa thức kết quả là : ");
     Indathuc(dathuc5, soluong);
     }
     
     5. Chọn menu Build.Execute Dathuc.exe để dịch và chạy thử ứng dụng. Khi ứng dụng hiển thị cửa sổ làm việc, bạn hãy kiểm tra kết quả hiển thị các đa thức xem có đúng với yêu cầu không.
     

    Chuyên mục: Lập trình