Trường Đại Học Hàng Hải Việt Nam
Khoa Công Nghệ Thông Tin

ĐỀ CƯƠNG ÔN TẬP

MÔN HỌC: PHÂN TÍCH THIẾT KẾ
VÀ ĐÁNH GIÁ THUẬT TOÁN

Sinh viên: Đỗ Đức Hùng
Lớp: CNT50ĐH1
MSV: 37172
Mail: [email protected]
Web: http://doduchung.co.cc Hải Phòng, 21/06/2011
Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 1
MỤC LỤC

dần) theo năm sinh, cùng năm sinh theo tên. Áp dụng giải thuật sắp xếp chọn (hoặc chèn, hoặc nổi
bọt, hoặc đổi chỗ, …) 21
Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 2
3. Cho cấu trúc mặt hàng gồm: mã số, loại, tên, Khai báo cấu trúc mặt hàng ở trên (để lưu ở
dạng mảng, hoặc dạng danh sách liên kết đơn). Cài đặt hàm tìm kiếm mặt hàng nào đó theo mã (hoặc
tên, …). Nêu rõ giải thuật áp dụng. 23
4. Cài đặt và đánh giá độ phức tạp thuật toán in ra hoán vị của n số nguyên từ 1 đến n. Các
hoán vị được in ra phải thỏa mãn một tiêu chuẩn nào đó, ví dụ: tổng 2 phần tử liên tiếp của hoán vị
là số nguyên tố, hoặc tổng 2 phần tử liên tiếp của hoán vị là số hoàn hảo, … 25
5. Cài đặt và đánh giá độ phức tạp thuật toán in ra tất cả các xâu nhị phân có độ dài k. Xâu
được in ra phải thỏa mãn một điều kiện nào đó, ví dụ: biểu diễn thập phân của xâu đó là số hoàn hảo,
hoặc số nguyên tố, hoặc xâu đó không có 3 phần tử liên tiếp giống nhau, hoặc xâu đó phải có 2 ký tự
liền kề không giống nhau, … 27
6. Cài đặt và đánh giá độ phức tạp thuật toán in ra số nguyên có k chữ số. Số được in ra phải
thỏa mãn một điều kiện nào đó, ví dụ: số đó có tổng các chữ số là số nguyên tố, hoặc số hoàn hảo,
hoặc các chữ số phải khác nhau, … 28
7. Trình bày thuật toán nhân dãy ma trận A. Tìm số phép nhân ít nhất để nhân các ma trận có
kích thước nào đó, ví dụ: 6x5, 5x7, 7x8, 8x3, 3x5 29
8. Trình bày thuật toán tìm xâu con chung dài nhất của hai xâu. Áp dụng tìm xâu con chung dài
nhất của hai xâu con sau: “CDADDADC”, “ACDDCCA” 32
III. Cấu trúc đề thi học kỳ: (mỗi câu 2/10 điểm) 36

Các tiêu chí đánh giá thuật toán:
+ Thuật toán đơn giản, dễ hiểu, dễ cài đặt.
+ Dựa vào thời gian thực hiện và tài nguyên mà thuật toán sử dụng để thực hiện trên
các bộ dữ liệu.
2. Thế nào là bài toán tìm kiếm? (định nghĩa, đầu vào, đầu ra, mục đích, …)
Tìm kiếm là 1 trong những vấn đề thuộc lĩnh vực nghiên cứu của ngành khoa học máy
tính và được ứng dụng rộng rãi trên thực tế.
Chúng ta quan tâm đến bài toán tìm kiếm trên 1 mảng, hoặc 1 danh sách các phần tử cùng
kiểu
Kết quả tìm kiếm là vị trí của phần tử thỏa mãn điều kiện tìm kiếm: có trường khóa bằng
với 1 giá trị khóa cho trước. Từ vị trí này chúng ta có thể truy cập tới các thông tin khác được
chứa trong trường dữ liệu của phần tử tìm thấy. Nếu kết quả là không tìm thấy thì giá trị trả về
Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 4
sẽ được gán cho một giá trị đặc biệt nào đó tương đương với việc không tồn tại phần tử nào có
vị trí đó: chẳng hạn – 1 với mảng và NULL với danh sách liên kết.
Có nhiều thuật toán tìm kiếm như: tìm kiếm vét cạn, tìm kiếm tuần tự, tìm kiếm nhị phân,
v.v.v v.
3. Trình bày thuật toán tìm kiếm tuyến tính (các bước, sơ đồ thuật toán, độ phức tạp, …)
Các bước:
- Duyệt qua các phần tử của mảng
- Nếu tìm thấy phần tử có khóa bằng khóa tìm kiếm thì trả về vị trí của phần tử đó. Ngược

