Tin học đại cương Chương 3: Lý thuyết thuật toán

bangtqh@utc2.edu.vn TIN HỌC ðẠI CƯƠNG Chương 3: Lý thuyết thuật toán Tin học đại cương - Chương 3 2bangtqh@utc2.edu.vn Nội dung 1. Khái niệm thuật toán. 2. Chương trình máy tính, ngôn ngữ lập trình. 3. Tính chất của thuật toán. 4. Các cách biểu diễn thuật toán. 5. Thiết kế và phân tích thuật toán. 6. Đệ quy và thuật toán đệ quy. 7. Một số bài toán tìm kiếm, sắp xếp đơn giản. 8. Bài tập. Tin học đại cương - Chương 3 3bangtqh@utc2.edu.vn Tin học Đại cương - Chương 3 3/51 Thuật toán là gì? Thuật toán, thuật giải, hay giải thuật, ñều dùng để chỉ một thuật ngữ tiếng Anh có tên là ALGORITHM. Chúng ta sẽ tìm hiểu: q Thuật toán theo cách hiểu thông thường q Các thao tác trong thuật toán q Định nghĩa thuật toán trong tin học Tin học đại cương - Chương 3 4bangtqh@utc2.edu.vn Thuật toán - cách hiểu thông thường q Bất cứ công yêu cầu gì cũng cần phải được giải quyết một cách khoa học Theo nghĩa rộng, khái niệm “thuật toán” (algorithm) được sử dụng ở mọi nơi, không riêng gì trong lĩnh vực tin học. q Theo cách hiểu thông tường Thuật toán là một loạt các thao tác (operation) có thứ tự (order) nhằm giải quyết một yêu cầu nào đó. q Ví dụ: “Thuật toán nấu cơm” – Bước 0: Ước lượng gạo cần thiết – Bước 1: Vo gạo – Bước 2: Cho gạo và nước thích hợp vào nồi cơm điện(NCĐ) – Bước 3: Cắm điện, chuyển chế ñộ “cook” – Bước 4: Chờ ñến khi NCĐ chuyển sang chế ñộ “warm” – Bước 5: Chờ thêm 10 phút nữa – Bước 6: Cơm chín, kết thúc. Tin học đại cương - Chương 3 5bangtqh@utc2.edu.vn Trò chơi 5 quân bài q Chọn 5 quân bài ngẫu nhiên trong bộ bài 52 quân. q Yêu cầu: Hãy tìm ra quân bài lớn nhất trong số các quân bài hiện có. – Mỗi lần chỉ ñược lật 1 quân bài trong số 5 quân. – Ghi lại quá trình tìm kiếm theo mỗi bước Tin học đại cương - Chương 3 6bangtqh@utc2.edu.vn Trò chơi 5 quân bài … Quân bài lớn nhất là: Tin học đại cương - Chương 3 7bangtqh@utc2.edu.vn Trò chơi 5 quân bài (tt) So sánh Quân bài lớn nhất: Tin học đại cương - Chương 3 8bangtqh@utc2.edu.vn Trò chơi 5 quân bài (tt) So sánh Quân bài lớn nhất: Tin học đại cương - Chương 3 9bangtqh@utc2.edu.vn Trò chơi 5 quân bài (tt) So sánh Quân bài lớn nhất: Tin học đại cương - Chương 3 10bangtqh@utc2.edu.vn Trò chơi 5 quân bài (tt) So sánh Quân bài lớn nhất: Tin học đại cương - Chương 3 11bangtqh@utc2.edu.vn Các thao tác trong thuật toán q Thao tác tuần tự (sequential operation): Một công việc đã được xác định rõ ràng, thực hiện xong thì chuyển sang công việc khác. q Thao tác kiểm tra điều kiện (conditional operation): Kiểm tra điều kiện đưa ra có thoả mãn hay không để quyết định thao tác tiếp theo. q Thao tác lặp (iterative operation): Quay trở lại bước nào đó trong dãy thao tác. – Một thao tác có thể ñược lặp đi lặp lại nhiều lần tới khi một điều kiện nào đó ñược thoả mãn Tin học đại cương - Chương 3 12bangtqh@utc2.edu.vn Định nghĩa giải thuật – (Cách 1) q Giải thuật là một dãy các câu lệnh chặt chẽ và rõ ràng xác định một trình tự thao tác trên một đối tượng nào đó sao cho sau một số bước hữu hạn thực hiện, ta thu được kết quả mong muốn. – Câu lệnh (statement): đơn vị thao tác, tính toán, xử lý – Trình tự rõ ràng (well-ordered): thực hiện xong bước này mới chuyển sang bước khác, không nhập nhằng. – Đối tượng (object): các dữ kiện của bài toán, dữ liệu trung gian, kết quả,… – Kết quả (result): Thông tin, lời giải cho bài toán,… Tin học đại cương - Chương 3 13bangtqh@utc2.edu.vn Định nghĩa giải thuật – Cách 2 q Giải thuật là bất cứ thủ tục tính toán (computational procedure) nào nhận các dữ liệu vào (input) và trả thông tin ra (output). q Giải thuật là dãy các thao tác xử lý dữ liệu để có được thông tin mong muốn. q Ví dụ: “Bài toán sắp xếp dãy số” – Input: Dãy số. – Output: Dãy số ñã sắp xếp. INPUT ALGORITHM OUTPUT Tin học đại cương - Chương 3 14bangtqh@utc2.edu.vn Chương trình máy tính q Máy tính? – Làm theo “lệnh” của con người. – Điểm mạnh là tính toán với tốc độ cao (hàng tỷ phép tính trên giây). q Làm thế nào để “ra lệnh” cho máy tính? – Lập chương trình cho máy tính. q Chương trình ? – Nói cho máy tính biết phải làm gì, như thế nào,… Tin học đại cương - Chương 3 15bangtqh@utc2.edu.vn Ngôn ngữ lập trình q Muốn “ra lệnh” cho máy tính: – Sử dụng một “ngôn ngữ” chung ngôn ngữ lập trình (programming language) – Lập trình (computer programming) • Dùng ngôn ngữ lập trình lập nên chương trình hoạt động cho máy tính. q Các thế hệ của ngôn ngữ lập trình – Thế hệ 1 (bậc thấp): ngôn ngữ máy, assembly. – Thế hệ 2: Gần với ngôn ngữ tự nhiên hơn, phục vụ những nhu cầu lập trình nhất định (FORTRAN, COBOL, ALGOL,… ) – Thế hệ 3: Gần gũi, vạn năng (PASCAL, C, C++,…) – Thế hệ 4: Truy vấn, hỗ trợ quyết định, lập trình trí tuệ nhân tạo (SQL, LISP, PROLOG,…). Tin học đại cương - Chương 3 16bangtqh@utc2.edu.vn Từ giải thuật đến chương trình q Giải thuật chỉ là “phương pháp”. q Sử dụng giải thuật như thế nào để giải quyết bài toán – Cần phải có máy tính. – Lập trình: Mô tả (cài đặt) giải thuật lên máy tính. q Biểu diễn đối tượng xử lý bởi dữ liệu (data) trong chương trình (có nhiều kiểu dữ liệu với cấu trúc khác nhau). q Thuật giải + cấu trúc dữ liệu = chương trình ALGORITHMSDATA STRUCTURES PROGRAM+ = Tin học đại cương - Chương 3 17bangtqh@utc2.edu.vn Chương trình viết bằng ngôn ngữ C Tin học đại cương - Chương 3 18bangtqh@utc2.edu.vn “Giải thuật nấu cơm” q Giải thuật nấu cơm (đề phòng trường hợp có thêm khách) – Bước 0: Ước lượng số gạo cần thiết. – Bước 1: Vo gạo. – Bước 2: Cho gạo và nước thích hợp vào nồi cơm điện(NCĐ). – Bước 3: Cắm điện, chuyển chế ñộ “cook”. – Bước 4: Chờ ñến khi NCĐ chuyển sang chế ñộ “warm”. – Bước 5: Chờ thêm 10 phút nữa. – Bước 6: Cơm chín. Nếu không có thêm khách thì sang bước 8. – Bước 7: Quay lại bước 0. – Bước 8: Kết thúc. q Nhận xét: Bước 6 là thao tác kiểm tra điều kiện và bước 7 là thao tác lặp. Tin học đại cương - Chương 3 19bangtqh@utc2.edu.vn Các tính chất của thuật toán q Tính hữu hạn dừng – Một thuật toán bất kỳ phải đảm bảo dừng sau một số hữu hạn bước. q Tính đúng đắn – Thuật toán phải đảm bảo giải quyết bài toán một cách đúng đắn, cho kết quả “chính xác” và “đầy đủ” theo yêu cầu. q Tính đơn giản và hiệu quả – Đơn giản: Dễ hiểu, dễ lập trình. – Hiệu quả: Tiêu tốn ít thời gian và tài nguyên máy tính. Tin học đại cương - Chương 3 20bangtqh@utc2.edu.vn Các tính chất của thuật toán (tt) q Tính xác định: – Mỗi thao tác thực hiện trong thuật toán phải được xác định rõ ràng, không gây hiểu lầm. q Tính phổ dụng: – Mọi thuật toán phải đảm bảo giải quyết được nhiều bài toán đồng dạng, trên nhiều bộ số liệu khác nhau. q Luôn có ñại lượng vào ra (input/output) – Mọi thuật toán đều phải minh họa cách nhận số liệu vào để tính toán (input) sau ñó thông báo kết quả tìm được (output). Tin học đại cương - Chương 3 21bangtqh@utc2.edu.vn Có phải mọi bài toán đều có thuật giải ? q Có những bài toán không có giải thuật tổng quát để giải quyết. q Có những bài toán chưa có giải thuật hữu hiệu để giải quyết. q Có những bài toán chưa có giải thuật tìm lời giải. Tin học đại cương - Chương 3 22bangtqh@utc2.edu.vn Các cách biểu diễn thuật toán q Liệt kê từng bước q Sơ đồ khối q Sử dụng giả ngôn ngữ lập trình Tin học đại cương - Chương 3 23bangtqh@utc2.edu.vn Phương pháp liệt kê từng bước q Các thao tác của giải thuật được liệt kê từng bước. q Tại mỗi bước, sử dụng ngôn ngữ tự nhiên ñể diễn tả công việc phải làm. q Bước đứng trước (có số thứ tự nhỏ hơn) được thực hiện trước. q Ưu nhược điểm – Dễ hiểu, dễ làm – Phụ thuộc vào “cách hành văn” của người diễn đạt – Với những giải thuật phức tạp, cách diễn đạt này trở nên rườm rà – … Tin học đại cương - Chương 3 24bangtqh@utc2.edu.vn Ví dụ q Giải thuật “Tìm vị trí xuất hiện đầu tiên của một số nguyên trong dãy số nguyên ñã cho”: – Bước 1: Nhập dãy số nguyên a1, a2, …., aN – Bước 2: Nhập số nguyên s – Bước 3: Gán vị trí p ban ñầu = 0 và vị trí i ñang xét = 1 p = 0, i=1 – Bước 4: So sánh ai với s • Nếu ai =s thì ghi nhận vị trí p = i Sang Bước 5 • Nếu ai ≠ s và i < N thì gán i=i+1 và lặp lại bước 4, ngược lại sang Bước 5 – Bước 5: Nếu p ≠ 0 thì ñưa ra vị trí cần tìm là p, ngược lại thông báo không tìm thấy giá trị s trong dãy số ñã cho. – Bước 6: Kết thúc. Tin học đại cương - Chương 3 25bangtqh@utc2.edu.vn Biểu diễn thuật toán bằng sơ đồ khối q Sử dụng các hình khối để minh hoạ cho các lệnh hay thao tác. q Sử dụng mũi tên để diễn đạt thứ tự thực hiện. q Đây là cách diễn đạt khoa học, có tính nhất quán cao. q Các hình khối cơ bản – Khối bắt đầu. – Khối kết thúc. – Khối thao tác cụ thể. – Khối kiểm tra điều kiện. – Khối vào/ra dữ liệu. – Khối gọi chương trình con. q Các ký pháp. Tin học đại cương - Chương 3 26bangtqh@utc2.edu.vn Các hình khối cơ bản q Khối bắt đầu và kết thúc q Thực hiện công việc A q Vào/ra dữ liệu q Gọi chương trình con A (ít dùng) q Kiểm tra điều kiện – Tuỳ thuộc điều kiện (Đúng hay Sai) mà rẽ nhánh thích hợpA Begin End A Điều kiện Đúng Sai Tin học đại cương - Chương 3 27bangtqh@utc2.edu.vn Một số cấu trúc cơ bản q Cấu trúc rẽ nhánh q Cấu trúc lặp §iÒu KiÖn Sai §óng Xö lý nÕu ®óng Xö lý nÕu sai If… then… If… then… else… while…do… repeat…until… Tin học đại cương - Chương 3 28bangtqh@utc2.edu.vn Tính chu vi và diện tích HCN q Phương pháp liệt kê – B1. Nhập hai cạnh a,b – B2. Tính chu vi • C = 2*(a+b) – B3. Tính diện tích • S = a*b – B4. In chu vi C – B5. In diện tích S – Kết thúc q Sơ đồ khối Begin End §äc c¹nh a,b C := 2*(a+b) In ra C,S S := a*b Tin học đại cương - Chương 3 29bangtqh@utc2.edu.vn Lưu đồ thuật giải tính tổng N số tự nhiên ñầu tiên q Cách 1 q Cách 2 Tin học đại cương - Chương 3 30bangtqh@utc2.edu.vn Tính chu vi, diện tích tam giác q Phương pháp liệt kê – B1. Nhập cạnh a,b,c – B2. Kiểm tra xem a,b,c có phải ba cạnh tam giác không • Nếu (a+b>c) và (b+c>a) và (a+c>b) thì sang bước 3 • Nếu không thì thông báo “không tạo thành tam giác” và kết thúc – B3. Tính chu vi C = (a+b+c) – B4. Tính nửa chu vi p = C/2 – B5. Tính diện tích tam giác theo công thức Hê-rông • S = – B6. In kết quả C,S q Lưu đồ thuật toán )(*)(*)(* cpbpapp −−− )(*)(*)(* cpbpapp −−− Tin học đại cương - Chương 3 31bangtqh@utc2.edu.vn Biểu diễn thuật toán bằng giả ngôn ngữ q Giả ngôn ngữ – Dựa trên ngôn ngữ lập trình bậc cao. – Gần với ngôn ngữ tự nhiên của con người. – Ví dụ: • Ngôn ngữ giả Pascal (tựa Pascal) có các ký pháp khá giống với ngôn ngữ lập trình Pascal, ñược rút gọn sao cho dễ diễn đạt. q Giả ngôn ngữ ñược đưa ra với mục đích diễn đạt các giải thuật sao cho gần với ngôn ngữ lập trình và ngôn ngữ tự nhiên. q Sử dụng giả ngôn ngữ khiến việc chuyển từ giải thuật sang chương trình dễ dàng hơn. Tin học đại cương - Chương 3 32bangtqh@utc2.edu.vn Giải thuật tính tổng N số tự nhiên ñầu tiên Nhập N i:=0 S:=0 REPEAT S:=S+i i:=i+1 UNTIL (i>N) In S Tin học đại cương - Chương 3 33bangtqh@utc2.edu.vn Thiết kế và phân tích thuật toán q Quá trình viết chương trình giải bài toán: – Phân tích yêu cầu bài toán – Thiết kế giải thuật – Viết chương trình – Chạy thử, đánh giá q Thiết kế giải thuật là từ yêu cầu của một bài toán, diễn đạt một giải thuật giải quyết bài toán đó. – Mô-đun hoá việc giải quyết bài toán. – Tinh chỉnh từng bước. q Phân tích giải thuật – Xem xét các tiêu chuẩn của giải thuật có ñược thoả mãn không, nếu có thì ñến mức độ nào. Tin học đại cương - Chương 3 34bangtqh@utc2.edu.vn Thiết kế từ trên xuống q Các bài toán lớn đòi hỏi giải thuật có quy mô lớn. q Mô-đun hoá – Bài toán = nhiều mô-đun – Mô-đun lớn = nhiều mô-đun con. – Việc giải quyết một mô-đun ở mức thấp nhất là “đủ ñơn giản” Chia để trị. q Thiết kế từ trên xuống (top- down design): Bài toán được xem xét từ tổng quát đến chi tiết. BÀI TOÁN A B C A1 A2 A2.1 A2.2 C1 C2 A2.3 Tin học đại cương - Chương 3 35bangtqh@utc2.edu.vn Bài toán giải phương trình bậc 2 GIẢI PHƯƠNG TRÌNH BẬC II NHẬP HỆ SỐ XỬ LÝ HIỂN THỊ KẾT QUẢ TRƯỜNG HỢP SUY BIẾN TRƯỜNG HỢP KHÔNG SUY BIẾN TÍNH DELTA TÍNH NGHIỆM THEO DELTA Tin học đại cương - Chương 3 36bangtqh@utc2.edu.vn Phương pháp tinh chỉnh từng bước q Phương pháp tinh chỉnh từng bước (stepwise refinement) – Ban đầu, sử dụng ngôn ngữ tự nhiên ñể diễn tả những công việc chính của giải thuật. – Các bước sau, các công việc được chi tiết hoá dần dần, ngôn ngữ tự nhiên ñược thay thế dần dần bằng giả ngôn ngữ. – Cuối cùng, giả ngôn ngữ ñược chuyển sang ngôn ngữ lập trình q Đặc điểm – Thể hiện rõ ý tưởng thiết kế từ trên xuống – Gắn liền việc thiết kế giải thuật với việc lập trình Tin học đại cương - Chương 3 37bangtqh@utc2.edu.vn Sắp xếp dãy theo thứ tự tăng dần q Phác thảo “thô” với những “ý tưởng cơ bản” – “Từ dãy các số chưa ñược sắp xếp, tìm số nhỏ nhất và ñưa lên ñầu” – Lặp lại quy trình trên tới khi dãy chưa được sắp xếp trở thành rỗng. q Ban đầu, dãy chưa sắp xếp là dãy ñã cho, dãy đã sắp xếp là rỗng. q Lưu trữ dãy bằng “mảng” (danh sách các số), ñưa số nhỏ nhất (aj) lên đầu danh sách là ñổi chỗ nó với số ñầu tiên. q Đổi chỗ – Số trung gian := aj – aj := số ñầu tiên – Số ñầu tiên : = số trung gian q …, cuối cùng ta được chương trình với ngôn ngữ cụ thể Tin học đại cương - Chương 3 38bangtqh@utc2.edu.vn Phân tích giải thuật q Tính đúng đắn – Chạy thử nghiệm, ñối chiếu kết quả phát hiện được tính sai. – Dùng công cụ toán học để chứng minh tính đúng đắn. q Tính đơn giản – Giải thuật có dễ hiểu, dễ lập trình không? q Tính hiệu quả – Đơn giản chưa chắc đã hiệu quả. – Đối với nhiều bài toán, tính hiệu quả là quan trọng, các giải thuật đơn giản lại gây tốn tài nguyên, chạy chậm. – Thời gian tính toán ðộ phức tạp tính toán – Những giải thuật hiệu quả phải có ñộ phức tạp (thời gian) tính toán chấp nhận được. q Tính dừng – Chứng minh, suy luận – Chạy thử Tin học đại cương - Chương 3 39bangtqh@utc2.edu.vn Đệ quy và giải thuật đệ quy q Một đối tượng là ñệ quy nếu nó bao gồm chính nó hoặc được định nghĩa bởi chính nó. q Ví dụ: – Trong chương trình thời sự trên vô tuyến, ñôi khi ta thấy lại hình ảnh của màn hình phía sau phát thanh viên. – Định nghĩa số tự nhiên: • 1 là số tự nhiên • N là số tự nhiên nếu N-1 là số tự nhiên – Định nghĩa giai thừa: • 0! = 1 • N! = N(N-1)! Tin học đại cương - Chương 3 40bangtqh@utc2.edu.vn Giải thuật đệ quy q Lời giải của bài toán T có ñược dựa trên lời giải một bài toán T’ nào đó thì lời giải đó là một lời giải đệ quy và giải thuật đó gọi là giải thuật đệ quy. q Bài toán T’ phải nhỏ hơn bài toán T. q Ví dụ “Bài toán tính N!” – Tn = tính N! • Tính Tn-1 = tính (N-1)! – Tính Tn-2 = (N-2)! » … – Tn-1 = Tn-2 x (N-1) • Tn = Tn-1 x N Tính 3! Tính 2! 3! = 3 x 2! Tính 1! 2! = 2 x 1! Tính 0! = 1 1! = 1 x 0! Tin học đại cương - Chương 3 41bangtqh@utc2.edu.vn Bài toán “Tháp Hà Nội” q Có 3 cọc A,B,C q Có N ñĩa tại cọc A – Kích thước các đĩa khác nhau. – Đĩa to đặt dưới đĩa bé. q Cọc B,C không có ñĩa nào. q Yêu cầu – Chuyển N đĩa từ cọc A sang cọc C. – Mỗi lần chỉ ñược chuyển một đĩa từ cọc này sang cọc khác. – Không được xếp đĩa to lên trên đĩa bé. 2 1 N A C B Tin học đại cương - Chương 3 42bangtqh@utc2.edu.vn Bài toán “Tháp Hà Nội” – Lời giải đệ quy q Đánh số các đĩa theo thứ tự từ dưới lên q Nếu N = 1 – Chuyển đĩa duy nhất (đĩa 1) từ cột A sang cột C q Nếu N = 2 – Chuyển đĩa 2 từ cột A sang cột B – Chuyển đĩa 1 từ cột A sang cột C – Chuyển đĩa 2 từ cột B sang cột C q N bất kỳ – Chuyển N-1 đĩa trên cùng từ cọc A sang cọc B – Chuyển đĩa 1 từ cọc A sang cọc C – Chuyển N-1 đĩa từ cọc B sang cọc C Tin học đại cương - Chương 3 43bangtqh@utc2.edu.vn Một số bài toán tìm kiếm, sắp xếp q Tìm giá trị lớn nhất, nhỏ nhất của dãy số? – Cho một dãy số. – Hãy cho biết giá trị lớn nhất và nhỏ nhất của dãy số? q Tìm vị trí xuất hiện của một số trong một dãy số? – Cho một dãy số và một dãy số. – Chỉ ra các vị trí xuất hiện của số ñã cho trong dãy? q Sắp xếp dãy số – Cho một dãy số. – Sắp xếp dãy theo thứ tự tăng (giảm) dần? Tin học đại cương - Chương 3 44bangtqh@utc2.edu.vn Tìm giá trị lớn nhất, nhỏ nhất q Ý tưởng – Gán cho giá trị lớn nhất (nhỏ nhất) giả ñịnh giá trị của phần tử ñầu tiên trong dãy. – Duyệt dãy và tìm phần tử lớn hơn (nhỏ hơn) giá trị lớn nhất giả ñịnh và ghi nhận phần tử lớn hơn (nhỏ hơn) làm giá trị lớn nhất (nhỏ nhất) giả ñịnh mới. – Duyệt xong dãy, giá trị lớn nhất (nhỏ nhất) giả ñịnh chính là giá trị cần tìm. Tin học đại cương - Chương 3 45bangtqh@utc2.edu.vn Lưu đồ thuật giải (tìm giá trị lớn nhất) Max := A[1] i := 2 BEGIN Nhập N, A i := i+1 END In ra Max i > N Max<A[i] Max := A[i] Đ S Đ S A là dãy số có N phần tử Lần lượt so sánh và tìm phần tử giả ñịnh mới Giả ñịnh giá trị lớn nhất là phần tử ñầu tiên Kết thúc dãy, phần tử giả định là giá trị lớn nhất Tin học đại cương - Chương 3 46bangtqh@utc2.edu.vn Tìm vị trí xuất hiện của số trong dãy q Ý tưởng – Lần lượt so sánh số ñã cho với các phần tử trong dãy. – Nếu kết quả so sánh là bằng nhau thì ghi nhận vị trí. – Kết thúc dãy được danh sách các vị trí cần tìm. Tin học đại cương - Chương 3 47bangtqh@utc2.edu.vn Lưu đồ thuật toán i := 1 Found := False BEGIN Nhập N, A, X i := i+1 END In ra i (i < N) and (not found) X = A[i] Found := True Đ S Đ S Found Đ In “Không thấy” S A - Dãy số có N phần tử X - Phần tử cần tìm Vòng lặp tìm kiếm Tin học đại cương - Chương 3 48bangtqh@utc2.edu.vn Sắp xếp dãy số q Ý tưởng – Tìm phần tử nhỏ nhất (lớn nhất) trong dãy. – Đổi chỗ phần tử ñó với phần tử ñầu tiên trong dãy (vị trí a), dãy đầu tiên sẽ ñược chia làm 2 phần. • Phần đầu: tính từ vị trí a về ñầu dãy, ñã được sắp xếp • Phần sau: Còn lại, chưa sắp xếp. – Thực hiện lại hai bước trên với phần sau của dãy số – Đến khi phần chưa sắp xếp của dãy số là rỗng thì dừng.. Tin học đại cương - Chương 3 49bangtqh@utc2.edu.vn Lưu đồ giải thuật (sắp xếp tăng dần) BEGIN Nhập n, a i := 1 j := i+1i ≤ n-1 j ≤ n a[i] > a[j] tmp:=a[i] a[i]:=a[j] a[j]:=tmp In a END j := j+1 Đ S Đ S a là dãy số có n phần tử Đổi chỗ a[i] và a[j] Vòng lặp sắp xếp Đ S Bắt đầu từ phần tử ñầu tiên của dãy i := i+1 Chuyển sang sắp xếp dãy tiếp theo Đến khi không còn dãy nào chưa sắp xếp Tin học đại cương - Chương 3 50bangtqh@utc2.edu.vn Bài tập: Nêu ý tưởng + Lưu đồ giải thuật q Tìm tất cả vị trí xuất hiện của phần tử X trong dãy A – Input: Dãy số A, phần tử X – Output: Các vị trí xuất hiện của X trong A q Đếm số phần tử âm/không âm của dãy số A – Input: Dãy số A – Output: Số lượng phần tử âm, số lượng phần tử không âm trong A q Tính n! bằng giải thuật lặp – Input: n – Output: n! Tin học đại cương - Chương 3 51bangtqh@utc2.edu.vn Bài tập – Biểu diễn thuật toán bằng sơ đồ khối q Vẽ sơ ñồ biểu diễn thuật toán tìm trung bình cộng của dãy số a1, a2, …, an q Vẽ sơ ñồ biểu diễn thuật toán tìm TBC các số chẵn và chia hết cho 5 trong dãy số a1, a2, …, an q Vẽ sơ ñồ biểu diễn thuật toán đếm xem trong dãy số a1, a2, …, an có bao nhiêu cặp có chỉ số liên tiếp (vd: a2, a3) thỏa điều kiện tích chúng chia hết tổng của chúng. q Vẽ sơ ñồ khối biểu diễn thuật toán kiểm tra xem 1 số nguyên N có là số nguyên tố hay không?