Download miễn phí Bài giảng Cơ sở dữ liệu - Một số giải thuật cơ bản
Bài tập cài đặt
Viết bổ sung các hàm vào chương trình xử lý mảng 1 chiều
các hàm thực hiện những yêu cầu sau:
1. Viết hàm sắp xếp tăng theo PP insertion sort cho dữ liệu số
nguyên/số thực/ký tự/ chuỗi ký tự.
2. Viết hàm sắp xếp tăng theo PP interchange sort cho dữ liệu
số nguyên/số thực/ký tự/ chuỗi ký tự.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Chương 2. MỘT SỐ GIẢI THUẬT CƠ BẢNCẤU TRÚC DỮ LIỆU
Created by Bich Ngan 02/2012
1. Giải thuật tìm kiếm trên mảng số
2
1.1. Tìm kiếm tuyến tính (Linear Search)
Ý tưởng:
Thuật toán tiến hành so sánh x lần lượt với các phần tử thứ
1, thứ 2,… của mảng a cho đến khi gặp phần tử có khóa cần
tìm, hay đã tìm hết mảng mà không thấy x.
Ví dụ: Cho dãy số sau:
5 3 6 8 9 1 2
Tìm phần tử có giá trị x = 9, x= 10
Created by Bich Ngan3
Minh họa ví dụ
Vị trí trong dãy (i) 0 1 … 4
Giá trị a 5 3 … 9
Kết quả so sánh
a và x 5!= 9 3!=9 … 9= = 9
Created by Bich Ngan4
Xét dãy số A có 7 phần tử:
5 3 6 8 9 1 2
Tìm x = 9
Tìm
được
x=9 tại
vị trí 4.
Kết thúc
quá
trình
Minh họa ví dụ
Vị trí trong dãy
(i) 0 1 … 6 7
Giá trị a 5 3 … 2 null
Kết quả so sánh
a và x 5!= 10 3!=10 … 2!= 10
Created by Bich Ngan5
Xét dãy số A có 7 phần tử:
5 3 6 8 9 1 2
Tìm x = 10
i=7, a
không
tồn tại.
Không
có 10
trong
dãy A.
Kết thúc
quá trình
1.1. Tìm kiếm tuyến tính (Linear Search) (tt)
Cài đặt
Created by Bich Ngan6
int LinearSearch (int a[], int n, int x)
{
for(int i=0;i
return i; // trả về vị trí của x trong a
return -1; // trả về -1 báo là không có x trong a
}
1.2. Thuật toán tìm kiếm nhị phân (Binary Search)
Ý tưởng
Giả sử dãy số a đã có thứ tự tăng.
Tại mỗi bước tiến hành so sánh x với phần tử nằm vị trí giữa của
dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định
giới hạn dãy tìm ở bước kế tiếp là nửa trên hay nửa duới của dãy tìm
kiếm hiện hành.
Ví dụ:
Cho dãy a có 7 phần tử: 3 4 6 8 9 10 13
Tìm x = 10 và x = 2
Created by Bich Nga7
Minh họa ví dụ
Cho dãy số a: 3 4 6 8 9 10 13
tìm x= 10.
Created by Bich Ngan8
Bước left right Mid = [(left+right)/2] a[mid]
Kết quả
so sánh x
và a[mid]
1 0 6 [(0+6)/2] = 3 8 8<10
2 Left = mid +1
= 3+1 = 4
6 [(4+6)/2] = 5 10 10 = = 10
Tìm
được
x=10 tại
vị trí 5.
Kết thúc
quá
trình
Minh họa ví dụ
Cho dãy số a: -1 0 6 8 9 10 13
tìm x= 2.
Created by Bich Ngan9
Bước left right Mid =[(left+right)/2] a[mid]
Kết quả so sánh
x và a[mid]
1 0 6 [(0+6)/2] = 3 8 8>2
2 0 Right = mid – 1
= 3-1 = 2
[(0+2)/2] = 1 0 0 < 2
3 Left = mid +1
= 1+1 = 2
2 2 6 6>2
4 2 Mid-1 = 2-1=1 ?
Tại bước 4 có left>right -> vô lý.
Kết luận không có x = 2 trong a
1.2. Tìm kiếm nhị phân (Binary Search) (tt)
Cài đặt
Created by Bich Ngan10
int BinarySearch (int a[], int n, int x)
{
int left = 0, right = n-1;
while(left<=right)
{
int mid = (left + right)/2;
if(a[mid] == x)
return mid;
else
if( a[mid]
}
return -1;
}
Bài tập lý thuyết
Cho dãy số sau:
7 9 13 17 27 30 31 35 38 40
a. Tìm x= 17, x=35, x=40
b. Tìm x = 23, x=10, x=36
Cho dãy ký tự
Z R L K H F E C A
a. Tìm x = R, x = C
b. Tìm x = D, x = Q
Created by Bich Ngan11
Bài tập thực hành
Cho mảng 1 chiều a chứa n số nguyên. Viết chương trình thực hiện các
yêu cầu sau:
1. Viết hàm nhập/xuất mảng a.
2. Tìm max/min của a.
3. Đếm số phần tử chẵn/lẻ trong a.
4. Tìm kiếm phần tử x trong a theo 2 dạng ( trả về vị trí/xuất câu thông
báo) với giải thuật tìm kiếm tuyến tính/ tìm kiếm nhị phân.
5. Tìm trên a có bao nhiêu phần tử x.
Created by Bich Ngan12
Bài tập (tt)
6. Tìm trên a có bao nhiêu phần tử lớn hơn x.
7. Tính tổng các phần tử của a.
8. Xuất các số nguyên tố trong a.
9. Xuất các số hoàn thiện trong a.
10. Xuất các phần tử ở vị trí chẵn/ vị trí lẻ trong a.
11. Xuất giá trị max/min kèm theo vị trí của giá trị đó trong mảng a.
12. Cho 2 dãy số b có m phần tử, dãy c có n phần tử. Ghép b và c thành
dãy a được xếp tăng dần.
13
2 Các giải thuật sắp xếp cơ bản
14
Đường link xem demo của các giải thuật sắp xếp:
2. CÁC GIẢI THUẬT SẮP XẾP
(Các thuật toán minh họa sắp xếp dãy không tăng trên mảng
1 chiều chứa dữ liệu là các số nguyên)
Created by Bich Ngan15
Các phương pháp sắp xếp thông dụng
2.1. Sắp xếp đổi chỗ trực tiếp – Interchange Sort
2.2. Sắp xếp chọn trực tiếp – Selection Sort
2.3. Sắp xếp chèn trực tiếp – Insertion Sort
2.4. Sắp xếp ổi bọt – Bubble Sort
Sắp xếp là quá trình xử lý một danh sách các phần tử để đặt
chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên
nội dung thông tin lưu trữ tại mỗi phần tử.
2.1. Sắp xếp đổi chỗ trực tiếp – interchange Sort
Khái niệm nghịch thế:
Xét dãy các số a: a1, a2, … an, với a là dãy không giảm.
Nếu iaj thì ta gọi đó là 1 nghịch thế.
Ví dụ: Cho dãy số a như sau:
14 5 7 8 3.
Vậy dãy trên trên có các cặp nghịch thế sau: (14, 5); (7, 3); (8, 3)….
Ý tưởng thuật toán:
Xuất phát từ đầu dãy, lần lượt xét từng phần tử cho đến cuối
dãy. Tại mỗi phần tử tìm tất cả nghịch thế chứa phần tử này,
đổi chỗ phần tử này với các phần tử trong cặp nghịch thế.
Created by Bich Ngan16
Minh họa ví dụ interchange sort
Cho dãy số a
Bước 1: xét nghịch thế của phần tử thứ 0 – a0
Created by Bich Ngan17
10 14 52 73091
10 14 52 73091
i=0 j=1
2 14 510 73091
i=0 j=2
Minh họa ví dụ interchange sort (tt)
Created by Bich Ngan18
1 14 510 73092
i=1 j=2
1 14 52 730910
i=2 j=4
1 14 102 73095
i=3 j=4
Bước 2: xét nghịch thế của phần tử thứ 1 – a1
Bước 3: xét nghịch thế của phần tử thứ 2 – a2
Bước 4: xét nghịch thế của phần tử thứ 3 – a3
Created by Bich Ngan19
Minh họa ví dụ interchange sort (tt)
Bước 4: xét nghịch thế của phần tử thứ 3 – a3 tiếp theo
1 10 142 73095
i=3 j=5
1 9 142 730105
i=3 j=7
1 7 142 930105
i=4 j=5
Bước 5: xét nghịch thế của phần tử thứ 4 – a4
Minh họa ví dụ interchange sort (tt)
Bước 4: xét nghịch thế của phần tử thứ 4 – a4 tiếp theo
Bước 5: xét nghịch thế của phần tử thứ 6 – a6
1 7 102 930145
i=4 j=7
1 7 92 1030145
i=5 j=7
1 7 92 1430105
i=6 j=7
Bước 5: xét nghịch thế của phần tử thứ 5 – a5 tiếp theo
1 7 92 3014105
Dừng. Vậy dãy đã được sắp xếp.
Ví dụ
Minh họa thao tác sắp xếp dữ liệu theo phương pháp
interchange Sort cho các dãy dữ liệu sau:
Sắp xếp tăng:
13 8 12 6 9 10 12 7
A H K R E C Z G
Sắp xếp giảm
13 8 12 6 9 10 12 7
A H K R E C Z G
Created by Bich Ngan21
Cài đặt
Created by Bich Ngan22
void Interchangesort(int a[],int n)
{
for(int i=0;i
swap(a,a[j]); //ham hoan doi gia
//tri 2 so nguyen
}
void swap(int &x, int &y)
{
int t = x;
x = y;
y = t;
}
Bài tập cài đặt
Viết bổ sung các hàm vào chương trình xử lý mảng 1 chiều
các hàm thực hiện những yêu cầu sau:
1. Viết hàm sắp xếp tăng theo PP interchange sort cho dữ liệu
số nguyên/số thực/ký tự/ chuỗi ký tự.
2. Viết hàm sắp xếp tăng theo PP interchange sort cho dữ liệu
số nguyên/số thực/ký tự/ chuỗi ký tự.
Created by Bich Ngan23
2.2. Sắp xếp chọn trực tiếp – Selection sort
Ý tưởng giải thuật
Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa
phần tử này về vị trí thứ 0 của dãy hiện hành; sau đó
không quan tâm đến nó nữa, xem dãy hiện hành chỉ
còn (n – 1) phần tử, bắt đầu từ vị trí thứ 1; lặp lại quá
trình đó trên dãy hiện hành… đến khi dãy hiện hành
chỉ còn 1 phần tử thì dừng
Created by Bich Ngan24
Created by Bich Ngan25
Minh họa ví dụ Selection sort
Cho dãy số a
Bước 1: Tìm min của dãy số từ a0 – an-1 . Sau đó hoán đổi min với a0
10 14 52 73091
10 14 52 73091
i=0
min
Created by Bich Ngan26
Minh họa ví...