ĐẠI HỌC SÀI GÒN
1
PHÂN TÍCH VÀ THIẾT KẾ
GIẢI THUẬT
Giảng viên hướng dẫn : Th.S Nguyễn Hòa
Nhóm sinh viên thực hiện:
Nguyễn Xuân Vũ – 3109410224
Ngô Văn Chơn – 3109410016
Lê Thị Diễm Trinh – 3109410196
Đặng Anh Đào – 3109410030
I. Chiến lược thiết kế trực tiếp
1. Bài toán tìm cặp điểm gần nhau
a. Thuật toán
private void BruteForce(Pairs []d,ref Pairs A)
{
double Dmin = 9999;
A = new Pairs();
for (int i = 0; i < d.Length; i++)
for (int j = i + 1; j < d.Length; j++)
{
double k = Math.Sqrt((d[i].x - d[j].x) * (d[i].x -
d[j].x) + (d[i].y- d[j].y) * (d[i].y - d[j].y));
if (k < Dmin)
{
Dmin = k;
A.x = i; A.y = j;
}
}
}
b. Độ phức tạp
- Thao tác cơ bản là : Math.Sqrt((d[i].x - d[j].x) * (d[i].x - d[j].x) + (d[i].y- d[j].y) *

- Trường hợp tốt nhất T(n) = O(n)
- Trường hợp xấu nhất thực hiện n-m+1 chuyến so sánh mỗi chuyến thực hiện
m lần so các ký tự, T(n) = O(nm)
- Trường hợp trung bình T(n) = (
∑
i=0
n−m
(
1
)
mcp/(n-m+1) + (1-p)(n-m+1)mc
c. Test
Mảng Thời gian
100 0000289 (?)
2000 0005001 (?)
5000 0007068 (?)
d. Giao diện chương trình demo
II. Chiến lược thiết kế quy hoạch động
1. Bài toán Fibonacci
a. Giải thuật
public double Values()
{
double[] a = { 0, 1, 1 };
if (_n < 0) return 0;
if (_n < 3) return a[_n];
for (int i = 3; i <= _n; i++)
{
a[0] = a[1];
4
a[1] = a[2];