Bài giảng Kỹ thuật lập trình - Chương 1: Tổng quan về phương pháp lập trình có cấu tổ chức - Trần Minh Thái

KỸ THUẬT LẬP TRÌNHTRẦN MINH THÁI – minhthai@huflit.edu.vn www.minhthai.edu.vn PHẠM ĐỨC THÀNH – phamducthanh@huflit.edu.vnwww.phamthao.com 12/3/20201Trần Minh Thái - Phạm Đức ThànhPP lập trình có cấu trúc, kỹ thuật phân tích và thiết kế CT có cấu trúc.Kỹ thuật xử lý, tổ chức cấu trúc dữ liệu theo nhu cầu của từng bài toán, theo vấn đề cần giải quyết. Đồng thời trình bày minh hoạ một số bài toán ứng dụng tiêu biểu của các cấu trúc dữ liệu này.Kỹ thuật đệ quy và bài toán quy hoạch động cơ bản.PP tổ chức dữ liệu, kỹ thuật lập trình tối ưu và kiểm thử tính đúng đắn của CT.12/3/20202Mục tiêu – Kiến thứcTrần Minh Thái - Phạm Đức ThànhPhân tích giải thuật và thể hiện giải thuật trên ngôn ngữ lập trình C#.Module hóa CT, áp dụng các kỹ thuật lập trình đệ quy, quy hoạch động để giải quyết một số bài toán cụ thể. Cài đặt được các CT bằng ngôn ngữ C# để giải quyết các bài toán dựa trên các cấu trúc dữ liệu hướng giải quyết vấn đề.Thực hiện được việc phân tích và kiểm thử CT.12/3/20203Trần Minh Thái - Phạm Đức ThànhMục tiêu – Kỹ năngChuẩn bị bài trước khi đến lớp.Tích cực tham gia lớp học đầy đủ.Yêu thích các học phần lập trình.12/3/20204Trần Minh Thái - Phạm Đức ThànhThái độ của sinh viênChuẩn bị đọc tài liệu/bài học trước khi lên lớp.Làm trước các bài tập thực hành quy định, trước khi lên lớp giờ thực hành.Tham dự tối thiểu 80% số tiết học lý thuyết.Tham gia đầy đủ 100% giờ thực hành.Thực hiện đầy đủ các bài tập nhóm.Tham dự kiểm tra giữa học kỳ, kết thúc học phần.Chủ động tổ chức thực hiện giờ tự học.12/3/20205Trần Minh Thái - Phạm Đức ThànhNhiệm vụ sinh viên12/3/20206Điểm thành phầnQuy địnhTrọng sốĐiểm chuyên cầnSố tiết tham dự học/tổng số tiết10%Điểm bài tậpSố bài tập đã làm/số bài tập được giao.10%Điểm bài tập nhóm- Báo cáo/thuyết minh/...- Được nhóm xác nhận có tham gia.5%Điểm thực hành (bài tập)- Báo cáo/kỹ năng, kỹ xảo thực hành/....- Tham gia 100% số giờ 10%Điểm kiểm tra giữa kỳ- Thi thực hành/vấn đáp (45 phút)15%Điểm thi kết thúc học phần- Thi viết (90 phút)- Tham dự đủ 80% tiết lý thuyết và 100% giờ thực hành50%Trần Minh Thái - Phạm Đức ThànhĐánh giá12/3/20207Giáo trình chính[1] Tập Slide bài giảng môn Kỹ thuật lập trìnhTài liệu tham khảo thêm[2] Trần Đan Thư, Nguyễn Thanh Phương, Đinh Bá Tiến, Trần Minh Triết và Đặng Bình Phương, Kỹ thuật lập trình , ĐHKHTN TPHCM, NXB KH và KT, 2014 (thư viện của trường, thư quán ĐHKHTN TPHCM).[3] Thomas H. Cormen et al, Introduction to Algorithms, The MIT Press, McGraw-Hill Book Company, 2010 (website/google).Các loại tài liệu khác[4] Website MSDN: [5] Trần Minh Thái, Giáo trình Kỹ thuật lập trình, 2012 (website tác giả: www.minhthai.edu.vn) Trần Minh Thái - Phạm Đức ThànhTài liệu tham khảoNội dung12/3/2020Trần Minh Thái - Phạm Đức Thành8Chương 1Tổng quan về phương pháp lập trình có cấu trúcChương 2Kỹ thuật xử lý dữ liệu có cấu trúcChương 3Kỹ thuật lập trình đệ quyChương 4Phương pháp quy hoạch độngChương 5Kiểm thử và kỹ thuật tối ưu chương trìnhChương 1Tổng quan về phương pháp lập trình có cấu trúc(3 tiết)12/3/2020Trần Minh Thái - Phạm Đức Thành91.1. Đặt vấn đề1.2. Giới thiệu kỹ thuật lập trình có cấu trúc1.3. Cấu trúc lệnh và cấu trúc dữ liệu1.4. Các nguyên lý lập trình 1.5. Phương pháp phân tích và thiết kế chương trình có cấu trúc1.6. Tóm tắt chương12/3/202010Trần Minh Thái - Phạm Đức ThànhNội dung12/3/202011Thời kỳ đầu: Ngôn ngữ LT bậc thấp Nạp, theo dõi onlineTìm, sửa lỗi khóHệ thống máy cấu hình yếuBộ nhớ ítTốc độ chậmCT được xây dựng: KT tuyến tínhTuần tự, nhảy (goto)Thư viện nghèo, c.phí lớn, độ tin cậy thấp Trần Minh Thái - Phạm Đức Thành[1.1] Đặt vấn đề12/3/202012Hệ thống máy tính: cấu hình mạnh, nhanhCác nhà tin học tìm hiểu sâu về ngôn ngữ LT, thuật toánTrần Minh Thái - Phạm Đức Thành[1.1] Đặt vấn đề12/3/202013Dijkstra, Hoare, Knuth, ..Gồm: lệnh rẽ nhánh, lặp.Chương trình sáng sủa, dễ minh họa, phù hợp tư duy, người mới LTTrần Minh Thái - Phạm Đức Thành[1.2] Giới thiệu LT có cấu trúcThuật toán là tập hữu hạn các lệnh, thao tác cơ bản trên tập các đối tượng đầu vào, thực hiện một chức năng, công việc cụ thể, nhằm thu được kết quả đầu ra mong muốn.12/3/202014Chương trìnhMã hóa thuật toánTrần Minh Thái - Phạm Đức Thành[1.3] Cấu trúc lệnh vs Cấu trúc DL12/3/202015ĐT đầu ra, vàoCT dữ liệuCác thao tácCác lệnh, CT điều khiểnTrần Minh Thái - Phạm Đức Thành[1.3] Cấu trúc lệnh vs Cấu trúc DL12/3/202016static void Main(string[] args){ Console.Write("Nhap n="); int n = int.Parse(Console.ReadLine()); if (n , =, ==, !=Phép toán logic: &&, ||, !Các toán tử thao tác trên bit: &, |, ^, >>, Thứ tự ưu tiên các phép toán12/3/202029Trần Minh Thái - Phạm Đức ThànhTập các phép toánstring Chuoi=Console.ReadLine(); char kytu =char.Parse( Console.ReadLine());StreamReader sr = new StreamReader("data.txt");string S=sr.ReadLine(); char kyTu = char.Parse( sr.ReadLine());12/3/202030Trần Minh Thái - Phạm Đức ThànhTập các lệnh vào/ ra cơ bảnConsole.WriteLine("{0}", Chuoi);Console.WriteLine("{0}", kytu);StreamWriter sw = new StreamWriter("data.txt");sw.WriteLine("{0}", S);sw.WriteLine("{0}", kyTu);12/3/202031Trần Minh Thái - Phạm Đức ThànhTập các lệnh vào/ ra cơ bảnThao tác trên chuỗiThao tác trên fileThao tác trên cấu trúc12/3/202032Trần Minh Thái - Phạm Đức ThànhThao tác trên KDL có cấu trúcint index=S.IndexOf(kyTu);int index=S.IndexOf(Chuoi);int kq= S1.CompareTo (S);S1 = S;S1 = S1 +" "+S;S1= S1.ToLower(); S1 = S1.ToUpper();int len = S1.Length;12/3/202033Trần Minh Thái - Phạm Đức ThànhThao tác trên chuỗiStreamReader sr; StreamWriter sw;sr = new StreamReader("data_input.txt");sw = new StreamWriter("data_out.txt");sr.Close(); sw.Close();string S = sr.ReadLine(); sw.WriteLine(S);if(sr == null) { }if (sw == null) { }12/3/202034Trần Minh Thái - Phạm Đức ThànhThao tác trên filestruct Struct_Name{ public int thuocTinh_1; public double thuocTinh_2; public char thuocTinh_3;}12/3/202035Struct_Name strN;strN.thuocTinh_1 = 5;strN.thuocTinh_2 = 6;strN.thuocTinh_3 = 'a';Struct_Name strN1 = strN;Trần Minh Thái - Phạm Đức ThànhThao tác trên KDL cấu trúcCác biến cục bộ trong hàm dù có trùng tên với biến toàn cục không làm thay thay đổi giá trị biến toàn cụcTên các biến trong danh sách đối số của hàm đều là hình thứcCác biến khai báo bên trong hàm đều là các biến cục bộKhi phải sử dụng biến phụ nên dùng biến cục bộ. Hạn chế tối đa sử dụng biến toàn cục, tránh xảy ra các hiệu ứng phụ12/3/202036Trần Minh Thái - Phạm Đức ThànhNguyên lý địa phươngLỗi cú pháp: (design time)Lỗi cảnh báo (warning)Lỗi khi chạy chương trình (run time error)12/3/202037Trần Minh Thái - Phạm Đức ThànhNguyên lý an toànKhi viết chương trìnhVí dụ: Sai từ khóaSai cú pháp về cấu trúc lệnh, biểu thứcThiếu các dấu ngoặc, dấu chấm phẩy khi kết thúc lệnhChưa khai báo nguyên mẫu hàm (prototype)12/3/202038Trần Minh Thái - Phạm Đức ThànhLỗi cú pháp: (design time)Khi viết chương trìnhThường là khi ta khai báo biến mà không sử dụngKhai báo biến mà không khởi gán giá trịLỗi do thứ tự ưu tiên phép toán12/3/202039Trần Minh Thái - Phạm Đức ThànhLỗi cảnh báo (warning)Compiler không thể phát hiện lỗi nàyNgười lập trình gây ra khi thiết kế CT, xử lý dữ liệuPhải testing mới phát hiện đượcPhải chứng minh được tính đúng đắn của CTKhông lường trước được thông tin nhập vào khi thiết kế CT: Vòng lặp không có điểm dừng xác định Công thức tính toán khi cài đặt chương (lỗi logic)12/3/202040Trần Minh Thái - Phạm Đức ThànhLỗi khi chạy chương trìnhDữ liệu thao tác thế ấyCấu trúc dữ liệu  thao tác trên đóKiểu dữ liệu là một tên thể hiện: tập đối tượng, miền xác định, thao tácMột biến thuộc: Kiểu dữ liệu xác địnhKiểu cơ bảnKiểu do người dùng tự định nghĩa12/3/202041Trần Minh Thái - Phạm Đức ThànhNguyên lý nhất quánThao tác trên biến này phụ thuộc vào thao tác được phép trên kiểu dữ liệu đóHai kiểu dữ liệu khác nhau: tên khác nhau, miền xác định và thao tác là khác nhauKiểu ký tự: về nguyên tắc không được thực hiện phép toán số học trên nó. !!! Ngôn ngữ C# (họ hàng) xem kiểu ký tự là số nguyên (mã ASCII) => các phép toán số học vẫn được sử dụng12/3/202042Trần Minh Thái - Phạm Đức ThànhNguyên lý nhất quánPhương pháp TOP-DOWNPhương pháp BOTTOM-UP12/3/202043Trần Minh Thái - Phạm Đức Thành[1.5] Phương pháp phân tích & thiết kếQuá trình phân tích bài toán được thực hiện từ trên xuống. Từ vấn đề chung nhất đến cụ thể nhất. Từ trừu tượng tổng quan đến đơn giản nhất là đơn vị chương trình (module – đơn thể)12/3/202044Trần Minh Thái - Phạm Đức ThànhPhương pháp TOP-DOWN12/3/202045Mức tổng quanChức năng chính F1Chức năng phụ 1.1đơn thể 1.1.1đơn thể 1.1.2Chức năng phụ 1.2Chức năng chính F2Chức năng phụ 2.1đơn thể 2.1.1Chức năng chính F3Mức 0Mức 1Mức 2Mức đơn thểTrần Minh Thái - Phạm Đức ThànhPhương pháp TOP-DOWNĐi từ chi tiết cụ thể riêng biệt đến phần chung nhất cao hơn. Từ các modul tới tổng thể chương trình.Top-Down: ppháp phân rã vấn đề từ trên xuống, chủ yếu trong quá trình phân tích và thiết kế hệ thống chương trình.Bottom-up thường được sử dụng trong quá trình cài đặt, viết chương trình.12/3/202046Trần Minh Thái - Phạm Đức ThànhPhương pháp BOTTOM-UPNgôn ngữ LT bất kỳ đều dựa trên tập các cấu trúc lệnh điều khiển, các cấu trúc DL + phép toán được định nghĩa trên nóNgười học nên lập trình từ các kiến thức cơ bản về câu lệnh, cú pháp, cấu trúc lệnh, dữ liệu và phép toán tương ứng trên nó (nguyên lý tối thiểu)Phân biệt hai loại biến toàn cục và địa phương. Giúp ta biết cách truyền tham biến (ref, out) hay truyền tham trị cho đối số của hàm12/3/202047Trần Minh Thái - Phạm Đức Thành[1.6] Tóm tắtNguyên lý nhất quán: dữ liệu nào, thì phép toán đó.Khi cài đặt nên lường trước và kiểm tra chặt chẽ các lỗi có thể xảy ra.Phân rã từ vấn đề lớn thành các module nhỏ gọi là top-down.Cài đặt chương trình từ các module đến lắp ghép thành cả hệ thống gọi là bottom-up.12/3/202048Trần Minh Thái - Phạm Đức Thành[1.6] Tóm tắtBài 1: VCT nhập vào số tự nhiên n. Tìm tất cả bộ 3 các số tự nhiên a, b, c sao cho a2 + b2 = c2, với a<=b<=c<=n;Bài 2: VCT nhập vào số tự nhiên n. In ra dãy số Fibonaci nhỏ hơn n.Trong đó: F0 = F1 = 1; Fn = Fn-1 + Fn-212/3/202049Trần Minh Thái - Phạm Đức Thành[1.7] Bài tậpBài 3: VCT nhập vào số tự nhiên n. Liệt kê tất cả các số nguyên tố nhỏ hơn n.Bài 4: VCT nhập vào số tự nhiên n. Liệt kê tất cả các số nguyên tố nhỏ hơn n dùng sàng Estheven.Bài 5: VCT nhập vào số tự nhiên n. Liệt kê tất cả các số nguyên tố nhỏ hơn n nằm trong cùng bậc hàng chục dùng sàng Estheven (Ví dụ: 11, 13, 15, 17).Bài 6: Cho số nguyên dương n. VCT phân tích n ra thành các thừa số nguyên tố. Ví dụ: n=12=2*2*3.12/3/202050Trần Minh Thái - Phạm Đức Thành[1.7] Bài tập