TRƯỜNG ĐH HỒNG ĐỨC
KHOA CNTT&TT

 BÀI TIỂU LUẬN

HỌC PHẦN CẤU TRÚC DỮ LIỆU VÀ GIẢI
THUẬT

Đề tài:
“Cài đặt chương trình thực hiện các phép toán trên đa thức một biến”
SVTH : Bùi Hữu Giáp
Lớp : Đại học tin – K15
MSV : 1261030003
Thanh Hóa, 11/2013 LỜI CẢM ƠN

Trong quá trình học tập tại trường, em đã được học hỏi và tiếp thu rất nhiều
kiến thức đại cương cũng như chuyên ngành nhằm nâng cao vốn hiểu biết và là
hành trang quí báu giúp chúng em vững bước vào đời. Em xin gửi lời cảm ơn chân
thành đến quý thầy cô đã giảng dạy chúng em trong suốt thời gian qua, khoa Công
Nghệ Thông Tin và truyền thông cũng như tất cả quý thầy cô trong trường Đại
học Hồng Đức. Đặc biệt em xin chân thành cảm ơn cô Trịnh Thị Phú - người đã
tận tình hướng dẫn em trong suốt thời gian thực hiện đề tài này.
Tuy nhiên, dù rất cố gắng nhưng do thời gian có hạn nên chắc rằng bài tiểu
luận của em khó tránh khỏi những thiếu sót. Em rất mong nhận được sự thông
cảm và đóng góp ý kiến của quý thầy cô và các bạn để bài tiểu luận của em được
hoàn chỉnh hơn.
Em xin chân thành cảm ơn! Thanh Hóa, 11/2013
Sinh viên thực hiện
MỤC LỤC

3.6.5. Hàm cộng hai đa thức 20
3.6.6. Hàm trừ hai đa thức 23
3.6.7. Hàm nhân hai đa thức 23
3.6.8. Hàm chia hai đa thức 24
3.6.9. Hàm tính đạo hàm của đa thức 25
3.6.10. Hàm tính nguyên hàm của đa thức 26
3.6.11. Hàm tính giá trị của đa thức 27
PHẦN IV: KẾT LUẬN 28
3.1. Tóm tắt kết quả nghiên cứu 28
3.2. Đề xuất 29
TÀI LIỆU THAM KHẢO 30

Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
1
GVHD: Trịnh Thị PhúCHƯƠNG I: MỞ ĐẦU

1.1. Lí do chọn đề tài
Đa thức là một trong những phạm trù toán học cơ bản, không chỉ học sinh ở
nước ta mà còn ở tất cả các nước trên thế giới được tiếp cận khá sớm. Ở Việt Nam,
ngay từ chương trình môn toán trung học cơ sở, học sinh đã được tiếp cận với
khái niệm đa thức. Một trong những khái niệm mở đầu được đề cập tới đó là đa
thức một biến.
Có rất nhiều phép toán có thể thực hiện trên đa thức một biến như: cộng hai
đa thức, trừ hai đa thức, nhân hai đa thức… Việc thực hiện các phép toán này đối

- Thực hiện công việc cộng hai đa thức một biến.
- Thực hiện công việc trừ hai đa thức một biến.
- Thực hiện công việc nhân hai đa thức một biến.
- Thực hiện công việc chia hai đa thức một biến.
- Thực hiện công việc tính đạo hàm của một đa thức một biến.
- Thực hiện công việc tính nguyên hàm của một đa thức một biến.
- Thực hiện công việc tính giá trị của một đa thức một biến với giá trị xác
định của ẩn.
1.3. Khách thể, đối tượng và phạm vi nghiên cứu
1.3.1. Khách thể nghiên cứu
Cài đặt một chương trình thực hiện tất cả những phép toán thường gặp trên
đa thức một biến.

1.3.2. Đối tượng và phạm vi nghiên cứu
Các phép toán thường gặp trên đa thức một biến.
1.4. Các phương pháp nghiên cứu
- Phương pháp thu thập tài liệu: thu thập tài liệu từ những bài báo khoa học,
các trang web tin học và một số ebook về đề tài nghiên cứu, giáo trình và các tài
liệu học tập khác.
- Phương pháp phân tích và tổng hợp tài liệu: từ những tài liệu đã thu thập,
tiến hành tìm hiểu, phân tích và tồng hợp nội dung liên quan đến đề tài.
- Phương pháp chuyên gia: trong quá trình nghiên cứu có sự góp ý, điều
chinh từ giáo viên hướng dẫn.
- Phương pháp phân tích và tổng hợp kinh nghiệm: sau quá trình tìm hiểu và
đúc kết kinh nghiệm, tiến hành tổng hợp và hoàn thiện đề tài.
- Phương pháp thực nghiệm: sau khi cài đặt xong chương trình cần xây dựng
Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp

