›
›

Bài giảng Tin học đại cương - Phần 2, Chương 2: Thuật toán

pptx 73 trang haiha333 07/01/2022 5201
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tin học đại cương - Phần 2, Chương 2: Thuật toán", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_tin_hoc_dai_cuong_phan_2_chuong_2_thuat_toan.pptx

Nội dung text: Bài giảng Tin học đại cương - Phần 2, Chương 2: Thuật toán

  1. Phần 2: Giải quyết bài toán Nội dung chính 1. Chương 1: Giải quyết bài toán • Khái niệm về bài toán • Quá trình giải quyết bài toán bằng máy tính • Phương pháp giải quyết bài toán bằng MT 2. Chương 2: Thuật toán • Khái niệm • Biểu diễn thuật toán • Thuật toán đệ quy • Thuật giải heuristic • Một số thuật toán thông dụng 01-Jan-16 33
  2. Bạch Tuyết Sai đẹp hơn Đúng Thỏa mãn Tìm cách hại Ngừng Đến nhà 7 chú lùn Lừa Bạch Tuyết Về lâu đài 01-Jan-16 34
  3. Chương 2: Thuật toán Nội dung chính 1. Khái niệm 2. Biểu diễn thuật toán 3. Thuật toán đệ quy 4. Thuật giải heuritic 5. Một số thuật toán thông dụng 01-Jan-16 35
  4. Chương 2: Thuật toán 1. Khái niệm Khái niệm • Thuật toán (algorithm) là khái niệm cơ sở của Toán học và Tin học • Nghiên cứu thuật toán đóng vai trò quan trọng trong khoa học máy tính – Máy tính chỉ có khả năng thực hiện công việc theo một thuật toán. – Thuật toán chỉ đạo máy tính từng bước phải làm gì. Thuật toán là gì? 01-Jan-16 36
  5. Chương 2: Thuật toán 1. Khái niệm Khái niệm • Một tập các lệnh hay chỉ thị nhằm hướng dẫn việc thực hiện một công việc nào đó • Bao gồm một dãy hữu hạn các chỉ thị rõ ràng và có thể thi hành được, được bố trí theo một trình tự nhất định, cần thực hiện trên những dữ liệu vào sao cho sau một số hữu hạn bước ta thu được kết quả của bài toán cho trước • Thuật toán là sự thể hiện của một phương pháp để giải quyết một vấn đề 01-Jan-16 37
  6. Chương 2: Thuật toán 1. Khái niệm Ví dụ Tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên 1. Đặt giá trị lớn nhất tạm thời (Max) bằng số nguyên đầu tiên của dãy Max là giá trị lớn nhất ở mỗi giai đoạn thực hiện 2. Nếu tất cả số nguyên nào trong dãy đã được xét, thực hiện bước 5 3. So sánh số nguyên kế tiếp trong dãy với Max • Nếu lớn hơn Max thì thay Max bằng số nguyên này. 4. Lặp lại bước 2 5. Thông báo: Max là giá trị lớn nhất trong dãy số. 01-Jan-16 38
  7. Chương 2: Thuật toán 1. Khái niệm Ví dụ Đổi số thập phân sang dạng nhị phân 1 1. Cho biết N 2 2. Chia N cho 2 3 3. Ghép phần dư vào bên trái kết quả N≠0 4 4. Lấy phần thương làm N mới 5. Nếu N khác 0, lặp lại Bước 2 5 6. Xong 6 01-Jan-16 39
  8. Chương 2: Thuật toán 1. Khái niệm Định nghĩa (KHMT) Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác và trình tự thực hiện các thao tác đó sao cho sau khi thực hiện dãy thao tác này theo trình tự đã chỉ ra, với đầu vào (input) ta thu được kết quả đầu ra (output) mong muốn 01-Jan-16 40
  9. Chương 2: Thuật toán 1. Khái niệm Thao tác/lệnh • Là hành động cần được thực hiện bởi cơ chế của thuật toán • Các thao tác (lệnh) sẽ biến đổi bài toán từ trạng thái trước tới trạng thái sau • Dãy các thao tác cần thiết sẽ biến đổi bài toán từ trạng thái ban đầu đến kết quả • Các thao tác có thể phân tích thành thao tác khác nhỏ hơn • Thứ tự thao tác là quan trọng – Cùng tập thao tác, thứ tự khác nhau dẫn đến kết quả khác nhau • Cơ cấu thể hiện trình tự thực hiện các thao tác gọi là Cấu trúc điều khiển 01-Jan-16– Có 3 loại cơ bản: Tuần tự, Lặp, Rẽ nhánh 41
  10. Chương 2: Thuật toán 1. Khái niệm Các đặc trưng của thuật toán Khi mô tả thuật toán, cần chú ý các đặc trưng – Nhập (input) – Xuất (output) – Tính xác định (definiteness) – Tính hữu hạn (finiteness) – Tính hiệu quả – Tính tổng quát 01-Jan-16 42
  11. Chương 2: Thuật toán 1. Khái niệm Nhập/Xuất • Nhập (input): – Các giá trị “đầu vào” (input values) từ một tập hợp nhất định nào đó. • Xuất (output): – Những giá trị trả về (output values) thuộc một tập hợp nhất định nào đó thể hiện lời giải cho bài toán/vấn đề – Tương ứng với tập hợp các giá trị nhập 01-Jan-16 43
  12. Chương 2: Thuật toán 1. Khái niệm Tính xác định (definiteness) • Các bước trong thuật toán phải chính xác rõ ràng, không gây sự nhập nhằng nhầm lẫn • Cùng một điều kiện nhập, cùng một giải thuật thì 2 bộ VXL (người, máy) phải cho ra cùng một kết quả 01-Jan-16 44
  13. Chương 2: Thuật toán 1. Khái niệm Tính hữu hạn (finiteness) • Trong mọi trường hợp của dữ liệu vào, thuật toán phải cho ra hay kết quả sau một thời gian hữu hạn – Thời gian có thể phụ thuộc vào từng bài toán cụ thể hoặc phụ thuộc vào các thuật toán khác nhau cho một bài toán 01-Jan-16 45
  14. Chương 2: Thuật toán 1. Khái niệm Tính hiệu quả • Thực hiện thuật toán cần – Thời gian – Các công cụ hỗ trợ (giấy, bộ nhớ, ) • Để ghi kết quả trung gian • Độ phức tạp thuật toán: Thời gian và các công cụ hỗ trợ – Thuật toán càng hiệu quả độ phức tạp càng bé – Trong máy tính, thường quan tâm tới • Thời gian thực hiện – Số thao tác cơ bản cần thựchiện 01-Jan-16 • Độ lớn của bộ nhớ mà thuật toán sử dụng 46
  15. Chương 2: Thuật toán 1. Khái niệm Tính tổng quát Thuật toán có tính tổng quát cao nếu có thể giải bất kỳ bài toán nào trong một lớp lớn các bài toán Ví dụ Thuật toán giải phương trình ax2+bx+c=0 phổ dụng hơn thuật toán giải phương trình x2+5x+6=0 01-Jan-16 47
  16. Chương 2: Thuật toán Nội dung chính 1. Khái niệm 2. Biểu diễn thuật toán 3. Thuật toán đệ quy 4. Thuật giải heuristic 5. Một số thuật toán thông dụng 01-Jan-16 48
  17. Chương 2: Thuật toán 2. Biểu diễn thuật toán Đặt vấn đề • Tại sao: – Truyền đạt thuật toán cho người khác – “Truyền đạt” thuật toán cho máy tính • Chuyển thành chương trình điều khiển • Phương pháp: 1. Ngôn ngữ tự nhiên 2. Ngôn ngữ lưu đồ(sơ đồ khối) 3. Ngôn ngữ tựa ngôn ngữ lập trình (mã giả) 4. Ngôn ngữ lập trình 01-Jan-16 49
  18. Chương 2: Thuật toán 2. Biểu diễn thuật toán 1. Ngôn ngữ tự nhiên • Nguyên tắc: – Sử dụng ngôn ngữ tự nhiên để liệt kê các bước của thuật toán • Đặc điểm – Không yêu cầu phải có một số kiến thức đặc biệt – Dài dòng – Không làm nổi bật cấu trúc của thuật toán 01-Jan-16 50
  19. Chương 2: Thuật toán 2. Biểu diễn thuật toán 1. Ngôn ngữ tự nhiên→Ví dụ 1 Giải phương trình ax+ b = 0 • B1: Nhập a • B2: Nhập b. • B3: Nếu a =0 thực hiện B6 • B4: Thông báo: Nghiệm –b/a • B5: Thực hiện B10 • B6: Nếu b = 0, thực hiện B9 • B7: Thông báo: Phương trình vô nghiệm. • B8: Thực hiện B10 • B9: Thông báo: Phương trình vô số nghiệm. • B10: Kết thúc 01-Jan-16 51
  20. Chương 2: Thuật toán 2. Biểu diễn thuật toán 1. Ngôn ngữ tự nhiên→Ví dụ 2 Tìm giá trị lớn nhất của một dãy N số nguyên • B1:Nhập N • B2: Nhập dãy số ai gồm N số. • B3:Gán giá trị a1 cho Max, 2 cho biến i (i2) • B4:Nếu i > N, thực hiện bước 8 • B5:Nếu ai > Max, gán giá trị ai choMax. • B6:Tăng i lên 1 đơn vị. • B7:Quay lên B4. • B8:Thông báo: Max là giá trị lớn nhất dãy • B9:Kết thúc. 01-Jan-16 52
  21. Chương 2: Thuật toán 2. Biểu diễn thuật toán 1. Ngôn ngữ lưu đồ (sơ đồ khối) Công cụ diễn đạt các thuật toán trực quan • Đưa ra một cái nhìn tổng quan về quá trình xử lý theo thuật toán • Gồm hệ thống các nút có hình dạng khác nhau, thể hiện các chức năng khác nhau, được nối với nhau bởi các cung Thành phần chủ yếu của thuật toán 01-Jan-16 53
  22. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Nút /khối giới hạn • 2 loại nút giới hạn: nút đầu và nút cuối • Ghi rõ điểm bắt đầu và kết thúc (dừng) của thuật toán • Được biểu diễn bởi hình ôvan có ghi chữ bên trong BẮT ĐẦU KẾT THÚC 01-Jan-16 54
  23. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Nút/Khối thao tác Là một hình chữ nhật chứa dãy các lệnh cần thực hiện như gán, tính toán = b2-4ac 01-Jan-16 55
  24. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Nút/khối vào/ra dữ liệu Là một hình bình hành chứa đựng một thao tác nhập/ xuất dữ liệu Nhập a, b In giá trị Max 01-Jan-16 56
  25. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Nút/khối điều kiện Là một hình thoi chứa một điều kiện/biểu thức logic cần kiểm tra. Đúng Sai a < b Nút điều kiện có 2 cung ra chỉ hướng ứng với 2 trường hợp: điều kiện đúng và điều kiện sai 01-Jan-16 57
  26. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Nút/khối gọi chương trình con Là một hình chữ nhật, cạnh kép chứa tên một chương trình con cần thực hiện – Chương trình con: Thuật toán đã biết – Nhằm cho sơ đồ đỡ rắc rối Đổi chỗ A và B 01-Jan-16 58
  27. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Cung Là các đường nối từ nút này đến nút khác của lưu đồ Đúng > 0 sai X = . Vô Nghiệm 01-Jan-16 59
  28. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Hoạt động • Bắt đầu từ nút giới hạn đầu tiên (nút bắt đầu). • Thực hiện các thao tác được ghi trong nút • Theo một cung đi tới nút khác • Nếu là nút điều kiện: đi theo cung tương ứng với trạng thái của điều kiện được kiểm tra. • Thuật toán sẽ dừng khi gặp nút kết thúc 01-Jan-16 60
  29. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Ví dụ 1 → Biểu diễn bằng lời Giải phương trình ax+ b = 0 • B1: Nhập a • B2: Nhập b. • B3: Nếu a =0 thực hiện B6 • B4: Thông báo: Nghiệm –b/a • B5: Thực hiện B10 • B6: Nếu b = 0, thực hiện B9 • B7: Thông báo: Phương trình vô nghiệm. • B8: Thực hiện B10 • B9: Thông báo: Phương trình vô số nghiệm. • B10: Kết thúc 01-Jan-16 61
  30. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Ví dụ 1 → Biểu diễn sơ đồ khối Bắt đầu Nhập a, b Sai Đúng a = 0 x = -b/a Sai Đúng b = 0 Nghiệm là: x Vô Nghiệm Vô số Nghiệm Kết thúc 01-Jan-16 62
  31. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Ví dụ 2 → Biểu diễn bằng lời Tìm giá trị lớn nhất của một dãy N số nguyên • B1:Nhập N • B2: Nhập dãy số ai gồm N số. • B3:Gán giá trị a1 cho Max, i2. • B4:Nếu i > N, thực hiện bước 8 • B5:Nếu ai > Max, gán giá trị ai choMax. • B6:Tăng i lên 1 đơn vị. • B7:Quay lên B4. • B8:Thông báo: Max là giá trị lớn nhất dãy • B9:Kết thúc. 01-Jan-16 63
  32. Chương 2: Thuật toán 2. Biểu diễn thuật toán 2. Sơ đồ khối → Ví dụ 2 → Biểu diễn sơ đồ khối 01-Jan-16 64
  33. Chương 2: Thuật toán 2. Biểu diễn thuật toán 3. Ngôn ngữ tựa ngôn ngữ lập trình (mã giả) • Mô tả thuật toán theo ngôn ngữ tựa ngôn ngữ lập trình – Sử dụng các mệnh đề có cấu trúc chuẩn hóa – Vẫn dùng ngôn ngữ tự nhiên. • Có thể sử dụng các ký hiệu toán học • Có thể sử dụng cấu trúc kiểu thủ tục để trình bày thuật toán đệ quy/thuật toán phức tạp • Đặc điểm: – Tiện lợi, đơn giản, và dễ hiểu. • Các cấu trúc thường gặp: – Gán, lựa chọn, lặp, nhảy, gọi hàm 01-Jan-16 65
  34. Chương 2: Thuật toán 2. Biểu diễn thuật toán 3. Mã giả → Phát biểu gán • Mục đích: – Đặt giá trị cho một biến • Biểu diễn: Max := a1 Max a1 n  n + 1 01-Jan-16 66
  35. Chương 2: Thuật toán 2. Biểu diễn thuật toán 3. Mã giả → Lựa chọn/rẽ nhánh if then endif Hoặc là if then else endif 01-Jan-16 67
  36. Chương 2: Thuật toán 2. Biểu diễn thuật toán 3. Mã giả → Cấu trúc lặp while do end while repeat until for biếngiá trị đầu to giá trị cuối do end for for biến giá trị đầu downto giá trị cuối do end for 01-Jan-16 68
  37. Chương 2: Thuật toán 2. Biểu diễn thuật toán 3. Mã giả → Lệnh nhảy không điều kiện Nhảy đến vị trí có nhãn là L goto L 01-Jan-16 69
  38. Chương 2: Thuật toán 2. Biểu diễn thuật toán 3. Mã giả → Hàm/Thủ tục • Khai báo hàm Function ( ) Hành động với các tham số return End Function • Gọi hàm [Call] ( ) 01-Jan-16 70
  39. Chương 2: Thuật toán 2. Biểu diễn thuật toán 3. Mã giả → Ví dụ: tìm số lớn nhất của dãy 1. Begin 2. Input N i N Sai 3. Input a1, a 2, aN 4. Max a1 5. i  2 6. While i N do 7. If ai > Max Then 8. Max  ai 9. End if 10. i i+1 11.End while 12.Output Max 13.End 01-Jan-16 71
  40. Chương 2: Thuật toán 2. Biểu diễn thuật toán 4. Ngôn ngữ lập trình • Tuân theo cú pháp của ngôn ngữ lập trình – Cấu trúc tuần tự – Cấu trúc rẽ nhánh – Cấu trúc lặp – Chương trình con • Tồn tại nhiều loại ngôn ngữ lập trình – Ngôn ngữ máy /Hợp ngữ – Ngôn ngữ bậc cao: • Fortran, Pascal, C/C++/C#,Java 01-Jan-16 72
  41. Chương 2: Thuật toán 2. Biểu diễn thuật toán 4. Ngôn ngữ lập trình → Ví dụ #include Giải phương trình ax+b=0 int main(){ float a,b; Bắt đầu scanf("%f %f",&a,&b); if(a==0) if (b==0) printf("Vo so nghiem"); Nhập a, b else printf("Vo nghiem"); else printf("Nghiem %f",-b/a); Sai Đúng return 0; a = 0 } x = -b/a Sai Đúng b = 0 Nghiệm là: x Vô Nghiệm Vô số Nghiệm Kết thúc 01-Jan-16 73
  42. Chương 2: Thuật toán Nội dung chính 1. Khái niệm 2. Biểu diễn thuật toán 3. Thuật toán đệ quy 4. Thuật giải heuristic 5. Một số thuật toán thông dụng 01-Jan-16 74
  43. Chương 2: Thuật toán 3. Thuật toán đệ quy Ví dụ đệ quy 01-Jan-16 75
  44. Chương 2: Thuật toán 3. Thuật toán đệ quy Khái niệm thuật toán đệ quy • Bài toán có thể được phân tích và đưa tới việc giải một bài toán cùng loại nhưng cấp độ thấp hơn, – Độ lớn dữ liệu vào nhỏ hơn – Giá trị cần tính toán nhỏ hơn • Ví dụ: Định nghĩa giai thừa Giai thừa của một số tự nhiên n, ký hiệu là n!, được định nghĩa bằng cách quy nạp như sau: • 0!=1, • n!=(n-1)!*n, với mọi n>0 • Giải một bài toán có thể dựa trên chính nó – Mỗi bước của thuật toán hiện lại chính thuật toán đó • Dữ liệu vào có độ lớn thấp hơn Thuật toán đệ qui. 01-Jan-16 76
  45. Chương 2: Thuật toán 3. Thuật toán đệ quy Ví dụ 1: Tính giai thừa của một số tự nhiên • Input: số tự nhiên n • Output: F(n)=n! • Thuật Toán: Function F(n); If n=0 then F = 1 Else F:=n * F(n-1) End If return F End Function 01-Jan-16 77
  46. Chương 2: Thuật toán 3. Thuật toán đệ quy Ví dụ 2: Bài toán tháp Hà nội A B C Yêu cầu: Dịch chuyển N đĩa từ cọc A sang B với trung gian là cọc C Trường hợp với N= 2: A B C 01-Jan-16 78
  47. Chương 2: Thuật toán 3. Thuật toán đệ quy Ví dụ 2: Bài toán tháp Hà nội Trường hợp tổng quat với N > 2: A B C PROCEDURE ThapHanoi (N,A,B,C) IF N= 2 Then Print(A→C, A→B, C→B) ELSE ThapHanoi(N-1,A,C,B) Print(A →B) ThapHaNoi(N-1,C,B,A) ENDIF 01-JanE-16ND 79
  48. Chương 2: Thuật toán 3. Thuật toán đệ quy Lưu ý • Thuật toán đệ qui gồm 2 phần – Phần cơ sở: không cần thực hiện lại thuật toán • Không có yêu cầu gọi đệ qui. • Là điều kiện dừng cử giả thuật đệ quy – Phần đệ qui: có yêu cầu gọi đệ qui • Yêu cầu thực hiện lại thuật toán • Đặt trong một điều kiện kiểm tra việc gọi đệ qui. • Đệ qui dễ gây tình trạng tràn bộ nhớ (stack). • Nếu có thể, nên viết dưới dạng lặp. P1 For k 1 To N Do P P*k Print P 01-Jan-16 80
  49. Chương 2: Thuật toán Nội dung chính 1. Khái niệm 2. Biểu diễn thuật toán 3. Thuật toán đệ quy 4. Thuật giải heuristic 5. Một số thuật toán thông dụng 01-Jan-16 81
  50. Chương 2: Thuật toán 4. Thuật giải Heuristic Vấn đề mở rộng khái niệm thuật toán • Có những bài toán đến nay vẫn chưa có một cách giải theo kiểu thuật toán được tìm ra và cũng không biết có tồn tại thuật toán hay không. • Có những bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá dài hoặc các điều kiện cho thuật toán khó đáp ứng • Có những bài toán được giải theo cách giải vi phạm thuật toán nhưng vẫn được chấp nhận. Cần phải đổi mới cho khái niệm thuật toán – Mở rộng những tiêu chuẩn của thuật toán 01-Jan-16 82
  51. Chương 2: Thuật toán 4. Thuật giải Heuristic Mở rộng tiêu chuẩn của thuật toán • Tính xác định (tính đơn trị của mỗi bước) – Các giải thuật đệ qui: bước tiếp gọi đến chính nó – Các giải thuật ngẫu nhiên: bước tiếp không xác định rõ • Tính đúng đắn (được hiểu cho kết quả đúng) – Không còn bắt buộc với một số cách giải cho các bài toán nhất là các cách giải gần đúng. – Trong thực tế có nhiều trường hợp, chấp nhận các cách giải cho kết quả gần đúng nhưng ít phức tạp và hiệu quả • Ví dụ: trong trí tuệ nhân tạo – Cách giải theo kiểu heuristic. Đơn giản, tự nhiên nhưng cho kết quả đúng hoặc gần đúng trong phạm vi cho phép 01-Jan-16 83
  52. Chương 2: Thuật toán 4. Thuật giải Heuristic Thuật giải Heuristic • Khái niệm thuật giải: – Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán • Thuật giải heuritic – Thể hiện cách giải bài toán với các đặc tính sau: • Tìm được lời giải tốt (không chắc là tốt nhất) • Dễ dàng và nhanh chóng hơn so với giải thuật tối ưu • Thể hiện một cách hành động khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người. 01-Jan-16 84
  53. Chương 2: Thuật toán 4. Thuật giải Heuristic Nguyên lý thiết kế thuật giải heuristic • Nguyên lý vét cạn thông minh: – Trong một bài toán tìm kiếm, khi không gian tìm kiếm lớn, thường tìm cách để giới hạn lại không gian hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu. • Nguyên lý tham lam: – Lấy tiêu chuẩn tối ưu (trên phạm vi toàn bộ) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải. • Nguyên lý thứ tự: – Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được 01-Jan-16 một lời giải tốt 85
  54. Chương 2: Thuật toán Nội dung chính 1. Khái niệm 2. Biểu diễn thuật toán 3. Thuật toán đệ quy 4. Thuật giải heuristic 5. Một số thuật toán thông dụng 01-Jan-16 86
  55. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Các bài toán 1. Thuật toán số học – Hoán đổ giá trị – Số nguyên tố, phân tích ra thừa số nguyên tố – Tìm ước số chung, phân số tối giản – Số hoàn hảo 2. Thuật toán về dãy – Vào/ra dãy – Tìm Max, Min – Sắp xếp – Tìm phần tử; Đếm phần tử – Tính toán trên các phần tử • Trung bình cộng, tính tổng, 01-Jan-16– Chèn phần tử/Xóa phần tử (liên quan tới kiểu mảng)87
  56. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Hoán đổi giá trị 2 biến X, Y Nguyên tắc: Dùng một biến trung gian T Begin 1. TX 2. X Y 3. YT End Function swap(X,Y) TX X Y YT End Function 01-Jan-16 88
  57. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Kiểm tra số nguyên tố Begin 1. Input P 2. Flag  FALSE 3. If P=1 Then Goto Bước 6 4. flag  TRUE (gán cho cờ hiệu “flag” giá trị true) 5. For k:=2 to p-1 do Function Prime(P):Bool If (k là ước số của P) Then Flag  FALSE flag  FALSE; Goto B6 return Flag Endif End Function End for 6. If flag=TRUE Then Output: P là số nguyên tố Else Output: P không là số nguyên tố Endif 0E1-Jnand-16 89
  58. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Liệt kê các số nguyên tố [2 N] Bắt đầu Begin Input N Nhập N For p  2 to N do p 2 If Prime(P) Then Output: P Endif Sai p N End For Đúng End Đúng Prime(P) Hiển thị P Sai p p + 1 Kết thúc 01-Jan-16 90
  59. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Tìm ƯSCLN của 2 số nguyên dương (1/3) 1. Nhập số a 2. Nhập số b 3. Chia a cho b với số dư là r 4. Nếu r = 0 thực hiện 6 5. Nếu r ≠0 gán giá trị b cho a, giá trị r cho b và quay lại bước 3 6. Thông báo kết quả ƯSCLN là b 7. Kết thúc 01-Jan-16 91
  60. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Tìm ƯSCLN của 2 số nguyên dương (2/3) Bắt đầu Begin Nhập a, b 1. Input a, b 2. Repeat r = a MOD b 3. r  a MOD b 4. if r=0 then goto 8 Đúng r=0 5. a  b Sai 6. b  r a b b r 7. Until r=0 8. Output USCLN là: b ƯSCLN là b End Kết thúc 01-Jan-16 92
  61. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Tìm ƯSCLN của 2 số nguyên dương (3/3) Bắt đầu Begin Nhập a, b 1. Input a, b 2. Repeat r = a MOD b 3. r  a MOD b a b 4. a  b b r 5. b  r Sai 6. Until r=0 r =0 7. Output USCLN là: a Đúng End ƯSCLN là a Kết thúc 01-Jan-16 93
  62. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Giải phương trình ax2+bx+c = 0 01-Jan-16 94
  63. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Nhập dãy số cho tới khi tổng lớn hơn 2012 Bắt đầu S 0 Begin 1. S0 Nhập a 2. Repeat Input a S S +a S S + a 3. Until S > 2012 S S > 2012 End Đ Kết thúc 01-Jan-16 95
  64. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Bài tập tại lớp Mô tả các thuật toán (sơ đồ khối/mã giả) sau 1. Nhập dãy số nguyên cho tới khi gặp một số âm và đưa ra tổng của các số chia hết cho 5 2. Nhập dãy số nguyên cho tới khi gặp một số chia hết cho 5 và dưa ra trung bình cộng của các số dương trong dãy đã nhập 3. Nhập dãy số cho tới khi gặp số âm và đưa ra số lượng các số nằm trong đoạn [11 22] 4. Nhập dãy số cho tới khi tổng của dãy lớn hơn 1001 hoặc số phần tử đã nhập là 100 01-Jan-16 96
  65. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Nhập giá trị cho dãy N số Bắt đầu Begin Nhập day(N) 1. Input N 2. i  1 Đọc N 3. While i N do i1 4. Input ai 5. i i+1 Sai 6. End while i N End Đúng NhapDay(N) Begin Nhập ai 1. Input N ii+1 2. For i 1 to N do Input ai 3.End For Kết thúc End 01-Jan-16 97
  66. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Tìm phần tử nhỏ nhất cho dãy N số Bắt đầu Begin 1. Nhapday(N) NhapDay(N) 2. p1 p1 3. i 2 i 2 4. While i N do Đúng 5. If ai N 6. pi Sai Đúng 7. Endif ai<ap pi Sai 8. i i+1 i i + 1 9. Endwhile 10. Output P/tử nhỏ nhất: p P/tử thứ p nhỏ nhất End Kết thúc 01-Jan-16 98
  67. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Tìm tổng của dãy gồm N số Bắt đầu Begin Tổng các số lẻ 1. NhapDay(N) NhapDay(N) chia hết cho 5 2. S 0 3. For i 1 to N do S0 Begin i 1 S  S+ ai 1. NhapDay(N) Sai 4. En d For i N 2. S 0 5.Ou tput: Tổng là S Đúng 3. i  1 End SS+ai 4. While i N do S  S + ai i i + 1 i i+1 5. End while Tổng là: S 6. Output: Tổng là S End 01-Jan-16 Kết thúc 99
  68. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Kiểm tra phần tử có thuộc dãy (1/3) Begin 1. Nhập N, dãy số a1, a2, aN và số cần tìm A 2. i1 3. Nếu i > N sang bước 7 4.Nếu A = ai sang bước 8 5. ii+1 6. Quay về bước 3 7. Thông báo: A không thuộc dãy và kết thúc 8. Thông báo A thuộc dãy và kết thúc End 01-Jan-16 100
  69. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Kiểm tra phần tử có thuộc dãy (2/3) Bắt đầu Begin Hủy bỏ lệnh 1. NhapDay(N) NhapDay(N) Goto ? 2.Input A 3. i 1 Nhập số cần tìmA 4. While (i N) Do If a =A Then i 1 i Output A ở vị tríi Đúng Goto B7 i > N Số A không tồntại End If Sai Đúng ii+1 ai=A A tồn tại ở vị trí i Sai 5. End While i i + 6. Output A không tồntại 1 7. Kết thúc End 01-Jan-16 101
  70. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Kiểm tra phần tử có thuộc dãy (3/3) Bắt đầu Begin 1. NhapDay(N) NhapDay(N) 2.Input A 3. i 1 4. While (i N AND a A) Do Nhập số cần tìmA i i  i + 1 i 1 5. End While 6. If ai=A Then Output A ởvị trí i 7. ELSE Output A không tồntại Sai i N AND ai A 8. End If End Đúng Đúng Sai i i + 1 ai=A A tồn tại ở vị trí i Số A không tồntại 01-Jan-16 Kết thúc 102
  71. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Sắp xếp theo thứ tự tăng của dãy gồm N số Begin Đã Đã sắp 1. Nhập N và dãy a1, a2, aN a1 2. i  1  xếp 3. Nếu i = N, thuật toán kết thúc ai-1 4. j  i + 1 i Đang ai j xét 5. Nếu j > N thực hiện bước 9 ai+1 6.Nếu aj < ai thì đổi chỗ ai và aj Chưa sắp 7. j j + 1  8. Quay lại thực hiện bước 5 xếp 9. i  i + 1 10. Quay lại thực hiện bước 3 aN End 01-Jan-16 103
  72. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Sắp xếp theo thứ tự tăng của dãy gồm N số Bắt đầu Begin NhapDay(N) 1. NhapDay(N) 2. i 1 i1 3. While i N i j Sai 7. End If a < a Đúng 8. j  j+1 j i Swap(a i, aj) Sai 9. End while jj+1 10. i  i + 1 11.End while ii+1 End 01-Jan-16 Kết thúc 104
  73. Chương 2: Thuật toán 5. Một số thuật toán thông dụng Bài tập về nhà Mô tả các thuật toán (sơ đồ khối/mã giả) sau • Đếm số chẵn của một dãy N số nguyên • Đưa ra trung bình cộng các số dương của một dãy gồm N số • Sắp xếp lại dãy N số thực theo nguyên tắc: – Các số 0 ở đầu dãy, sau đó là các số âm rồi đến các số dương • Đếm số hạng đạt giá trị bằng giá trị lớn nhất • . 01-Jan-16 105