Bài giảng Toán rời rạc: Thuật toán - ThS. Hoàng Thị Thanh Hà
lượt xem 3
download
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!
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: 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ẵng 21 August 2018 1
- Nội dung 1. Khái niệm 2. Các đặc trưng của thuật toán 3. Các cách biểu diễn thuật toán 4. Thuật toán tìm kiếm 5. Thuật toán xử lý số 6. Thuật toán sắp xếp 21 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 định 21 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 s 21 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 p 21 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 con 21 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 cua mang "); scanf ("%d",&n); for (i= 1; i
- Thuật toán tìm kiếm Tìm kiếm nhị phân (mảng a đã được sắp xếp tăng dần) – Thuật toán này chỉ áp dụng trong trường hợp bảng được sắp xếp theo thứ tự tăng dần. – Phần tử x được so sánh với số hạng ở giữa bảng. – Sau đó bảng được tách thành 2 bảng con. – Quá trình tìm kiếm được tiếp tục trên một trong 2 bảng con dựa trên kết quả so sánh x với phần tử ở giữa bảng ban đầu. 21 August 2018 15
- Thuật toán tìm kiếm Tìm kiếm nhị phân: mã giả (NN C) Int BinarySearch(int x, int a1, a2, …, an) { int i = 1, j = n, m; while (i < j) { m = (i + j)/2; (nếu m lẻ thì phải làm tròn) if (x>am) i=m+1; else j=m; } if (x==ai) return(i); else return(0) } 21 August 2018 16
- Một số thuật toán xử lý số Tìm ước chung lớn nhất của 2 số nguyên dương Kiểm tra số nguyên tố Kiểm tra số chính phương 21 August 2018 17
- Một số thuật toán xử lý số Thuật toán tìm ước số chung lớn nhất Int UCLN(int a, int b) { While (a!=0 && b!=0) if (a>b) a = a – b; else b = b – a; if (a==0) return(b); else return(a); } 21 August 2018 18
- Một số thuật toán xử lý số Kiểm tra số nguyên tố int ktnt(int n) { int i, kt=1; for(i=2; i
- Một số thuật toán xử lý số Kiểm tra số chính phương int ktcp(int n) { int i = 1, kt = 0; while (n>i*i) i = i + 1; if (i*i == n) kt = 1; return(kt); } 21 August 2018 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Toán rời rạc: Chương 5 - Nguyễn Đức Nghĩa
78 p | 324 | 60
-
Bài giảng Toán rời rạc: Bài 10 - TS. Nguyễn Văn Hiệu
32 p | 151 | 26
-
Bài giảng Toán rời rạc: Bài 9 - TS. Nguyễn Văn Hiệu
21 p | 118 | 24
-
Bài giảng Toán rời rạc 2 - Bài toán tìm đường đi ngắn nhất
28 p | 356 | 16
-
Bài giảng Toán rời rạc: Bài 11 - TS. Nguyễn Văn Hiệu
39 p | 102 | 8
-
Bài giảng Toán rời rạc 2 - Tìm kiếm trên đồ thị
52 p | 114 | 8
-
Bài giảng Toán rời rạc 2 - Đồ thị Euler, đồ thị Hamilton
32 p | 106 | 7
-
Bài giảng Toán rời rạc: Chương 6 - Nguyễn Đức Nghĩa
83 p | 135 | 7
-
Bài giảng Toán rời rạc: Chương 1 - Nguyễn Lê Minh (2020)
47 p | 96 | 6
-
Bài giảng Toán rời rạc 1: Phần 2
75 p | 30 | 5
-
Bài giảng Toán rời rạc 2: Phần 2
59 p | 38 | 5
-
Bài giảng Toán rời rạc: Chương 5 - Nguyễn Quỳnh Diệp
84 p | 38 | 4
-
Bài giảng Toán rời rạc: Bài 2 - Vũ Thương Huyền
42 p | 38 | 3
-
Bài giảng Toán rời rạc: Chương 2 - Nguyễn Quỳnh Diệp
44 p | 39 | 3
-
Bài giảng Toán rời rạc: Chương 6 - TS. Đặng Xuân Thọ
20 p | 36 | 2
-
Bài giảng Toán rời rạc: Thuật toán tham lam - Trần Vĩnh Đức
64 p | 24 | 2
-
Bài giảng Toán rời rạc - Phần 8: Cây (TS. Nguyễn Viết Đông)
113 p | 21 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn