Ậ
Ậ
Ỹ
K THU T L P TRÌNH
TRẦN MINH THÁI – minhthai@huflit.edu.vn
www.minhthai.edu.vn
PHẠM ĐỨC THÀNH – phamducthanh@huflit.edu.vn
www.phamthao.com
1 9/17/16 Trần Minh Thái - Phạm Đức Thành
Mục tiêu – Kiến thức
v PP 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.
v 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.
v Kỹ thuật đệ quy và bài toán quy hoạch động cơ
bản.
v 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.
2 9/17/16 Trần Minh Thái - Phạm Đức Thành
Mục tiêu – Kỹ năng
v Phâ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#.
v 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ể.
v 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 đề.
v Thực hiện được việc phân tích và kiểm thử CT.
3 9/17/16 Trần Minh Thái - Phạm Đức Thành
Thái độ của sinh viên
v Chuẩn bị bài trước khi đến lớp. v Tích cực tham gia lớp học đầy đủ. v Yêu thích các học phần lập trình.
4 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nhiệm vụ sinh viên v Chuẩn bị đọc tài liệu/bài học trước khi lên lớp. v 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.
v Tham dự tối thiểu 80% số tiết học lý thuyết. v Tham gia đầy đủ 100% giờ thực hành. v Thực hiện đầy đủ các bài tập nhóm. v Tham dự kiểm tra giữa học kỳ, kết thúc học
phần.
v Chủ động tổ chức thực hiện giờ tự học.
5 9/17/16 Trần Minh Thái - Phạm Đức Thành
Đánh giá
ể
ố
ể ể
ố
ậ
ố ế t ậ ượ
ầ Đi m thành ph n ầ Đi m chuyên c n ậ Đi m bài t p
c
ọ Tr ng s 10% 10%
ể
ậ
ế
Đi m bài t p nhóm
5%
ượ
ậ ỹ ả
ự
ỹ
10%
ự ể Đi m th c hành (bài t p)ậ
ố ờ
ự
tra
ể ki m
Quy đ nhị ự ọ ổ ố ế S ti t tham d h c/t ng s ti ố S bài t p đã làm/s bài t p đ giao. Báo cáo/thuy t minh/... Đ c nhóm xác nh n có tham gia. Báo cáo/k năng, k x o th c hành/.... Tham gia 100% s gi ấ Thi th c hành/v n đáp (45 phút)
15%
ế
ế
50%
ế
ế
t lý thuy t và
ể Đi m gi a kữ ỳ ể Đi m thi k t thúc ầ ọ h c ph n 9/17/16
Thi vi t (90 phút) ự ủ Tham d đ 80% ti ờ ự th c hành 100% gi Trần Minh Thái - Phạm Đức Thành
6
Tài liệu tham khảo
ậ ậ
ậ
ả
ỹ
Giáo trình chính [1] T p Slide bài gi ng môn K thu t l p trình
ầ
ễ
ư
ươ
ả
ặ
ầ
ế
ươ
ệ Tài li u tham kh o thêm
t và Đ ng Bình Ph
ế ậ ậ
ư
ư ệ ủ
ạ
ệ
ầ
ỹ
Các lo i tài li u khác
[2] Tr n Đan Th , Nguy n Thanh Ph ng, Đinh Bá ỹ ng, K Ti n, Tr n Minh Tri 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, McGrawHill Book Company, 2010 (website/google). [4] Website MSDN: http://msdn.microsoft.com [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)
7 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nội dung
8 9/17/16 Trần Minh Thái - Phạm Đức Thành
Ch
ng 1
ổ
ậ
ng pháp l p
ươ ề ươ T ng quan v ph trình có c u trúc
ấ t)ế
(3 ti
9 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nội dung
v 1.1. Đặt vấn đề v 1.2. Giới thiệu kỹ thuật lập trình có cấu trúc v 1.3. Cấu trúc lệnh và cấu trúc dữ liệu v 1.4. Các nguyên lý lập trình v 1.5. Phương pháp phân tích và thiết kế
chương trình có cấu trúc
v 1.6. Tóm tắt chương
10 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.1] Đặt vấn đề
11 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.1] Đặt vấn đề
12 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.2] Giới thiệu LT có cấu trúc
13 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.3] Cấu trúc lệnh vs Cấu trúc DL v Thuậ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.
14 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.3] Cấu trúc lệnh vs Cấu trúc DL
15 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc lệnh – rẽ nhánh
ề
ệ Đi u ki n
Đúng
L nhệ
static void Main(string[] args) { Console.Write("Nhap n="); int n = int.Parse(Console.ReadLine()); if (n < 0) n = -n; Console.WriteLine("n={0}",n); }
16 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc lệnh – rẽ nhánh
ề
Sai
ệ Đi u ki n
Đúng
ệ
ườ
ng
L nh cho tr ợ
h p đúng
ệ L nh cho ợ ườ ng h p sai
tr
17 9/17/16
if (n % 2 == 0) Console.WriteLine("{0} chan",n); else Console.WriteLine("{0} le", n); Trần Minh Thái - Phạm Đức Thành
Cấu trúc lệnh – lựa chọn
switch (n) { case 1: Console.WriteLine(“One"); break; case 2: Console.WriteLine(“Two"); break; ......... case 9: Console.WriteLine(“Nine"); break; default: Console.WriteLine(“Else”); break;
}
18 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc lệnh – lặp
Khởi gán
Đúng
Kiểm tra biểu thức điều kiện
Thực hiện các câu lệnh
Dừng
Tăng/giảm chỉ số
19 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc lệnh - lặp
static void Main(string[] args) { Console.Write("Nhap n="); int n = int.Parse(Console.ReadLine()); for(int i=1; i<=n; i++) Console.Write("{0,4}", i); }
20 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc lệnh – lặp
static void Main(string[] args) { Console.Write("Nhap n="); int n = int.Parse(Console.ReadLine()); int i=1; while (i <= n) { Console.Write("{0,4}", i); i++; } }
21 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc lệnh – lặp
static void Main(string[] args) { Console.Write("Nhap n="); int n = int.Parse(Console.ReadLine()); int i=1; do { Console.Write("{0,4}", i); i++; }while (i <= n) ; }
22 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc dữ liệu
23 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc dữ liệu
24 9/17/16 Trần Minh Thái - Phạm Đức Thành
Cấu trúc dữ liệu
25 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.4] Các nguyên lý lập trình
v Nguyên lý tối thiểu v Nguyên lý địa phương v Nguyên lý an toàn v Nguyên lý nhất quán
26 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nguyên lý tối thiểu
v Tập nguyên tắc v Tối thiểu
Ø Cấu trúc lệnh Ø Kiểu dữ liệu + phép toán
v Hệ thống thư viện
27 9/17/16 Trần Minh Thái - Phạm Đức Thành
Công cụ tối thiểu
v Tập các phép toán v Tập các lệnh vào ra cơ bản v Thao tác trên các kiểu dữ liệu có cấu trúc cơ
bản
28 9/17/16 Trần Minh Thái - Phạm Đức Thành
Tập các phép toán
v Phép toán số học cơ bản: +, - , *, %, / v Phép toán số học mở rộng: ++, --, +=, ... v Phép toán so sánh: >, <, <=, >=, ==, != v Phép toán logic: &&, ||, ! v Các toán tử thao tác trên bit: &, |, ^, >>, <<
(không sử dụng cho số thực)
(kiểu)
v Toán tử chuyển đổi kiểu: v Thứ tự ưu tiên các phép toán
29 9/17/16 Trần Minh Thái - Phạm Đức Thành
Tập các lệnh vào/ ra cơ bản
v string Chuoi=Console.ReadLine(); v char kytu =char.Parse( Console.ReadLine());
v StreamReader
=
new
sr StreamReader("data.txt");
v string S=sr.ReadLine(); v char kyTu = char.Parse( sr.ReadLine());
30 9/17/16 Trần Minh Thái - Phạm Đức Thành
Tập các lệnh vào/ ra cơ bản
v Console.WriteLine("{0}", Chuoi); v Console.WriteLine("{0}", kytu);
v StreamWriter
=
new
sw StreamWriter("data.txt");
v sw.WriteLine("{0}", S); v sw.WriteLine("{0}", kyTu);
31 9/17/16 Trần Minh Thái - Phạm Đức Thành
Thao tác trên KDL có cấu trúc
v Thao tác trên chuỗi v Thao tác trên file v Thao tác trên cấu trúc
32 9/17/16 Trần Minh Thái - Phạm Đức Thành
Thao tác trên chuỗi
v int index=S.IndexOf(kyTu); v int index=S.IndexOf(Chuoi); v int kq= S1.CompareTo (S); v S1 = S; v S1 = S1 +" "+S; v S1= S1.ToLower(); v S1 = S1.ToUpper(); v int len = S1.Length;
33 9/17/16 Trần Minh Thái - Phạm Đức Thành
Thao tác trên file
v StreamReader sr; v StreamWriter sw; v sr = new StreamReader("data_input.txt"); v sw = new StreamWriter("data_out.txt"); v sr.Close(); v sw.Close(); v string S = sr.ReadLine(); v sw.WriteLine(S); v if(sr == null) { } v if (sw == null) { }
34 9/17/16 Trần Minh Thái - Phạm Đức Thành
Thao tác trên KDL cấu trúc
public double
public char
Struct_Name strN; strN.thuocTinh_1 = 5; strN.thuocTinh_2 = 6; strN.thuocTinh_3 = 'a';
struct Struct_Name { public int thuocTinh_1; thuocTinh_2; thuocTinh_3; } Struct_Name strN1 = strN;
35 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nguyên lý địa phương
v Cá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ục
v Tên các biến trong danh sách đối số của hàm
đều là hình thức
v Các biến khai báo bên trong hàm đều là các
biến cục bộ
v 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ụ
36 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nguyên lý an toàn
v Lỗi cú pháp: (design time) v Lỗi cảnh báo (warning) v Lỗi khi chạy chương trình (run time error)
37 9/17/16 Trần Minh Thái - Phạm Đức Thành
Lỗi cú pháp: (design time)
v Khi viết chương trình v Ví dụ:
Ø Sai từ khóa Ø Sai cú pháp về cấu trúc lệnh, biểu thức Ø Thiếu các dấu ngoặc, dấu chấm phẩy khi
kết thúc lệnh
Ø Chưa khai báo nguyên mẫu hàm
(prototype)
38 9/17/16 Trần Minh Thái - Phạm Đức Thành
Lỗi cảnh báo (warning)
v Khi viết chương trình v Thường là khi ta khai báo biến mà không sử
dụng
v Khai báo biến mà không khởi gán giá trị v Lỗi do thứ tự ưu tiên phép toán
39 9/17/16 Trần Minh Thái - Phạm Đức Thành
Lỗi khi chạy chương trình
v Compiler không thể phát hiện lỗi này v Người lập trình gây ra khi thiết kế CT, xử lý
dữ liệu
v Phải testing mới phát hiện được v Phải chứng minh được tính đúng đắn của CT v Khô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)
40 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nguyên lý nhất quán
v Dữ liệu thao tác thế ấy v Cấu trúc dữ liệu thao tác trên đó v 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ác
v Một biến thuộc: Kiểu dữ liệu xác định
Ø Kiểu cơ bản Ø Kiểu do người dùng tự định nghĩa
41 9/17/16 Trần Minh Thái - Phạm Đức Thành
Nguyên lý nhất quán
v Thao 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 đó
v 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 nhau
v Kiể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ụng
42 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.5] Phương pháp phân tích & thiết kế
v Phương pháp TOP-DOWN v Phương pháp BOTTOM-UP
43 9/17/16 Trần Minh Thái - Phạm Đức Thành
Phương pháp TOP-DOWN
v Quá trình phân tích bài toán được thực hiện
từ trên xuống.
v Từ vấn đề chung nhất đến cụ thể nhất. v Từ trừu tượng tổng quan đến đơn giản nhất là đơn vị chương trình (module – đơn thể)
44 9/17/16 Trần Minh Thái - Phạm Đức Thành
Phương pháp TOP-DOWN
45 9/17/16 Trần Minh Thái - Phạm Đức Thành
Phương pháp BOTTOM-UP
v Đi từ chi tiết cụ thể riêng biệt đến phần
chung nhất cao hơn.
v Từ các modul tới tổng thể chương trình. v 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.
v Bottom-up thường được sử dụng trong quá
trình cài đặt, viết chương trình.
46 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.6] Tóm tắt
v Ngô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ó
v 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)
v 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àm
47 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.6] Tóm tắt
v Nguyên lý nhất quán: dữ liệu nào, thì phép
toán đó.
v 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.
v Phân rã từ vấn đề lớn thành các module nhỏ
gọi là top-down.
v 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.
48 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.7] Bài tập
v Bà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;
v Bài 2: VCT nhập vào số tự nhiên n. In ra dãy
số Fibonaci nhỏ hơn n.
v Trong đó:
Ø
Ø
F0 = F1 = 1; Fn = Fn-1 + Fn-2
49 9/17/16 Trần Minh Thái - Phạm Đức Thành
[1.7] Bài tập
v Bà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.
v 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.
v 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).
50 9/17/16 Trần Minh Thái - Phạm Đức Thành
![C++ File IO: Thư Viện và Ứng Dụng Thực Tế [Hướng Dẫn Chi Tiết]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251013/oursky06/135x160/39851768932654.jpg)
![Bài giảng Phân tích thiết kế và đánh giá thuật toán Trường ĐH Hàng Hải [Mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250909/oursky06/135x160/58071768925368.jpg)
