Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
LỜI NÓI ĐẦU
Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao
cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấu trúc dữ liệu được chọn
cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu
từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện
nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt. Các
cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép
toán trên đó được cung cấp bởi một ngôn ngữ lập trinh.
Mỗi loại cấu trúc dữ liệu phù hợp với một vài loại ứng dụng khác nhau, một số cấu trúc dữ
liệu dành cho những công việc đặc biệt.
Trong thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan trọng.
Kinh nghiệm trong việc xây dựng các hệ thống lớn cho thấy khó khăn của việc triển khai chương
trình, chất lượng và hiệu năng của kết quả cuối cùng phụ thuộc rất nhiều vào việc chọn cấu trúc
dữ liệu tốt nhất.
Để có thể đi sâu và nắm vững một cách có hệ thống kiến thức đã thu nhận được trong quá
trình học môn Cấu trúc dữ liệu và giải thuật, em chọn đề tài “Với số tự nhiên n cho trước tính
xem có bao nhiêu cách biểu diễn n thành tổng của 1 hay nhiều số tự nhiên khác” để tìm hiểu
và nghiên cứu.
Trong quá trình thực hiện đồ án, chúng em xin chân thành cảm ơn sự hướng dẫn tận tình
của thầy Phan Thanh Tao đã giúp đỡ em hoàn thành tốt đồ án môn học này.
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 1
Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
A. Giới thiệu đề tài:
Tên đề tài: Với số tự nhiên n cho trước tính xem có bao nhiêu cách biểu diễn n thành
tổng của 1 hay nhiều số tự nhiên khác(không tính đến thứ tự của các số hạng, ví dụ 3=2+1=1+2
coi như là một cách biểu diễn)

một cách đệ quy.
b. Mô hình :
Lời giải của bài toán thường biểu diễn bằng một vecto gồm n thành phần x=(x
1…
x
n
) phải
thỏa mãn các điều kiện nào đó. Để chỉ ra lời giải x ta phải xây dựng dần các thành phần x
i
.
Tại mỗi bước i :
 Đã xây dựng xong các thành phần x
1
x
i-1
.
 Xây dựng thành phần x
i
bằng cách lần lượt thử tất cả các khả năng mà x
i
có thể
chọn.
• Nếu 1 khả năng j nào đó phù hợp cho x
i
thì xác định x
i
theo khả năng j .
Thường phải có thêm thao tác ghi nhận trạng thái mới của bài toán để hổ trợ
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 3
Đồ án cấu trúc dữ liệu và giải thuật

Ghi nhận trạng thái mới;
If(i<n) Try(i+1)
Else Ghi nhận nghiệm;
Trả lại trạng thái cũ;
}
}
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 4
Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
2.Đệ quy và giải thuật đệ quy :
a. Khái niệm :
Ta nói một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng
khác cùng dạng với chính nó bằng quy nạp.
b. Giải thuật :
Nếu lời giải của một bài toán P được thực hiện bằng lời giải của bài toán P’ có dạng giống
như P thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy gợi là giải thuật đệ
quy.
Lưu ý : P’ tuy có dạng giống như P, nhưng theo một nghĩa nào đó, P’ phải «nhỏ » hơn P ,
dễ giải hơn P và việc giải nó không câng dùng đến P.
Định nghĩa một hàm đệ quy hay một thủ tục đệ quy gồm hai phần :
 Phần neo(anchor) : Phần này được thực hiện khi mà công việc quá
đơn giản, có thể giải trực tiếp chứ không cần phải nhờ đến một bài toán con nào cả.
 Phần đệ quy : Trong trường hợp bài toán chưa thể giải được bằng
phần neo, ta xác định nhữn bài toán con và gọi đệ quy giải những bài toán con đó.
Khi đã có lời giải (đáp số) của những bài toán con rồi thì phối hợp chúng lại để giải
bài toán đang quan tâm.
Phần đệ quy thể hiện tính « quy nạp » của lời giải. Phần neo cũng rất quan trọng bởi nó
quyết định tới tính hữu hạn dừng của lời giải.
c. Ví dụ về giải thuật đệ quy :

