Bài giảng Tin học cơ sở: Bài 7 - Đào Kiến Quốc
lượt xem 12
download
Bài giảng Tin học cơ sở: Bài 7 - Thuật toán có nội dung trình bày về bài toán và thuật toán, các phương pháp biểu diễn thuật toán, các đặc trưng của thuật toán và một số nội dung liên quan khác.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Tin học cơ sở: Bài 7 - Đào Kiến Quốc
- ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ BÀI GIẢNG TIN HỌC CƠ SỞ BÀI 7 . THUẬT TOÁN Giảng viên: ĐÀO KIẾN QUỐC Mobile 098.91.93.980 Email: dkquoc@vnu.edu.vn
- NỘI DUNG Bàitoán và thuật toán Các phương pháp biểu diễn thuật toán Các đặc trưng của thuật toán
- Input Yêu cầu Output KHÁI NIỆM BÀI TOÁN Cho số tự n có phải số “có” hay nhiên n nguyên tố hay “không” không Cho hồ sơ Tìm tất cả các sinh Danh sách sv điểm sinh viên viên có điểm trung thoả mãn bình trên 8 Thiết kế hình Tính sức bền Độ bền học, tải trọng Cho một bài toán nghĩa là cho input, và yêu cầu để tìm (tính) ra output
- KHÁI NIỆM THUẬT TOÁN Thuật toán (algorithm) là một quá trình gồm một dãy hữu hạn các thao tác có thể thực hiện được sắp xếp theo một trình tự xác định dùng để giải một bài toán Ví dụ : thuật toán Euclid tìm ước số chung lớn nhất của hai số tự nhiên. – USCLN(a,b) = USCLN (b,a)) – Nếu a> b, USCLN(a,b) = USCLN (a-b,b) – USCLN(a,a)= a
- THUẬT TOÁN EUCLID TIM USCLN CỦA HAI SỐ TỰ NHIÊN Bài toán: Cho hai số m, n tìm d = USCLN(m,n) 1. Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước 2 2. Bước 2: Nếu m> n thì về bước 4 nếu không thực hiện tiếp bước 3 3. Bước 3: m
- VÍ DỤ CÁC BƯỚC CỦA THUẬT TOÁN EUCLID Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước 2 m n Bước 2: Nếu m> n thì về bước 4, mn và n. Kết thúc 3 6 m
- CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN Input Output Tính xác định Tính khả thi Tính dừng Tính phổ dụng
- PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN Dùng các chỉ dẫn Dùng sơ đồ khối Dùng cấu trúc điều khiển
- BIỂU DIỄN BẰNG LƯU ĐỒ/SƠ ĐỒ KHỐI Khối thao tác Khối output Khối input đối tượng:= biểu Khối input thức Khởi đầu Kết thúc Khối điều kiện + - Thứ tự xử lý
- BIỂU DIỄN BẰNG LƯU ĐỒ thuật toán EUCLID Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước 2 Bước 2: Nếu m> n thì về bước 4, nếu không thực hiện tiếp bước 3 Bước 3: m n ? d:= m + - m:=m-n n:= n - m d
- BIỂU DIỄN BẰNG CẤU TRÚC ĐIỀU KHIỂN Trong khi m ≠ n thì lặp lại khối read(m,n); sau: Nếu m > n thì while m n do Bớt m đi một lượng là n if m>n then Điều chỉnh lại giá trị Nếu ngược lại thì m:=m-n của m và n Bớt n đi một lượng là m else n:= n-m; Cho tới khi m = n thì tuyên bố write(m); USCLN chính là giá trị chung của m và n Chương trình trong PASCAL
- HIỆU QUẢ CỦA THUẬT TOÁN Mỗibài toán có thể có nhiều thuật toán khác nhau: hiệu quả khác nhau – Độ phức tạp về thời gian: quy về số phép tính cơ bản cần được thực hiện – Độ phức tạp không gian: sự tiêu tốn không gian nhớ.
- VÍ DỤ HIỆU QUẢ TÌM KIẾM Bài toán tìm kiếm: Cho một dãy n số khác nhau a1,a2...ai... an và một số x. Hãy cho biết x có trong dãy số đó hay không và ở vị trí thứ bao nhiêu. Thuật toán tìm kiếm tuần tự như sau: Bước 1. Cho i = 1 Bước 2. Nếu ai = x thì chuyển tới bước 5, nếu không thực hiện tiếp bước 3 Bước 3. Tăng i lên 1 và kiểm tra i > n. Nếu đúng về bước 4. Nếu sai quay về bước 2 Bước 4. Tuyên bố không có số x. Kết thúc Bước 5. Tuyên bố số x chính là số thứ i. Kết thúc Số bước tìm trung bình là n/2. Nếu có 1 triệu phần tử thì phải mất khoảng 500.000 phép so sánh
- HIỆU QUẢ CỦA THUẬT TOÁN Thuật toán 2: Tìm kiếm nhị phân (thu hẹp dần vùng tìm kiếm, đối với danh sách đã được sắp xếp) Bước 1. Cho d := 1, c:=n (d: đầu, c: cuối, g: giữa) Bước 2. Tính g := [(d+c)/2] Bước 3. So x với ag. Nếu x=ag chuyển tới bước 7. Nếu khác thì tiếp tục thực hiện bước 4 Bước 4. Nếu d=c thì tuyên bố không có số x và kết thúc. Nếu không thì thực hiện bước 5 tiếp theo Bước 5. Nếu x < ag thì thay c bằng ag và quay về bước 2. Nếu không thì thực hiện bước 6 tiếp theo Bước 6. Thay d bằng ag và quay về bước 2 Bước 7. Tuyên bố số x chính là số thứ g. Kết thúc Số bước tìm trung bình là log2n. Nếu có 1 triệu phần tử thì chỉ mất khoảng 20 lần tìm, rất nhỏ so với tìm tuần tự
- CÂU HỎI VÀ BÀI TẬP 1. Thuật toán là gì? Cho ví dụ. 2. Xác định input và output cho các thuật toán sau đây: a. Rút gọn một phân số. b. Kiểm tra xem ba số cho trước a, b và c có thể là độ dài ba cạnh của một tam giác hay không? 3. Trình bày tính chất xác định của thuật toán và nêu rõ nghĩa của tính chất này 4. Cho tam giác ABC có góc vuông A và cho biết cạnh a và góc B. Hãy viết thuật toán để tính góc C, cạnh b và cạnh c. 5. Hãy phát biểu thuật toán để giải bài toán sau: "Có một số quả táo. Dùng cân hai đĩa (không có quả cân) để xác định quả táo nặng nhất" 6. Chỉ dùng phép cộng, tính bình phương của một số
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Tin học cơ sở 1 - Phan Thị Hà (chủ biên)
193 p | 194 | 22
-
Bài giảng Tin học cơ sở: Bài 16 - Đào Kiến Quốc
16 p | 142 | 13
-
Bài giảng Tin học cơ sở: Bài 3 - Đào Kiến Quốc
16 p | 141 | 13
-
Bài giảng Tin học cơ sở 1: Phần 2
87 p | 52 | 8
-
Bài giảng Tin học cơ sở: Bài 1 - Thông tin và xử lý thông tin
19 p | 143 | 8
-
Bài giảng Tin học cơ sở 1: Phần 1
110 p | 39 | 7
-
Bài giảng Tin học cơ sở 3 bài 1: Tổng quan về cơ sở dữ liệu quan hệ
11 p | 25 | 5
-
Bài giảng Tin học cơ sở: Chương 4 - Các thành phần nhập liệu
39 p | 69 | 5
-
Bài giảng Tin học cơ sở 1 - Chương 0: Giới thiệu môn học
8 p | 151 | 5
-
Bài giảng Tin học cơ sở (Basics of Informatics) - Chương 1: Thông tin và biểu diễn thông tin
18 p | 40 | 5
-
Bài giảng Tin học cơ sở (Basics of Informatics) - Chương 5: Các vấn đề xã hội của công nghệ thông tin
13 p | 37 | 4
-
Bài giảng Tin học cơ sở 3 bài 3: Table and relation
43 p | 12 | 4
-
Bài giảng Tin học cơ sở 2: Chương 0 - ThS. Nguyễn Mạnh Sơn
7 p | 119 | 4
-
Bài giảng Tin học cơ sở: Chương 6 - An toàn thông tin, các hướng phát triển mới trong công nghệ thông tin
15 p | 93 | 4
-
Bài giảng Tin học cơ sở: Chương 4 - Hệ thống thông tin và ngôn ngữ lập trình
18 p | 65 | 4
-
Bài giảng Tin học cơ sở 2: Chương 2 - ThS. Nguyễn Mạnh Sơn
38 p | 72 | 3
-
Bài giảng Tin học cơ sở 2: Chương 0 - Nguyễn Ngọc Duy
4 p | 83 | 2
-
Bài giảng Tin học cơ sở - Chương 1: Giới thiệu chung
13 p | 57 | 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