Bài giảng Toán rời rạc: Thuật toán - ThS. Hoàng Thị Thanh Hà

Bài giảng Toán rời rạc - Thuật toán được biên soạn gồm các nội dung chính sau: Khái niệm; Các đặc trưng của thuật toán; Các cách biểu diễn thuật toán; Thuật toán tìm kiếm; Thuật toán xử lý số; Thuật toán sắp xếp. 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 Toán rời rạc: Thuật toán - ThS. Hoàng Thị Thanh Hà Toán rời rạc (1): THUẬT TOÁN Ts. Hoàng Thị Thanh Hà Ha.htt@due.edu.vn 0905 238 835 Khoa Thống kê –Tin học Trường Đại học Kinh tế Đại học Đà Nẵng21 August 2018 1 Nội dung1. Khái niệm2. Các đặc trưng của thuật toán3. Các cách biểu diễn thuật toán4. Thuật toán tìm kiếm5. Thuật toán xử lý số6. Thuật toán sắp xếp21 August 2018 2 Khái niệm thuật toán Ví dụ : bài toán hoán đổi 2 số nguyên a,b – Cách 1: tam=a; a=b; b= tam; – Cách 2: a= a+b; b= a-b; a=a-b;21 August 2018 3 Khái niệm thuật toán Định nghĩa: – Thuật toán là một bảng liệt kê các chỉ dẫn (hay quy tắc) cần thực hiện theo từng bước xác định nhằm giải một bài toán đã cho.21 August 2018 4 Các đặc trưng của thuật toán Đầu vào: Thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ Đầu ra: Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trị đầu ra Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng. Tính xác định: Các bước thao tác phải hết sức rõ ràng, không nhập nhằng Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ liệu khác nhau trong một miền xác định21 August 2018 5 Các cách biểu diễn thuật toán Dùng ngôn ngữ tự nhiên (biểu diễn bằng lời) hay còn gọi là giả lệnh Dùng sơ đồ khối Dùng mã giả (pseudocode)21 August 2018 6 Các cách biểu diễn thuật toán Dùng ngôn ngữ tự nhiên – Ví dụ 2 : xây dựng thuật toán tính tổng s=1+2+…n Bước 1: Nhập giá trị n Bước 2: Cho s = 0, i = 0 (i là biến đếm) Bước 3: Trong khi i còn nhỏ hơn n thì thực hiện – Bước 3.1: tăng i lên một đơn vị (i = i + 1) – Bước 3.2: cộng i vào s (s = s + i) – Bước 3.3: lặp lại bước 3 Bước 4: Xuất ra giá trị của s21 August 2018 7 Các cách biểu diễn thuật toán Dùng ngôn ngữ tự nhiên – Ví dụ 3: xây dựng thuật toán tính giai thừa p = n! = 1.2.3…n Bước 1: Nhập giá trị n Bước 2: Cho p = 1, i = 1 (i là biến đếm) Bước 3: Trong khi i còn nhỏ hơn n thì thực hiện – Bước 3.1: tăng i lên một đơn vị (i = i + 1) – Bước 3.2: nhân i vào p (p = p * i) – Bước 3.2: lặp lại bước 3 Bước 4: Xuất ra giá trị của p21 August 2018 8 Các cách biểu diễn thuật toán Sơ đồ khối gồm các kí hiệu sau: begin end Bắt đầu Kết thúc Nhập/xuất dữ liệu điều kiện đúng sai Thực hiện công việc Kiểm tra rẽ nhánh Gọi chương trình con21 August 2018 9 Các cách biểu diễn thuật toán Ví dụ: vẽ sơ đồ khối tính n!, p = 1.2.3. …. n Begin Nhap n i=1 p=1 S i Các cách biểu diễn thuật toán Ví dụ: dùng mã giả để biểu diễn thuật toán tính n! Main{ – Scanf (“%d”,n); – P=1; – For (i= 1;i Thuật toán tìm kiếm Tìm kiếm phần tử x trong mảng a gồm n phần tử – Tìm kiếm tuần tự – Tìm kiếm nhị phân (mảng a đã được sắp xếp)21 August 2018 12 Thuật toán tìm kiếm Tìm kiếm phần tử x trong mảng a gồm n phần tử: – Tìm kiếm tuần tự : duyệt từ đầu đến cuối danh sách, khi gặp x thì dừng, hoặc dừng khi đã duyệt đến cuối danh sách.21 August 2018 13 Thuật toán tìm kiếm Tìm kiếm tuần tự : duyệt từ đầu đến cuối danh sách, khi gặp x thì dừng, hoặc dừng khi đã duyệt đến cuối danh sách Dùng mã giả:int main(){ int n,i,x, vitri=0, found=0; int a[100]; printf(nhap so phan tu cu ...