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
54 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2439 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Khóa luận Đại số đa thức và các phương án cài đặt, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
CHƯƠNG 1: ĐA THỨC VÀ CÁC PHÉP TOÁN ĐA THỨC
Định nghĩa đa thức
Biểu thức hình thức:
(1) f(x) = anxn + an-1xn-1 + ... + a1x + a0
- Trong đó an, an-1, ..., a1, a0 Є K (K là một trường tuỳ ý) với an ≠ 0, được gọi là đa thức bậc n. Ta viết degf = n có nghĩa là bậc của f bằng n.
- Các phần tử an, an-1, ..., a1, a0 Є K được gọi là các hệ tử, x là ẩn
- aixi, i = là các hạng tử của đa thức f(x)
- anxn là hạng tử cao nhất của đa thức f(x).
- a0 là hạng tử tự do của đa thức f(X).
- Đa thức f(x) = anxn, a ≠ 0 còn được gọi là đơn thức bậc n.
- Trong trường hợp a0 ≠ 0, n = 0 thì f(x) có bậc bằng 0.
- Đa thức f(x) được gọi là đa thức không nếu và chỉ nếu tất cả các hệ số của nó bằng 0.
- Nhấn mạnh ở đây rằng ta luôn đồng nhất biểu thức (1) với các biểu thức dẫn dắt từ (1), tức là tổng theo thứ tự tuỳ ý các đơn thức tham gia trong (1). Như vậy biểu thức viết theo thứ tự ngược lại với (1).
(2) a0 + a1x + ... + an-1xn-1 + anxn
cùng là một đa thức g(x) đồng nhất với f(x).
- Khi K là một trường số thực hoặc phức thay cho thuật ngữ hệ tử và hạng tử ta sẽ dùng thuật ngữ hệ số và số hạng.
Định nghĩa các phép toán trên đa thức
2.1) Phép cộng hai đa thức
Cho f(x) = anxn + an-1xn-1 + ... + a1x + a0
và g(x) = bnxn + bn-1xn-1 + ... + b1x + b0,
là các đa thức với hệ số trong K.
Khi đó đa thức:
f(x) + g(x) = (an + bn) xn + (an-1 + bn-1) xn-1 + ... + (a1 + b1)x + (a0 + b0)
được gọi là tổng của hai đa thức f(x) và g(x).
Ở đây nếu bậc của hai đa thức không bằng nhau ta viết thêm các số hạng với hệ số bằng không.
2.2) Trừ hai đa thức
Phép trừ hai đa thức cũng tương tự như phép cộng hai đa thức:
Cho f(x) = anxn + an-1xn-1 + ... + a1x + a0
và g(x) = bnxn + bn-1xn-1 + ... + b1x + b0,
là các đa thức với hệ số trong K.
Khi đó đa thức:
f(x) - g(x) = (an - bn) xn + (an-1 - bn-1) xn-1 + ... + (a1 - b1)x + (a0 - b0)
được gọi là hiệu của hai đa thức f(x) và g(x).
Ở đây nếu bậc của hai đa thức không bằng nhau ta viết thêm các số hạng với hệ số bằng không.
2.3) Phép nhân hai đa thức
Cho hai đa thức:
f(x) = anxn + an-1xn-1 + ... + a1x + a0, an ≠ 0
g(x) = bmxm + bm-1xm-1 + ... + b1x + b0, bm ≠ 0
thì
f(x)g(x) = dn+mxn+m + dn+m-1xn+m-1 + ... + d1 x+ d0
trong đó
di = akbj, i = 0, 1, ..., n +m.
Hiển nhiên
degf(X)g(X) = degf(X) + degg(X)
f(X)g(X) = g(X)f(X)
và f(X)(r(X) + s(X)) = f(X)r(X) + f(X)s(X)
Phép chia hai đa thức
Giả sử f, g Є K[x] và g ≠ 0 khi đó f có thể viết duy nhất dưới dạng:
f = gq + r
Với q, r Є K[x] và degr < degq
Biểu thức (1) được gọi là phép chia có dư đa thức f(x) cho đa thức g(x) ≠ 0. Đa thức f(x) được gọi là đa thức bị chia, đa thức g(x) là đa thức chia, đa thức q(x) là thương còn đa thức r(x) là phần dư của phép chia.
Nếu r(x) = 0 ta nói f(x) chia hết cho g(x), khi đó ta cũng nói g(x) là một ước của f(x).
2.5) Tính giá trị của đa thức.
Cho đa thức f(x) = anxn + an-1xn-1 + ... + a0.
Với các hệ số của đa thức a0, a1, ... , an-1, an và x cho trước.
Để tính giá trị của đa thức ta dùng thuật toán Horner
P = (... ((anx + an-1)x + an-2)x + ... + a1)x + a0, trong đó quá trình truy hồi được tiến hành như sau:
Pn = an
Pn-1 = Pnx + an-1
...
P = P0 = P1x + a0
P := Px + ak
Với k =
2.6) Ước chung lớn nhất của hai đa thức.
Nhắc lại rằng g Є K[x], g ≠ 0 được gọi là ước chung của f Є K[x] nếu f chia hết cho g và ta viết f | g.
Cho f, g, h Є K[x]. Ta nói
+ h là ước chung của f và g nếu h | f và h | g.
+ h là ước chung lớn nhất (UCLN) của f và g, nếu nó là ước chung của f và g và chia hết cho mọi ước chung khác.
Áp dụng thuật chia ECLIDE ta có thể tìm ước chung lớn nhất của hai đa thức f và g không đồng thời bằng không.
Thật vậy ta coi g ≠ 0. Chia f cho g ta được phần dư r1. Nếu r1 ≠ 0, ta chia g cho r1, được phần dư r2. Cứ tiếp tục vì bậc của các phần dư giảm dần nên tồn tại k ≥ 1 sao cho rk-1 | rk. Ta sẽ kiêm lại khi đó rằng.
rk = (f, g)
Thật vậy xuất phát từ đẳng thức rk-1 = rkhk+1
Suy ra rk | rk-2 và cũng vậy rk|rk-3. Cứ như vậy ta nhận được
rk|g và rk|f
Bây giờ nếu φ là một ước chung tuỳ ý của f và g thì φ | r1 và cũng vậy φ | r2. Cứ như thế ta lại nhận được φ | rk
CHƯƠNG 2: CÀI ĐẶT ĐA THỨC BẰNG MẢNG
Lý do cài đặt bằng mảng
Cấu trúc mảng là cấu trúc rất quen thuộc ở mọi ngôn ngữ lập trình. Đặc biệt trong ngôn ngữ lập trình Pascal. Nếu như chúng ta biết cách khai thác và sử dụng sẽ giúp chúng ta giải quyết được nhiều bài toán.
1.1) Ưu điểm:
Dùng mảng có lợi điểm là có thể đọc ngược, đọc xuôi một cách dễ dàng và truy xuất đến một phần tử mảng cũng hết sức nhanh chóng.
Mảng được lưu trữ kế tiếp nên việc truy nhập vào phần tử của mảng được thực hiện trực tiếp dựa vào địa chỉ tính được, nên tốc độ nhanh và đồng đều đối với mọi phần tử.
2.2) Nhược điểm:
Mặc dầu có rất nhiều ứng dụng ở đó mảng có thể được sử dụng để thể hiện mối quan hệ về cấu trúc giữa các phần tử dữ liệu. Tuy nhiên cũng lộ rõ một số nhược điểm như:
Không có phép bổ sung phần tử hoặc loại bỏ phần tử được thực hiện đối với mảng.
Không tận dụng được các vùng nhớ có kích thước nhớ nhỏ vì các thành phần của mảng cần được lưu trữ một cách kế tiếp.
Khi dùng mảng đều phải khai báo trước kích thước của mảng. Trong khi đó chúng ta lại không thể dự đoán trước kích thước của dữ liệu vì thế thường xảy ra tình trạng: khai báo kích thước gây lãng phí bộ nhớ hoặc ngược lại khai báo thiếu thì máy bị treo không chạy nổi chương trình.
Ví dụ cộng (3x^2 – x + 3)
Với (2x^2 + x - 3)
Để có kết quả là (5x^2)
Có thể dùng mảng một chiều để biểu diễn: hệ số của số hạng xi sẽ được lưu trữ ở phần tử thứ i của mảng một chiều, ta quy ước bậc của đa thức được lưu trữ ở phần tử -1. Như vậy phép cộng hai đa thức chính là phép cộng hai mảng. Cách biểu diễn đã đưa tới phép xử lý đơn giản. Tuy nhiên ta cũng thấy một số nhược điểm:
Đa thức: 3x^2 – x + 3 được lưu trữ
Hệ số
Chỉ số mảng -1 0 1 2
2
3
-1
3
Các hệ số tương ứng các lũy thừa
Đa thức: 2x^2 + x – 3 được lưu trữ
-1 0 1 2
2
2
1
-3
Kết quả khi cộng hai đa thức trên:
-1 0 1 2
2
5
0
0
Ta thấy kết quả là một mảng mới biểu diễn nhiều phần tử bằng 0, nó vẫn chiếm ô nhớ trong bộ nhớ, trong khi đó các giá trị đó không sử dụng tới khuynh hướng này tạo ra sự lãng phí bộ nhớ rất rõ.
Định nghĩa kiểu mảng.
Kiểu mảng (Array) là một kiểu dữ liệu có cấu trúc gồm một số cố định các phần tử có cùng một kiểu dữ liệu đặt sau tên mảng. Nói cách khác, dữ liệu kiểu mảng là một mảng (dãy) của nhiều dữ liệu thuộc một kiểu khác.
Kiểu mảng có những đặc trưng sau:
Các phần tử của mảng phải cùng kiểu, kiểu đó gọi là kiểu cơ sở hay kiểu thành phần.
Các phần tử trong mảng có chỉ số, tức là vị trí số thứ tự của chúng trong mảng. Kiểu của chỉ số phải là kiểu rời rạc. Mỗi phần tử có thể được truy nhập trực tiếp thông qua chỉ số.
Các chỉ số là các biểu thức nằm trong dấu ngoặc vuôn [] đặt ngay sau tên mảng và kiểu của chúng gọi là kiểu chỉ số.
Kiểu chỉ số là một kiểu nguyên hoặc miền con, giá trị của chỉ số có thể là âm hoặc dương.
Cách khai báo.
3.1) Khai báo gián tiếp
TYPE
= Array[] of ;
VAR
:;
3.2) Khai báo trực tiếp
VAR
= Array[] of ;
Ý tưởng giải thuật
Bài toán đặt ra phải xử lý được các phép toán trên đa thức cài đặt bằng mảng.
Đặc trưng của đa thức là một bộ hệ số, mỗi hệ số tương ứng với số luỹ thừa và bậc cuả đa thức.
f(x) = anxn + an-1xn-1 + ... + a0, an ≠ 0
Biểu diễn bộ hệ số, và bậc của đa thức trên cùng mảng một chiều.
Các chỉ số -1 0 1 ... n-2 n-1 n
n
a0
a1
...
an-2
an-1
an
...
Hệ số
Các hệ số tương ứng các lũy thừa
Khai báo đa thức a:
Var
a:array[-1..maxbac] of real;
Trong đó:
maxbac là một số cố định cho trước.
a[-1] = n là bậc của đa thức.
Cộng hai đa thức
Cho hai đa thức f(x) và g(x) như sau:
f(x) = anxn + an-1xn-1 + ... + a0, an ≠ 0
g(x) = bmxm + bm-1xm-1 + ... + b0, bm ≠ 0
* Phép tính cộng hai đa thức được thực hiện như sau:
Ta biểu diễn từng đa thức dưới dạng mảng một chiều, trong đó phần tử đầu tiên của mảng chính là bậc của đa thức, các phần tử còn lại chứa hệ số tương ứng với luỹ thừa của từng số hạng.
Phép cộng hai đa thức được thực hiện là phép tính cộng lần lượt các hệ số cùng luỹ thừa lại với nhau. Ở đây nếu luỹ thừa của hai đa thức không bằng nhau ta viết thêm các số hạng với hệ số bằng không.
Khi cộng hai đa thức với nhau ta sẽ được một đa thức mới, đa thức c với:
c[i] = a[i] + b[i] (i: 0->max(n,m))
Trừ hai đa thức
Thực hiện phép trừ đa thức a cho đa thức b
Tương tự như phép tính cộng hai đa thức, ta chỉ thay dấu cộng bởi dấu trừ.
Nhân hai đa thức
Cho hai đa thức f(x) và g(x) như sau:
f(x) = anxn + an-1xn-1 + ... + a0, an ≠ 0
g(x) = bmxm + bm-1xm-1 + ... + b0, bm ≠ 0
+ Biểu diễn đa thức a:
Nhân hai đa thức thực hiện như sau:
For i:=0 to n+m do
Begin
c[i]:=0;
For k:=0 to i do
If (k<=n) and (i-k<m) then
c[i]:= c[i] + a[k]*b[i-k] ;
End;
Chia hai đa thức
Cho hai đa thức f(x) và g(x) như sau:
f(x) = anxn + an-1xn-1 + ... + a0, an ≠ 0
g(x) = bmxm + bm-1xm-1 + ... + b0, bm ≠ 0
Dựa vào định nghĩa phép chia hai đa thức đã trình bày ở chương 1 để thực hiện phép chia đa thức a cho đa thức b.
4.5) Tính giá trị của đa thức
Áp dụng thuật toán Horner để tính giá trị của đa thức.
4.6) Tìm ước chung lớn nhất của hai đa thức
Áp dụng thuật chia ECLIDE
Cài đặt chương trình
Cộng hai đa thức.
Procedure CongDT(a,b:mang;Var c:mang);
Var i,n,m,max:shortint;
Begin
n:=round(a[-1]);m:=round(b[-1]);
If n>m then max:=n
Else max:=m;
For i:=0 to max do
c[i]:=a[i]+b[i];
i:=max;
While (c[i]=0) and (i>=0) do dec(i);
c[-1]:=i;
End;
Trừ hai đa thức.
Procedure TruDT(a,b:mang;Var c:mang);
Var i,n,m,max:shortint;
Begin
n:=round(a[-1]);m:=round(b[-1]);
If n>m then max:=n
Else max:=m;
For i:=0 to max do
c[i]:=a[i] - b[i];
i:=max;
While (c[i]=0) and (i>=0) do dec(i);
c[-1]:=i;
End;
Nhân hai đa thức.
Procedure NhanDT(a,b:mang; Var c:mang);
Var i,k,n,m:shortint;
Begin
n:=round(a[-1]);m:=round(b[-1]);
If (n<0) or (m<0) then c[-1]:=-1
Else
Begin
For i:=0 to n+m do
Begin
c[i]:=0;
For k:=0 to i do
If (k<=n) and (i-k<=m) then
c[i]:=c[i]+a[k]*b[i-k];
End;
c[-1]:=n+m;
End;
End;
Chia hai đa thức
Procedure ChiaDT(a,b:mang; Var q,r:mang);
Var m,l,h,n,i:shortint;
q1,t:mang;
Begin
If a[-1]<b[-1] then r:=a
Else Begin
q[-1]:=a[-1]-b[-1];
For i:=0 to round(q[-1]) do q[i]:=0;
m:=round(b[-1]);
While a[-1]>=m do
Begin
n:=round(a[-1]);
l:=n-m;
q1[-1]:=l;
For i:=0 to l do q1[i]:=0;
q1[l]:=a[n]/b[m];
q[l]:=q1[l];
NhanDT(q1,b,t);
TruDT(a,t,r);
a:=r;
End;
End;
End;
Tính giá trị của đa thức
Function GiaTri(x:real; a:mang):real;
Var n,i:shortint;
t:real;
Begin
n:=round(a[-1]);
If n>=0 then
Begin
t:=a[n];
For i:=1 to n do t:=t*x+a[n-i]
End;
GiaTri:=t;
End;
Tìm ước chung lớn nhất của hai đa thức
Procedure UCLN(a,b:mang; var c:mang);
Var q,r:mang;
Begin
While b[-1]>=0 do
Begin
ChiaDT(a,b,q,r);
a:=b;
b:=r;
End;
c:=a;
If c[-1]=0 then c[0]:=1;
End;
CHƯƠNG 3: CÀI ĐẶT ĐA THỨC BẰNG MẢNG ĐỘNG
Lý do cài đặt bằng mảng động.
Bài toán mà chúng ta đã cài đặt bằng mảng ở trên, biến mà chúng ta dùng là biến tĩnh, là biến có kích thước, kiểu dữ liệu cố định và địa chỉ của biến là không đổi. Các biến này tồn tại trong suốt quá trình chạy chương trình. Đó là lý do gây lãng phí bộ nhớ.
Để khắc phục nhược điểm này ngôn ngữ lập trình pascal cho phép sử dụng biến động. Biến động không được sinh ra lúc bắt đầu chương trình mà sinh ra trong quá trình thực hiện chương trình. Sau khi thực hiện xong có thể xoá khỏi bộ nhớ. Nói cách khác, mặc dù gặp khai báo biến nhưng máy không cấp phát ô nhớ cho biến mà chỉ cấp phát khi nào biến cần tới. Sau khi dùng xong có thể xoá để tiết kiệm bộ nhớ.
Tuy nhiên biến động cũng có một số nhược điểm là không có địa chỉ nhất định nên không thể truy cập đến chúng được. Để khắc phục nhược điểm nhà thiết kế phần mềm cung cấp cho chúng ta một loại biến đặc biệt, biến này chứa địa chỉ của biến động gọi là biến con trỏ. Biến con trỏ cho phép thao tác trên các giá trị địa chỉ. Mục đích của biến con trỏ giúp khai thác bộ nhớ, tiết kiệm bộ nhớ, an toàn dữ liệu.
Cách khai báo
2.1) Kiểu con trỏ
Type
= ;
2.2) Biến con trỏ
Var
: ^;
2.3) Lấy nội dung của một biến con trỏ đang trỏ đến
^
2.4) Tạo biến động
Dùng thủ tục New(Var ptr:Pointer)
Tạo ra một vùng biến động có kiểu và kích thước theo quy định.
Hướng con trỏ đến vùng biến động này.
2.5) Xoá biến động
- Thủ tục Release(Var HeapPtr : Pointer);
Thủ tục cho phép xoá toàn bộ vùng nhớ Heap đã cấp phát tính từ điểm đã đánh dấu.
Đặt con trỏ HeapPtr tới địa chỉ của biến động đã được đánh dấu xoá bằng thủ tục Mark trong Heap. Khi thi hành thủ tục Release sẽ xoá tất cả vùng nhớ nằm ở phía trên địa chỉ này. Không xoá những vùng nhớ được các biến động sử dụng ở giữa Heap.
- Thủ tục Dispose(Var Ptr : Pointer);
Thủ tục xoá một vùng nhớ do thủ tục New cấp phát cho một biến động.
Cách lưu trữ đa thức
Cách lưu trữ đa thức như sau:
Type
mang = array[0..maxbac] of ^real;
dt = Record
m: mang;
bac: shortint;
End;
Var
a: ^dt;
Trong đó: maxbac: một số cố định cho trước.
a.bac: bậc của đa thức.
a.m[0]^ .. a.m[a.bac]^: hệ số tương ứng với luỹ thừa.
Dựa vào cách lưu trữ đó, ta cài đặt các phép toán của đa thức hoàn toàn giống như cách cài đặt đa thức bằng mảng.
* Ví dụ minh họa thực hiện nhân hai đa thức
Cho hai đa thức:
Đa thức a: ‘7x^7 + 3x^5 + 5x + 1’
bậc 0 1 2 3 4 5 6 7 8 ... 100
1
5
3
7
7
...
Đa thức b: ‘-7x^7 + 2x^2 + 3’
bậc 0 1 2 3 4 5 6 7 8 ... 100
3
2
-7
7
...
Sau khi thực hiện phép nhân hai đa thức ta sẽ được một đa thức mới:
bậc 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 … 100
3
15
2
10
9
-8
35
-14
21
-49
14
...
Cài đặt chương trình.
4.1) Cộng hai đa thức
Procedure MCT_CongDT( a1,b1:dt;var c1:dt);
Var
i,n,m,max:shortint;
Begin
m:=a1.bac; n:=b1.bac;
If n>m then max:=n else max:=m;
For i:=0 to max do
If (a1.m[i]nil) then
Begin
new(c1.m[i]);
If b1.m[i]nil then
Begin
c1.m[i]^:=a1.m[i]^+b1.m[i]^;
If c1.m[i]^=0 then
Begin
dispose(c1.m[i]);
c1.m[i]:=nil;
End;
End
Else c1.m[i]^:=a1.m[i]^
End
Else if b1.m[i]nil then
Begin
new(c1.m[i]);
c1.m[i]^:=b1.m[i]^;
End;
i:=max;
While (c1.m[i]=nil) and (i>=0) do dec(i);
c1.bac:=i;
End;
4.2) Trừ hai đa thức
Procedure MCT_Trudt(a1,b1:dt; var c1:dt);
Var
i,n,m,max:shortint;
Begin
m:=a1.bac; n:=b1.bac;
If n>m then max:=n else max:=m;
For i:=0 to max do
If (a1.m[i]nil) then
Begin
new(c1.m[i]);
If b1.m[i]nil then
Begin
c1.m[i]^:=a1.m[i]^-b1.m[i]^;
If c1.m[i]^=0 then
Begin
dispose(c1.m[i]);
c1.m[i]:=nil;
End;
End
Else c1.m[i]^:=a1.m[i]^
End
Else if b1.m[i]nil then
Begin
new(c1.m[i]);
c1.m[i]^:=-b1.m[i]^;
End;
i:=max;
While (c1.m[i]=nil) and (i>=0) do dec(i);
c1.bac:=i;
End;
4.3) Nhân hai đa thức
Procedure MCT_NhanDT(a1,b1:dt;var c1:dt);
Var
i,j,k,n,m,max:shortint;
t:real;
Begin
m:=a1.bac; n:=b1.bac;
If (m<0) or (n<0) then c1.bac:=-1
Else
Begin
For i:=0 to m+n do
Begin
c1.m[i]:=nil;
t:=0;
For k:=0 to i do
(b1.m[ik]nil) then t:=t+a1.m[k]^*b1.m[i-k]^;
If (knil) and
If t0 then
Begin
new(c1.m[i]);
c1.m[i]^:=t;
End;
End;
c1.bac:=m+n;
End
End;
4.4) Chia hai đa thức
Procedure MCT_ChiaDT(a1,b1:dt; var q1,r1:dt);
Var
i,j,k,m,n,l:shortint;
q2,t1:dt;
Begin
If a1.bac<b1.bac then r1:=a1
Else
Begin
q1.bac:=a1.bac-b1.bac;
For i:=0 to q1.bac do q1.m[i]:=nil;
n:=b1.bac;
While a1.bac>=n do
Begin
m:=a1.bac;
l:=m-n;
q2.bac:=l;
For i:=0 to l do q2.m[i]:=nil;
new(q2.m[l]);
q2.m[l]^:=a1.m[m]^/b1.m[n]^;
new(q1.m[l]);
q1.m[l]^:=q2.m[l]^;
MCT_NhanDT(q2,b1,t1);
MCT_TruDT(a1,t1,r1);
a1:=r1;
End;
End;
End;
4.5) Tính giá trị của đa thức
Function MCT_GT(a1:dt;x1:real):real;
Var
i,n:shortint;
t:real;
Begin
n:=a1.bac;
If n>=0 then
Begin
t:=a1.m[n]^;
For i:=1 to n do
Begin
If a1.m[n-i]nil then t:=t*x1+a1.m[n-i]^
Else t:=t*x1
End;
End;
MCT_GT:=t;
End;
4.6) Ước chung lớn nhất của hai đa thức
Procedure MCT_TinhUCLN(a1,b1:dt;var c1:dt);
Var
q1,r1:dt;
Begin
While b1.bac>=0 do
Begin
MCT_ChiaDT(a1,b1,q1,r1);
a1:=b1;
b1:=r1;
End;
c1:=a1;
if c1.bac=0 then c1.m[0]^:=1;
End;
CHƯƠNG 4: CÀI ĐẶT ĐA THỨC BẰNG DANH SÁCH LIÊN KẾT
Lý do cài đặt bằng danh sách liên kết
Điểm mạnh của mảng là tốc độ truy nhập. Do tất cả các phần tử của mảng được bố trí cạnh nhau trong bộ nhớ của máy tính, nên ta có thể đi thẳng đến bất kỳ phần tử nào thông qua chỉ số. Với danh sách liên kết con đường đi dài hơn: Trước hết phải đi tới phần tử đầu tiên hoặc phần tử cuối cùng, rồi từ đó lần lượt chuyển từ phần tử này qua phần tử khác cho tới phần tử cần truy nhập. Do vậy ở những tình huống mà tốc độ cần hơn bộ nhớ thì mảng hay hơn danh sách liên kết.
Trong trường hợp cần thiết bộ nhớ hoặc cần thường xuyên thêm vào, bớt đi các phần tử thì danh sách liên kết tiện hơn mảng. Để chèn một phần tử vào mảng ta phải di chuyển nhiều phần tử để dành chỗ cho phần tử mới. Khi huỷ một phần tử cũng phải dồn các phần tử bên dưới để đè lên phần tử cần huỷ. Để làm điều này đối với danh sách liên kết ta chỉ cần thực hiện các phép thay đổi địa chỉ một cách thích hợp.
Danh sách nối đơn
2.1) Nguyên tắc
Ở đây mỗi phần tử của danh sách được lưu trữ trong một phần tử nhỏ mà ta gọi là nút. Mỗi nút bao gồm một số từ máy kế tiếp. Các nút này có thể nằm bất kỳ ở chỗ nào trong bộ nhớ. Trong mỗi nút, ngoài phần thông tin ứng với một phần tử, còn có chứa địa chỉ của phần tử đứng sau nó trong danh sách. Qui các của mỗi nút có thể hình dung như sau:
INFO LINK
Trường INFO chứa thông tin của phần tử.
Trường LINK chứa địa chỉ (mối nối) nút tiếp theo.
Riêng nút cuối cùng thì không có nút đứng sau nó nên mối nối ở nút này là một “địa chỉ đặc biệt” chỉ để dùng để đánh dấu nút kết thúc danh sách ta ký hiệu là NULL.
Để có thể truy nhập được vào mọi nút trong danh sách, tất nhiên phải truy nhập vào nút đầu tiên, nghĩa là cần có con trỏ L trỏ tới nút đầu tiên này.
Nếu dùng mũi tên để chỉ mối nối, ta sẽ có một hình ảnh một danh sách nối đơn như sau:
L
A
B
C
D
2.2) Một số thao tác đối với danh sách lưu trữ đa thức.
- Kiểm tra đa thức 0
- Thực hiện phép loại bỏ một nút ra khỏi danh sách
- Thực hiện phép chuẩn hoá cho một đa thức
+ Sắp xếp lại đa thức nhập vào theo số mũ giảm dần
+ Gộp những số mũ giống nhau
+ Loại bỏ những hệ số không có nghĩa
Cách lưu trữ đa thức
Type
Kieudl=record
hso:real;
lth:byte;
End;
Trosh=^Kieush;
kieush=record
nd:kieudl;
ke:trosh;
End;
dt = record
trodt:pointer;
bac:shortint;
End;
Var TroDS: trosh;Hệ số
LThừa
Hệ số
LThừa
Hệ số
LThừa
Hệ số
LThừa
bậc DT
=> Ý tưởng giải thuật để giải quyết bài tóan
Chương trình xử lý đa thức nhập vào dưới dạng là một xâu, vì vậy cần phải xử lý xâu đa thức đó lưu vào các nút của danh sách liên kết. Và từ ý tưởng cài đặt đa thức bằng mảng, mảng con trỏ, ta thực hiện phép chuyển đa thức dưới về lưu trữ mảng và mảng con trỏ.
Giả sử xâu nhập vào có dạng: ‘x+3x^5+3*x+x+4-7x^7-3’
Yêu cầu đặt ra:
- Loại bỏ dấu cách và dấu ‘*’ trong xâu
- Ta phải thực hiện được tách từng đơn thức (mỗi đơn thức được phân cách bởi các toán tử) lưu hệ số và lũy thừa vào nút của danh sách liên kết.
- Chuẩn hóa lại đa thức
- In đa thức dưới dạng : -7x^7+3x^5+5x+1
- Chuyển đa thức về lưu trữ mảng
- Chuyển đa thức về lưu trữ mảng con trỏ
* Cộng hai đa thức
- Ghép hai danh sách a với danh sách b
- Chuẩn hoá lại danh sách
Ví dụ minh họa cộng hai đa thức:
Đa thức a: ‘7x^7 + 3x^5 + 5x + 1’
7
5 1
1 0
NIL
-7 7
3 5
Đa thức b: ‘-7x^7 + 2x^2 + 3’
7
7 7
2 2
3 0
NIL
Ghép hai danh sách trên
5 1
1 0
-7 7
NIL
3 5
bậc
3 0
2 2
7 7
Sau khi chuẩn hóa lại
5
5 1
4 0
NIL
3 5
2 2
* Trừ hai đa thức
Khi trừ đa thức a cho đa thức b cách thực hiện cũng giống như đối với cộng hai đa thức nhưng khác ở chỗ: ghép danh sách a với danh sách b (hệ số của danh sách b phải lấy giá trị đối).
* Có thể minh họa nhân đa thức a với đa thức b đã cho trên như sau:
7
7 7
2 2
3 0
NIL
7
5 1
1 0
NIL
-7 7
3 5
Kết quả sau khi nhân hai đa thức:
2 2
10 3
3 0
NIL
15 1
9 5
14
21 12
-49 14
-14 9
-8 7
35 8
21 12
-49 14
-14 9
-8 7
35 8
21 12
-49 14
-14 9
-8 7
35 8
21 12
-49 14
-14 9
-8 7
35 8
21 12
-49 14
-14 9
-8 7
35 8
21 12
-49 14
-14 9
-8 7
35 8
Cài đặt chương trình.
4.1) Kiểm tra đa thức 0 (danh sách rỗng)
Function DSLK_Dt0(f:dt):boolean;
Begin
DSLK_Dt0:=(f.trodt=Nil);
End;
4.2) Thực hiện loại bỏ một nút trong danh sách
Procedure DSLK_LoaiBo(Var TroDs:pointer; Q:Pointer);
Var
tam:trosh;
Begin
tam:=TroDs;
If TroDs=Q then TroDs:=tam^.ke
Else
Begin
While tam^.keQ do tam:=tam^.ke;
tam^.ke:=tam^.ke^.ke;
End;
dispose(Q);
End;
4.3) Thực hiện thao tác chuẩn hóa lại danh sách
Procedure DSLK_Chuanhoa(var f:dt);
Var
tam,tam1,tam2:trosh;
n:kieudl;
Begin
tam:=f.trodt;
While tam^.kenil do
Begin
tam1:=tam^.ke;
While tam1nil do
Begin
If tam^.nd.lth<tam1^.nd.lth then
Begin
n:=tam1^.nd; tam1^.nd:=tam^.nd; tam^.nd:=n;
End;
tam1:=tam1^.ke;
End;
tam:=tam^.ke;
End;
tam:=f.trodt;
tam1:=tam^.ke;
While tam^.kenil do
Begin
While (tam^.nd.lth=tam1^.nd.lth) and (tam1nil) do
Begin
tam^.nd.hso:=tam^.nd.hso+tam1^.nd.hso;
tam2:=tam1;
tam1:=tam1^.ke; tam^.ke:=tam1;dispose(tam2);
End;
If tam^.nd.hso=0 then DSLK_loaibo(f.trodt,tam);
tam:=tam1;
tam1:=tam^.ke;
End;
tam:=f.trodt;
If tamnil then f.bac:=tam^.nd.lth
Else f.bac:=-1;
End;
4.4) Viết đa thức
Procedure DSLK_VietDT(f:dt);
Var
tam:trosh;
Begin
tam:=f.trodt;
If DSLK_DT0(f) then write(0) else
While tam nil do
Begin
If (abs(tam^.nd.hso) 1) then write(tam^.nd.hso:5:2)
Else if (tam^.nd.hso=-1) and (tam^.nd.lth >0) then write('-')
Else if (tam^.nd.lth=0) then write(tam^.nd.hso:5:2);
If tam^.nd.lth>0 then write('x');
If tam^.nd.lth>1 then write('^',tam^.nd.lth);
If (tam^.kenil) and (tam^.ke^.nd.hso>0) then write('+');
tam:=tam^.ke;
End;
writeln;
End;
4.5) Cộng hai đa thức
Procedure DSLK_CongDT(f,g:dt; var h:dt);
Var
tam,tam1:trosh;
Begin
h.trodt:=nil;
If (not DSLK_DT0(f)) and (not DSLK_DT0(g)) then
Begin
tam:=f.trodt;
While tamnil do
Begin
new(tam1);
tam1^.nd:=tam^.nd;
tam1^.ke:=h.trodt;
h.trodt:=tam1;
tam:=tam^.ke;
End;
tam:=g.trodt;
While tamnil do
Begin
new(tam1);
tam1^.nd:=tam^.nd;
tam1^.ke:=h.trodt;
h.trodt:=tam1;
tam:=tam^.ke;
End;
End
Else If not DSLK_DT0(g) then h:=g
Else h:=f;
DSLK_chuanhoa(h);
End;
4.6) Trừ hai đa thức
Procedure DSLK_TruDT(f,g:dt; var h:dt);
Var
tam,tam1:trosh;
Begin
h.trodt:=nil;
tam:=f.trodt;
While tamnil do
Begin
new(tam1);
tam1^.nd:=tam^.nd;
tam1^.ke:=h.trodt;
h.trodt:=tam1;
tam:=tam^.ke;
End;
tam:=g.trodt;
While tamnil do
Begin
new(tam1);
tam1^.nd.hso:=-tam^.nd.hso;
tam1^.nd.lth:=tam^.nd.lth;
tam1^.ke:=h.trodt;
h.trodt:=tam1;
tam:=tam^.ke;
End;
DSLK_chuanhoa(h);
End;
Nhân hai đa thức
Procedure DSLK_NhanDT(f,g:dt; var h:dt);
Var
tam,tama,tamb,tamc:trosh;
Begin
h.trodt:=nil;
If (not DSLK_DT0(f)) and (not DSLK_DT0(g)) then
Begin
tama:=f.trodt;
While tamanil do
Begin
tamb:=g.trodt;
While tamb nil do
Begin
new(tam);
tam^.nd.hso:=tama^.nd.hso*tamb^.nd.hso;
tam^.nd.lth:=tama^.nd.lth+tamb^.nd.lth;
tam^.ke:=h.trodt;
h.trodt:=tam;
DSLK_chuanhoa(h);
tamb:=tamb^.ke;
End;
DSLK_chuanhoa(f);
tama:=tama^.ke;
End;
DSLK_chuanhoa(f);
End;
End;
4.8) Chia hai đa thức
Procedure DSLK_ChiaDT(f,g:dt; Var h,k:dt);
Var
t,q1:dt;
tama,tamb,tamq1:trosh;
Begin
If f.bac<g.bac then
Begin
k:=f;
h.trodt:=nil;
End
Else
Begin
h.trodt:=nil; tamb:=g.trodt;
While f.bac>=g.bac do
Begin
new(tamq1); tama:=f.trodt;
tamq1^.nd.lth:=f.bac-g.bac;
tamq1^.nd.hso:=tama^.nd.hso/tamb^.nd.hso;
tamq1^.ke:=nil;
q1.trodt:=tamq1;
DSLK_NhanDT(q1,g,t);
DSLK_TruDT(f,t,k);
tamq1^.ke:=h.trodt;
h.trodt:=tamq1;
f:=k;
End;
End;
DSLK_Chuanhoa(h);
End;
4.9) Tính giá trị cho đa thức
Function DSLK_GT(f:dt; x:real):real;
Var
tam:trosh;
i,n:byte;
t:real;
Begin
tam:=f.trodt;
t:=tam^.nd.hso;
While tamnil do
Begin
If tam^.ke nil then
Begin
n:= tam^.nd.lth-tam^.ke^.nd.lth;
For i:=1 to n-1 do t:=x*t;
t:=x*t+tam^.ke^.nd.hso;
End
Else for i:=1 to tam^.nd.lth do t:=x*t;
tam:=tam^.ke;
End;
DSLK_GT:=t;
End;
4.10) Tìm ước chung lớn nhất cho hai đa thức.
Procedure DSLK_TinhUCLN(f,g:dt;var h:dt);
Var
q,r:dt;
tamc:trosh;
Begin
While g.bac>=0 do
Begin
DSLK_ChiaDT(f,g,h,k);
f:=g;
g:=k;
End;
h:=f;
If h.bac=0 then
Begin
tamc:=h.trodt;
tamc^.nd.hso:=1;
End; End;
CHƯƠNG 5: THIẾT KẾ ĐỒ HỌA
Cách sử dụng Font Tiếng Việt trong pascal
Ngôn ngữ lập trình pascal chỉ cung cấp cho chúng ta bộ phông tiếng anh. Để có Tiếng Việt trong pascal, ta sử dụng phần mềm soạn thảo Tiếng Việt trong môi trường DOS (tất nhiên những phần mềm này đã có sẵn bộ Font Tiếng Việt được cài sẵn) để gõ tiếng việt trong chương trình của mình (không sử dụng bộ phông Tiếng Việt trong các xâu ký tự, không được phép sử dụng chúng trong việc đặt tên biến, tên hàm,...)
Sau khi chạy chương trình ta cần phải chạy chương trình thường trú điều khiển phông Tiếng Việt đó mới có thể quan sát được Tiếng Việt trong chương trình của mình, và ta cũng có thể nhập được Tiếng Việt thông qua các thủ tục Read, Readln.
Trong chương trình sử dụng phần mềm VietRes, đây là một phần mềm thường thường trú trong môi trường DOS giúp chúng ta gõ Tiếng Việt trong các chương trình (giống như VietKey). Để sử dụng chương trình này ta chỉ cần đánh lệnh VRD trong DOS, khi đó sẽ thấy biểu tượng quay tròn bên trên góc phải của màn hình, để mở bảng điều khiển chương trình ta ấn CTRL+TAB.
Cài đặt Font vào hệ thống.
Sau khi ta có bộ Font, để sử dụng được nó vào hệ thống máy (BIOS). Lúc này bộ Font mới sẽ thay thế cho bộ Font mặc định ở trong BIOS, khi đó các ký tự sẽ được hiển thị dưới dạng khác tương ứng với mã ASCII của bộ Font cũ.
Procedure loadfont;
Begin
asm
mov ah,11h
mov al,00h
mov bx,1000h
mov cx,0FFh
lea dx,fe
mov bp,dx
mov dx,ds
mov es,dx
mov dx,0
int 10h
end;
end;
Procedure removefont;
Begin
asm
mov ax,1104h
xor bx,bx
int 10h
end;
End;
Trong đó: loadfont (thủ tục cài đặt Font tiếng việt);
removefont (thủ tục loại bỏ Font tiếng việt).
=> Để hiển thị Tiếng Việt trong chương trình cần gọi thủ tục loadfont, khi muốn xóa bỏ font gọi thủ tục removefont. Tuy nhiên hai thủ tục trên chỉ cho phép ta hiển thị Font tiếng việt, để gõ Tiếng Việt trong chương trình phải sử dụng một phần mềm hỗ trợ Tiếng Việt (VRD của VietRes).
Cách sử dụng chuột trong Pascal
Để sử dụng chuột trong Pascal ta dùng ngắt 33h và các hàm trong Dos
) Ngắt 33h, hàm 00h khởi tạo driver con chuột
Hàm này khởi tạo driver con chuột và thực hiện kiểm tra con chuột.
Vào: AX = 0000h
Ra: AX = FFFFh: Trong trường hợp này, driver được cài đặt.
BX = số lượng phím của con chuột
AX = 0000h: Lỗi, driver không được cài đặt
Con trỏ của con chuột được đặt vào giữa màn hình và sau đó biến mất. Trong chế độ đồ thị, nó có dạng mũi tên, còn trong chế độ văn bản nó có dạng hình chữ nhật sáng. Con trỏ tự động xuất hiện trong trang 0, không phụ thuộc vào chế độ. Vùng di chuyển của con trỏ là cả màn hình
Trong chương trình sử dụng thủ tục mreset để khởi tạo chuộtProcedure mreset;
Begin
Asm
xor ax,ax
int 33h
End;
End;
Ngắt 33h, hàm 01h hiện con trỏ của con chuột
Hàm này cho hiện con trỏ của con chuột lên màn hình. Sau khi gọi hàm này, ta thấy con trỏ xuất hiện trên màn hình và nó sẽ đi theo các di chuyển của con chuột.
Vào: AX = 0001h
Ra: Không
Trong chương trình sử dụng thủ tục mshow để hiện chuột
Procedure mshow;
Begin
Asm
mov ax,0001h
int 33h
End;
End;
2.3) Ngắt 33h, hàm 02h dấu con trỏ của con chuột
Hàm này dấu con trỏ của con chuột
Vào: AX = 0002h
Ra: Không
Procedure mhide;
Begin
Asm
mov ax,0002h
int 33h
End;
End;
=> Thủ tục mhide để ẩn chuột
2.4) Ngắt 33h, hàm 03h xác định vị trí con chuột và trạng thái các phím của con chuột
Hàm này cho biết vị trí hiện thời của con chuột và trạng thái của các phím con chuột.
Vào: AX = 0003h
Ra: BX = trạng thái các phím con chuột
CX = tọa độ ngang của con chuột
DX = tọa độ dọc của con chuột
Trong chương trình sử dụng thủ tục mget để lấy tọa độ chuột
Procedure mget(var x,y:integer);
Var tg:word;
Begin
Asm
mov ax,0003h
int 33h
mov tg,cx
End;
x:=tg;
Asm
mov tg,dx
End;
y:=tg;
End;
2.5) Ngắt 33h, hàm 05h xác định xem đã có bao nhiêu lần một phím được ấn
Hàm này cho biết một phím đã được ấn bao nhiêu lần kể từ lần gọi hàm này lần cuối, hàm cũng cho biết vị trí con trỏ tại thời điểm phím được ấn lần cuối.
Vào: AX = 0005h
BX = Phím (0 = phím trái)
Ra: AX = Trạng thái tất cả các phím của con chuột
BX = Số lần phím được ấn kể từ lần gọi hàm này lần cuối
=> Hàm sau dùng để phát hiện đang ấn chuột trái
Function mlpressed:boolean;
Var n:integer;
Begin
Asm
mov ax,0005h
xor bx,bx
int 33h
mov n,bx
End;
mlpressed:=n>0;
End;
2.6) Ngắt 33h, hàm 06h xác định xem đã có bao nhiêu lần một phím được nhả
Hàm này cho biết một phím được nhả bao nhiêu lần kể từ lần gọi hàm này lần cuối, hàm cũng cho biết vị trí con trỏ tại thời điểm phím được nhả lần cuối.
Vào: AX = 0006h
Ra: BX = phím (0 = phím trái)
Functionmlreleased:boolean;
Var n:integer;
Begin
Asm
mov ax,0006h
xor bx,bx
int 33h
mov n,bx
End;
mlreleased:=n>0;
End;
BX = Số lần phím được nhả kể từ lần gọi hàm này lần cuối
Thiết kế màn hình chính
KHOA LUAN TOT NGHIEP
GVHD: TS. Nguyễn Trung Hòa
SV: Trần Thị Lê Na lớp 43B1CNTT
KẾT LUẬN
Đề tài đã xây dựng được các phương án cài đặt, lưu trữ đa thức dưới 3 loại cấu trúc dữ liệu: mảng, mảng động, danh sách liên kết. Với mỗi loại cấu trúc, giải thuật để thực hiện các phép toán đa thức có những đặc điểm riêng, từ đơn giản đối với cấu trúc mảng đến phức tạp hơn đối với cấu trúc mảng động và phức tạp nhất đối với danh sách liên kết. Đề tài cũng đã đưa ra được giải thuật xử lý một xâu ký tự theo hướng đặt tương ứng một xâu ký tự (theo một quy cách nhất định) với một đa thức (Nhận diện đa thức từ bàn phím). Ngoài ra đề tài cùng đã thể hiện thành công kỹ thuật đồ hoạ Pascal trong việc tạo menu có sử dụng ngắt 33h và các hàm của BIOS để điều khiển chuột. Đề tài có thể sẽ được hoàn chỉnh hơn trong tương lai theo hướng là một phần mềm hỗ trợ học sinh phổ thông trung học cơ sở tự học phần đa thức của toán phổ thông.
Qua thời gian làm đề tài, dẫu không phải là dài nhưng bản thân em đã học tập được nhiều từ bạn bè, từ thầy cô giáo và đã đúc kết được nhiều kinh nghiệm quý để bổ sung kiến thức quý báu cho mình. Mặc dù công việc đã được hoàn thành và chương trình cài đặt đa thức đã được xây dựng. Song do điều kiện thời gian và phạm vi tìm hiểu có phần hạn chế nên chương trình của em vẫn còn một số hạn chế nhất định. Bởi vậy, em rất mong được sự chỉ bảo hướng dẫn của thầy cô giáo và bạn bè góp ý kiến kịp thời sửa chữa những sai sót để chương trình được hoàn thiện hơn. Cuối cùng, một lần nữa em xin chân thành cảm ơn thầy giáo Tiến sỹ Nguyễn Trung Hòa đã hướng dẫn và giúp đỡ em hoàn thành đề tài này.
Vinh, ngày 11 tháng 05 năm 2006.
Sinh viên thực hiệ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
Lý do cài đặt bằng mảng 8
Định nghĩa kiểu mảng 10
Cách khai báo 10
Ý tưởng giải thuật 11
Cài đặt đa thức 13
Chương 3: Cài đặt đa thức bằng mảng con trỏ 18
Lý do cài đặt bằng mảng con trỏ 18
Cách khai báo 18
Cách lưu trữ đa thức 19
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
Lý do cài đặt bằng danh sách liên kết 28
Danh sách nối đơn 28
Cách lưu trữ 30
Cài đặt chương trình 33
Chương 5: Thiết kế đồ họa 43
Cách sử dụng Font tiếng việt trong Pascal 43
Cách sử dụng chuột trong Pascal 44
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
TÀI LIỆU THAM KHẢO
Giáo trình lý thuyết và bài tập Pascal toàn tập; Tác giả Nguyễn Đình Tê và Hoàng Đức Hải; Nhà xuất bản lao động xã hội.
Cấu trúc dữ liệu và giải thuật; Tác giả Đỗ Xuân Lôi; Nhà xuất bản thống kê.
Cẩm nang lập trình hệ thống cho máy vi tính IBM – PC bằng Pascal, C, Assembler, Basic; Tác giả Michael Tischer; Dịch: Quách Tuấn Ngọc, Nguyễn Mạnh Hùng, Nguyễn Phú Tiến.
Số phức và đa thức sách bồi dưỡng thường xuyên cho giáo viên THPT; Tác giả Nguyễn Văn Khuê, Bùi Đắc Tắc, Nhà xuất bản giáo dục năm 1996.
Các file đính kèm theo tài liệu này:
- Đại số đa thức và các phương án cài đặt.doc