Bài giảng Kỹ thuật lập trình: Thuật toán - GV. Hà Đại Dương

Bài giảng trình bày về khái niệm, cách biểu diễn 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) và thuật toán tìm kiếm (tìm kiếm tuần tự và tìm kiếm nhị phân). Để biết rõ hơn về nội dung chi tiết của bài giảng, mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình: Thuật toán - GV. Hà Đại Dương10/25/2016Kỹ thuật lập trìnhTuần 10 - Thuật toánGiáo viên: Hà Đại Dươngduonghd@mta.edu.vn10/25/20161Nội dung1. 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ọt3. Thuật toán tìm kiếm– Tuần tự– Nhị phân4. Bài tập10/25/20162Thuật toán10/25/20163110/25/2016Khái niệm• 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 đã chotrong một khoảng thời gian hữu hạn.• Tai sao cần thuật toán?? Chuyển thànhchươ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ìmphần tử lớn nhất trong dãy có n số cho trước.10/25/20164Mô tả thuật toán tìm số lớn nhất1. 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ớnhơ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ầntử lớn nhất trong dãy (cần tìm).10/25/20165Dạng giả mã10/25/20166210/25/2016Tính chất của TT …1. Tính chính xác: để đảm bảo kết quả tínhtoán hay các thao tác mà máy tính thựchiệ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áccâu lệnh được sắp xếp theo thứ tự nhấtđịnh.10/25/20167Tí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áytính vẫn phải cho kết quả như nhau.4. Tính phổ dụng: Thuật toán không chỉ ápdụ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ộtsố hữu hạn các bước tính toán.10/25/20168Biể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/20169310/25/2016Mô 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ệuxác định. Ví dụ, dãy số nguyên a(1), a(2), ...,a(n), với n a kENDYESk=i10/25/201613Giả mã• Sử dụng ngôn ngữ tự nhiên kết hợp với mộtngô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àitoán).• Dễ hiểu, dễ cài đặt.10/25/201614Ví dụ10/25/2016155