x
n
với các hệ số a
i
∊ℝ là một đa thức một biến trên ℝ. Nếu a
n
≠ 0 thì P(x) là đa
thức một biến bậc n.
Đa thức trên có thể viết ngắn gọn nhờ ký hiệu xich-ma là
(x) =








2.2. Phép cộng trừ hai đa thức.
Cho hai đa thức:
(x) =








(x) =


2.3. Phép nhân hai đa thức.
Cho hai đa thức:
(x) =








Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
5
GVHD: Trịnh Thị Phú(x) =








Khi đó P(x).Q(x) là một đa thức có bậc m+n và có các hệ số xác định bởi

0
). Δy được gọi là số gia hàm số.
Xét tỷ số


. Nếu khi Δx→0, tỷ số đó dần tới một giới hạn thì giới hạn đó
được gọi là đạo hàm của hàm số y=f(x) tại điểm x
0
kí hiệu là ʄ'(x) hay
̇
().
ʄ

(
x
)
= lim
→
ʄ
(


+Δx
)
−ʄ(

)


Công thức tính đạo hàm đa thức một biến:

GVHD: Trịnh Thị PhúCHƯƠNG III: NỘI DUNG

3.1. Tổ chức lưu trữ
Trong chương trình, em sử dụng cấu trúc node để lưu trữ mỗi phần tử của
đa thức, đồng thời định nghĩa kiểu dữ liệu con trỏ có tên dslk có kiểu node để
sau này dễ sử dụng:
struct node
{
int mu;
float hs;
node *next;
};
typedef node *dslk;

trong đó, mu là một trường có kiểu int dùng để lưu trữ số mũ của phần tử;
hs là một trường có kiểu float dùng để lưu trữ hệ số của phần tử đó.
3.2. Tổ chức menu lựa chọn cho chương trình
Menu chính của chương trình được tổ chức như hình 1:
Việc hiển thị ra menu của chương trình và đọc vào lựa chọn của người dùng
được thực hiện bởi hai hàm void inmenu(int choice) và int menu():
Hình
1. Menu chính của chương trình
Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
8

Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
9
GVHD: Trịnh Thị Phú }
else if (c>='0'&&c<='7')
choice=c%48;
else if (c==72)
{
if (choice==0)
choice=7;
else
choice ;
}
else if (c==80)
{
if (choice==7)
choice=0;
else
choice++;
}
}
}
Hàm void inmenu(int choice) dùng để hển thị menu ra ngoài màn hình với
một con trỏ dùng để trỏ vào lựa chọn choice tương ứng của người dùng.
Hàm int menu() trả về sự lựa chọn của người dùng. Trong hàm, một biến

char c=getch();
if (c==115||c==83)
break;
}
}
Hàm này được dùng để nhập vào một đa thức l bằng cách nhập lần lượt hệ
số và số mũ cho từng phần tử.
Hàm được phát biểu như sau:
- Khai báo một nút mới p.
- Đọc vào lần lượt giá trị cho hai trường p->hs và p->mu.
- Chèn nút p vào cuối đa thức l.
Dùng một biến c có kiểu char để kiểm tra xem đa thức đã được nhập xong chưa,
nếu sau khi nhập xong một phần tử, người dùng nhấn phím S (có mã 115 với
chữ in và 83 với chữ thường) thì dừng quá trình, nếu không phải thì tiếp tục
nhập.

Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
11
GVHD: Trịnh Thị Phú3.4. Hiển thị đa thức ra màn hình
Để có thể hiển thị một đa thức (được lưu trữ trong danh sách liên kết l) đã
được chuẩn hóa sẵn ra màn hình em đã sử dụng tới hàm void in(dslk l). Hàm
này có cấu trúc:
void in(dslk l)
{

printf("%.0fx",p->hs);
else
printf("%fx",p->hs);
}
else if (p->hs==1)
printf("x^%d",p->mu);
else if (p->hs==-1)
printf("-x^%d",p->mu);
else
{
if ((int)p->hs==p->hs)
printf("%.0fx^%d",p->hs,p->mu);
else
printf("%fx^%d",p->hs,p->mu);
}