2. Không phải lúc nào sự kết hợp lời giải của các bài toán con cũng cho ra lời giải của
bài toán lớn.
Để giải quyết những trường hợp như vậy phương pháp quy hoạch động dựa vào một
nguyên lý gọi là nguyên lý tối ưu của Bellman:
“Nếu lời giải bài toán là tối ưu thì lời giải của các bài toán con cũng tối ưu”.
Trong thuật toán quy hoạch động thường dùng các thao tác:
− Xây dựng một hàm quy hoạch động(hoặc phương trình quy hoạch động).
− Lập bản lưu lại các giá trị của hàm.
− Truy xuất lời giải tối ưu của bài toán từ bảng lưu.
II. Mô tả bài toán :
1.Yêu cầu :
Nhập từ bàn phím một số n và in ra màng hình số cách phân tích n thành tổng của dãy các
số nguyên dương, các cách phân tích là hoán vị của nhau thì chỉ tính là 1.
2.Ví dụ :
N = 5 thì có 7 cách phân tích :
1. 5= 1+1+1+1+1
2. 5= 1+1+1+2
3. 5= 1+1+3
4. 5= 1+2+2
5. 5= 1+4
6. 5= 2+3
7. 5= 5
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 7
Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
C. GIẢI THUẬT
I. Thuật toán quay lui :
1.Phương thức :
Giải thuật này sẽ liệt kê tất cả các cách phân tích 1 số n thành tổng của dãy các số nguyên

printf("\ncach %ld:: %d=",count++,n);
for(i=1;i<k;i++)
printf("%d+",x[i]);
printf("%d",x[k]);

}
void thu(int i)
{int j;
for(j=x[i-1];j<=(n-t[i-1])/2;j++)
{x[i]=j;
t[i]=t[i-1]+j;
thu(i+1);
}
x[i]=n-t[i-1];
in(i);
}
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 9
Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
main()
{
count=1;
do{printf("\nn=");scanf("%d",&n);}while(n>40);
x[0]=1;
t[0]=0;
thu(1);
getch();
}
II. Thuật toán đệ quy :

#include<stdio.h>
long f(int m,int v)
{
if(m==0)
{
if(v==0) return 1;
else return 0;
}
else
{
if(m>v) return f(m-1,v);
else return (f(m-1,v)+f(m,v-m)) ;
}
}
main()
{
int m,n,v;
do{printf("n=");scanf("%d",&n);}while(n>80);
printf("\n so cach phan tich =%ld",f(n,n));
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 11
Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
getch();
}
III. Quy hoạch động:
1. Phương thức:
Từ công thức truy hồi được xây dựng ở trên :
F[m-1, v] nếu m>v
F[m,v]=

int n, m, v;
printf("\nnhap vao so n can phan tich : ");
scanf("%d",&n);
for(v=0;v<=n;v++) F[0][v]=0;
F[0][0]=1;
for(m=1;m<=n;m++)
for(v=0;v<=n;v++)
{
if(v<m) F[m][v]=F[m-1][v];
else F[m][v]=F[m-1][v]+F[m][v-m];
}
printf("\nso cach phan tich la : %d", F[n][n]);
getch();
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 13
Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
}
b. Dạng 2 (cải tiến) :
Ta nhận thấy tại mỗi bước, ta chỉ cần lưu lại một dòng của bảng F bằng một mảng 1 chiều,
sau đó dùng mảng đó tính lại chính nó để sau khi tính, mảng một chiều sẽ lưu các giá trị của bảng
F trên dòng kế tiếp. Không cần dùng mảng 2 chiều để tối ưu và tiết kiệm không gian nhớ.
#include<stdio.h>
#include<conio.h>
int main()
{
unsigned long f[1000];
int v,m,n,i;
printf("Nhap so nguyen duong n= ");
scanf("%ld",&n);

Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
4. Đệ quy:
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 17
Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
E. Kết Luận
Với thuật toán quay lui, ngoài việc cho biết số cách phân tích được mà còn liệt kê được tất
cả các cấu hình cần tìm giúp ta dễ kiểm tra. Tuy nhiên, phương pháp này chỉ thực sự hữu dụng
đối với n nhỏ, trường hợp n lớn ta sẽ gặp rắc rối bởi số cấu hình cần in là rất lớn. Phương pháp
này có độ phức tạp hàm mũ (O (n
n
)).
Với thuật toán đệ quy (chia để trị), quá trình cài đặt đơn giản, tuy nhiên chỉ cho biết số
cách phân tích, với việc sử dụng ngăn xếp để lưu giá trị nên tốn bộ nhớ. Phương pháp này cũng có
độ phức tạp hàm mũ (O (2
n
)).
Với thuật toán quy hoạch động, ta tiết kiệm được bộ nhớ, có thể thực hiện với n lớn. Tuy
nhiên, nó cũng chỉ cho ta biết được số cách phân tích. Phương pháp này có độ phức tạp O(n
2
).
Phương pháp này tối ưu nhất (trong trường hợp bài toán ta đang xét).
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 18
Đồ án cấu trúc dữ liệu và giải thuật

GVHD:Phan Thanh Tao
MỤC LỤC

4. Đệ quy: 17
E. Kết Luận 18
SVTH:Phan Lữ Đặng Bình - Đỗ Thế Viên – Hà Phước Việt – Lê Thanh Vũ – Nhóm 12A Page 20