Sơ đồ thuật toán: Cài đặt bằng C:

Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 6
void selection_sort(int a[],int n)
{
int i,j,vtmin;
for(i=0;i<n-1;i++)
{
vtrimin=i;
for(j=i+1;j<n;j++)
if(a[j]<a[vtmin]) vtmin=j;
swap(&ap[vtmin],&a[i];
}
} Độ phức tạp thuật toán: O(n
2

a[j]=a[j-1];
j=j-1;
}
a[j]=temp;
}
}
Ví dụ:

Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 8
Độ phức tạp: O(n
2
)
7. Trình bày thuật toán sắp xếp nổi bọt (mô tả thuật toán, cài đặt, độ phức tạp, ví dụ)
Thuật toán dựa trên việc so sánh và đổi chỗ 2 phần tử ở kề nhau:
- Duyệt qua danh sách các bản ghi cần sắp xếp theo thứ tự, đổi chỗ 2 phần tử kề nhau nếu
chúng không đúng thứ tự.
- Lặp lại điều này cho tới khi không có 2 bản ghi nào sai thứ tự.
Sơ đồ thuật toán: Độ phức tạp: O(n

swap(&a[j-1],a[j]);
}

8. Trình bày thuật toán sắp xếp đổi chỗ (mô tả thuật toán, cài đặt, độ phức tạp, ví dụ)
Mô tả thuật toán: Bắt đầu xét phần tử đầu tiên a[i] với i=0, ta xét tất cả các phần tử đứng
sau a[i] gọi là a[j] với j nằm trong đoạn [i+1; n-1]. Với mỗi cặp a[i], a[j] đó, nếu có sự sai khác về
vị trí giữa a[i] và a[j] thì đổi chỗ a[i] và a[j]
Cài đặt thuật toán:
void exchange_sort(int a[],int n)
{
int i,j,tam;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[j]<a[i])
{
tam=a[j];
a[j]=a[i];
a[i]=tam;
}
} Đ
Ề

CƯƠNG PT
TK && ĐGTT

- Vì A[0] có thể lỗi vị trí nên ta sẽ gọi thủ tục heaprify đối với nó để chỉnh lại mảng trở
thành 1 heap.
- Lặp lại các thao tác trên cho tới khi chỉ còn 1 phần tử trong heap khi đó mảng đã được
sắp xếp.
Độ phức tạp: O(n*log(n))
Cài đặt bằng C:
void heapsort(int *A, int n)
{
int i;
buildheap(A, n);
for(i=n-1;i>0;i )
{
swap(A[0],A[i]);
heaprify(A,0,i-1);
}
}

