Cấu trúc dữ liệu - Chương I: Các khái niệm cơ bản

CTDL – Khoa CNTH – Viện ĐH Mở HN CẤU TRÚC DỮ LIỆU Khoa Công nghệ thông tin Email: trinhxuan@gmail.com Thời lượng: 60 tiết – LT Web: //sites.google.com/site/trinhxuan 1
CTDL – Khoa CNTH – Viện ĐH Mở HN ! Hình thức thi: BTL "  Nhóm 4 SV ! Cách tính điểm: " Điểm CC: 10% " Điểm GK: 20% " Điểm thi: 70% ! Bài tập lớn ! Test Bài tập lớn 2
CTDL – Khoa CNTH – Viện ĐH Mở HN *Tài liệu học tập: ! Giáo trình bắt buộc " Giáo trình Cấu trúc dữ liệu – Khoa CNTT, Viện ĐH Mở HN – Lưu hành nội bộ ! Giáo trình tham khảo " Đỗ Xuân Lôi, “Cấu trúc dữ liệu và giải thuật”, NXB Khoa học và kỹ thuật. " Introduction to Algorithms – The cormen 3
CTDL – Khoa CNTH – Viện ĐH Mở HN Mục đích môn học # Hiểu được khái niệm CTDL và Thuật toán # Biết cách đánh giá độ phức tạp của một thuật toán # Nắm được các CTDL cơ bản: Mảng, Danh sách # Hiểu và vận dụng được một số CTDL đặc biệt: Hàng đợi, Ngăn xếp, Cây, Đồ thị # Hiểu và áp dụng được một số thuật toán cơ bản: Tìm kiếm, Sắp xếp, 4
CTDL – Khoa CNTH – Viện ĐH Mở HN *Nội dung môn học 5
CTDL – Khoa CNTH – Viện ĐH Mở HN STT SỐ TIẾT NỘI DUNG GIẢNG DẠY Y/C Đọc TL Ghi chú 1 5 Đánh giá Thuật Toán - Phân công BTL Các buổi Thực hành có thể mang máy tính cá nhân đi thực hành 2 5 TK và SX x 3 5 TK và SX x 4 5 Thực hành mảng - Test x 5 5 DSLK Đơn x 6 5 Thực hành DSLK Đơn - Test x 7 5 Danh sách liên kết đôi x 8 5 Stack - Queue x 9 5 Cây x 10 5 Cây - Test x 11 5 Đồ thị x 12 5 Test BTL – Đánh giá sơ bộ - TH x 6
CTDL – Khoa CNTH – Viện ĐH Mở HN Lưu ý sử dụng Phòng máy ! Sử dụng điều hòa: Phải đăng ký và mất phí ! Tổng số buổi thực hành: 03 buổi ! Tổng phí phải nộp: 600.000đ (200.000/1 buổi) "  Phí tính trên 1 sinh viên: 10.000đ/3 buổi ! Lớp trưởng thu giúp ! Cách thức thực hiện: "  Buổi 1: Thu thập nguyên vọng sử dụng điều hòa "  Buổi 2+3: Thu tiền sử dụng điều hòa ! Nguyên tắc số ít theo số nhiều 7
CTDL – Khoa CNTH – Viện ĐH Mở HN Yêu cầu kiến thức cần có !  Xem và tổng hợp lại ngôn ngữ C !  Nội dung cần tổng hợp lại: "  Cấu trúc chương trình "  Khai báo biến "  Nhập/xuất dữ liệu "  Cấu trúc điều khiển "  Mảng "  Chuỗi "  Chương trình con – hàm "  Cấu trúc "  Con trỏ "  File "  8
CTDL – Khoa CNTH – Viện ĐH Mở HN CHƯƠNG I: CÁC KHÁI NIỆM CƠ BẢN 9
CTDL – Khoa CNTH – Viện ĐH Mở HN I. Giới thiệu ! Các bước để xây dựng bài toán tin học trong máy tính Bài toán thực tế Yêu cầu Thiết kế Giải thuật Thuật toán #include Chương trình Lập trình • Ngôn ngữ lập trình: • PASCAL, • C/C++, • JAVA, • Visual Basic •  Xây dựng một bài toán tin học thực chất là chuyển một bài toán thực tế thành một bài toán giải quyết được bằng máy tính 10
CTDL – Khoa CNTH – Viện ĐH Mở HN II. Các bước xây dựng chương trình Xác định bài toán Tìm CTDL biểu diễn bài toán Tìm thuật toán Lập trình Kiểm thử Tối ưu chương trình 11
CTDL – Khoa CNTH – Viện ĐH Mở HN 1. Xác định bài toán #  Xác định xem ta phải giải quyết vấn đề gì? #  Xác định yêu cầu cần thực hiện của bài toán $ các thao tác cần thực hiện #  Các bài toán tin học cần phải chỉ ra lời giải tốt nhất bởi vì nếu không lời giải đó có thể đòi hỏi nhiều thời gian và chi phí. 12
CTDL – Khoa CNTH – Viện ĐH Mở HN 2. Tìm CTDL biểu diễn bài toán %  Xác định input và output của bài toán %  Input: dữ liệu đầu vào %  Output: Kết quả mong muốn đạt được Các tiêu chuẩn: #  Biểu diễn đầy đủ các thông tin nhập và xuất của bài toán #  Phải phù hợp với các thao tác của thuật toán mà ta lựa chọn để giải quyết bài toán #  Cài đặt được trên máy tính với một ngôn ngữ lập trình xác định 13
CTDL – Khoa CNTH – Viện ĐH Mở HN 3. Tìm thuật toán %  Xác định hệ thống chặt chẽ và rõ ràng các quy tắc để từ Input có được Output %  Xác định dãy thao tác trên CTDL đầu vào để giải quyết yêu cầu bài toán Đảm bảo #  Mỗi bước thao tác rõ ràng #  Không được rơi vào quá trình vô hạn #  Sau khi thực hiện các bước phải cho kết quả đúng #  Phải đảm bảo cài đặt được chương trình 14
CTDL – Khoa CNTH – Viện ĐH Mở HN 4. Lập trình #  Xác định ngôn ngữ lập trình được sử dụng #  Thông thường ta không nên cụ thể hóa ngay toàn bộ chương trình mà nên tiến hành theo phương pháp tinh chế từng bước # Nguyên tắc % Ban đầu, thể hiện thuật toán với các bước tổng thể, mỗi bước nêu lên một công việc phải thực hiện % Một công việc đơn giản hoặc là một đoạn chương trình đã được học thuộc thì ta tiến hành viết mã lệnh ngay bằng ngôn ngữ lập trình % Một công việc phức tạp thì ta lại chia thành những công việc nhỏ hơn để lại tiếp tục với những công việc nhỏ hơn đó. 15
CTDL – Khoa CNTH – Viện ĐH Mở HN 5. Kiểm thử #  Kiểm tra lỗi chương trình #  Lỗi cơ bản &  Lỗi cú pháp &  Lỗi cài đặt &  Lỗi thuật toán #  Lập bộ test để kiểm thử #  Nguyên tắc xây dựng bộ test &  Bắt đầu với bộ test nhỏ, đơn giản, &  Tiếp theo vẫn là các bộ test nhỏ, nhưng chứa các giá trị đặc biệt hoặc tầm thường. &  Các bộ test phải đa dạng, tránh sự lặp đi lặp lại &  Có một vài bộ test lớn 16
CTDL – Khoa CNTH – Viện ĐH Mở HN 6. Tối ưu chương trình #  Đặt mục tiêu viết chương trình sao cho đơn giản, làm sao chạy ra kết quả đúng, sau đó ta xem lại những chỗ nào viết chưa tốt thì tối ưu lại mã lệnh để chương trình ngắn hơn, chạy nhanh hơn #  Không nên viết tới đâu tối ưu tới đó, bởi chương trình có mã lệnh tối ưu thường phức tạp và khó kiểm soát. #  Tiêu chuẩn tối ưu &  Tính tin cậy &  Tính uyển chuyển &  Tính trong sáng &  Tính hữu hiệu 17
CTDL – Khoa CNTH – Viện ĐH Mở HN III. CTDL và Thuật toán ! Xây dựng một bài toán cần: " Xác định Cấu trúc dữ liệu ! Đối tượng dữ liệu dùng trong bài toán $ Tổ chức biểu diễn được đối tượng " Xác định Thuật toán ! Các yêu cầu xử lý trên đối tượng đó $ Xác định và xây dựng thao tác xử lý trên đối tượng CTDL + Thuật toán = Chương trình Structure Data + Algorithm = Program 18
CTDL – Khoa CNTH – Viện ĐH Mở HN a. Cấu trúc dữ liệu – Structure Data ! Cấu trúc dữ liệu là một cách để tổ chức và lưu thông tin các đối tượng bài toán (thực tế) vào trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả ! Các kiểu cấu trúc dữ liệu cơ bản: " Mảng, Bản ghi " Danh sách liên kết, Ngăn xếp, Hàng đợi " Cây " Đồ thị 19
CTDL – Khoa CNTH – Viện ĐH Mở HN !  Các yếu tố xác định một kiểu CTDL: "  Tên kiểu CTDL "  Miền giá trị "  Kích thước lưu trữ "  Tập các toán tử (thao tác) thực hiện trên kiểu dữ liệu đó !  Các tiêu chuẩn đánh giá một CTDL: "  Phản ảnh đúng thực tế "  Phù hợp với thao tác xử lý "  Tiết kiệm tài nguyên hệ thống !  Một cấu trúc dữ liệu được thiết kế tốt cho phép: "  Thực hiện nhiều phép toán, "  Sử dụng càng ít tài nguyên, "  Thời gian xử lý và không gian bộ nhớ tốt 20
CTDL – Khoa CNTH – Viện ĐH Mở HN b. Thuật toán - Algorithm: ! Thuật toán, còn gọi là giải thuật " là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề nào đó trong một số bước hữu hạn, " hoặc cho ra một kết quả (output) từ một tập hợp của các dữ liệu đưa vào (input) Input Output Thuật toán 21
CTDL – Khoa CNTH – Viện ĐH Mở HN * Tính chất của thuật toán ! Tính chính xác ! Tính rõ ràng ! Tính khách quan ! Tính phổ dụng ! Tính kết thúc 22
CTDL – Khoa CNTH – Viện ĐH Mở HN IV. Đánh giá độ phức tạp thuật toán ! Các tiêu chí lựa chọn thuật toán: "  1. Thuật toán đơn giản, dễ hiểu. "  2. Thuật toán dễ cài đặt (dễ viết chương trình) "  3. Thuật toán cần ít bộ nhớ "  4. Thuật toán chạy nhanh ! => để đánh giá thuật toán dựa vào độ phức tạp thuật toán ! Độ phức tạp thuật toán được thể hiện qua: "  Không gian "  Thời gian 23
CTDL – Khoa CNTH – Viện ĐH Mở HN a. Độ phức tạp không gian: ! Là tổng số chi phí về mặt không gian (bộ nhớ) cần thiết sử dụng cho thuật toán $ đánh giá dựa vào tổng số bộ nhớ khai báo cho các biến ! Chi phí bộ nhớ gồm: " Lưu dữ liệu vào - input " Lưu dữ liệu ra - output " Lưu các kết quả trung gian - temp 24
CTDL – Khoa CNTH – Viện ĐH Mở HN b. Độ phức tạp thời gian: !  là tổng thời gian cần thiết để hoàn thành thuật toán ! Được đánh giá dựa vào số lượng các thao tác được sử dụng trong thuật toán dựa trên bộ dữ liệu đầu vào !  Các thao tác được xem xét: "  Phép so sánh "  Phép cộng, trừ, nhân, chia, "  Phép toán thay đổi "  Phép gán "  Phép trả lại giá trị "  !  Khi xét độ phức tạp thuật toán chỉ tập trung vào độ phức tạp tính toán (độ phức tạp thời gian) 25
CTDL – Khoa CNTH – Viện ĐH Mở HN int sum (int n) { int sum, i ; sum = 0; i = 1; while (i < n) { sum = sum + i; i = i+ 1; } return sum; } No time 1 Unit 1 Unit n Unit (n Comparison) 2 x (n-1) Unit 2 x (n-1) Unit 1 Unit T"(n)"="1+1+n+2*(n+1)+2*(n+1)+1"="5n"+"1"" VD: Xác định độ phức tạp thuật toán 26
CTDL – Khoa CNTH – Viện ĐH Mở HN int Sum (int n) { int sum ; sum =0; for ( int i =0 ; i<n; i++) sum = sum + i; return sum; } VD: Xác định độ phức tạp không gian và thời gian thuật toán 27
CTDL – Khoa CNTH – Viện ĐH Mở HN %  Thời gian chạy trong trường hợp xấu nhất (worst-case running time) Là thời gian chạy lớn nhất của thuật toán đó trên tất cả các dữ liệu vào cùng cỡ, %  Thời gian chạy trung bình (average running time) Là số trung bình cộng của thời gian chạy của thuật toán đó trên tất cả các dữ liệu vào cùng cỡ n. 5 3 10 13 6 9 15 21 12 8 61 39 Best Case Worst Case Average Case %  Thời gian chạy trong trường hợp tốt nhất (best-case running time) Là thời gian chạy nhỏ nhất (1 lần chạy) của thuất toán đó trên tất cả dữ liệu vào cùng cỡ Ký hiệu thời gian : T(n), trong đó n là cỡ của dữ liệu vào.! 39"5" *Phân loại đánh giá: 28
CTDL – Khoa CNTH – Viện ĐH Mở HN c. Ký hiệu O: !  Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm O - lớn !  Định nghĩa: "  Giả sử T(n) và g(n) là các hàm của đối số nguyên n. "  Ta nói T(n) là ô lớn của g(n)
và viết là: T(n) = O(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho T(n) <= c.g(n) với mọi n >= n0. !  Giả sử f(n) = 5n3 + 2n2 + 13n + 6, ta có: f(n) = 5n3 + 2n2 + 13n + 6 <= 5n3 + 2n3 + 13n3 + 6n3 <= 26n3 f(n) = O(n3). 29
CTDL – Khoa CNTH – Viện ĐH Mở HN int sum (int n) { int sum, i ; sum = 0; i = 1; while (i < n) { sum = sum + i; i = i+ 1; } return sum; } No time 1 Unit 1 Unit n Unit (n Comparison) 2 x (n-1) Unit 2 x (n-1) Unit 1 Unit T"(n)"="1+1+n+2*(n+1)+2*(n+1)+1"="5n"+"1"" <="5n"+"1n" <="6n"" T"(n)"="O(n)" VD: Xác định độ phức tạp thuật toán (O-lớn) 30
CTDL – Khoa CNTH – Viện ĐH Mở HN int Sum (int n) { int sum ; sum = 0; for ( int i =1 ; i<=n; i++) { sum = sum + i*i*i; } return sum; } No time 1 Unit 3n + 2 Unit 4 *n Unit 1 Unit T"(n)"="1"+"3n"+"2"+"4*n"+"1"="7n"+"4"" <="7n"+"4n" <="11n"" T"(n)"="O(n)" VD: Xác định ký hiệu O –lớn của thuật toán 31
CTDL – Khoa CNTH – Viện ĐH Mở HN %  Vòng lặp đơn (for, while, do-while) for ( int i = 0; i<n ; i++) { s1, s2,, sk } Câu lệnh s1, s2, có dạng O(1) %  Các câu lệnh thông thường s1, s2,, sk (i = 1; i = i*i ) O(1) O(n) *Một số trường hợp ký tự O-lớn đặc biệt 32
CTDL – Khoa CNTH – Viện ĐH Mở HN %  Lưa chọn (if-else, switch) if ( condition ) { s1, s2,, sk } else { s1, s2,, sk } Câu lệnh s1, s2, có dạng O(1) O(1) 33
CTDL – Khoa CNTH – Viện ĐH Mở HN %  Vòng lặp lồng nhau (for, while, do-while) for ( int i = 0; i<n ; i++) { for ( int j = 0; j<n ; j ++) { s1, s2,sk } } Câu lệnh s1, s2, có dạng O(1) O(n2) 34
CTDL – Khoa CNTH – Viện ĐH Mở HN %  Tổng hợp (tuần tự, for, while, do-while) for( int k =0 ; k<n ; k++) { s1, s2,sk } s1, s2, , sk for ( int i = 0; i<n ; i++) { for ( int j = 0; j<n ; j++) { s1, s2,sk } } Câu lệnh s1, s2, có dạng O(1) O(n) O(n2) O(1) O(n2) 35
CTDL – Khoa CNTH – Viện ĐH Mở HN Ký hiệu ô lớn Tên gọi O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n) hằng logarit tuyến tính nlogn bình phương lập phương mũ 36
CTDL – Khoa CNTH – Viện ĐH Mở HN V. Biểu diễn thuật toán ! Liệt kê theo bước ! Sơ đồ khối – flow chart ! Mã giả - Pseudocode " Dùng ngôn ngữ C để cài đặt thuật toán 37
CTDL – Khoa CNTH – Viện ĐH Mở HN * Sử dụng lưu đồ khối ! Là công cụ rất trực quan để diễn đạt các thuật toán ! Là hệ thống các nút có hình dạng khác nhau, thể hiện các chức năng khác nhau và được nối bởi các cung ! Các thành phần của lưu đồ khối: 38
CTDL – Khoa CNTH – Viện ĐH Mở HN int sum (int n) { int sum, i ; sum = 0; i = 1; while (i < n) { sum = sum + i; i = i+ 1; } return sum; } VD: Xây dựng sơ đồ thuật toán sau Begin i < n Sum = 0; i = 1; sum = sum + i i = i + 1 End return sum; Đúng Sai 39
CTDL – Khoa CNTH – Viện ĐH Mở HN VI. Giải thuật đệ quy (recursion) ! Khái niệm ! Bài toán ! Lời giải và giải thuật đệ quy 40
CTDL – Khoa CNTH – Viện ĐH Mở HN 1. Giải thuật đệ quy ! Giải thuật đệ quy là lời giải một bài toán P được thực hiện bằng lời giải của bài toán P khác có dạng giống như P, P phải nhỏ hơn P ! Ví dụ: " Tính giai thừa " Tính tổng các số nhỏ hơn hoặc bằng n 41
CTDL – Khoa CNTH – Viện ĐH Mở HN ! Định nghĩa một giải thuật đệ quy: " phần neo (anchor) ! Chỉ ra lời giải đơn giản của bài toán $ trường hợp đơn giản ! Có thể giải trực tiếp chứ không cần phải nhờ đến một bài toán con nào khác " phần đệ quy ! xác định những bài toán con đã có và bài toán cần giải thực hiện gọi đệ quy giải những bài toán con đó, ! để giải bài toán thì phối hợp các các bài toán con đã có lời giải lại với nhau theo nguyên tắc xác định # Ví dụ: Tính giai thừa & Phần tử neo: n = 1 & Phần đệ quy: Giai thừa (n) = n * Giai thừa (n-1) 42
CTDL – Khoa CNTH – Viện ĐH Mở HN 2. Phân loại hàm đệ quy # Đệ quy tuyến tính Trong thân hàm gọi 1 lần chính nó # Đệ quy nhị phân Thân hàm gọi 2 lần chính nó # Đệ quy phi tuyến Thân hàm lặp gọi nhiều lần chính nó # Đệ quy tương hỗ Hai hàm đệ quy gọi nhau int Giaithua ( int n ) { if (n==1) return 1; return n * Giaithua ( n-1 ); } long Fibonaci ( int n ) { if (n<=2) r t r ; else return Fibonaci( n – 2 + Fibonaci( n – 1 ); } long Tong ( int n ) { if (n<6) return n; long S = 0; for ( int i = 5; i > 0; i-- ) S = S + Tong( n-i ); return S; } long G( int n ); long U ( int n) { if (n<5) return n; return U(n-1) + G(n-2); } long G( int n ) { if (n<8) return n-3; return U(n-1) + G(n-2); } 43
CTDL – Khoa CNTH – Viện ĐH Mở HN 3. Kỹ thuật tìm giải thuật đệ quy #  Thông số hóa bài toán #  Tìm các điều kiện biên (điều kiện chặn) &  Lời giải với giá trị cụ thể &  Tìm giải thuật cho các tình huống này #  Tìm giải thuật tổng quát theo hướng đệ quy lui dần về tình huống bị chặn #  Thực hiện cài đặt &  Viết chương trình theo đúng thứ tự công thức đệ quy 44
CTDL – Khoa CNTH – Viện ĐH Mở HN 45
Ví dụ: Thực hiện giải bài toán tính tổng các số nguyên nhỏ hơn hoặc bằng n bằng đệ quy (n là số nguyên dương) CTDL – Khoa CNTH – Viện ĐH Mở HN VD: TÍNH TỔNG N PHẦN TỬ CỦA MẢNG A Thông số hóa: int a[ ], int n Điều kiện biên: Mảng 0 phần tử thì tổng bằng 0. Giải thuật tổng quát Sum (a, n) = a[0] + a[1] + a[2] + ... + a[n-2] + a[n-1] Sum(a, n-1) Sum (a, n) = 0 nếu n=0 a[n-1] + Sum (a, n-1) với n>=1 46
CTDL – Khoa CNTH – Viện ĐH Mở HN VD: TÍNH TỔNG N PHẦN TỬ CỦA MẢNG A (tiếp) int Sum ( int a[ ], int n) { if ( n == 0 ) return 0; else return ( a[n-1] + Sum (a, n-1) ); } Cài đặt thuật toán 47
CTDL – Khoa CNTH – Viện ĐH Mở HN VD2: Tìm trị lớn nhất của mảng a gồm n phần tử ! Điều kiện biên: Mảng 1 phần tử thì trị lớn nhất là a[0]. !  Giải thuật chung: Max(a,n) = a[0] , a[1] , a[2] , ... , a[n-2] , a[n-1] Max(a, n-1 ) Max (a,n) = a[0] , n=1 a[n-1] > Max(a, n-1)? a[n-1] : Max(a,n-1) Sv tự viết 48
CTDL – Khoa CNTH – Viện ĐH Mở HN Cài đặt đệ quy tìm phần tử lớn nhất trong mảng float Max ( float a[ ], int n ) { if (n==1) return a[0]; else return ((a[n-1] > Max(a, n-1))? a[n-1] : Max(a,n-1)); } 49
CTDL – Khoa CNTH – Viện ĐH Mở HN BÀI TẬP VỀ NHÀ ! Giải bài toán tìm phần tử lớn nhất của mảng a gồm n số nguyên bằng đệ quy ! Yêu cầu: " Viết bằng tay đầy đủ các bước để giải " Đầu giờ sau nộp lại cho GV 50
CTDL – Khoa CNTH – Viện ĐH Mở HN Tóm lược bài học Các khái niệm CTDL và thuật toán Đánh giá độ phức tạp thuật toán Biểu diễn thuật toán Các bước thiết kế thuật toán Giải thuật đệ quy 51
CTDL – Khoa CNTH – Viện ĐH Mở HN Bài tập về nhà !  Làm theo nhóm !  Trình bày đầy đủ - chi tiết các bước để giải quyết bài toán !  Bài toán: cho thông tin của hàng hóa gồm: mã hàng hóa, tên hàng hóa, số lượng và đơn giá. Viết chương trình quản lý hàng hóa với các yêu cầu: "  Nhập vào một danh sách hàng hóa "  In lại danh sách hàng hóa "  In danh sách hàng hóa có đơn giá trên 50000 "  Tính tổng tiền của tất cả các hàng hóa "  Đếm số hàng hóa có số lượng dưới 20 !  Yêu cầu: "  Cài đặt code "  Làm báo cáo chi tiết các bước để giải bài toán (viết tay hoặc đánh máy) 52
CTDL – Khoa CNTH – Viện ĐH Mở HN Bài tập viết hàm đệ quy ! Tính tổng các số nguyên nhỏ hơn hoặc bằng n ! Tính tổng các phần tử của mảng a gồm n số nguyên ! BTVN: Bài tập viết hàm đệ quy "  Tính số Fibonaci thứ n "  Tìm phần tử lớn nhất của mảng a gồm n phần tử 54
CTDL – Khoa CNTH – Viện ĐH Mở HN 5. Nhận xét về hàm đệ quy HÀM ĐỆ QUY: Vừa tốn bộ nhớ vừa chạy chậm vì gọi hàm nhiều   Giải thuật đệ quy đẹp (gọn gàng), dễ chuyển thành chương trình.   Nhiều ngôn ngữ không hỗ trợ giải thuật đệ quy (Fortran).   Nhiều giải thuật rất dễ mô tả dạng đệ quy nhưng lại rất khó mô tả với giải thuật không-đệ-quy. 68
CTDL – Khoa CNTH – Viện ĐH Mở HN 7. Khử đệ quy !  Là quá trình chuyển đổi 1 giải thuật đệ quy thành giải thuật không đệ quy. !  Chưa có giải pháp cho việc chuyển đổi này một cách tổng quát. !  Cách tiếp cận: " Dùng quan điểm đệ quy để tìm giải thuật cho bài toán. " Mã hóa giải thuật đệ quy. " Khử đệ quy để có giải thuật không-đệ-quy. 69
CTDL – Khoa CNTH – Viện ĐH Mở HN *Khử đệ quy bằng vòng lặp ! Ý tưởng: Lưu lại các trị của các lần tính toán trước làm dữ liệu cho việc tính toán của lần sau. ! Đi từ điều kiện biên đi tới điều kiện kết thúc. 70
CTDL – Khoa CNTH – Viện ĐH Mở HN Thí dụ: Hàm tính giai thừa của n long GiaiThua( int n) { if (n<2) return 1; return n * GiaiThua(n-1); } Trị cần lưu long GiaiThua( int n) { long K=1; for (int i =2; i<=n;i++) K=K*i; return K; } Điều kiện biên K chính là kết qủa của trị giai thừa trước đó 71
CTDL – Khoa CNTH – Viện ĐH Mở HN Thí dụ hàm tính trị thứ n của dãy Fibonacci: 1 1 2 3 5 8... long Fibo(int n) { if (n<=2) return 1; // hai chặn return Fibo(n-2) + Fibo (n-1); } t 1 t 2 t3=t1+t2 t1 t2 t3 t1 t2 t3 t1 t2 t3 long Fibo(int n) { if (n<=2) return 1; // hai chặn long t1=1, t2=1; for (int i=3; i<=n;i++) { t3=t1+t2; t1=t2; t2= t3; } return t3; } i = 3 4 5 6 72
CTDL – Khoa CNTH – Viện ĐH Mở HN BTVN ! Làm bài tập về nhà số 01, viết ra giấy, đầu giờ buổi sau thu ! Đọc và nghiên cứu trước giáo trình phần: " Thuật toán tìm kiếm (tuyến tính và nhị phân) " Thuật toán sắp xếp (selection, insertion ) " Mỗi thuật toán xác định: ! Ý tưởng ! Các bước thực hiện ! Đánh giá độ phức tạp thuật toán ! Lấy ví dụ minh họa 77