Lý thuyết:
1. Thuật toán là gì? Tính chất, cách biểu diễn, độ phức tạp?
a. Thuật toán là cách thức, quy trình để hoàn thành 1 công việc cụ thể xác định nào đó
b. Tính chất:
- Tính đúng đắn: Thuật toán cần phải đảm bảo cho một kết quả đúng sau khi thực hiện đối
với các bộ dữ liệu đầu vào.
- Tính dừng: Thuật toán cần phải đảm bảo sẽ dừng sau 1 số bước hữu hạn bước.
- Tính xác định: Các bước của thuật toán phải được hiểu rõ ràng, cụ thể, tránh gây nhập
nhằng hoặc nhầm lẫn đối với người đọc và hiểu, cài đặt thuật toán.
- Tính hiệu quả: thuật toán được xem là hiệu quả nếu như nó có khả năng giải quyets hiệu
quả bài toán đặt ra trong thời gian hoặc các điều kiện cho phép trên thực tế đáp ứng được
yêu cầu của người dùng
- Tính phổ quát: thuật toán có thể giải quyết được 1 lớp các bài toán tương tự
c. Cách biểu diễn: có 2 cách biểu diễn thuật toán:
- Mô tả các bước thực hiện của thuật toán.
- Sử dụng sơ đồ giải thuật
d. Độ phức tạp:
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ề 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.

Ví dụ:
Tác giả: Đỗ Đức Hùng. Website: Mail:
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(&a[vtmin],&a[i];
}
}
Đề cương ôn tập môn Phân tích, thiết kế và đánh giá thuật toán3
6. Trình bày thuật toán sắp xếp chèn (mô tả thuật toán, cài đặt, độ phức tạp, ví dụ)
Thuật toán dựa vào thao tác chính là chèn mỗi khóa vào một dãy con đã được sắp xếp của dãy cần
sắp xếp. Phương pháp này thường được sử dụng trong việc sắp xếp các cây bài trong quá trình chơi
bài.
Sơ đồ thuật toán:
Tác giả: Đỗ Đức Hùng. Website: Mail:
Đề cương ôn tập môn Phân tích, thiết kế và đánh giá thuật toán4
Cài đặt thuật toán bằng C:
Ví dụ:
Độ 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 có
thứ tự.

thì đổi chỗ a[i] và a[j]
Cài đặt thuật toán:
Sơ đồ thuật toán:
Tác giả: Đỗ Đức Hùng. Website: Mail:
void bubble_sort(int a[],int n)
{
int i,j;
for(i=n-1;i>=0;i )
for(j=1;j<=i;j++)
if(a[j-1]>a[j])
swap(&a[j-1],a[j]);
}
void bubble_sort2(int a[],int n)
{
int i,j;
for(i=0;i<n;i++)
for(j=n-1;j>i;j )
if(a[j-1]>a[j])
swap(&a[j-1],a[j]);
}
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;

- Khử đệ quy bằng đệ quy arsac
Ví dụ: Hàm tính số fibonaci thứ n
12. Thế nào là chiến lược vét cạn? Ưu, nhược điểm của vét cạn? Ví dụ.
Chiến lược vét cạn là thử tất cả các khả năng xem khả năng nào là nghiệm đúng của bài toán cần giải
quyết.
Ví dụ giải bài toán in ra tất cả các số nguyên tố 4 chữ số abcd sao cho ab=cd được thực hiện bằng
thuật toán vét cạn như sau:
Tác giả: Đỗ Đức Hùng. Website: Mail:
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);
}
}
int fb(int n)
{
if(n==1||n=2) return 1;
else return fb(n-1)+fb(n-2);
}
for(a=1;a<=9;a++)
for(b=0;b<=9;b++)
for(c=0;c<=9;c++)
for(d=0;d<=9;d++)
if(ngto(a*1000+b*100+c*10+d) && (10*a+b==10*c+d)
printf("%d%d%d%d",a,b,c,d);
Đề cương ôn tập môn Phân tích, thiết kế và đánh giá thuật toán9

x[k]=j;
try(k+1);
}
}
int power(int a,int n)
{
if(n==0) return 1;
else
{
int t=power(a,n/2);
if(n%2==0) return t*t;
else return a*t*t;
}
}
Đề cương ôn tập môn Phân tích, thiết kế và đánh giá thuật toán10
- Selection: Chọn 1 phần tử gọi là phần tử quay (pivot)
- Partition (phân hoạch): đặt tất cả các phần tử của mảng < phần tử quay sang bên trái và
ngược lại là sang bên phải phần tử quay. Phần tử quay trở thành phần tử có vị trí đúng
trong mảng.
- Đệ quy: gọi tới chính thủ tục sắp xếp nhanh đối với 2 nửa mảng nằm 2 bên phần tử quay
Ví dụ:
Trong ví dụ sau đây ta luôn chọn phần tử chốt là phần tử đứng giữa danh sách với chỉ số của phần tử
chốt được chọn là k = int((k
1
+ k
2
) / 2) + 1
a = (2,6,3,7,4,5,1)
7 4
Do ngẫu nhiên, phần tử chốt a[4] = 7 là phần tử lớn nhất trong dãy, ta tìm từ trái sang phải không có

