Bài giảng Nhập môn lập trình - Chương 2: Thuật toán - Nguyễn Minh Huy
Thuꢀt toán
GV. Nguyꢀn Minh Huy
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
1
Nꢃi dung
ꢀ Khái niꢄm thuꢁt toán.
ꢀ Biꢅu diꢀn thuꢁt toán.
ꢀ Đánh giá thuꢁt toán.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
2
Nꢃi dung
ꢀ Khái niꢁm thuꢀt toán.
ꢀ Biꢅu diꢀn thuꢁt toán.
ꢀ Đánh giá thuꢁt toán.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
3
Khái niꢄm thuꢁt toán
ꢀ Thuꢁt toán là gì?
ꢀ Bài toán 1:
ꢁ Tính tꢆng sꢇ lꢈn nhꢉt và sꢇ nhꢊ nhꢉt giꢋa 7, 1, 9?
ꢀ Nhꢁn xét:
ꢁ Có nhiꢌu cách giꢍi bài toán khác nhau.
ꢁ Các cách giꢍi khác nhau có hiꢄu quꢍ khác nhau.
ꢀ Thuꢁt toán:
ꢁ Cách giꢍi cꢎ thꢅ mꢃt bài toán.
ꢁ Các bưꢈc đꢅ đi đꢏn kꢏt quꢍ sau cùng.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
4
Khái niꢄm thuꢁt toán
ꢀ Đꢐc trưng cꢑa thuꢁt toán:
ꢀ Có nhiꢌu thuꢁt toán cho mꢃt bài toán.
ꢀ Thuꢁt toán quyꢏt đꢒnh hiꢄu quꢍ lꢓi giꢍi.
ꢀ Thuꢁt toán ~ thuꢁt giꢍi.
ꢀ Các tính chꢉt cꢑa thuꢁt toán:
ꢁ Tính chính xác (correctness).
ꢁ Tính tꢆng quát (abstraction).
ꢁ Tính dꢔng (halting).
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
5
Khái niꢄm thuꢁt toán
ꢀ Nhꢋng lꢄnh cơ bꢍn:
ꢀ Máy tính hiꢅu nhꢋng lꢄnh cơ bꢍn:
ꢁ Lꢄnh nhꢁp, xuꢉt.
ꢁ Lꢄnh tính toán sꢇ hꢕc: +, ꢂ, *, /, %, =.
ꢁ Lꢄnh kiꢅm tra điꢌu kiꢄn: >, <, >=, <=, ==, !=.
ꢁ Lꢄnh nhꢍy bưꢈc.
ꢀ Khái niꢄm lꢁp trình:
ꢁ Sꢖ dꢎng nhꢋng lꢄnh cơ bꢍn.
ꢁ Lꢗp ghép theo mꢃt thuꢁt toán.
ꢁ Giꢍi quyꢏt đưꢘc bài toán.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
6
Nꢃi dung
ꢀ Khái niꢄm thuꢁt toán.
ꢀ Biꢂu diꢃn thuꢀt toán.
ꢀ Đánh giá thuꢁt toán.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
7
Biꢅu diꢀn thuꢁt toán
ꢀ Biꢅu diꢀn bꢙng mã giꢍ (pseudo code):
ꢀ Dùng ngôn ngꢋ tꢚ nhiên.
ꢀ Đơn giꢍn hơn ngôn ngꢋ lꢁp trình.
ꢀ Các ký hiꢄu cho lꢄnh cơ bꢍn:
ꢂB1: Nhꢀp a, b, c.
ꢂB2: Xuꢅt b.
Nhꢁp/Xuꢉt
Nhꢁp/Xuꢉt
ꢂB1: b = 5.
ꢂB2: a = a + b.
Tính toán sꢇ hꢕc
Kiꢅm tra điꢌu kiꢄn
Nhꢍy bưꢈc
+, ꢂ, *, /, %, =
ꢂB1: a = a + b.
ꢂB2: Nꢆu a > 5 Xuꢉt “lꢈn hơn”
Ngưꢇc lꢈi Xuꢉt “nhꢊ hơn”.
Nꢏu <điꢌu kiꢄn> ꢛ
Ngưꢘc lꢜi ꢛ
ꢂB1: a = a + b.
ꢂB2: Nꢆu a < 100 Chuyꢆn đꢆn B1.
Chuyꢅn đꢏn<bưꢈc>
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
8
Biꢅu diꢀn thuꢁt toán
ꢀ Biꢅu diꢀn thuꢁt toán bꢙng mã giꢍ:
* Thuꢁt toán tìm sꢇ lꢈn nhꢉt:
ꢂB1: Nhꢀp a, b, c.
* Thuꢁt toán tính giai thꢔa N:
ꢂB1: Nhꢀp N.
ꢂB2: S = 1.
ꢂB2: max = a.
max = b.
S = S * N.
N = N – 1.
Chuyꢅn đꢏn B3.
Ngưꢇc lꢈi chuyꢅn đꢏn B4.
ꢂB4: Nꢆu c > max
max = c.
ꢂB5: Xuꢅt max.
ꢂB4: Xuꢅt S.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
9
Biꢅu diꢀn thuꢁt toán
ꢀ Biꢅu diꢀn bꢙng lưu đꢝ (flow chart):
ꢀ Dùng hình vꢞ biꢅu diꢀn thuꢁt toán.
ꢀ Trꢚc quan, dꢀ nꢗm bꢗt.
ꢀ Các ký hiꢄu cho các lꢄnh cơ bꢍn:
Nhꢁp/Xuꢉt
Nhꢁp a, b, c
Xuꢉt x, y
Tính toán sꢇ hꢕc
a = a + b
a > 5
Kiꢅm tra điꢌu kiꢄn
Nhꢍy bưꢈc
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
10
Biꢅu diꢀn thuꢁt toán
ꢀ Biꢅu diꢀn thuꢁt toán bꢙng lưu đꢝ:
Nhꢁp a, b, c
max = a
Nhꢁp N
S = 1
đúng
đúng
sai
b > max
sai
max = b
max = c
N > 1
đúng
S = S * N
c > max
sai
N = N ꢂ 1
Xuꢉt max
Xuꢉt S
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
11
Biꢅu diꢀn thuꢁt toán
ꢀ Chꢜy tꢔng bưꢈc thuꢁt toán:
ꢀ Kiꢅm tra tính chính xác.
ꢀ Lꢐp bꢍng theo dõi các giá trꢒ.
Dòng lꢁnh
Nhꢁp N
N
S
3
S = 1
1
3
N = 3 > 1
S = S * N
N = N ꢂ 1
2
1
N = 2 > 1
S = S * N
N = N ꢂ 1
6
6
N = 1 = 1
Xuꢉt S
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
12
Nꢃi dung
ꢀ Khái niꢄm thuꢁt toán.
ꢀ Biꢅu diꢀn thuꢁt toán.
ꢀ Đánh giá thuꢀt toán.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
13
Đánh giá thuꢁt toán
ꢀ Các tiêu chí đánh giá:
ꢀ Thꢓi gian thꢚc hiꢄn:
ꢁ Tùy thuꢃc sꢇ bưꢈc thuꢁt toán.
ꢁ Sꢇ bưꢈc tùy thuꢃc đꢃ lꢈn dꢋ liꢄu.
ꢁ Đꢜi lương “O lꢈn”:
ꢁ Tương quan giꢋa đꢃ lꢈn dꢋ liꢄu và sꢇ bưꢈc thꢚc hiꢄn.
ꢀ Dung lưꢘng bꢃ nhꢈ:
ꢁ Tùy thuꢃc sꢇ lưꢘng ký hiꢄu sꢖ dꢎng.
ꢁ Dung lưꢘng ~ thꢓi gian.
ꢀ Mꢟc đꢃ dꢀ hiꢅu.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
14
Đánh giá thuꢁt toán
ꢀ Đꢃ phꢟc tꢜp cꢑa các thuꢁt toán:
Thuꢀt toán
Đꢉ phꢊc tꢈp
Dꢈng
Hꢙng sꢇ
Tuyꢏn tính
Tìm sꢇ lꢈn nhꢉt (3 sꢇ)
Tính giai thꢔa N
O(K)
O(n)
Sꢗp xꢏp dãy sꢇ
(N phꢠn tꢖ)
Bubblesort: O(n2)
Quicksort: O(n*log(n))
Đa thꢟc
Ngưꢓi đưa thư
(N thành phꢇ)
O(Kn)
O(n!)
Phi tuyꢏn
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
15
Tóm tꢗt
ꢀ Thuꢁt toán:
ꢀ Các bưꢈc đưa đꢏn kꢏt quꢍ bài toán.
ꢀ Bài toán có nhiꢌu thuꢁt toán vꢈi hiꢄu quꢍ khác nhau.
ꢀ Tính chꢉt: chính xác, phꢆ quát, dꢔng.
ꢀ Mã giꢍ: dùng ngôn ngꢋ tꢚ nhiên.
ꢀ Lưu đꢝ: dùng hình vꢞ.
ꢀ Đánh giá thuꢁt toán:
ꢀ Thꢓi gian thꢚc hiꢄn
ꢂ Đꢃ phꢟc tꢜp thuꢁt toán.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
16
Bài tꢁp
ꢀ Bài tꢁp 2.1:
Xây dꢚng thuꢁt toán tính tuꢆi cꢑa mꢃt ngưꢓi như sau:
ꢂ Nhꢁp vào năm sinh.
ꢂ Tính tuꢆi hiꢄn tꢜi và xuꢉt kꢏt quꢍ.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
17
Bài tꢁp
ꢀ Bài tꢁp 2.2:
Xây dꢚng thuꢁt toán tính nút bꢍng sꢇ xe như sau:
ꢂ Nhꢁp vào sꢇ cꢑa bꢍng sꢇ xe (mꢃt sꢇ có 4 chꢋ sꢇ).
ꢂ Tính và xuꢉt sꢇ nút.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
18
Bài tꢁp
ꢀ Bài tꢁp 2.3:
Xây dꢚng thuꢁt toán mô phꢊng máy tính tay như sau:
ꢂ Nhꢁp vào 2 sꢇ nguyên.
ꢂ Nhꢁp vào phép tính (+, ꢂ, *, /).
ꢂ Thꢚc hiꢄn phép tính vꢔa nhꢁp trên 2 sꢇ nguyên và xuꢉt kꢏt quꢍ.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
19
Bài tꢁp
ꢀ Bài tꢁp 2.4:
Xây dꢚng thuꢁt toán xꢏp loꢜi cho hꢕc sinh như sau:
ꢂ Nhꢁp vào điꢅm văn, toán, ngoꢜi ngꢋ.
ꢂ Tính điꢅm trung bình (văn, toán hꢄ sꢇ 2).
ꢂ Xꢏp loꢜi cho hꢕc sinh như sau:
+ Khá: ĐTB >= 6.5.
+ Trung bình: ĐTB >= 5.0.
+ Yꢏu: ĐTB < 5.0.
ꢂ Xuꢉt điꢅm trung bình và kꢏt quꢍ xꢏp loꢜi.
Nhꢁp môn lꢁp trình ꢂ Nguyꢀn Minh Huy
20
Tải về để xem bản đầy đủ
24 trang
22800
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn lập trình - Chương 2: Thuật toán - Nguyễn Minh Huy", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_nhap_mon_lap_trinh_chuong_2_thuat_toan_nguyen_minh.pdf
