intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Cấu trúc dữ liệu - Phần 1

Chia sẻ: Nguyen Nguyen | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
172
lượt xem 35
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo bài giảng môn Cấu trúc dữ liệu - Phần 1 Tổng quan giải thuật

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu - Phần 1

  1. Tổng quan giải thuật GVGD: Trương Phước Hải LOGO
  2. Nội dung 1. Bài toán và giải thuật 2. Biểu diễn giải thuật 3. Giải toán trên máy tính 4. Thiết kế giải thuật 2
  3. Bài toán và giải thuật  Khái niệm bài toán Là một công việc mà ta muốn máy tính thực hiện thay cho  ta hoặc hỗ trợ một phần 3
  4. Bài toán và giải thuật  Mô tả bài toán Bài toán được mô tả thông qua các thành phần input và  output Input: dữ liệu đầu vào (nguyên liệu) tối thiểu để giải được  bài toán Output: dữ liệu đầu ra (thành phẩm) theo yêu cầu của bài  toán Input và output cần phải được xác định đúng đắn  4
  5. Bài toán và giải thuật  Ví dụ bài toán Cho 2 số nguyên dương a, b. Hãy tìm UCLN của a và b  Input: a, b  Output: c = UCLN(a, b)  Cho 2 số nguyên a, b. Hãy tìm phân số tối giản của phân  số a/b. Input: a, b  Output: tu, mau  5
  6. Bài toán và giải thuật  Ví dụ không phải bài toán Cho danh sách điểm thi học kỳ môn giải thuật của sinh viên  khoa CNTT. Cho biết sinh viên có điểm thi cao nhất Hãy sắp thứ tự danh sách sinh viên khoa CNTT theo điểm  thi môn giải thuật 6
  7. Bài toán và giải thuật  Khái niệm giải thuật (thuật toán) Là dãy hữu hạn các thao tác được sắp xếp theo một trình  tự xác định để tạo ra output từ input của bài toán. Phân biệt giải thuật và thuật giải:  Giải thuật: luôn cho kết quả đúng với mọi trường hợp  của input. Thuật giải: cho kết quả của bài toán là gần đúng, nhưng  không luôn luôn đúng. 7
  8. Bài toán và giải thuật  Ví dụ: giải phương trình bậc 1: ax + b = 0 Bước 1: Nhập a, b  Bước 2: Kiểm tra a  0   Nếu đúng thì sang bước 3.  Ngược lại sang bước 4. Bước 3:   Thông báo phương trình có nghiệm –b/a.  Đến bước 5. Bước 4: Kiểm tra b  0   Nếu đúng thì phương trình vô nghiệm.  Ngược lại phương trình có vô số nghiệm. Bước 5: kết thúc  8
  9. Bài toán và giải thuật  Các tính chất của giải thuật Tính dừng: giải thuật phải đi đến kết thúc sau một số bước  hữu hạn các thao tác thi hành Tính xác định: các thao tác thi hành phải rõ ràng và chỉ có  một cách hiểu Tính đúng đắn: giải thuật phải cho output chính xác trong  mọi trường hợp của input Tính hiệu quả: giải thuật phải có tốc độ thi hành nhanh, sử  dụng ít bộ nhớ 9
  10. Bài toán và giải thuật  Ví dụ uống thuốc Bước 1: cho 1 muỗng café thuốc vào ly  Bước 2: pha 20ml nước và uống sau khi ăn  Bước 3: uống đến khi nào hết bệnh thì dừng  10
  11. Bài toán và giải thuật  Ví dụ nấu cơm Bước 1: đong 2 lon gạo  Bước 2: vo sạch và cho vào nồi  Bước 3: đổ nước ngập 1 đốt ngón tay  Bước 4: cắm điện nấu đến khi đèn tắt là chín  11
  12. Bài toán và giải thuật  Ví dụ nấu cơm Bước 1: đong 2 lon gạo  Bước 2: vo sạch và cho vào nồi  Bước 3: đổ nước ngập 1 đốt ngón tay  Bước 4: cắm điện nấu đến khi đèn tắt là chín  12
  13. Nội dung 1. Bài toán và giải thuật 2. Biểu diễn giải thuật 3. Giải toán trên máy tính 4. Thiết kế giải thuật 13
  14. Biểu diễn giải thuật  Liệt kê các bước thi hành  Vẽ sơ đồ khối thi hành  Mã giả điều khiển 14
  15. Biểu diễn giải thuật  Liệt kê các bước thi hành: Chỉ ra thao tác thực hiện trong từng bước một  Ưu điểm: biểu diễn được các bài toán có số bước thực thi  nhiều Nhược điểm: khó thấy được tổng thể trực quan về luồng thi  hành ở các bước của bài toán 15
  16. Biểu diễn giải thuật  Giải pt bậc 2: ax2 + bx + c = 0 (a  0) Bước 1: Nhận giá trị của a, b, c  Bước 2: tính d = b2 – 4.a.c  Bước 3: kiểm tra d ≥ 0   Nếu đúng: đến bước 4  Ngược lại: đến bước 5 Bước 4:   Kết luận nghiệm là x1 = (-b - d)/(2.a) và x2 = (-b + d)/(2.a)  Đến bước 6. Bước 5:   Kết luận phương trình vô nghiệm. Đến bước 6. Bước 6: kết thúc  16
  17. Biểu diễn giải thuật  Vẽ sơ đồ khối thi hành Sử dụng các khối kí hiệu để mô tả cho từng thao tác làm  việc Ưu điểm: trực quan, kiểm tra được luồng đường đi của  thuật toán Nhược điểm: nếu bài toán có quá nhiều thao tác sẽ gây rối  do có quá nhiều kí hiểu biểu diễn. Do đó chỉ biểu diễn các bài toán ở dạnh nhỏ 17
  18. Biểu diễn giải thuật  Các khối biểu diễn thao tác thi hành Hướng thi Kết thúc giải thuật Bắt đầu giải thuật hành F T xử lý kiểm tra tính toán nhập/xuất 18
  19. Biểu diễn giải thuật  Giải phương trình bậc 1: ax + b = 0 Bắt đầu nhập a, b F T a0 F T Phương trình b0 có nghiệm –b/a Phương trình Phương trình vô số nghiệm vô nghiệm Kết thúc 19
  20. Biểu diễn giải thuật  Mã giả điều khiển: Sử dụng mã giả tựa ngôn ngữ lập trình để biểu diễn thuật  toán. vd: kiểm tra số nguyên n có phải là số nguyên tố?  dem = 0 for i = 1 to n do if (n % 2 = 0) then dem = dem + 1 if dem = 2 then printf(“là số nguyên tố”) else printf(“không phải là số nguyên tố”) 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0