{
int p=partition(A,l,r);
quicksort(A,l,p-1);
quicksort(A,p+1,r);
}
}
int partition(int *A, int l, int r)
{
int p=A[l];
int i=l+1;
int j=r;
while(l)
{
while(A[i]<=p && i<r) i++;
while(A[j]>=p && j>l) j ;
if(i>=j)
{
swap(A{[i],A[j]);
return j;
}
else swap(A[i],A[j]);
}
}
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;

của X[1 n-1] và Y[1 m].
- Ngược lại nếu ký tự không nằm trong Z là ký tự của Y thì Z sẽ là dãy con dài nhất của X[1 n] và
Y[1 m-1].
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]
Tác giả: Đỗ Đức Hùng. Website: Mail:
Đề cương ôn tập môn Phân tích, thiết kế và đánh giá thuật toán13
Bước 4: Tìm dãy con dài nhất của X[1 n] và Y[1 m]
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]
19. Trình bày bài toán nhân ma trận.

}
}
reverse lcs; //Dao nguoc xau lcs;
return lcs;
}
Đề cương ôn tập môn Phân tích, thiết kế và đánh giá thuật toán14
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.
20. 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ử dụng để giải
các bài toán tối ưu (tìm nghiệm của bài toán tốt nhất theo 1 tiêu chí nào đó). Các thuật toán quy
hoạch động luôn cho 1 nghiệm tối ưu. Các thuật toán tham lam thực hiện các lựa chọn tối ưu cục bộ
với hy vọng các lựa chọn đó sẽ dẫn đến 1 nghiệm tối ưu toàn cục cho bài toán cần giải quyết.
Ưu điểm: dễ cài đặt (độ phức tạp thời gian thường là hàm tuyến tính hoặc cùng lắm là bậc 2). Dễ gỡ
lỗi và sử dụng ít bộ nhớ.
Nhược điểm: Không phải lúc nào chúng cũng cho các lời giải tối ưu.
Ví dụ: Dãy số (3, 4, 5, 17, 7, 8, 9) cần chọn ra dãy con của nó sao cho dãy con đó là một dãy đơn
điệu tăng. Dễ dàng thấy kết quả đúng là (3, 4, 5, 7, 8, 9). Tuy nhiên theo cách chọn tham ăn sau khi
chọn xong 3 phần tử đầu là 3, 4, 5 sẽ chọn tiếp phần tử 17, phần tử hợp thành 1 dãy tăng dài hơn đối
với các phần tử được chọn trước đó và kết quả là 3, 4, 5, 17. Nhưng kết quả này không phải là đúng.
21. Trình bày bài toán sắp lịch các sự kiện.
Một phòng học chỉ có thể sử dụng cho 1 lớp học tại 1 thời điểm. Có n lớp học muốn sử dụng phòng
học, mỗi lớp học có 1 lịch học được cho bởi 1 khoảng thời gian I
j
=[s
j
, f

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:
Bổ đề 1: Tồn tại 1 lịch học (thời khóa biểu) tối ưu cho tập S
i, j
chứa lớp C
k
trong S
i, j
kết thúc đầu tiên,
có nghĩa là lớp C
k
trong S
i, j
với giá trị chỉ số k nhỏ nhất.
Bổ đề 2: Nếu chọn lớp C
k
như bổ đề 1 thì tập S
i, k
sẽ là tập rỗng.
Bài tập:
1. Cho cấu trúc sinh viên gồm các trường: tên, tuổi, địa chỉ, … Khai báo cấu trúc trên để có thể lưu

tg=*a;
*a=*b;
*b=tg;
}
//sap xep theo chieu tang dan
void xep(svien sv[], int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(sv[j].tuoi<sv[i].tuoi) hoandoi(&sv[j],&sv[i]);
else if(sv[j].tuoi==sv[i].tuoi && strcmp(sv[j].ten,sv[i].ten)<0)
hoandoi(&sv[j],&sv[i]);
}
void xuat(svien a[], int n)
{
int i;
printf("\nHo ten Dia chi Tuoi\n");
for(i=0;i<n;i++)
printf("%-20s%-20s%10d\n",a[i].ten,a[i].diachi,a[i].tuoi);
}
void main()
{
svien sv[100];
int n;
printf("So sinh vien: ");
scanf("%d",&n);
nhap(sv,n);
xep(sv,n);
xuat(sv,n);

listnode p;
p=getnode();
p->nvien=nv;
if(*list==NULL) *list=p;
else
{
p->next=*list;
*list=p;
}
}
void nhap(listnode *list)
{
nhanvien a;
int n,i;
printf("So nhan vien: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nNhap nhan vien thu %d:\n",i+1);
printf("Ten nhan vien: ");
fflush(stdin);
gets(a.ten);
printf("Nam sinh: ");
scanf("%d",&a.ns);
printf("He so luong: ");
scanf("%d",&a.hsl);
them(a,list);
}
}
void xep(listnode *list)