10. Thế nào là giải thuật đệ quy? Ưu, nhược điểm của đệ quy? Cách khử đệ quy. Ví dụ.
- Đệ quy là cách định nghĩa một đối tượng dựa trên chính nó, hay cụ thể hơn là trên các
thể hiện cụ thể, đơn giản của nó. 1 hàm đệ quy là 1 hàm mà trong thân hàm có lời gọi tới chính
nó (số lượng và vị trí không hạn chế).
Ưu điểm của đệ quy: Chương trình ngắn gọn và đẹp hơn.
Nhược điểm của đệ quy: Tốn vùng nhớ, thời gian truyền đối mục, thiết lập vùng nhớ trung
gian và trả về kết quả.
Cách khử đệ quy:
- Khử đệ quy bằng vòng lặp
- Khử đệ quy bằng đệ quy arsac
Ví dụ: Hàm tính số fibonaci thứ n
int fb(int n)
{ if(n==1||n=2) return 1;

hành tiếp, thuật toán sẽ quay lui về trạng thái trước đó và lựa chọn các khả năng khác.
Ưu điểm: Thuật toán tìm ra được tất cả các nghiệm của bài toán 1 cách dễ dàng, có thể áp
dụng cho các bài toán với kích thước input nhỏ.
Nhược điểm: Tốn nhiều thời gian cho phép thử nghiệm.
Ví dụ: Sinh các dãy nhị phân độ dài N (N<=20)
void try(int k)
{
int j;
if(k==n) in_nghiem();
else
for(j=0;j<=1;j++)
{
x[k]=j;
try(k+1);
}
}

Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 13
13. Thế nào là chiến lược chia để trị? Ưu, nhược điểm của chia để trị? Ví dụ.
Thuật toán chia để trị thực hiện chia bài toán thành các bài toán nhỏ hơn, giải các bài toán
nhỏ hơn đó, sau đó kết hợp nghiệm của các bài toán nhỏ hơn đó lại thành nghiệm của bài toán

Vấn đề chọn chốt: Chọn khóa lớn nhất trong 2 phần tử có khóa khác nhau đầu tiên kể từ
trái qua, nếu mảng chỉ gồm 1 hay nhiều phần tử có khóa bằng nhau thì không có chốt.
Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 14
Vấn đề phân hoạch: Để phân hoạch mảng ta dùng 2 con nháy L và R, trong dó L từ bên trái
và R từ bên phải, ta cho L chạy sang phải cho tới khi gặp phần tử có khóa >= chốt và cho R chạy
từ trái cho tới khi gặp phần tử có khóa < chốt. Tại chỗ dừng của L và R, nếu L < R thì hoán vị
a[L] và a[R], lặp lại quá trình dịch sang phải, sang trái của 2 con nháy này cho đến khi L > R.
Giải thuật:
- Xác định chốt
- Phân hoạch mảng đã cho thành 2 mảng con a[i] a[k-1] và a[k] a[j]
- Sắp xếp mảng a[i] a[k-1] (Đệ quy)
- Sắp xếp mảng a[k] a[j] (Đệ quy)
- Quá trình sẽ dừng khi không còn tìm thấy chốt
Độ phức tạp: O(n*log(n))
Ví dụ:

Cài đặt:
int phanhoach(int a[],int l, int r, int pivotindex)
{
int v=a[pivotindex],i,j;
hoandoi(&a[pivotindex],&a[r]);

}
}

15. Trình bày thuật toán tìm kiếm nhị phân? (mô tả thuật toán, cài đặt, độ phức tạp, ví
dụ)
Mô tả thuật toán:
- Input: mảng a[] đã được sắp xếp, có khóa tìm kiếm k.
- Output: vị trí của phần tử có khóa bằng k.
Cài đặt:
int binary_search(int a[], int left, int right, int key)
{
int mid;
while(left<=right)
{
mid=(left+right)/2;
if(a[mid]==key) return mid;
if(a[mid]<key) left=mid+1;
else right=mid-1;
}
return -1;
}
Độ phức tạp: O(log(n))
16. Trình bày chiến lược quy hoạch động? Ưu, nhược điểm? Ví dụ.
Quy hoạch động là 1 phương pháp giải bài toán bằng cách kết hợp các lời giải cho các bài
toán con của nó giống như phương pháp chia để trị. Quy hoạc động được áp dụng khi các bài
toán con của bài toán ban đầu không độc lập với nhau, chúng có chung các bài toán con nhỏ
hơn. Trong trường hợp như vậy 1 thuật toán chia để trị sẽ thực hiện nhiều việc hơn những gì
thực sự cần thiết, nó sẽ lặp lại việc giải quyết các bài toán con nhỏ hơn đó. 1 thuật toán quy
hoạch động sẽ chỉ giải quyết tất cả các bài toán con nhỏ 1 lần duy nhất sau đó lưu kết quả vào 1
bản ghi và điều này giúp nó tránh không phải tính toán lại các kết quả mỗi khi gặp 1 bài toán

