Luận Văn Đại số đa thức và các phương án cài đặt

LỜI MỞ ĐẦU

Đại số đa thức là một lĩnh vực quan trọng của đại số. Nó là công cụ để nghiên cứu các phương trình đại số trong toán học và nhiều lý thuyết của Toán học hiện đại. Chúng ta đã tiếp xúc với các phép toán về đa thức ngay từ học trung học phổ thông. Với học sinh phổ thông việc thực hiện các phép toán đa thức là rất cần thiết mặc dầu mất khá nhiều thời gian.

Ngày nay tin học đã thâm nhập vào tất cả mọi hoạt động của xã hội loài người và máy tính điện tử trở thành công cụ đắc lực không chỉ giảm nhẹ lao động (kể cả lao động có trí tuệ) mà còn giúp thêm cho con người những năng lực mới mà trước đây chúng ta khó hình dung được. Việc xây dựng một chương trình có thể thực hiện được các phép tính đa thức nhằm hiểu sâu hơn các vấn đề về cài đặt dữ liệu và các giải thuật thích hợp với các dữ liệu ấy. Nó sẽ là một công việc có ích cho bản thân đồng thời có thể giúp các học sinh trung học tự kiểm tra các kết quả tính toán khi làm toán với các đa thức.

Với ý nghĩa đó đề tài đã tiến hành nghiên cứu các vấn đề về đại số đa thức và các phương án cài đặt đa thức. Nội dung của đề tài được trình bày trong năm chương, ngoài phần mở đầu, kết luận và tài liệu tham khảo. Kết quả chính thu được của đề tài:

Chương 1: Đa thức và phép tính đa thức

Trong chương này trình bày đa thức như là một tổng đại số của các đơn thức một biến và các phép toán cơ bản trên tập hợp các đa thức một biến (cộng, trừ, nhân, chia, giá trị của đa thức tại một điểm và khái niệm về ước chung lớn nhất của hai đa thức).


Chương 2: Cài đặt đa thức bằng mảng

Dựa vào định nghĩa cũng như các phép toán về đa thức đưa ra được cách lưu trữ đa thức trong mảng là mảng một chiều gồm -1 -> n phần tử (n là một số cố định cho trước), trong đó phần tử đầu tiên lưu giá trị bậc của đa thức. Từ đó cài đặt các phép toán: cộng, trừ, nhân, tính giá trị của đa thức và tìm ước chung lớn nhất của hai đa thức trên mảng. Tuy nhiên với cách lưu trữ này cũng có một số thuận lợi và khó khăn khi cài đặt chương trình.

Chương 3: Cài đặt đa thức bẳng mảng con trỏ

Đa thức được lưu trữ bởi một bản ghi gồm hai trường, một trường để lưu bậc của đa thức trường còn lại là mảng con trỏ. Trong quá trình cài đặt các phép tóan, khi cần thiết để lưu các hệ số của đa thức tương ứng với lũy thừa ta mới cấp phát biến động tương ứng với chỉ số của mảng con trỏ.

Dựa trên lưu trữ đa thức bằng mảng con trỏ để thực hiện các phép toán đối với đa thức, cài đặt thuật toán cũng giống như đối với mảng.

Chương 4: Cài đặt đa thức bảng danh sách liên kết

Các phương pháp lưu trữ đã trình bày ở trên dễ dàng cài đặt nhưng rất tốn bộ nhớ. Để khắc phục bằng cách lưu trữ đa thức dưới dạng là một danh sách liên kết bao gồm các nút được liên kết với nhau. Mỗi nút là gồm ba trường: hệ số, lũy thừa và một con trỏ để lưu địa chỉ của nút tiếp theo trong danh sách, ngoài ra còn có một nút để chứa bậc của đa thức, nút này là nút đầu trong danh sách.

Lưu trữ bằng danh sách liên kết phức tạp hơn đối với mảng và mảng con trỏ, vì vậy việc thực hiện cài đặt các phép toán khó khăn hơn. Bằng cách lưu trữ này cũng đã thực hiện thành công việc cài đặt các phép toán cộng, trừ, nhân, chia, tính giá trị và tìm ước chung lớn nhất của hai đa thức.

Chương 5: Thiết kế đồ họa

Để giao diện thân thiện hơn với người sử dụng, đề tài còn nghiên cứu về kỹ thuật đồ họa trong Pascal trong việc tạo menu, dùng tiếng việt trong Pascal và có sử dụng ngắt 33h và các hàm của BIOS để điều khiển chuột.


Đề tài được hoàn thành dưới sự hướng dẫn của thầy giáo Tiến sỹ Nguyễn Trung Hòa. Nhân dịp này em xin được bày tỏ lòng biết ơn sâu sắc tới thầy giáo hướng dẫn vì sự giúp đỡ và chỉ dẫn hết sức nhiệt tình, chu đáo.

Em xin gửi lời cảm ơn tới Nhà trường, khoa Công nghệ Thông tin đã tạo điều kiện cho chúng em được học tập và rèn luyện trong suốt bốn năm học vừa qua.

Em xin tỏ lòng biết ơn sâu sắc tới các thầy giáo, cô giáo, bạn bè trong khoa đã giúp đỡ trong quá trình học tập và nghiên cứu.

Đề tài không tránh khỏi nhiều thiếu sót. Em kính mong nhận được sự chỉ bảo của các thầy giáo, cô giáo và sự góp ý của các bạn trong khoa.



Sinh viên

Trần Thị Lê Na


MỤC LỤC

Trang

Lời mở đầu 1

Chương 1: Đa thức và các phép toán đa thức 4

1. Định nghĩa đa thức 4

2. Định nghĩa các phép toán trên đa thức 4

2.1 Cộng hai đa thức 4

2.2 Trừ hai đa thức 5

2.3 Nhân hai đa thức 5

2.4 Chia hai đa thức 6

2.5 Tính giá trị của đa thức 6

2.6 Ước chung lớn nhất của hai đa thức 7

Chương 2: Cài đặt đa thức bằng mảng 8

1. Lý do cài đặt bằng mảng 8

2. Định nghĩa kiểu mảng 10

3. Cách khai báo 10

4. Ý tưởng giải thuật 11

5. Cài đặt đa thức 13

Chương 3: Cài đặt đa thức bằng mảng con trỏ 18

1. Lý do cài đặt bằng mảng con trỏ 18

2. Cách khai báo 18

3. Cách lưu trữ đa thức 19

4. Cài đặt chương trình 21

Chương 4: Cài đặt đa thức bằng danh sách liên kết 28

1. Lý do cài đặt bằng danh sách liên kết 28

2. Danh sách nối đơn 28

3. Cách lưu trữ 30

4. Cài đặt chương trình 33

Chương 5: Thiết kế đồ họa 43

1. Cách sử dụng Font tiếng việt trong Pascal 43

2. Cách sử dụng chuột trong Pascal 44

3. Thiết kế màn hình chính 49

Kết luận 50

Mục lục 51

Tài liệu tham khảo 52