printf("%-20s%12d%12d\n",p->nvien.ten,p->nvien.ns,p->nvien.hsl);
p=p->next;
}
}
void main()
{
listnode nv=NULL;
nhap(&nv);
xep(&nv);
xuat(&nv);
getch();
}
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.
Áp dụng thuật toán vét cạn:
#include <stdio.h>
#include <conio.h>
typedef struct {
int ms;
char loai[10],ten[20];
}hang;
void nhap(hang h[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("Nhap mat hang thu %d: \n",i+1);
printf("Ma mat hang: ");
scanf("%d",&h[i].ms);

nhap(h,n);
xuat(h,n);
printf("Ma so can tim: ");
scanf("%d",&x);
if(tim(h,n,x)==0) printf("Khong tim thay key");
else printf("Vi tri: %d",tim(h,n,x)+1);
getch();
}
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, …
#include <stdio.h>
#include <conio.h>
int sngto(int a[], int n)
{
int i,tong;
for(i=0;i<n-1;i++)
{
tong=a[i]+a[i+1];
if(tong!=2 && tong!=3 && tong!=5 && tong!=7)
if((tong==1||tong%2==0||tong%3==0||tong%5==0||tong%7==0)) return 0;
}
return 1;
}
void hoandoi(int *a,int *b)
{
int tg;
tg=*a;
*a=*b;
*b=tg;

hoandoi(&a[k],&a[i]);
dau=i+1;
cuoi=n-1; //Lat nguoc doan cuoi giam dan, a:
while(dau<cuoi)
{
hoandoi(&a[dau],&a[cuoi]);
dau++;
cuoi ;
}
}
}while(i>=0);
}
void main()
{
int a[100],n;
printf("So phan tu can hoan vi: ");
scanf("%d",&n);
autonhap(a,n);
sinhhoanvi(a,n);
getch();
}
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, …
#include <stdio.h>
#include <conio.h>
/*int ktra(int a[],int n)
{
int i;

xuly(0,a,k);
getch();
}
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, …
#include <stdio.h>
#include <conio.h>
void xuat(int a[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d",a[i]);
printf("\t");
}
void test(int i, int a[],int n)
{
int j;
for(j=0;j<=9;j++)
if(i==0 && j!=0 || i!=0)
{
a[i]=j;
if(i==n-1) xuat(a,n);
else
test(i+1,a,n);
}
}
void main()
{
int a[100],n;

khi đó F[i,i]=0 với mọi i.
Để tính M
i
*M
i+1
* *M
j
ta có thể có nhiều cách kết hợp:
M
i
*M
i+1
* *M
j
=(M
i
*M
i+1
* *M
k
) * (M
k+1
* M
k+2
* * M
j
) (Với
i k j
≤ <
)

* * M
j
) có
kích thước a
k+1
x a
j+1
. Vậy chi phí này là a
i
*a
k+1
*a
j+1
Từ đó suy ra: do có nhiều cách kết hợp, mà ta cần chọn cách kết hợp để có chi phí ít nhất nên ta sẽ
cực tiểu hóa F[i,j] theo công thức:
[ ] [ ] [ ]
1 1
, min( , 1, * * )
i k j
F i j F i k F k j a a a
+ +
= + + +
Tại mỗi bước tính F[i,j] ta ghi nhận lại điểm k, chẳng hạn ta đặt T[i,j]=k
Sau là code chương trình:
#include <conio.h>
#include <stdio.h>
void nhap(int a[],int n)
{
int i;
for(i=0;i<n+1;i++)

p=a[i];
q=a[k+1];
r=a[j+1];
x=f[i][k]+f[k+1][j]+p*q*r;
if(x<f[i][j])
{
f[i][j]=x;
t[i][j]=k;
Tác giả: Đỗ Đức Hùng. Website: Mail:
Đề cương ôn tập môn Phân tích, thiết kế và đánh giá thuật toán23
}
}
}
}
void trace(int i,int j,int t[][100])
{
int k;
if(i==j) printf("M[%d]",i+1);
else
{
printf("(");
k=t[i][j];
trace(i,k,t);
printf(" * ");
trace(k+1,j,t);
printf(")");
}
}
void main()
{

{
int i,j;
a[0]=' ';
b[0]=' ';
printf(" ");
for(i=0;i<strlen(a);i++) printf("%3c",a[i]);
printf("\n");
for(i=0;i<strlen(b);i++)
{
printf("%c",b[i]);
for(j=0;j<strlen(a);j++)
printf("%3d",c[i][j]);
printf("\n");
}
Tác giả: Đỗ Đức Hùng. Website: Mail:
Đề cương ôn tập môn Phân tích, thiết kế và đánh giá thuật toán25