if ((p->next!=NULL)&&(p->next->hs>=0))
printf("+");
p=p->next;
}
}
Hàm được phát biểu như sau:
- Đầu tiên, kiểm tra xem danh sách liên kết l xem có rỗng không, nếu
danh sách rỗng thì in ra màn hình con số 0.
- Dung một con trỏ có kiểu dslk để duyệt từng phần tử của đa thức
(từng nút của danh sách liên kết) theo thứ tự từ đầu tới cuối và thực
hiện lần lượt các công việc:
Cài đặt chương trình thực hiện các phép toán trên đa thức một biến
p->next=l;
l=p;
}
else
Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
14
GVHD: Trịnh Thị Phú {
dslk q;
q=l;
for (int i=2;i<vt;i++)
q=q->next;
p->next=q->next;
q->next=p;
}
}
Hàm này được dùng để chẻn một nút p vào vị trí vt của danh sách liên kết l.
Hàm được phát biểu như sau:
- Đầu tiên, kiểm tra xem vị trí chèn có phải là 1 không, nếu đúng thì:
+ Gán p->next bằng l.
+ Gán p cho l.
- Nếu vị trí chèn không phải là 1 thì:
+ Dùng một con trỏ q để di chuyển tới ngay trước vị trí cần
chèn.
+ Gán p->next bằng q->next.

Hàm này được dùng để xóa một phần tử ở vị trí vt của danh sách liên kết l.
Hàm được phát biểu như sau:
- Khai báo một biến p kiểu dslk, gán cho p bằng l.
- Kiểm tra xem vt có phải là 1 không, nếu đúng thì:
+ Gán l bằng l->next.
+ Xóa p.
- Nếu vt khác 1 thì:
+ Di chuyển p tới ngay trước vị trí của phần cần xóa.
+ Khai báo hai biến q vả r kiểu dslk, gán r bằng p->next, gán q
bằng r->next.
+ Xóa r.
+ Gán p->next bằng q.
3.5.3. Hàm xóa toàn bộ một danh sách liên kết
void xoa(dslk &l)
Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
16
GVHD: Trịnh Thị Phú{
while (l!=NULL)
{
dslk p=l;
l=l->next;
delete(p);
}
}

GVHD: Trịnh Thị Phú }
q=q->next;
}
p=p->next;
}

}
Hàm này được dùng để sắp xếp một đa thức l có n theo thứ tự giảm dần số
mũ của các phần tử.
Hàm được phát biểu như sau:
- Khai báo hai con trỏ p và q.
- Dùng hai vòng while và hai con trỏ p và q để sắp xếp đa thức theo
thuật toán nổi bọt với điều kiện so sánh là số mũ của hai phần tử.
Nếu số mũ của phần tử được con trỏ p trỏ tới nhỏ hơn số mũ của
phần tử được con trỏ q trỏ tới thì đổi hệ số và số mũ của hai phần tử
cho nhau.
3.6.2. Hàm chuẩn hóa đa thức
void stand(dslk &l)
{
if (l==NULL)
return;
sort(l);
dslk p=l;
int i=1;
while (p->next!=NULL)
{
dslk q=p;

- Dùng một con trỏ p duyệt từ phần tử thứ nhất tớ phần tử n-1 của đa
thức và thực hiện các công việc:
+ Khai báo một biến q kiểu dslk và gán cho q bằng p, gán cho p
bằng p->next.
+ Nếu q->hs bằng 0 thì xóa q ra khỏi đa thức.
+ Nếu q->hs bằng p->hs thì gán cho p->hs giá trị tổng của q-
>hs và p->hs rồi sau đó xóa q khỏi đa thức.
- Kiểm tra hệ số của phần tử thứ n của đa thức xem có bằng 0 không,
nếu đúng thì xóa phần tử này khỏi đa thức.
3.6.3. Hàm đổi dấu của đa thức
void ddau(dslk &l)
{
dslk p=l;
while (p!=NULL)
{
p->hs=-p->hs;
p=p->next;
}
}
Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
19
GVHD: Trịnh Thị PhúHàm này được dùng để đổi dấu của đa thức hay tương đương với việc ta
nhân đa thức đó với -1.
Hàm này được phát biểu như sau: duyệt lần lượt từng phần tử của đa thức

theo hoặc có nhưng số mũ của phần tử tiếp theo không bé hơn mũ
của phần tử hiện tại là 1 thì chèn một phần tử có hệ số là 0 và số mũ
là số mũ của phần tử hiện tại trừ đi 1 vào sau phần tử hiện tại.
Cài đặt chương trình thực hiện các phép toán trên đa thức một biến SVTH: Bùi Hữu Giáp
20
GVHD: Trịnh Thị Phú3.6.5. Hàm cộng hai đa thức
void add(dslk &l1,dslk l2)
{
dslk p=l1,q=l2,lr=NULL;
while (p!=NULL||q!=NULL)
{
if (p==NULL)
{
dslk r=new node;
r->hs=q->hs;
r->mu=q->mu;
insert(r,1,lr);
q=q->next;
}
else if (q==NULL)
{
dslk r=new node;
r->hs=p->hs;
r->mu=p->mu;

q=q->next;
}
else
{
dslk r=new node;
r->hs=p->hs+q->hs;
r->mu=p->mu;

insert(r,1,lr);
p=p->next;
q=q->next;
}
}
}
xoa(l1);