Bước 2: Xây dựng công thức truy hồi tính độ dài lớn nhất của dãy con của 2 dãy
- Gọi C[i][j] là độ dài dãy con lớn nhất của 2 dãy X[1 i] và Y[1 j]
- C[i][0] = C[0][j] với mọi i, j.
- Lời giải của bài toán chính là C[n][m].
- Công thức truy hồi
[ 1][ 1] 1(1)
[ ][ ]
max( [ 1][ ], [ ][ 1])(2)
C i j
C i j
C i j C i j
  



 


- Trường hợp 1 là khi X[i] = Y[j], ngược lại là trường hợp 2.
Bước 3: Xây dựng thuật toán tìm dãy con chung dài nhất của 2 dãy X[1 n] và Y[1 m]
int longest_common_sequence(X,Y)
{
for(i=0;i<=m;i++) C[i][0]=0;
for(j=0;j<n;j++) C[0][j]=0;
Đ
Ề

CƯƠNG PT
TK && ĐGTT


}

Ta dùng 1 mảng D[i][j] trỏ ngược tới (i, j-1) hoặc (i-1, j) hoặc (i-1, j-1) và lần ngược từ D[m][n].
D[i][j] = 1 (Trên trái) nếu C[i][j] = 1 + C[i-1][j-1].
D[i][j] = 2 (Trên) nếu C[i][j] = C[i-1][j]
D[i][j] = 3 (Trái) nếu C[i][j] = C[i][j-1]

18. Trình bày bài toán nhân ma trận.
Để giảm số phép nhân cần dùng chúng ta sẽ tránh tạo ra các ma trận trung gian có kích
thước lớn và do phép nhân ma trận có tính kết hợp nên có thể đạt được điều này bằng cách sử
dụng các dấu đóng mở ngoặc để chỉ ra thứ tự phép nhân giữa các ma trận. Bên cạnh đó phép
nhân ma trận không đối xứng nên không thể hoán vị thứ tự của chúng mà không làm thay đổi
kết quả.
Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 18
Nếu có n ma trận thì sẽ có n+1 số nguyên là kích thước của chúng và sẽ có tổ hợp chập 2
của n phần tử các xâu con (mỗi xâu tương ứng với mỗi thứ tự của các dấu ngoặc) giữa 1 và n
nên chỉ cần dùng O(n
2
) không gian nhớ để lưu kết quả các bài toán con.
19. Trình bày chiến lược tham lam. Ưu, nhược điểm? Ví dụ.
Chiến lược tham lam cũng giống như các thuật toán quy hoạch động thường được sử

các lớp này có thể được sắp xếp giữa các lớp C
i
và C
j
.
Chúng ta có thể thêm vào 2 lớp giả định C
0
và C
n+1
với f
0
= −∞ và S
n+1
=+∞. Khi đó giá trị
S
0, n+1
sẽ là tập chứa tất cả các lớp.
Giả sử lớp C
k
là 1 phần của lịch học tối ưu của các lớp nằm trong S
i, j
khi đó i < k < j và lịch
học tối ưu bao gồm tập con lớn nhất của S
i, k
, {C
k
}, và 1 tập con lớn nhất của S
k, j
.
Thực hiện 1 lựa chọn tham lam:

