Chương 1: Tổng quan về CTDL - Cô Võ Thị Hường

Môn học Cấu trúc dữ liệu và giải thuật GV: Võ Thị Hường LOGO Chương 1:Tổng quan về Cấu trúc dữ liệu và giải thuật Chương 2:Đệ qui và giải thuật đệ qui Chương 3:Danh sách Chương 4:Các phương pháp sắp xếp cơ bản Chương 5:Tìm kiếm Chương 6:Cây Chương 7:Đồ thị www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về 1. Giải thuật CTDLvà GT 1.1 Khái niệm Giải thuật là:  Một dãy các thao tác  Được mô tả chính xác theo trình tự nhất định  Giải quyết bài toán sau một số hữu hạn các bước CHƢƠNG 1:Tổng quan về CTDLvà GT 1.2. Các đặc trƣng của giải thuật  Dữ liệu vào: Mỗi thuật toán đều có một số giá trị nhập vào, chúng được gọi là Input data.  Dữ liệu ra: Mỗi thuật toán có một số giá trị đưa ra, chúng được gọi là Output data.  Tính xác định: Mọi bước của một thuật toán bao giờ cũng được xác định rõ ràng, chính xác và do đó luôn thực hiện được. www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT 1.2. Các đặc trƣng của giải thuật  Tính dừng: Sau một số hữu hạn các bước bài toán luôn được giải quyết  Tính phổ dụng: Thuật toán có thể làm việc với các kiểu dữ liệu khác nhau trong miền xác định và luôn dẫn đến kết quả mong muốn.  Tính hiệu quả: Được thể hiện ở sự đúng đắn của thuật toán và độ phức tạp của thuật toán. Tính hiệu quả được thể hiện bởi khả năng thực thi các bước của thuật toán để đạt đƣợc kết quả mong muốn và tổng thời gian thực hiện thuật toán phải www.themegallery.com đủ nhỏ. Company Logo CHƢƠNG 1: GIỚI THIỆU CTDL > 1.3. Các phƣơng pháp diễn đạt giải thuật 1.3.1 Sử dụng ngôn ngữ tự nhiên: Sử dụng ngôn ngữ thường ngày để biểu diễn các bước của thuật toán. Phương pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT 1.3.2 Sử dụng sơ đồ khối (flowchart): Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý. www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT 1.3.2 Sử dụng sơ đồ khối Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác: - Thao tác chọn lựa (decision): dựa theo một điều kiện nào đó. Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện. - Thao tác xử lý (process): Các thao tác còn lại không thuộc loại chọn lựa được xếp vào loại hành động. Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý www.themegallery.com Company Logo Tìm Max của 3 số nguyên a,b,c. -Bước 1.Nhập (a,b,c). -Bước 2. Gán Max=a. -Bước 3.Nếu Max>b đúng thì đưa ra Max=a,ngược lại thì đưa ra Max=b -Bước 4.So sánh Max vừa tìm được với c,nếu Max>c đúng thì đến bước 5, còn sai thì đưa ra Max=c. -Bước 5.In ra Max và kết thúc. www.themegallery.com Company Logo www.themegallery.com Company Logo www.themegallery.com Company Logo www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT 1.3.3 Sử dụng mã giả(pseudocode): Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Dùng mã giả vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà 1.3.3 Sử dụng mã giả GT Trong mã giả vẫn dùng một phần ngôn ngữ tự nhiên. Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó. 1.3.4 Sử dụng ngôn ngữ lập trình(code):Pascal, C, C++, C#,... www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT 1.4 Thuật toán Euclid Là giải thuật tính ước chung lớn nhất của 2 số một cách hiệu quả Giả sử a = bq + r, với a, b, q, r là các số nguyên, ta có www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT 1.4.1 Sử dụng ngôn ngữ tự nhiên - Bước 1: Lấy a chia dư cho b được số dư là r - Bước 2: Kiểm tra r Nếu r = 0 : USCLN là b, kết thúc. Nếu r 0 : Gán a = b, b = r, quay lại bước 1 www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT 1.4.2 Sử dụng sơ đồ khối Begin r=a mod b r=0 false a = b, b = r true usc= b End www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT Chương trình dùng vòng lặp 1.4.3 Sử dụng mã giả procedure USCLN(a, b : Chương trình đệ quy positive integers) procedure USCLN(a, b : Begin positive integers) Begin x := a if a mod b = 0 then USCLN := b y := b else USCLN(b; a mod b); while y ≠ 0 End begin r := x mod y x := y y := r end{x la USCLN cần tìm } end www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT Sử dụng ngôn ngữ lập trình // Chương trình đệ quy int USCLN (int m,int n) { if (m%n = 0) return n; else USCLN(n,m%n); } www.themegallery.com // Chương trình dùng vòng lặp int USCLN (int m, int n) { int r ; r = m % n; while (r!= 0) { m = n; n =r; r = m % n; } return n; } Company Logo CHƢƠNG 1:Tổng quan về CTDLvà 2. Cấu trúc dữ liệu GT Cấu trúc dữ liệu là cách biểu diễn các dữ liệu dùng để mô tả các đối tượng cần xử lý trong máy tính. Các tiêu chuẩn đánh giá cấu trúc dữ liệu: - Phản ánh đúng thực tế: phản ánh đúng và đầy đủ các thuộc tính của đối tượng. Đây là tiêu chuẩn quan trọng nhất. Ví dụ: Số SV trong lớp: số nguyên. Điểm trung bình: số thực. -Phù hợp với các giải thuật xử lý trên đó: các thao tác của cấu trúc dữ liệu phải phù hợp với đối tượng được mô tả. -- Tiết kiệm tài nguyên hệ thống: tránh lãng phí bộ nhớ. www.themegallery.com Company Logo CHƢƠNG 1:Tổng quan về CTDLvà GT 3. Mối liên hệ giữa giải thuật và cấu trúc dữ liệu Để xây dựng 1 chương trình từ bài toán thực tế cần chú trọng 2 vấn đề: -Tổ chức biểu diễn các đối tượng thực tế: -Xây dựng các thao tác xử lý dữ liệu Cấu trúc dữ liệu + Giải thuật = Chƣơng trình www.themegallery.com Company Logo 4. Bài tập 1: Trình bày thuật toán của bài toán sau bằng ngôn ngữ tự nhiên, lưu đồ và mã giả. Nhập vào 2 số nguyên a và b. Giải phương trình: ax + b = 0. 2: Trình bày thuật toán của bài toán sau bằng ngôn ngữ tự nhiên, lưu đồ và mã giả Nhập vào 3 số nguyên a, b và c. Giải phương trình: ax2 + bx + c = 0. 3: Xây dựng sơ đồ giải thuật cho bài toán tính số Fibonaci thứ N, biết rằng dãy số Fibonaci được định nghĩa như sau: F[0] = F[1] = 1, F[N] = F[N-1] + F[N-2] với N ≥ 2 Bài 1. Nhập 2 số nguyên a, b. Giải pt ax+b=0 * Sử dụng ngôn ngữ tự nhiên - Bƣớc 1: Nhập vào 2 hệ số a và b. - Bƣớc 2: Xét điều kiện a = 0 ? Nếu đúng là a = 0, thì đi đến bước 3. Nếu không, nghĩa là a ≠ 0, thì đi đến bước 4. - Bƣớc 3: Xét điều kiện b = 0 ? Nếu b = 0, thì báo phương trình có vô số nghiệm. Ði đến bước 5. Nếu b ≠ 0, thông báo phương trình vô nghiệm. Ði đến bước 5. -Bƣớc 4: Thông báo phương trình có một nghiệm duy nhất là x = - b/a. - Bƣớc 5: Ngừng thuật toán.