Kỹ thuật lập trình - Tuần 10: Thuật toán

10/25/2016 1 Tuần 10 - Thuật toán Giáo viên: Hà Đại Dương duonghd@mta.edu.vn Kỹ thuật lập trình 10/25/2016 1 Nội dung 1. Thuật toán (Khái niệm, Biểu diễn) 2. Thuật toán sắp xếp – Sắp xếp chọn – Sắp xếp chèn – Sắp xếp nổi bọt 3. Thuật toán tìm kiếm – Tuần tự – Nhị phân 4. Bài tập 10/25/2016 2 Thuật toán 10/25/2016 3 10/25/2016 2 • Một thuật toán là một bản liệt kê các chỉ dẫn, các quy tắc cần thực hiện theo từng bước xác định nhằm giải quyết một bài toán đã cho trong một khoảng thời gian hữu hạn. • Tai sao cần thuật toán?? Chuyển thành chương trình (ngôn ngữ nào đó) 1 cách dễ dàng và đúng đắn. • Ví dụ: Mô tả thuật toán giải quyết bài toán tìm phần tử lớn nhất trong dãy có n số cho trước. Khái niệm 10/25/2016 4 Mô tả thuật toán tìm số lớn nhất 1. Chỉ số phần tử lớn nhất tạm thời (LNTT) = chỉ số phần tử đầu tiên; 2. So sánh số tiếp theo với giá trị LNTT, nếu lớn hơn giá trị LNTT thì đặt:  Chỉ số phần tử LNTT = chỉ số phần tử đó; 3. Nếu còn phần tử trong dãy -> lặp lại bước 2). 4. Phần tử LNTT ở thời điểm này chính là phần tử lớn nhất trong dãy (cần tìm). 10/25/2016 5 Dạng giả mã 10/25/2016 6 10/25/2016 3 Tính chất của TT 1. Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác. 2. Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnh minh bạch; các câu lệnh được sắp xếp theo thứ tự nhất định. 10/25/2016 7 Tính chất của TT 3. Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính vẫn phải cho kết quả như nhau. 4. Tính phổ dụng: Thuật toán không chỉ áp dụng cho một bài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau. 5. Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán. 10/25/2016 8 Biểu diễn thuật toán • Có 3 cách biểu diễn thuật toán: – Dùng ngôn ngữ tự nhiên – Sơ đồ khối và – Giả mã. • Dùng ngôn ngữ tự nhiên: mô tả các bước xử lý bằng ngôn ngữ viết. 10/25/2016 9 10/25/2016 4 Mô tả dữ liệu vào/ra • Dữ liệu đầu vào: Một thuật toán phải mô tả rõ các giá trị đầu vào từ một tập hợp các dữ liệu xác định. Ví dụ, dãy số nguyên a(1), a(2), ..., a(n), với n<. • Dữ liệu đầu ra: Từ một tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán. Ví dụ, io là chỉ số phần tử lớn nhất trong a(1),...,a(n). 10/25/2016 10 Ví dụ • Thuật toán tìm số lớn nhất 10/25/2016 11 Sơ đồ khối • Sử dụng bộ kí hiệu các khối để thể hiện thuật toán. • Bộ kí hiệu: – Hộp chữ nhật: Các toán tử gán và phép toán tính toán; – Hình thoi: Phép toán so sánh cho kết quả thuộc tập: {đúng, sai}. – Đường kẻ + mũi tên: Chỉ thao tác tiếp theo; – Hình elip: Bắt đầu hoặc Kết thúc thuật toán 10/25/2016 12 10/25/2016 5 10/25/2016 13 YES NO YES NO START input a1, a2, .., an k = 1 i = 2 k = i ai > ak i ≤ n i = i + 1 END output ak Giả mã • Sử dụng ngôn ngữ tự nhiên kết hợp với một ngôn ngữ lập trình. • Cần tuân thủ quy tắc của một ngôn ngữ: – Có các cấu trúc cơ bản: tuần tự, lặp và rẽ nhánh. – Có hệ thống từ khóa, từ điển (phụ thuộc vào bài toán). • Dễ hiểu, dễ cài đặt. 10/25/2016 14 Ví dụ 10/25/2016 15 10/25/2016 6 Chương trình 10/25/2016 16 Ví dụ 2 • Tìm phần tử có giá trị b trong dãy có n số cho trước. 10/25/2016 17 10/25/2016 18 10/25/2016 7 Chất lượng biểu diễn thuật toán 1. Đúng với ý tưởng đặt ra của bài toán 2. Đơn giản, dễ hiểu 3. Dễ cài đặt 10/25/2016 19 Tính hiệu quả 1. Thời gian: Chi phí cho thời gian tính toán ít hơn so với các thuật toán giải quyết cùng bài toán. 2. Bộ nhớ: Chiếm dụng bộ nhớ ít hơn so với các thuật toán giải quyết cùng bài toán. 3. Độ chính xác: Nếu là cung cấp lời giải gần đúng thì gần với lời giải đúng hơn so với thuật toán giải quyết cùng bài toán 10/25/2016 20 Tính hiệu quả • Tùy theo bài toán, mục đích mà xét các tiêu chí nói trên. • Tùy theo chất lượng của thuật toán mà có thể xét trên mọi tập dữ liệu thử nghiệm, hoặc trên một số tập dữ liệu minh họa cho một vài khía cạnh nào đó. 10/25/2016 21 10/25/2016 8 Ví dụ 3 • Bài toán: Đếm số lần xuất hiện giá trị b trong dãy a. • Biểu diễn thuật toán 1. Dạng mô tả bằng lời 2. Dạng sơ đồ khối 3. Dạng giả mã • Viết chương trình (10 phút) 10/25/2016 22 Thuật toán sắp xếp 10/25/2016 23 Bài toán • Cho một mảng a (giá trị của nó so sánh được), hãy sắp xếp mảng a tăng (hoặc giảm) dần. • Một số bài toán thực tế: – Danh sách lớp: Sắp xếp theo họ tên (tiếng Việt) – Bảng điểm tổng kết quả khoá học: sắp xếp theo điểm tổng kết – Bảng điểm kết quả thi đại học: sắp xếp theo SBD – • Ví dụ: Sắp xếp dãy 8, 6, 9, 7, 5 giảm dần 10/25/2016 24 10/25/2016 9 Sắp xếp chọn(Selection sort) 10/25/2016 25 Sắp xếp chọn • Thuật toán: 1. Phần tử đang xem xét là i = 0 2. Chọn phần tử lớn nhất trong đoạn [i .. N-1] và đổi chỗ cho phần tử đang xét i; 3. Nếu chưa hết dãy: Đặt i = i + 1, lặp lại bước 2 Nếu hết dãy chuyển đến bước 4. 4. Kết thúc: Mảng đã sắp xếp giảm dần • Ý tưởng trên đã đề cập đến trong tuần 6 10/25/2016 26 Ví dụ 4 • Biểu diễn thuật toán sắp xếp chọn (10 phút): – Dạng sơ đồ khối – Dạng giả mã • Viết chương trình (10 phút) – Hàm sắp xếp – Hàm in kết quả 10/25/2016 27 10/25/2016 10 10/25/2016 28 Sắp xếp chèn (Insertion sort) 10/25/2016 29 Ý tưởng • Với 1 dãy đã sắp xếp, ví dụ: 9, 5,2 • Việc thêm vào được thực hiện bằng cách duyệt từ cuối lại để tìm vị trí đúng của nó và chèn vào. Ví dụ thêm và 7 ở dãy trên. • Dãy có 1 phần tử được hiểu là đã sắp xếp 10/25/2016 30 9,5,2,7 9,5,7,2 9,7,5,2 9,7,5,2 10/25/2016 11 Ví dụ 5 • Sắp xếp dãy 8, 6, 9, 7, 5 giảm dần 8 6 -> 8,6 9 -> 8,6,9 -> 8,9,6 -> 9,8,6 7 -> 9,8,6,7 -> 9,8,7,6 5 -> 9,8,7,6,5 10/25/2016 31 Giả mã • Input: A[0..N-1] phần từ • Ouput: A[0..N-1] đã được sắp xếp không tăng • for i=1 -> N-1 1. x=A[i]; 2. vt=i; 3. while (vt>0 && A[vt-1]<x) –A[vt]=A[vt-1]; –vt--; 4. A[vt]=x; 10/25/2016 32 Ví dụ 5 • Viết hàm sắp xếp 1 mảng giảm dần (10 phút) 10/25/2016 33 10/25/2016 12 Sắp xếp nổi bọt (Bubble sort) 10/25/2016 34 Ý tưởng • Xét hai phần tử ở đầu tiên của dãy, nếu không đúng thứ tự đổi chỗ cho nhau • Tiếp tục xét các cặp đến cuối dãy • Lặp lại quá trình với cặp đầu dãy đến lúc không có cặp nào bị thay đổi 10/25/2016 35 Giả mã • Input: A[0..N-1] phần tử • Output: A[0..N-1] phần tử sắp xếp không tăng • for i= N-1 -> 1 1. solandoi=0 2. for j=0->i-1 if(a[j]>a[j+1]) - DoiCho(a[j],a[j+1]); - solandoi = solandoi +1; 3. if (solandoi ==0) break; 10/25/2016 36 10/25/2016 13 Ví dụ 6 • Sắp xếp giảm dần sử dụng thuật toán Bubble sort. • Hàm DoiCho(x,y) dùng để đổi giá trị của x và y cho nhau đã viết ở bài trước. • Viết hàm (10 phút) 10/25/2016 37 Thuật toán tìm kiếm 10/25/2016 38 Tìm kiếm tuần tự • Tìm phần tử có giá trị b trong mảng a gồm n phần tử. • Với mảng a và b là số ta đã làm ở ví dụ 2 10/25/2016 39 10/25/2016 14 Xem lại ví dụ 2 • Giả mã 10/25/2016 40 Xem lại ví dụ 2 10/25/2016 41 Ví dụ 7 • Viết chương trình tìm kiếm (tuần tự) Họ tên 1 sinh viên trong danh sách sinh viên của lớp. • Viết chương trình (10 phút) 10/25/2016 42 10/25/2016 15 Tìm kiếm nhị phân • Xét bài toán tìm b trong dãy a có n phần tử. • Nếu a đã được sắp xếp (tăng dần) -> có thể tìm kiếm nhanh hơn theo ý tưởng sau: 1. So sánh b với phần tử ở “giữa” của a, phần tử k 2. Nếu bằng nhau -> Kết thúc 3. Nếu b<a[k], chỉ cần tìm b trong đoạn [0,k-1] 4. Nếu b>a[k], chỉ cần tìm b trong đoạn [k+1,n-1] Thực hiện tương tự cho bước 3/bước 4 (với đoạn ngắn hơn) 10/25/2016 43 Giả mã • Viết thuật toán dạng giả mã (15 phút) 10/25/2016 44 Input: a[0..N-1], x 1. vt = -1; 2. l = 0; 3. r = N-1; 2. while(l<=r) a. k=(l+r)/2; b. if (a[k]=x) vt=k; break; else if(a[k]<x) i = k + 1; else r=k-1; Ví dụ 8 • Viết hàm tìm kiếm nhị phân (10 phút) 10/25/2016 45 10/25/2016 16 Bài tập 10/25/2016 46 Bài tập 1. Mô tả thuật toán sắp xếp chọn – Dạng sơ đồ khối – Dạng giả mã 2. Mô tả thuật toán sắp xếp chèn – Dạng sơ đồ khối – Dạng giả mã 10/25/2016 47 Bài tập về nhà 1. Mô tả thuật toán sắp xếp nổi bọt – Dạng sơ đồ khối – Dạng giả mã 2. Mô tả thuật toán tìm kiếm tuần tự – Dạng sơ đồ khối – Dạng giả mã 3. Mô tả thuật toán tìm kiếm nhị phân – Dạng sơ đồ khối – Dạng giả mã 10/25/2016 48 10/25/2016 17 Bài tập về nhà 4. Tìm hiểu và thử ngiệm thuật toán sắp xếp nhanh (Quick sort) 5. Tìm hiểu và thử ngiệm thuật toán sắp xếp trộn (Merge sort) 10/25/2016 49