(hoặc giảm dần) theo tuổi, cùng tuổi theo tên. Áp dụng giải thuật sắp xếp chọn (hoặc chèn,
hoặc nổi bọt, hoặc đổi chỗ, …)
1.

#include <stdio.h>
2. #include <conio.h>
3. typedef struct{
4. char ten[40],diachi[50];
5. int tuoi;
6. }svien;
7. void nhap(svien a[],int n)
8. {
9. int i;
10. for(i=0;i<n;i++)
11. {
12. printf("\nNhap thong tin sinh vien thu %d: \n",i+1);
13. printf("Ho ten: ");
14. fflush(stdin);
15. gets(a[i].ten);
16. printf("Dia chi: ");
17. fflush(stdin);
18. gets(a[i].diachi);
19. printf("Tuoi: ");
20. scanf("%d",&a[i].tuoi);
21. }
22. }
23. void hoandoi(svien *a, svien *b)
24. {
25. svien tg;
26. tg=*a;

43. printf("\nHo ten Dia chi
Tuoi\n");
44. for(i=0;i<n;i++)
45. printf("%-20s%-20s%10d\n",a[i].ten,a[i].diachi,a[i].tuoi);
46. }
47. void main()
48. {
49. svien sv[100];
50. int n;
51. printf("So sinh vien: ");
52. scanf("%d",&n);
53. nhap(sv,n);
54. xep(sv,n);
55. xuat(sv,n);
56. getch();
57. }

Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 21
2. Cho cấu trúc nhân viên gồm các trường: tên, năm sinh, hệ số lương, … Khai báo cấu trúc
nhân viên trên ở dạng danh sách liên kết. Cài đặt hàm sắp xếp danh sách nhân viên tăng dần
(hoặc giảm dần) theo năm sinh, cùng năm sinh theo tên. Áp dụng giải thuật sắp xếp chọn (hoặc

28. {
29. p->next=*list;
30. *list=p;
31. }
32. }
Đ
Ề

CƯƠNG PT
TK && ĐGTT

Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 22
33.

void nhap(listnode *list)
34. {
35. nhanvien a;
36. int n,i;
37. printf("So nhan vien: ");
38. scanf("%d",&n);
39. for(i=0;i<n;i++)
40. {
41. printf("\nNhap nhan vien thu %d:\n",i+1);
42. printf("Ten nhan vien: ");
43. fflush(stdin);
44. gets(a.ten);
45. printf("Nam sinh: ");


Tác giả: Đỗ Đức Hùng. Web: http://doduchung.co.cc Mail: [email protected] |Trang 23
69.

}
70. p=p->next;
71. }
72. }
73. void xuat(listnode *list)
74. {
75. listnode p;
76. p=*list;
77. printf("\nTen Nam sinh HSL\n");
78. while(p!=NULL)
79. {
80. printf("%-20s%12d%12d\n",p->nvien.ten,p->nvien.ns,p-
>nvien.hsl);
81. p=p->next;
82. }
83. }
84. void main()
85. {
86. listnode nv=NULL;
87. nhap(&nv);
88. xep(&nv);
89. xuat(&nv);
90. getch();

printf("Loai hang: ");
fflush(stdin);
gets(h[i].loai);
printf("Ten hang: ");
fflush(stdin);
gets(h[i].ten);
}
}
void xuat(hang h[],int n)
{
int i;
printf("\nMa hang Loai hang Ten hang\n");
for(i=0;i<n;i++)
printf("%-20d%-12s%-20s\n",h[i].ms,h[i].loai,h[i].ten);
}
int tim(hang h[],int n,int x)
{
int i=0;
while(h[i].ms!=x && i<n) i++;
if(i<n && (h[i].ms==x)) return i;
else return 0;
}
void main()
{
hang h[100];
int n,x;
printf("So mat hang: ");
scanf("%d",&n);
nhap(h,n);
xuat(h,n);