Algorithm with C++ - Công nghệ Website | Đại học Bách Khoa, Đại học Đà Nẵng

Algorithm with C++ - Công nghệ Website | Đại học Bách Khoa, Đại học Đà Nẵng giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học

35 18 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Công nghệ Web (CNWEB1)

Trường: Trường Đại học Bách khoa, Đại học Đà Nẵng

Thông tin:

146 trang 6 tháng trước

Tác giả:

Profile Kim Oanh
Algorithm with C++
1
MỤC LỤC
MỤC LỤC ............................................................................................................ 1
PHẦN I – ĐẶT V ẤN ĐỀ ................................................................................... 11
PHẦN II – NỘI DUNG NGHIÊN CỨU .......................................................... 13
2.1. CÀI ĐẶT WEBSITE LAPTRINHPHOTHONG.VN .................................. 13
2.1.1. Gi i thi u v laptrinhphothong.vn ớ ệ ề ............................................................ 13
2.1.2. Hƣớng dẫn sử d ng cho qu n tr viên ụ ả ị ....................................................... 14
2.1.2.1. Nh p n i dung bài t p mậ ộ ậ ới ..................................................................... 14
2.1.2.2. Nh p các test case c a bài t p ậ ủ ậ ................................................................ 15
2.1.2.3. Ki m tra l c khi publish ể ại trƣớ ................................................................ 15
2.1.3. Hƣớng dẫn sử d i dùng ụng cho ngƣờ ......................................................... 16
2.1.2.1. Đăng ký sử dụng ....................................................................................16
2.1.2.2. Đăng nhập và gi i bài ả ............................................................................. 17
2.2. XÂY D NG H NG BÀI T P Ự Ệ THỐ Ậ .......................................................... 19
2.2.1. Các nguyên t c xây dắ ựng .......................................................................... 19
2.2.2. Các bƣớc xây d ựng.................................................................................... 21
CHƢƠNG 1 – CÁC KHÁI NIỆM CƠ BẢN CỦA C++ .................................... 24
A. KI N TH C GHI NH Ế Ứ Ớ ............................................................................. 24
1. Khung chƣơng trình của C++ ...................................................................... 24
2. Các l nh vào ra ệ ............................................................................................. 24
B. CÁC VÍ DỤ MẪU ...................................................................................... 24
C. BÀI TẬP ÁP D ỤNG................................................................................... 25
Bài 1.1 (N0101A) p xu t – Nhậ ấ ..................................................................... 25
Bài 1.2 (N0102A) Tính toán 1 – ................................................................... 25
Bài 1.3 (N0103A) Tính toán 2 – ................................................................... 26
Bài 1.4 (N0104A) Tính toán 3 – ................................................................... 26
Bài 1.5 (N0105A) Tính toán 4 – ................................................................... 26
Bài 1.6 (N0106A) Tính toán 5 – ................................................................... 26
Bài 1.7 (N0107B) – Căn n ............................................................................ 27
Bài 1.8 (N0108B) n n – Tổng 1 đế ................................................................ 27
Bài 1.9 (N0109B) ng các s l – Tổ ố ẻ .............................................................. 27
Bài 1.10 (N0110B) – Tổng bình phƣơng ...................................................... 27
Algorithm with C++
2
Bài 1.11 (N0111A Chia l y nguyên - – ) ấ dƣ.................................................. 28
Bài 1.12 (N0112A) n sau n t c – Liề – liề rƣớ .................................................. 28
Bài 1.13 (N0113A) n nguyên n l– Phầ – phầ ẻ ............................................... 28
Bài 1.14 (N0114B) Phép chia – .................................................................... 28
Bài 1.15 (N0115C) h p – Tổ ợ ........................................................................ 29
Bài 1.16 (N0116B) Mã ASCII – ................................................................... 29
Bài 1.17 (N0117C) nh h p – Chỉ ợ ................................................................... 29
Bài 1.18 (N0118C) m 1 – Giao điể ................................................................ 30
Bài 1.19 (N0119C) m 2 – Giao điể ................................................................ 30
Bài 1.20 (N0120C) m 3 – Giao điể ................................................................ 30
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ .................................................. 30
Bài 1.5 (N0105A) Tính toán 4 – ................................................................... 30
Bài 1.7 (N0107B) – Căn n ............................................................................ 31
Bài 1.9 (N0109B) ng l – Tổ ẻ ......................................................................... 31
Bài 1.10 (N0110B) – Tổng bình phƣơng ...................................................... 31
Bài 1.11 (N0111B) Chia l y nguyên - – ấ dƣ.................................................. 31
Bài 1.13 (N0113A) n nguyên n l– Phầ – phầ ẻ ............................................... 32
Bài 1.14 (N0114B) Phép chia – .................................................................... 32
Bài 1.15 (N0115C) h p – Tổ ợ ........................................................................ 32
Bài 1.17 (N0117C) nh h p – Chỉ ợ ................................................................... 32
Bài 1.18 (N0118C) m 1 – Giao điể ................................................................ 33
CHƢƠNG 2 - CẤU TRÚC R NHÁNH Ẽ ........................................................... 34
A. KI N TH C GHI NH Ế Ứ Ớ ............................................................................. 34
1. C u trúc r nhánh if ấ ẽ ...................................................................................... 34
2. C u trúc r nhánh if else ấ ẽ .............................................................................. 34
3. C u trúc switch ấ ............................................................................................. 34
B. CÁC VÍ DỤ MẪU ...................................................................................... 34
C. BÀI TẬP ÁP D ỤNG................................................................................... 36
Bài 2.1 (N0201A) n l – Chẵ ẻ ......................................................................... 36
Bài 2.2 (N0202A) Chia h t – ế ......................................................................... 36
Bài 2.3 (N0203B) n – Năm nhuậ .................................................................... 36
Bài 2.4 (N0204A) l– Số ớn hơn 1 .................................................................. 36
Algorithm with C++
3
Bài 2.5 (N0205B) l– Số ớn hơn 2 ................................................................. 37
Bài 2.6 (N0206A) – Số chính phƣơng .......................................................... 37
Bài 2.7 (N0207A) Ba c nh tam giác – ạ .......................................................... 37
Bài 2.8 (N0208A)– Phƣơng trình bậc hai ..................................................... 37
Bài 2.9 (N0209A) t 1 – Số nhỏ nhấ ................................................................ 38
Bài 2.10 (N0210A) t 2 – Số nhỏ nhấ .............................................................. 38
Bài 2.11 (N0211B) m th ng hàng – Ba điể ẳ .....................................................38
Bài 2.12 (N0212B) Chia h t cho 3 – ế ............................................................. 39
Bài 2.13 (N0213B) nhì – Số nhỏ .................................................................. 39
Bài 2.14 (N0214B) Quy t c chia – ắ ............................................................... 39
Bài 2.15 (N0215A) ng nhau – Bằ .................................................................. 39
Bài 2.16 (N0216D) Ngày sinh – ................................................................... 40
Bài 2.17 (N0217C) – Nhiều tu ổi hơn............................................................ 40
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ .................................................. 40
Bài 2.3 (N0203B) n – Năm nhuậ .................................................................... 40
Bài 2.5 (N0205A) l– Số ớn hơn 2 ................................................................. 41
Bài 2.6 (N0206A) – Số chính phƣơng .......................................................... 41
Bài 2.8 (N0208A)– Phƣơng trình bậc hai ..................................................... 41
Bài 2.11 (N0211B) m th ng hàng – Ba điể ẳ .....................................................42
Bài 2.16 (N0216C) Ngày sinh – ................................................................... 42
CHƢƠNG 3 - CẤU TRÚC VÒNG LẶP ............................................................ 44
A. KI N TH C GHI NH Ế Ứ Ớ ............................................................................. 44
1. C u trúc vòng l p for ấ ặ ................................................................................... 44
2. C u trúc vòng l p while ấ ặ ............................................................................... 44
3. C u trúc vòng l p do while ấ ặ .......................................................................... 44
B. CÁC VÍ DỤ MẪU ...................................................................................... 44
C. BÀI TẬP ÁP D ỤNG................................................................................... 46
Bài 3.1 (N0301A) u sao – Dấ ........................................................................ 46
Bài 3.1 (N0302A) t nhiên – Số ự ................................................................... 46
Bài 3.2 (N0303A) – Dấu thăng ..................................................................... 46
Bài 3.3 (N0304A) – Dấu đô la...................................................................... 47
Bài 3.4 (N0305B) không – Số ....................................................................... 47
Algorithm with C++
4
Bài 3.5 (N0306B) Giai th a – ừ ....................................................................... 47
Bài 3.6 (N0307C) dãy nh phân – Số ị ............................................................ 48
Bài 3.7 (N0308B) Dãy s 1 – ố ....................................................................... 48
Bài 3.8 (N0309C) Dãy s 2 – ố ....................................................................... 48
Bài 3.9 (N0310C) ng giai th a – Tổ ừ .............................................................. 48
Bài 3.10 (N0311B) ng ký t – Bả ự.................................................................. 49
Bài 3.12 (N0312A) T– ổng mũ bốn ................................................................. 49
Bài 3.13 (N0313B) T– ổng mũ ba ...................................................................49
Bài 3.14 (N0314B) Hình vuông d u $ – ấ .......................................................... 50
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ .................................................. 50
Bài 3.3 (N0303A) – Dấu đô la...................................................................... 50
Bài 3.5 ( N0305B) Giai th a – ừ ...................................................................... 50
Bài 3.6 (N0306C) dãy nh phân – Số ị ............................................................ 51
Bài 3.8 (N0308C) Dãy s 2 – ố ....................................................................... 51
Bài 3.9 (N0309C) ng giai th a – Tổ ừ .............................................................. 52
CHƢƠNG 4 – KIỂU DỮ U M NG M T CHI U LIỆ Ả Ộ Ề ..................................... 53
A. KI N TH C GHI NH Ế Ứ Ớ ............................................................................. 53
1. Khai báo mảng ............................................................................................. 53
2. Cách s dử ụng ................................................................................................ 53
B. CÁC VÍ DỤ MẪU ...................................................................................... 53
C. BÀI TẬP ÁP D ỤNG................................................................................... 54
Bài 4.1 (N0401A) Giá tr t – ị nhỏ nhấ ............................................................... 54
Bài 4.2 (N0402A) T ng m– ổ ảng ...................................................................... 55
Bài 4.3 (N0403A) T ng l – ổ ẻ ............................................................................ 55
Bài 4.4 (N0404B) Giá tr l n nh t – ị ớ ấ ................................................................ 55
Bài 4.5 (N0405B) Giá tr l – ị ẻ nhỏ nhất ............................................................ 56
Bài 4.6 (N0406A) Giá tr chia h t cho 3 – ị ế ....................................................... 56
Bài 4.7 (N0407A) T ng tr tuy i – ổ ị ệt đố ............................................................ 56
Bài 4.8 (N0408A) Các s không nh – ố ỏ hơn X................................................. 57
Bài 4.9 (N0409A) S n – ố thuộc đoạ .................................................................. 57
Bài 4.10 (N0410B) S – ố chính phƣơng ........................................................... 57
Bài 4.11 – (N0411B) Đếm ngh ch th ị ế ............................................................. 58
Algorithm with C++
5
Bài 4.12 (N0412B) S p x p – ắ ế .......................................................................... 58
Bài 4.13 (N0413B) T– ổng bình phƣơng ......................................................... 59
Bài 4.14 (N0414C) Quicksort – ....................................................................... 59
Bài 4.15 (N0415B) S l n xu t hi n nhi u nh t – ố ầ ấ ệ ề ấ ........................................... 59
Bài 4.16 (N0416A) Chia h t cho 3 – ế ............................................................... 60
Bài 4.17 (N0417B) Ký t t hi n nhi u nh t – ự xuấ ệ ề ấ ............................................ 60
Bài 4.18 (N0418B) Chia h t 3 và 5 – ế ............................................................... 60
Bài 4.19 (N0419B) Giá tr n k – ị nhỏ nhất đế .................................................... 61
Bài 4.20 (N0420C) Tr n m– ộ ảng ..................................................................... 61
Bài 4.21 (N0421D) Ph n t trung v – ầ ử ị............................................................. 62
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ .................................................. 62
Bài 4.5 (N0405A) Giá tr l – ị ẻ nh nhỏ ất ........................................................... 62
Bài 4.8 (N0408A) Các s không nh – ố ỏ hơn X................................................. 63
Bài 4.11 – (N0411B) Đếm ngh ch th ị ế ............................................................. 63
Bài 4.14 (N0414B) Quicksort – ....................................................................... 64
Bài 4.17 (N0417B) Ký t t hi n nhi u nh t – ự xuấ ệ ề ấ ............................................ 64
Bài 4.19 (N0419B) Giá tr n k – ị nhỏ nhất đế .................................................... 65
Bài 4.20 (N0420C) Tr n m– ộ ảng ..................................................................... 65
Bài 4.21 (N0421D) Ph n t trung v – ầ ử ị............................................................. 65
CHƢƠNG 5 – KIỂU DỮ U M NG HAI CHI U LIỆ Ả Ề ....................................... 67
A. KI N TH C GHI NH Ế Ứ Ớ ............................................................................. 67
1. Khái ni m ma tr n ệ ậ ........................................................................................ 67
2. Khai báo mảng hai chiều .............................................................................. 67
3. Cách s dử ụng ................................................................................................ 67
B. CÁC VÍ DỤ MẪU ...................................................................................... 68
C. BÀI TẬP ÁP D ỤNG................................................................................... 69
Bài 5.1 (N0501A) In ma tr n – ậ ........................................................................ 69
Bài 5.2 (N0502A) T ng trên ma tr n – ổ ậ ............................................................ 69
Bài 5.3 (N0503B) Hàng có t ng l n nh t – ổ ớ ấ ..................................................... 70
Bài 5.4 (N0504B) C t có t ng l n nh t – ộ ổ ớ ấ ........................................................ 70
Bài 5.5 (N0505A) Giá tr – ị chẵn l n nh t ớ ấ ........................................................ 71
Bài 5.6 (N0506A) T– ổng trên đƣờng chéo chính ........................................... 71
Algorithm with C++
6
Bài 5.7 (N0507B) T ng chéo ph – ổng trên đƣờ ụ .............................................. 71
Bài 5.8 (N0508C) T ng trên biên ma tr n – ổ ậ .................................................... 72
Bài 5.9 (N0509A) T ng hai ma tr n – ổ ậ ............................................................. 72
Bài 5.10 (N0510B) Tích hai ma tr n – ậ ............................................................ 73
Bài 5.11 (N0511C) T ng các b ng vuông – ổ ả .................................................... 74
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ .................................................. 74
Bài 5.3 (N0503B) Hàng có t– ổng lớn nhất ..................................................... 74
Bài 5.8 (N0508B) T ng trên biên ma tr n – ổ ậ .................................................... 75
Bài 5.10 (N0510B) Tích hai ma tr n – ậ ............................................................ 75
Bài 5.11 (N0511C) T ng các b ng vuông – ổ ả .................................................... 76
CHƢƠNG 6 – KIỂU DỮ U XÂU KÝ T LIỆ Ự................................................... 78
A. KI N TH C GHI NH Ế Ứ Ớ ............................................................................. 78
1. Hai ki u xâu trong C++ ể ................................................................................ 78
2. Khai báo và s dử ụng ..................................................................................... 78
3. Các phép toán và hàm thành viên ................................................................ 78
B. CÁC VÍ DỤ MẪU ...................................................................................... 78
C. BÀI TẬP ÁP D ỤNG................................................................................... 80
Bài 6.1 (N0601A dài xâu – ) Độ ....................................................................... 80
Bài 6.2 – (N0602A) Đếm ký tự ........................................................................ 80
Bài 6.3 (N0603A) Ký t hoa – ự ......................................................................... 80
Bài 6.4 (N0604A) Ký t s – ự ố........................................................................... 80
Bài 6.5 – (N0605B) Xâu đối xứng ................................................................... 81
Bài 6.6 (N0606B) T ng ch s – ổ ữ ố..................................................................... 81
Bài 6.7 – (N0607B) Đếm số từ ....................................................................... 81
Bài 6.8 (N0608B) Lo i b s – ạ ỏ chữ ố................................................................ 81
Bài 6.9 (N0609B) S ký t phân bi t – ố ự ệ .......................................................... 82
Bài 6.10 (N0610C) Mã hóa 1 – ....................................................................... 82
Bài 6.11 (N0611C) Mã hóa 2 – ....................................................................... 82
Bài 6.12 (N0612D) Mã hóa 3 – ...................................................................... 83
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ .................................................. 83
Bài 6.6 (N0606B) T ng ch s – ổ ữ ố..................................................................... 83
Bài 6.7 – (N0607B) Đếm số từ ....................................................................... 84
Algorithm with C++
7
Bài 6.9 (N0609C) S ký t phân bi t – ố ự ệ .......................................................... 84
Bài 6.10 (N0610C) Mã hóa 1 – ....................................................................... 85
Bài 6.11 (N0611C) Mã hóa 2 – ....................................................................... 85
CHƢƠNG 7 - KIỂU D U T N Ữ LIỆ ỆP VĂN BẢ ............................................... 87
A. KI N TH C GHI NH Ế Ứ Ớ ............................................................................. 87
1. L ng b t p và vào ra chu n ệnh đồ ộ ệ ẩ ............................................................... 87
2. T n trong C++ v n fstream ệp văn bả ới thƣ việ ............................................... 87
B. CÁC VÍ DỤ MẪU ...................................................................................... 87
C. BÀI TẬP ÁP D ỤNG................................................................................... 88
Bài 7.1 (N0701A) S – ố âm............................................................................... 88
Bài 7.2 (N0702B) Min max ra hai file – ......................................................... 89
Bài 7.3 (N0703B) S p x p d u ngoài – ắ ế ữ liệ ..................................................... 89
Bài 7.4 – (N0703B) Đọc file không bi t s ế ố lƣợng .......................................... 90
CHƢƠNG 8 - HÀM VÀ C U TRÚC HÀM Ấ .................................................... 91
A. KI N TH C GHI NH Ế Ứ Ớ ............................................................................. 91
1. C u trúc r nhánh if ấ ẽ ...................................................................................... 91
2. C u trúc r nhánh if else ấ ẽ .............................................................................. 91
3. C u trúc switch ấ ............................................................................................. 92
B. CÁC VÍ DỤ MẪU ...................................................................................... 93
C. BÀI TẬP ÁP D ỤNG................................................................................... 97
Bài 8.1 (N0801A) T ng các ch s – ổ ữ ố .............................................................. 97
Bài 8.2 (N0802A) T ng ch s chia h t cho 9 – ổ ữ ố ế ............................................ 98
Bài 8.3 – (N0803A) Đếm ƣớc chung lớn nh t ấ ................................................ 98
Bài 8.4 – (N0804A) Đếm bội chung nh t ỏ nhấ ................................................ 98
Bài 8.5 (N0805A) S c chia h t cho 7 – ố ƣớ ế ..................................................... 99
Bài 8.6 (N0806A) B i chung t ng ch s – ộ ổ ữ ố ................................................... 99
Bài 8.7 (N0807B) Nguyên t l n nh t – ố ớ ấ ......................................................... 99
Bài 8.8 (N0808B) Nguyên t t – ố nhỏ nhấ ...................................................... 100
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ ................................................ 100
Bài 8.1 (N0801A) T ng các ch s – ổ ữ ố ............................................................ 100
Bài 8.3 – (N0803A) Đếm ƣớc chung lớn nh t ấ .............................................. 100
Bài 8.5 (N0805A) S c chia h t cho 7 – ố ƣớ ế ................................................... 101
Algorithm with C++
8
Bài 8.7 (N0807B) Nguyên t l n nh t – ố ớ ấ ....................................................... 101
CHƢƠNG 9 – KIỂU DỮ U STRUCT LIỆ ....................................................... 103
A. KI ẾN THỨC GHI NH Ớ....................................................................... 103
1. Khai báo ..................................................................................................... 103
2. S d ng ki u struct ử ụ ể ..................................................................................... 103
B. CÁC VÍ DỤ MẪU 104....................................................................................
C. BÀI TẬP ÁP D ỤNG................................................................................. 106
Bài 9.1 (N0901A) Hình bình hành – .............................................................. 106
Bài 9.2 (N0902A) Di n tích hình bình hành – ệ .............................................. 106
Bài 9.3 (N0903B) Di– ện tích đa giác lồi ..................................................... 106
Bài 9.4 (N0904C) Danh sách h c sinh 107– ọ .......................................................
Bài 9.5 (N0905B) C u th – ầ ủ trẻ t nhấ ............................................................ 107
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ ................................................ 108
Bài 9.2 (N0902A) Di n tích hình bình hành – ệ .............................................. 108
Bài 9.3 (N0903B) Di– ện tích đa giác lồi ..................................................... 108
Bài 9.4 (N0904C) Danh sách h c sinh 109– ọ .......................................................
CHƢƠNG 10 – MỘT S THU T TOÁN S H N Ố Ậ Ố ỌC CƠ BẢ ....................... 110
A. KI N TH C GHI NH Ế Ứ Ớ ........................................................................... 110
1. Thu t toán tìm UCLN, BCNN ậ ................................................................... 110
2. Thu t toán ki m tra s nguyên tậ ể ố ố ............................................................... 111
3. Gi i thu t sàng nguyên t 112ả ậ ố...........................................................................
B. CÁC VÍ DỤ MẪU 112....................................................................................
C. BÀI TẬP ÁP D ỤNG................................................................................. 114
Bài 10.1 (N1001A) S – ố lƣợng s nguyên t ố ố ................................................ 114
Bài 10.2 (N1002B) S nguyên t n – ố ố trong đoạ ............................................ 114
Bài 10.3 (N1003B) S c bi t – ố đặ ệ .................................................................. 114
Bài 10.4 (N1004C) S bin bon 115– ố ..................................................................
Bài 10.5 (N1005B) S nguyên t fibonacci – ố ố ............................................... 115
Bài 10.6 – (N1006A) Cơ số k ....................................................................... 115
Bài 10.7 – (N1007B) Ƣớc ............................................................................. 116
Bài 10.8 (N1008B) S a s nguyên t – ố thừ ố ố.................................................. 116
Bài 10.9 (N1009C) S siêu nguyên t – ố ố ....................................................... 116
Algorithm with C++
9
Bài 10.10 (N1010D) S supper nguyên t – ố ố................................................. 117
Bài 10.11 – (N1011E) Định đề Bertrand ...................................................... 117
Bài 10.12 (N1012E) Li t kê s siêu nguyên t – ệ ố ố.......................................... 118
Bài 10.13 (N1013E) T ng ph n nguyên – ổ ầ .................................................... 118
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ ................................................ 118
Bài 10.2 (N1002B) S nguyên t n – ố ố trong đoạ ............................................ 118
Bài 10.3 (N1003B) S c bi t – ố đặ ệ .................................................................. 119
Bài 10.4 (N1004C) S bin bon 119– ố ..................................................................
Bài 10.5 (N1005B) S nguyên t fibonacci – ố ố ............................................... 120
Bài 10.7 – (N1007B) Ƣớc ............................................................................. 121
Bài 10.8 1008B) S a s nguyên t – (N ố thừ ố ố.................................................. 122
Bài 10.9 (N1009B) S siêu nguyên t – ố ố ....................................................... 122
Bài 10.10 (N1010D) S supper nguyên t – ố ố................................................. 123
Bài 10.11 – (N1011E) Định đề Bertrand ...................................................... 123
Bài 10.12 (N1012E) Li t kê s siêu nguyên t – ệ ố ố.......................................... 124
Bài 10.13 (N1013E) T ng ph n nguyên – ổ ầ .................................................... 125
CHƢƠNG 11 – ĐỆ QUY ................................................................................. 127
A. KI ẾN THỨC GHI NH Ớ....................................................................... 127
1. Khái niệm đệ quy ....................................................................................... 127
2. Ví d minh h a ụ ọ ........................................................................................... 127
3. M t s ng dộ ố ứ ụng c quy ủa đệ ...................................................................... 128
B. CÁC VÍ DỤ MẪU 129....................................................................................
C. BÀI TẬP ÁP D ỤNG................................................................................. 132
Bài 11.1 (N1101A) S t p con – ố ậ .................................................................... 132
Bài 11.2 (N1102A) Li t kê nh phân – ệ ị .......................................................... 132
Bài 11.3 (N1103A) Li t kê tam phân – ệ .......................................................... 132
Bài 11.4 (N1104B) Li t kê ch nh h p – ệ ỉ ợ ......................................................... 133
Bài 11.5 (N1105C) Li t kê ch nh h p t p A – ệ ỉ ợ ậ ............................................... 133
Bài 11.6 (N1106B) Li t kê t h– ệ ổ ợp .............................................................. 134
Bài 11.7 (N1107C) Li t kê t h– ệ ổ ợp t p A 134ậ .....................................................
Bài 11.8 (N1108B) Li t kê xâu ký t – ệ ự AB................................................... 135
Bài 11.9 (N1109D) Li t kê xâu h p l 135– ệ ợ ệ........................................................
Algorithm with C++
10
Bài 11.10 (N1110E) Li t kê xâu con – ệ .......................................................... 135
Bài 11.11 (N1111D) S – ố mũ 1 ...................................................................... 136
Bài 11.12 (N1112E) S – ố mũ 2 ..................................................................... 136
Bài 11.13 (N1113E) S – ố mũ 3 ..................................................................... 136
Bài 11.14 (N1114E) Quân h u – ậ ................................................................... 136
D. HƢỚNG D N GI I M T SẪ Ả Ộ Ố BÀI T P Ậ ................................................ 137
Bài 11.4 (N1104B) Li t kê ch nh h p – ệ ỉ ợ ......................................................... 137
Bài 11.5 (N1105B) Li t kê ch– ệ ỉnh h p t p A ợ ậ .............................................. 137
Bài 11.6 (N1105B) Li t kê t h– ệ ổ ợp .............................................................. 138
Bài 11.8 (N1108C) Li t kê xâu ký t – ệ ự AB................................................... 139
Bài 11.9 (N1109D) Li t kê xâu h p l 140– ệ ợ ệ........................................................
Bài 11.10 (N1110E) Li t kê xâu con – ệ .......................................................... 141
Bài 11.11 (N1111D) S – ố mũ 1 .................................................................... 141
Bài 11.12 (N1112E) S – ố mũ 2 ..................................................................... 142
Bài 11.13 (N1113E) S – ố mũ 3 ..................................................................... 143
Bài 11.14 (N1114E) Quân h u – ậ ................................................................... 143
KẾT LU N Ậ ....................................................................................................... 145
TÀI LIỆU THAM KH O Ả ................................................................................. 146
Algorithm with C++
11
PHẦ ĐẶN I – T VẤN ĐỀ
1.1. Lý do ch tài ọn đề
Theo Chƣơng trình giáo dục phổ thông 2018 đƣợc B Giáo dộ ục và Đào
tạo ban hành kèm 32/2018/TT-Thông tƣ số BGDĐT ngày 26/12/2018, môn Tin
học có tri t lý c t lõi t o ra mế ố ạ ột th h m ng công ngh trong ế ệ ới có tƣ duy áp dụ ệ
gi nhả ựi quyết các vấn đề th c tế. Vì vậy, ữ ứng kiến th c về phần gi i thu t và lả ậ ập
trình đóng vai trò rấ ọng trong chƣơng trình tin họt quan tr c ở bậc THPT.
Hiện t i ch c d y h c Tin h ng THCS và THPT ạ ất lƣợng việ ạ ọ ọc ở nhà trƣờ
trong c c nói chung, t nh Ngh An nói riêng còn mả nƣớ ỉ ệ ở ức độ tuy đã khá thấp,
đƣợc chú trọng, song giáo viên còn htrình độ ạn chế, việc tìm tòi ki n th c còn ế ứ
gặp nhi liên t i m công ngh nói chung và b ều khó khăn trong xu thế ục đổ ới ệ ộ
môn Tin h c nói riêng. L p trình là m t ph n r t quan tr ng trong n i dung ọ ậ ộ ầ ấ ọ ộ
chƣơng trình bộ ội dung chƣơng trình Giáo dụ môn Tin học hiện tại và cả n c phổ
thông 2018, là m ch ki n th c quan tr ng nh t trong 3 m ch ki n th c c a Tin ạ ế ứ ọ ấ ạ ế ứ ủ
học bao gồm: CS, ICT, DL.
Hiện t n l p trình trong SGK Tin h n minh h a b ại phầ ậ ọc cơ bả đang ọ ằng
ngôn ng lữ ập trình Pascal. Đây là ngôn ngữ có nhi ch s phát ều đóng góp trong lị ử
triển c a Tin h c th i. Tuy nhiên, vủ ọ ế giớ ới xu th phát triế ển của th i 4.0, ngôn ời đạ
ngữ Pascal không còn đƣợc hỗ trợ nhi u và chính th c b Tề ứ ị ổ chức Olympic Tin
học Quốc t l ng ph ế đƣa ra ngoài danh sách ngôn ngữ ập trình trong nhà trƣờ ổ
thông t ừ năm 2020.
Trƣớ ầ ậc nhu c u học t p của h giáo dọc sinh theo chƣơng trình ục phổ thông
2018 và h giáo viên có công c ng d y t t nh p môn l p trình, chúng tôi ỗ trợ ụ giả ạ ố ậ ậ
thi
ết kế “Hệ thống giải bài trực tuyến nh p môn l p trình v i Cậ ậ ớ
++
” với từng
chƣơng và bài t p v n d ng t n cao theo h các ậ ậ ụ ừ thấp đế ệ thống đánh giá Bloom.
1.2. Mục đích nghiên cứu
Nghiên c u m t s vứ ộ ố ấn đề khó khăn gặp phải khi giảng dạy lập trình trong
nhà trƣờ thông và đƣa ra giảng phổ i pháp xây dựng một hệ thống bài tập và một
công c E-ụ learning đi kèm.
Nghiên c u h (2001) t o ra h ng bài tứ ệ thống đánh giá Bloom ừ đó tạ ệ thố ập
phân lo i theo 6 m c: ạ ứ Nhớ, Hi u, V n dể ậ ụng, Phân tích, á, Sáng tĐánh gi ạo.
Algorithm with C++
12
1.3. Nhi m v nghiên c u ệ ụ ứ
Chúng tôi xây d ng là m t h ự ộ ệ thố ọ ậng h c t p Elearning bao gồm:
- Website JUDGE có ch m bài tức năng có thể chấ ự động, kiểm tra đánh
giá, h h c t p cho h c sinh, h giáo viên so n bài gi ng môn l p trình ỗ trợ ọ ậ ọ ỗ trợ ạ ả ậ
một cách d dàng, gi m thi ng tính hễ ả ểu khó khăn cho giáo viên, tăng cƣờ ợp tác,
thi đua trong việc dạy và học môn l p trình. ậ
- H ng bài t p nh
ệ thố ậ ập môn C v i nhi u ví d n l
++
ớ ề ụ chọ ọc và phân loại các
mức nh n biậ ết theo thang đánh giá Bloom.
1.4. Các phƣơng pháp nghiên cứu chính
- Nghiên c u lý luứ ận: Chúng tôi xem xét cách phân chia các mức độ nhận
thức theo thang Bloom v n d ng trong vi c phân lo i h ng bài t để ậ ụ ệ ạ ệ thố ập.
- u tra, quan sát: c tr ng v tình hình d y và h c l p trình trong Điề Thự ạ ề ạ ọ ậ
nhà trƣờng phổ thông.
- T ng k t kinh nghi T ng h p kinh nghi m d y và h c c a b n thân, ổ ế ệm: ổ ợ ệ ạ ọ ủ ả
đồ ệng nghi p, học sinh trong quá trình d y h c nh p môn l p trình. ạ ọ ậ ậ
Algorithm with C++
13
PHẦN II – N I DUNG NGHIÊN C U Ộ Ứ
2.1. T WEBSITE LAPTRINHPHOTHONG.VN CÀI ĐẶ
Trong ph d ng n n t ng c a NTUCoder xây d ng ần này chúng tôi đã sử ụ ề ả ủ ự
nên m t trang web d ng JUDGE có chộ ạ – ức năng chấm bài tự động với nhiều loại
ngôn ng ữ khác nhau nhƣ: C, C++, Python2, Python3 – đây là các ngôn ngữ đƣợc
chƣơng trình 2018 khuyến khích sử dụng.
2.1.1. i thi u v laptrinhphothong.vn Giớ ệ ề
Từ phía ngƣời dùng giao diện của laptrinhphothong.vn bao g m các ồ
menu: Trang ch , Bài t p, K thi, H ng ch m bài, Bài vi t, ủ ậ ỳ ỏi & đáp, Bả ấ ế
Chaxbox.
Ngƣời dùng có th làm bài t p thông qua chể đăng ký để ậ ức năng đăng ký.
Các ch n d s d ng. Khi vào menu bài t p, ức năng của trang đều đơn giả ễ ử ụ ậ
sẽ hiển th h ị ệ thống bài t p. Click vào các bài t p cậ ậ ụ thể ta s có n i dung và qua ẽ ộ
đó sử dụng ch i bài và n p bài: ức năng giả ạ
Algorithm with C++
14
Hệ thống bao g m m t máy chồ ộ ấm đƣợc cài đặt trên server online. Ngƣời
sử d ng có th n p bài b t c m nào khi có k t n i internet. ụ ể ạ ấ ứ thời điể ế ố
2.1.2. ng d n s d cho qu n tr viên Hƣớ ẫ ử ụng ả ị
Để p có th s d ng: đăng nhậ ể ử ụ
Tài kho n: ả hieptt@nghean.edu.vn 0983713301 - M t kh u: ậ ẩ
2.1.2.1. p n i dung bài t p mNhậ ộ ậ ới
Các n i dung c n nh ộ ầ ập:
Mã bài t p: duy nh t trong toàn b danh sách bài t p. ậ ấ ộ ậ
Tên bài t p: Mô t tên c a bài tậ ả ủ ập.
Giới h n th i gian và b : có th t l p th i gian và b cạ ờ ộ nhớ ể thiế ậ ờ ộ nhớ ần
dùng cho chƣơng trình.
Nội dung bài t p: Phát bi u bài toán. ậ ể
Giải thích ví d : ph n xu t hiụ ầ ấ ện bên dƣới ví dụ.
TestType: có 2 d ạng
o Output Matching: So sánh k t qu c a user v i k t quế ả ủ ớ ế ả đáp án,
đƣợc áp d ng khi k t qu ụ ế ả đáp án là duy nhất.
o Verify Output: áp d ng khi có nhi n viụ ều đáp án, lúc này cầ ết
chƣơng trình chấ ức đọ ủa user đểm test, t c kết quả c kiểm tra.
Trong trƣờng hợp này cần nhập thêm TestCompiler (trình biên
dịch code chấm test) và Code ch m test. ấ
ReviewCoder: m i m t ProblemSetter khác tham gia xem l i bài này. ờ ộ ạ
Ngƣời đƣợ ửa đƣợc mời chỉ có thể xem và test thử, không s c bài tập.
Nếu không mời ngƣời review thì để trống.
Published: Check vào thì bài t p m i xu t hi n cho user th ậ ớ ấ ệ ấy.
Algorithm with C++
15
2.1.2.2. p các test case c a bài t p Nhậ ủ ậ
Nhấn nút Thêm mới để đƣa vào testcase mớ i.
- Sample test: là test case s n th khi user xem bài t p. ẽ hiể ị ậ
- PreTest: hi n tệ ại chƣa sử dụng
2.1.2.3. m tra l c khi publish Kiể ại trƣớ
Algorithm with C++
16
Xem trước: Chọn nút cái kính lúp , gi ng xem ống nhƣ là user bình thƣờ
một bài tập, k c ể ả bài này chƣa đƣợc publish
Chạy test trước: Chọn nút 2 bánh xe :
2.1.3. Hƣớng dẫn s d ng i dùng ử ụ cho ngƣờ
2.1.2.1. Đăng ký sử dụng
Chức năng đăng ký sử dụng nằm ở góc phải trên của website. Sau khi
click vào ô đăng ký, website sẽ cho ta khung đăng ký sau:
Algorithm with C++
17
Sau khi nh p tên tài khoậ ản (user), đặt password, email thì m ng dột đƣờ ẫn
kích ho t s g i dùng qua tài kho n email. Vi dàng ạ ẽ ửi cho ngƣờ ả ệc đăng ký là dễ
đối v i s d ng. ới ngƣờ ử ụ
2.1.2.2. Đăng nhập và gi i bài ả
Sau khi đăng nhập ngƣờ ức năng chatbox, nại dùng có thể sử dụng các ch p
bài, comment trên các bài vi t. C n gi i bài n m trong menu bài tế ụ thể phầ ả ằ ập nhƣ
sau:
Để ả ế gi i bài t và tiập nào ngƣời dùng click vào mã bài đó, đọc đề n hành
giải bài.
Ngƣời dùng có thể giải bài trên CodeBlock r i copy mã ngu n n p lên ồ ồ ạ
trang nhƣ sau:
Click vào menu N p bài, s n th ộ ẽ hiể ị ra ô TextBox để nạp mã ngu ồn:
Algorithm with C++
18
Ngƣời dùng có thể sao chép mã ngu n và dán tr c ti p vào ô so n thồ ự ế ạ ảo
của website, hoặc có th bể upload file chƣơng trình từ ộ nhớ ngoài c a máy tính. ủ
Sau đó click vào nút Nộp bài và chờ kết qu v ả trả ề.
Trình ch m c a website s v các k t qu sau: ấ ủ ẽ trả ề ế ả
- Accepted: bài làm đúng tất cả các test.
- Wrong answer: có một test cho kết quả sai.
- Runtime error: lỗi chạy chƣơng trình (tràn mảng, chia cho 0, exit code
khác 0...).
- Time limit exceed: chạy quá giới hạn thời gian của bài tập.
- Memory limit exceed: chạy quá giới hạn bộ nhớ của bài tập.
- Output size limit exceed: xuất kết quả quá lớn.
- Compilation error: Biên dịch lỗi.
Ngƣờ ử ế ỉ ại s dụng thông qua k t quả chấm có thể điều ch nh l i code của
mình và ti p t c n i bài. ế ụ ạp để giả
Algorithm with C++
19
2.2. XÂY DỰNG HỆ NG BÀI T P THỐ Ậ
2.2.1. Các nguyên t c xây d ắ ựng
Thang đo Bloom ấp độ tƣ duy đƣợvề các c c Benjamin Bloom, một giáo
sƣ của trƣờng Đạ đƣa ra vào năm . Trong đó Bloom có nêu i học Chicago, 1956
ra sáu c n th c (g v i sáu m n thấp độ nhậ ứ ọi là thang đo Bloom) ớ ức độ nhậ ức
tƣơng ứng là: Bi t, Hi u, Vế ể ận d ng, Phân tích, T ng hụ ổ ợp, Đánh giá. Thang đo
này đã đƣợ ụng trong hơn năm thậ qua đã khẳng đị ƣu điểc sử d p kỷ nh m của
phƣơng pháp dạy học nhằm khuy n khích và phát tri n các kế ể ỹ năng tƣ duy của
ngƣờ ọ ỹi h c ở m n sức độ cao. Sau đó vào năm 2001, tiế Lorin Anderson cùng
với các c ng s (2001) phân chia sáu cộ ự đƣa ra Thang đánh giá Bloom ấp độ nhận
thức nhƣ sau: Nhớ (Remmember), Hi u (Understand), V n d (Apply), Phân ể ậ ụng
tích (Analyze) (Evaluate), Sáng t o (Create). Hi n t i, , Đánh giá ạ ệ ạ đây là một
thang đo các cấp độ ức đƣợ nhận th c sử dụng phổ biến trong nghiên cứu về giáo
dục trên th ế giới.
Mức độ
Ý nghĩa
Hành động
A – Nhớ
Nhớ thông tin
Xác định, mô tả, gọi tên, phân
loại.
B – u Hiể
Hiểu nghĩa, diễn giải khái
niệm
Tóm t t, bi i, gi i thích. ắ ến đổ ả
C – V n d ậ ụng
Sử dụng thông tin hay khái
niệm trong tình hu ng mố ới
Thiết l p, thậ ực hiện, tạo dựng,
mô ph ng, d n b ỏ ự đoán, chuẩ ị
lập k ế hoạch.
D – Phân tích
Chia nh thông tin và khái ỏ
niệm thành nh ng ph n nh ữ ầ ỏ
So sánh, đối chiếu, phân chia,
phân bi t, l a ch n, phân tích ệ ự ọ
Algorithm with C++
20
hơn để ểu đầy đủ hi hơn.
E – Đánh giá
Đánh giá vấn đề năng , khả
phán xét giá tr , quy . ị ết định
Đánh giá, phê bình, phán đoán
chứng minh, tranh lu n, bi n h . ậ ệ ộ
F – Sáng t o ạ
Tạo ra cái m i tớ ừ thông tin
đã có.
Tập hợp, sáng t o, xây dạ ựng,
phát minh, ch t o, lên kế ạ ế
hoạch.
Cụ thể các mức độ nhận thức trong sáu cấp độ ở sơ đồ trên đƣợc hiểu chi
tiết hơn nhƣ sau:
Cấp độ 1: Nhớ (remember)
Ở đây, nhớ là khả năng ghi nhớ và nhận diện thông tin. Nhớ là cần thiết
cho tất các mức độ tƣ duy đƣợc hiểu là nhớ lại những kiến thức đã học một cả và
cách máy móc và nhắc lại.
Để đánh giá mức độ nhớ của ngƣời học khi xây dựng hệ thống câu hỏi, ,
chúng tôi đƣa vào nhóm các bài tập nhắc lại một hoặc hai câu lệnh trong vùng
kiến thức đang đƣợc học.
Cấp độ 2: Hiểu (understand)
Hiểu là khả năng hiểu, diễn dịch, diễn giải, giải thích hoặc suy diễn (dự
đoán đƣợc kết quả hoặc hậu quả). Hiểu không đơn thuần là nhắc lại cái gì đó,
ngƣời học phải có khả năng diễn đạt khái niệm theo ý hiểu của họ.
Với mục đích đánh giá xem ngƣời học hiểu bài đến đâu, chúng tôi đƣa ra
các bài tập vẫn là sử dụng câu lệnh nhƣng đƣợc biến tấu cho những tình huốngít
đòi hỏi phải thay đổi một vài tham số để chƣơng trình hoạt động .
Cấp độ 3: Vận dụng (appy)
Vận dụng là khả năng sử dụng thông tin và chuyển đổi kiến thức từ dạng
này sang dạng khác (sử dụng những kiến thức đã học trong hoàn cảnh mới). Vận
dụng là bắt đầu của mức tƣ duy sáng tạo, tức là vận dụng những gì đã học vào
đời sống hoặc một tình huống mới.
Để đánh giá khả năng vận dụng của ngƣời học ôi phát biểu bài , chúng t
toán có xem lẫn các dữ kiện cần mô hình hóa toán học trƣớc khi lập trình.
Cấp độ 4: Phân tích (analysis)
Phân tích là khả năng nhận biết chi tiết, phát hiện và phân biệt các bộ
phận cấu thành của thông tin hay tình huống. Ở mức độ này đòi hỏi khả năng
Algorithm with C++
21
phân nhỏ đối tƣợng thành các hợp phần cấu thành để hiểu rõ hơn cấu trúc của
nó.
Muốn đánh giá khả năng phân tích của ngƣời học chúng tôi đƣa ra các ,
bài tập cần sử dụng khả năng phân tích độ phức tạp của thuật toán. Với các bài
tập dạng này với mục đích giúp ngƣời học có chúng tôi chia thành các sub –
đƣợc cách phân tích các thuật toán khác nhau để giải bài tập đó.
Cấp độ 5 Đánh giá: (evaluate)
Đánh giá là khả năng phán xét giá trị hoặc sử dụng thông tin theo các tiêu
chí thích hợp ỗ trợ đánh giá bằng lý do/lập luận). Để sử dụng đúng mức độ (h
này, ngƣời học phải có khả năng giải thích tại sao sử dụng những lập luận giá trị
để bảo vệ quan điểm.
Ở cấp độ này chúng tôi đƣa ra các bài tập đƣợc phát biểu ở dƣới nhiều
phƣơng diện khác nhau, ngƣời học cần biết tổng hợp nhiều vùng kiến thức để
đƣa ra chiến lƣợc giải quyết vấn đề một cách hiệu quả
Cấp độ 6 Sáng tạo (create: )
Sáng tạo là khả năng hợp nhất các thành phần để tạo thành một tổng
thể/sự vật lớn và trên cơ sở đó tạo ra những sự vật mới. Ở mức độ này ngƣời học
phải sử dụng những gì đã học để tạo ra hoặc sáng tạo một cái gì đó hoàn toàn
mới.
Với mức độ này, chúng tôi xây dựng các mô hình contest, ngƣời học có
thể tham gia xây dựng bài tập, sáng tạo đề thi ên cạnh đó xây dựng . B chúng tôi
các group , thảo luận sau khi kết thúc contest. Vì vậy trong hệ thống bài tập
chúng tôi thiết kế sẽ chỉ có 5 mức độ. Mức độ thứ sáu sẽ là mức độ tùy biến
trong giảng dạy của giáo viên và ngƣời học dựa trên các contest.
2.2.2. Các bƣớc xây dựng
Bƣớc 1 Xác định mục đích của hệ thống bài tập.
-
Mục đích xây dựng hệ thống bài tập nhập môn lập trình với C nhằm
++
giúp ngƣời học tiếp cận bộ môn lập trình thuật toán với ngôn ngữ lập
trình C++ theo thang đo Bloom (2001) .
- Tạo ra một sân chơi trí tuệ cho bộ môn lập trình thuật toán.
Bƣớc 2 Xác định nội dung hệ thống bài tập.
- Hệ thống lại các kiến thức cơ bản trong từng chƣơng
Algorithm with C++
22
-
Xây dựng hệ thống bài tập nhập môn lập trình với ngôn ngữ C
++
bao
gồm 11 chƣơng với các kiến thức từ nền tảng đến nâng cao.
Bƣớc 3 Xác định loại bài tập, các kiểu bài tập.
- Hệ thống bài tập xây dựng trong đề tài là các bài tập nhập môn lập
trình, nghĩa là phải phủ hết toàn bộ kiến thức cơ bản của ngôn ngữ C
++
.
- Trên cơ sở thang đo Bloom, chúng tôi phân loại bài tập trong mỗi
chƣơng theo 5 mức độ và đƣợc ký hiệu theo thứ tự A – Hiểu, Nhớ, B –
C – Vận dụng, D – Đánh giá Phân tích, E – .
Bƣớc 4 Thu thập thông tin để soạn hệ thống bài tập.
- Thu thập các sách bài tập, tài liệu liên quan đến hệ thống bài tập cần
xây dựng; tham khảo sách, báo, tạp chí… có liên quan.
-
Tìm trên trang web hiểu, nghiên cứu về các version mới nhất của C
++
chính thức http://cplusplus.com/.
- Số tài liệu thu thập đƣợc càng nhiều và càng đa dạng thì việc biên soạn
càng nhanh chóng và có chất lƣợng, hiệu quả. Vì vậy, cần tổ chức sƣu
tầm tƣ liệu một cách khoa học.
Bƣớc 5 Tiến hành soạn thảo bài tập.
- Xây dựng dàn ý các dạng bài tập theo từng chƣơng.
- Lồng ghép các nội dung thuật toán đi kèm kiến thức về ngôn ngữ.
- Phân dạng bài tập theo 5 mức độ A, B, C, D, E.
Bƣớc 6 Tham khảo, trao đổi ý kiến với đồng nghiệp.
- Sau khi xây dựng xong các bài tập, giáo viên tham khảo ý kiến các
đồng nghiệp về tính chính xác, khoa học và tính vừa sức với trình độ
của học sinh.
- Thảo luận trên các diễn đàn để đánh giá về mức độ tƣ duy của hệ
thống bài tập.
Bƣớc 7 Thực nghiệm, chỉnh sửa và bổ sung.
- Để khẳng định lại mục đích của hệ thống bài tập là nhằm củng cố kiến
thức và phát triển tƣ duy sáng tạo cho học sinh, giáo viên trao đổi với
các giáo viên thực nghiệm về khả năng nắm vững kiến thức và phát
triển năng lực vận dụng cho học sinh thông qua hoạt động giải các bài
tập.
- Bổ sung thêm các bài tập mới trong quá trình giảng dạy.
| 1/146
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Algorithm with C++ MỤC LỤC
MỤC LỤC ............................................................................................................ 1
PHẦN I – ĐẶT VẤN ĐỀ ................................................................................... 11
PHẦN II – NỘI DUNG NGHIÊN CỨU .......................................................... 13
2.1. CÀI ĐẶT WEBSITE LAPTRINHPHOTHONG.VN .................................. 13
2.1.1. Giới thiệu về laptrinhphothong.vn ............................................................ 13
2.1.2. Hƣớng dẫn sử dụng cho quản trị viên ....................................................... 14
2.1.2.1. Nhập nội dung bài tập mới ..................................................................... 14
2.1.2.2. Nhập các test case của bài tập ................................................................ 15
2.1.2.3. Kiểm tra lại trƣớc khi publish ................................................................ 15
2.1.3. Hƣớng dẫn sử dụng cho ngƣời dùng ......................................................... 16
2.1.2.1. Đăng ký sử dụng ................................................................................... .16
2.1.2.2. Đăng nhập và giải bài ............................................................................. 17
2.2. XÂY DỰNG HỆ THỐNG BÀI TẬP ......................................................... .19
2.2.1. Các nguyên tắc xây dựng .......................................................................... 19
2.2.2. Các bƣớc xây dựng .................................................................................... 21
CHƢƠNG 1 – CÁC KHÁI NIỆM CƠ BẢN CỦA C++ .................................... 24
A. KIẾN THỨC GHI NHỚ ............................................................................. 24
1. Khung chƣơng trình của C++ ...................................................................... 24
2. Các lệnh vào ra ............................................................................................. 24
B. CÁC VÍ DỤ MẪU ..................................................................................... .24 C. BÀI TẬP ÁP DỤN
G................................................................................... 25
Bài 1.1 – (N0101A) Nhập xuất ..................................................................... 25
Bài 1.2 – (N0102A) Tính toán 1 ................................................................... 25
Bài 1.3 – (N0103A) Tính toán 2 ................................................................... 26
Bài 1.4 – (N0104A) Tính toán 3 ................................................................... 26
Bài 1.5 – (N0105A) Tính toán 4 ................................................................... 26
Bài 1.6 – (N0106A) Tính toán 5 ................................................................... 26
Bài 1.7 – (N0107B) Căn n ............................................................................ 27
Bài 1.8 – (N0108B) Tổng 1 đến n ................................................................ 27
Bài 1.9 – (N0109B) Tổng các số lẻ .............................................................. 27
Bài 1.10 – (N0110B) Tổng bình phƣơng ...................................................... 27 1 Algorithm with C++
Bài 1.11 – (N0111A) Chia lấy nguyên - dƣ .................................................. 28
Bài 1.12 – (N0112A) Liền sau – liền trƣớc .................................................. 28
Bài 1.13 – (N0113A) Phần nguyên – phần lẻ ............................................... 28
Bài 1.14 – (N0114B) Phép chia .................................................................... 28
Bài 1.15 – (N0115C) Tổ hợp ........................................................................ 29
Bài 1.16 – (N0116B) Mã ASCII ................................................................... 29
Bài 1.17 – (N0117C) Chỉnh hợp ................................................................... 29
Bài 1.18 – (N0118C) Giao điểm 1 ................................................................ 30
Bài 1.19 – (N0119C) Giao điểm 2 ................................................................ 30
Bài 1.20 – (N0120C) Giao điểm 3 ................................................................ 30
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP .................................................. 30
Bài 1.5 – (N0105A) Tính toán 4 ................................................................... 30
Bài 1.7 – (N0107B) Căn n ............................................................................ 31
Bài 1.9 – (N0109B) Tổng lẻ ......................................................................... 31
Bài 1.10 – (N0110B) Tổng bình phƣơng ...................................................... 31
Bài 1.11 – (N0111B) Chia lấy nguyên - dƣ .................................................. 31
Bài 1.13 – (N0113A) Phần nguyên – phần lẻ ............................................... 32
Bài 1.14 – (N0114B) Phép chia .................................................................... 32
Bài 1.15 – (N0115C) Tổ hợp ........................................................................ 32
Bài 1.17 – (N0117C) Chỉnh hợp ................................................................... 32
Bài 1.18 – (N0118C) Giao điểm 1 ................................................................ 33
CHƢƠNG 2 - CẤU TRÚC RẼ NHÁNH ........................................................... 34
A. KIẾN THỨC GHI NHỚ ............................................................................. 34
1. Cấu trúc rẽ nhánh if ...................................................................................... 34
2. Cấu trúc rẽ nhánh if else .............................................................................. 34
3. Cấu trúc switch ............................................................................................. 34
B. CÁC VÍ DỤ MẪU ..................................................................................... .34 C. BÀI TẬP ÁP DỤN
G................................................................................... 36
Bài 2.1 – (N0201A) Chẵn lẻ ......................................................................... 36
Bài 2.2 – (N0202A) Chia hết ......................................................................... 36
Bài 2.3 – (N0203B) Năm nhuận .................................................................... 36
Bài 2.4 – (N0204A) Số lớn hơn 1 .................................................................. 36 2 Algorithm with C++
Bài 2.5 – (N0205B) Số lớn hơn 2 ................................................................. 37
Bài 2.6 – (N0206A) Số chính phƣơng .......................................................... 37
Bài 2.7 – (N0207A) Ba cạnh tam giác .......................................................... 37
Bài 2.8 – (N0208A) Phƣơng trình bậc hai ..................................................... 37
Bài 2.9 – (N0209A) Số nhỏ nhất 1 ................................................................ 38
Bài 2.10 – (N0210A) Số nhỏ nhất 2 .............................................................. 38
Bài 2.11 – (N0211B) Ba điểm thẳng hàng.................................................... .38
Bài 2.12 – (N0212B) Chia hết cho 3 ............................................................ .39
Bài 2.13 – (N0213B) Số nhỏ nhì .................................................................. 39
Bài 2.14 – (N0214B) Quy tắc chia .............................................................. .39
Bài 2.15 – (N0215A) Bằng nhau .................................................................. 39
Bài 2.16 – (N0216D) Ngày sinh ................................................................... 40
Bài 2.17 – (N0217C) Nhiều tuổi hơn ............................................................ 40
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP .................................................. 40
Bài 2.3 – (N0203B) Năm nhuận .................................................................... 40
Bài 2.5 – (N0205A) Số lớn hơn 2 ................................................................. 41
Bài 2.6 – (N0206A) Số chính phƣơng .......................................................... 41
Bài 2.8 – (N0208A) Phƣơng trình bậc hai ..................................................... 41
Bài 2.11 – (N0211B) Ba điểm thẳng hàng.................................................... .42
Bài 2.16 – (N0216C) Ngày sinh ................................................................... 42
CHƢƠNG 3 - CẤU TRÚC VÒNG LẶP ............................................................ 44
A. KIẾN THỨC GHI NHỚ ............................................................................. 44
1. Cấu trúc vòng lặp for ................................................................................... 44
2. Cấu trúc vòng lặp while ............................................................................... 44
3. Cấu trúc vòng lặp do while .......................................................................... 44
B. CÁC VÍ DỤ MẪU ..................................................................................... .44 C. BÀI TẬP ÁP DỤN
G................................................................................... 46
Bài 3.1 – (N0301A) Dấu sao ........................................................................ 46
Bài 3.1 – (N0302A) Số tự nhiên ................................................................... 46
Bài 3.2 – (N0303A) Dấu thăng ..................................................................... 46
Bài 3.3 – (N0304A) Dấu đô la ...................................................................... 47
Bài 3.4 – (N0305B) Số không ....................................................................... 47 3 Algorithm with C++
Bài 3.5 – (N0306B) Giai thừa ....................................................................... 47
Bài 3.6 – (N0307C) Số dãy nhị phân ............................................................ 48
Bài 3.7 – (N0308B) Dãy số 1 ....................................................................... 48
Bài 3.8 – (N0309C) Dãy số 2 ....................................................................... 48
Bài 3.9 – (N0310C) Tổng giai thừa .............................................................. 48
Bài 3.10 – (N0311B) Bảng ký tự .................................................................. 49
Bài 3.12 – (N0312A) Tổng mũ bốn ................................................................. 49
Bài 3.13 – (N0313B) Tổng mũ ba .................................................................. .49
Bài 3.14 – (N0314B) Hình vuông dấu $ .......................................................... 50
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP .................................................. 50
Bài 3.3 – (N0303A) Dấu đô la ...................................................................... 50
Bài 3.5 – ( N0305B) Giai thừa ...................................................................... 50
Bài 3.6 – (N0306C) Số dãy nhị phân ............................................................ 51
Bài 3.8 – (N0308C) Dãy số 2 ....................................................................... 51
Bài 3.9 – (N0309C) Tổng giai thừa .............................................................. 52
CHƢƠNG 4 – KIỂU DỮ LIỆU MẢNG MỘT CHIỀU ..................................... 53
A. KIẾN THỨC GHI NHỚ ............................................................................. 53
1. Khai báo mảng ............................................................................................. 53
2. Cách sử dụng ................................................................................................ 53
B. CÁC VÍ DỤ MẪU ..................................................................................... .53 C. BÀI TẬP ÁP DỤN
G................................................................................... 54
Bài 4.1 – (N0401A) Giá trị nhỏ nhất ............................................................... 54
Bài 4.2 – (N0402A) Tổng mảng ...................................................................... 55
Bài 4.3 – (N0403A) Tổng lẻ ............................................................................ 55
Bài 4.4 – (N0404B) Giá trị lớn nhất ................................................................ 55
Bài 4.5 – (N0405B) Giá trị lẻ nhỏ nhất ............................................................ 56
Bài 4.6 – (N0406A) Giá trị chia hết cho 3 ....................................................... 56
Bài 4.7 – (N0407A) Tổng trị tuyệt đối ............................................................ 56
Bài 4.8 – (N0408A) Các số không nhỏ hơn X ................................................. 57
Bài 4.9 – (N0409A) Số thuộc đoạn .................................................................. 57
Bài 4.10 – (N0410B) Số chính phƣơng ........................................................... 57
Bài 4.11 – (N0411B) Đếm nghịch thế ............................................................. 58 4 Algorithm with C++
Bài 4.12 – (N0412B) Sắp xếp .......................................................................... 58
Bài 4.13 – (N0413B) Tổng bình phƣơng ......................................................... 59
Bài 4.14 – (N0414C) Quicksort ....................................................................... 59
Bài 4.15 – (N0415B) Số lần xuất hiện nhiều nhất ........................................... 59
Bài 4.16 – (N0416A) Chia hết cho 3 ............................................................... 60
Bài 4.17 – (N0417B) Ký tự xuất hiện nhiều nhất ............................................ 60
Bài 4.18 – (N0418B) Chia hết 3 và 5 ............................................................... 60
Bài 4.19 – (N0419B) Giá trị nhỏ nhất đến k .................................................... 61
Bài 4.20 – (N0420C) Trộn mảng ..................................................................... 61
Bài 4.21 – (N0421D) Phần tử trung vị ............................................................. 62
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP .................................................. 62
Bài 4.5 – (N0405A) Giá trị lẻ nhỏ nhất ........................................................... 62
Bài 4.8 – (N0408A) Các số không nhỏ hơn X ................................................. 63
Bài 4.11 – (N0411B) Đếm nghịch thế ............................................................. 63
Bài 4.14 – (N0414B) Quicksort ....................................................................... 64
Bài 4.17 – (N0417B) Ký tự xuất hiện nhiều nhất ............................................ 64
Bài 4.19 – (N0419B) Giá trị nhỏ nhất đến k .................................................... 65
Bài 4.20 – (N0420C) Trộn mảng ..................................................................... 65
Bài 4.21 – (N0421D) Phần tử trung vị ............................................................. 65
CHƢƠNG 5 – KIỂU DỮ LIỆU MẢNG HAI CHIỀU ....................................... 67
A. KIẾN THỨC GHI NHỚ ............................................................................. 67
1. Khái niệm ma trận ........................................................................................ 67
2. Khai báo mảng hai chiều .............................................................................. 67
3. Cách sử dụng ................................................................................................ 67
B. CÁC VÍ DỤ MẪU ..................................................................................... .68 C. BÀI TẬP ÁP DỤN
G................................................................................... 69
Bài 5.1 – (N0501A) In ma trận ........................................................................ 69
Bài 5.2 – (N0502A) Tổng trên ma trận ............................................................ 69
Bài 5.3 – (N0503B) Hàng có tổng lớn nhất ..................................................... 70
Bài 5.4 – (N0504B) Cột có tổng lớn nhất ........................................................ 70
Bài 5.5 – (N0505A) Giá trị chẵn lớn nhất ........................................................ 71
Bài 5.6 – (N0506A) Tổng trên đƣờng chéo chính ........................................... 71 5 Algorithm with C++
Bài 5.7 – (N0507B) Tổng trên đƣờng chéo phụ .............................................. 71
Bài 5.8 – (N0508C) Tổng trên biên ma trận .................................................... 72
Bài 5.9 – (N0509A) Tổng hai ma trận ............................................................. 72
Bài 5.10 – (N0510B) Tích hai ma trận ............................................................ 73
Bài 5.11 – (N0511C) Tổng các bảng vuông .................................................... 74
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP .................................................. 74
Bài 5.3 – (N0503B) Hàng có tổng lớn nhất ..................................................... 74
Bài 5.8 – (N0508B) Tổng trên biên ma trận .................................................... 75
Bài 5.10 – (N0510B) Tích hai ma trận ............................................................ 75
Bài 5.11 – (N0511C) Tổng các bảng vuông .................................................... 76
CHƢƠNG 6 – KIỂU DỮ LIỆU XÂU KÝ TỰ ................................................... 78
A. KIẾN THỨC GHI NHỚ ............................................................................. 78
1. Hai kiểu xâu trong C++ ................................................................................ 78
2. Khai báo và sử dụng ..................................................................................... 78
3. Các phép toán và hàm thành viên ................................................................ 78
B. CÁC VÍ DỤ MẪU ..................................................................................... .78 C. BÀI TẬP ÁP DỤN
G................................................................................... 80
Bài 6.1 – (N0601A) Độ dài xâu ....................................................................... 80
Bài 6.2 – (N0602A) Đếm ký tự ........................................................................ 80
Bài 6.3 – (N0603A) Ký tự hoa ......................................................................... 80
Bài 6.4 – (N0604A) Ký tự số ........................................................................... 80
Bài 6.5 – (N0605B) Xâu đối xứng ................................................................... 81
Bài 6.6 – (N0606B) Tổng chữ số ..................................................................... 81
Bài 6.7 – (N0607B) Đếm số từ ....................................................................... 81
Bài 6.8 – (N0608B) Loại bỏ chữ số ................................................................ 81
Bài 6.9 – (N0609B) Số ký tự phân biệt ......................................................... .82
Bài 6.10 – (N0610C) Mã hóa 1 ....................................................................... 82
Bài 6.11 – (N0611C) Mã hóa 2 ....................................................................... 82
Bài 6.12 – (N0612D) Mã hóa 3 ...................................................................... 83
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP .................................................. 83
Bài 6.6 – (N0606B) Tổng chữ số ..................................................................... 83
Bài 6.7 – (N0607B) Đếm số từ ....................................................................... 84 6 Algorithm with C++
Bài 6.9 – (N0609C) Số ký tự phân biệt ......................................................... .84
Bài 6.10 – (N0610C) Mã hóa 1 ....................................................................... 85
Bài 6.11 – (N0611C) Mã hóa 2 ....................................................................... 85
CHƢƠNG 7 - KIỂU DỮ LIỆU TỆP VĂN BẢN ............................................... 87
A. KIẾN THỨC GHI NHỚ ............................................................................. 87
1. Lệnh đồng bộ tệp và vào ra chuẩn ............................................................... 87
2. Tệp văn bản trong C++ với thƣ viện fstream ............................................... 87
B. CÁC VÍ DỤ MẪU ..................................................................................... .87 C. BÀI TẬP ÁP DỤN
G................................................................................... 88
Bài 7.1 – (N0701A) Số âm ............................................................................... 88
Bài 7.2 – (N0702B) Min max ra hai file ......................................................... 89
Bài 7.3 – (N0703B) Sắp xếp dữ liệu ngoài ..................................................... 89
Bài 7.4 – (N0703B) Đọc file không biết số lƣợng .......................................... 90
CHƢƠNG 8 - HÀM VÀ CẤU TRÚC HÀM .................................................... 91
A. KIẾN THỨC GHI NHỚ ............................................................................. 91
1. Cấu trúc rẽ nhánh if ...................................................................................... 91
2. Cấu trúc rẽ nhánh if else .............................................................................. 91
3. Cấu trúc switch ............................................................................................. 92
B. CÁC VÍ DỤ MẪU ..................................................................................... .93 C. BÀI TẬP ÁP DỤN
G................................................................................... 97
Bài 8.1 – (N0801A) Tổng các chữ số .............................................................. 97
Bài 8.2 – (N0802A) Tổng chữ số chia hết cho 9 ............................................ 98
Bài 8.3 – (N0803A) Đếm ƣớc chung lớn nhất ................................................ 98
Bài 8.4 – (N0804A) Đếm bội chung nhỏ nhất ................................................ 98
Bài 8.5 – (N0805A) Số ƣớc chia hết cho 7 ..................................................... 99
Bài 8.6 – (N0806A) Bội chung tổng chữ số ................................................... 99
Bài 8.7 – (N0807B) Nguyên tố lớn nhất ......................................................... 99
Bài 8.8 – (N0808B) Nguyên tố nhỏ nhất ...................................................... 100
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP ................................................ 100
Bài 8.1 – (N0801A) Tổng các chữ số ............................................................ 100
Bài 8.3 – (N0803A) Đếm ƣớc chung lớn nhất .............................................. 100
Bài 8.5 – (N0805A) Số ƣớc chia hết cho 7 ................................................... 101 7 Algorithm with C++
Bài 8.7 – (N0807B) Nguyên tố lớn nhất ....................................................... 101
CHƢƠNG 9 – KIỂU DỮ LIỆU STRUCT ....................................................... 103 A.
KIẾN THỨC GHI NHỚ ....................................................................... 103
1. Khai báo ..................................................................................................... 103
2. Sử dụng kiểu struct ..................................................................................... 103
B. CÁC VÍ DỤ MẪU ................................................................................... .104 C. BÀI TẬP ÁP DỤN
G................................................................................. 106
Bài 9.1 – (N0901A) Hình bình hành .............................................................. 106
Bài 9.2 – (N0902A) Diện tích hình bình hành .............................................. 106
Bài 9.3 – (N0903B) Diện tích đa giác lồi ..................................................... 106
Bài 9.4 – (N0904C) Danh sách học sinh...................................................... .107
Bài 9.5 – (N0905B) Cầu thủ trẻ nhất ............................................................ 107
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP ................................................ 108
Bài 9.2 – (N0902A) Diện tích hình bình hành .............................................. 108
Bài 9.3 – (N0903B) Diện tích đa giác lồi ..................................................... 108
Bài 9.4 – (N0904C) Danh sách học sinh...................................................... .109
CHƢƠNG 10 – MỘT SỐ THUẬT TOÁN SỐ HỌC CƠ BẢN ....................... 110
A. KIẾN THỨC GHI NHỚ ........................................................................... 110
1. Thuật toán tìm UCLN, BCNN ................................................................... 110
2. Thuật toán kiểm tra số nguyên tố ............................................................... 111
3. Giải thuật sàng nguyên tố.......................................................................... .112
B. CÁC VÍ DỤ MẪU ................................................................................... .112 C. BÀI TẬP ÁP DỤN
G................................................................................. 114
Bài 10.1 – (N1001A) Số lƣợng số nguyên tố ................................................ 114
Bài 10.2 – (N1002B) Số nguyên tố trong đoạn ............................................ 114
Bài 10.3 – (N1003B) Số đặc biệt .................................................................. 114
Bài 10.4 – (N1004C) Số bin bon ................................................................. .115
Bài 10.5 – (N1005B) Số nguyên tố fibonacci ............................................... 115
Bài 10.6 – (N1006A) Cơ số k ....................................................................... 115
Bài 10.7 – (N1007B) Ƣớc ............................................................................. 116
Bài 10.8 – (N1008B) Số thừa số nguyên tố .................................................. 116
Bài 10.9 – (N1009C) Số siêu nguyên tố ....................................................... 116 8 Algorithm with C++
Bài 10.10 – (N1010D) Số supper nguyên tố ................................................. 117
Bài 10.11 – (N1011E) Định đề Bertrand ...................................................... 117
Bài 10.12 – (N1012E) Liệt kê số siêu nguyên tố .......................................... 118
Bài 10.13 – (N1013E) Tổng phần nguyên .................................................... 118
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP ................................................ 118
Bài 10.2 – (N1002B) Số nguyên tố trong đoạn ............................................ 118
Bài 10.3 – (N1003B) Số đặc biệt .................................................................. 119
Bài 10.4 – (N1004C) Số bin bon ................................................................. .119
Bài 10.5 – (N1005B) Số nguyên tố fibonacci ............................................... 120
Bài 10.7 – (N1007B) Ƣớc ............................................................................. 121
Bài 10.8 – (N1008B) Số thừa số nguyên tố .................................................. 122
Bài 10.9 – (N1009B) Số siêu nguyên tố ....................................................... 122
Bài 10.10 – (N1010D) Số supper nguyên tố ................................................. 123
Bài 10.11 – (N1011E) Định đề Bertrand ...................................................... 123
Bài 10.12 – (N1012E) Liệt kê số siêu nguyên tố .......................................... 124
Bài 10.13 – (N1013E) Tổng phần nguyên .................................................... 125 CHƢƠNG 11 – ĐỆ QU
Y ................................................................................. 127 A.
KIẾN THỨC GHI NHỚ ....................................................................... 127
1. Khái niệm đệ quy ....................................................................................... 127
2. Ví dụ minh họa ........................................................................................... 127
3. Một số ứng dụng của đệ quy ...................................................................... 128
B. CÁC VÍ DỤ MẪU ................................................................................... .129 C. BÀI TẬP ÁP DỤN
G................................................................................. 132
Bài 11.1 – (N1101A) Số tập con .................................................................... 132
Bài 11.2 – (N1102A) Liệt kê nhị phân .......................................................... 132
Bài 11.3 – (N1103A) Liệt kê tam phân .......................................................... 132
Bài 11.4 – (N1104B) Liệt kê chỉnh hợp ......................................................... 133
Bài 11.5 – (N1105C) Liệt kê chỉnh hợp tập A ............................................... 133
Bài 11.6 – (N1106B) Liệt kê tổ hợp .............................................................. 134
Bài 11.7 – (N1107C) Liệt kê tổ hợp tập A.................................................... .134
Bài 11.8 – (N1108B) Liệt kê xâu ký tự A
B................................................... 135
Bài 11.9 – (N1109D) Liệt kê xâu hợp lệ....................................................... .135 9 Algorithm with C++
Bài 11.10 – (N1110E) Liệt kê xâu con .......................................................... 135
Bài 11.11– (N1111D) Số mũ 1 ...................................................................... 136
Bài 11.12 – (N1112E) Số mũ 2 ..................................................................... 136
Bài 11.13 – (N1113E) Số mũ 3 ..................................................................... 136
Bài 11.14 – (N1114E) Quân hậu ................................................................... 136
D. HƢỚNG DẪN GIẢI MỘT SỐ BÀI TẬP ................................................ 137
Bài 11.4 – (N1104B) Liệt kê chỉnh hợp ......................................................... 137
Bài 11.5 – (N1105B) Liệt kê chỉnh hợp tập A .............................................. 137
Bài 11.6 – (N1105B) Liệt kê tổ hợp .............................................................. 138
Bài 11.8 – (N1108C) Liệt kê xâu ký tự A
B................................................... 139
Bài 11.9 – (N1109D) Liệt kê xâu hợp lệ....................................................... .140
Bài 11.10 – (N1110E) Liệt kê xâu con .......................................................... 141
Bài 11.11 – (N1111D) Số mũ 1 .................................................................... 141
Bài 11.12 – (N1112E) Số mũ 2 ..................................................................... 142
Bài 11.13 – (N1113E) Số mũ 3 ..................................................................... 143
Bài 11.14 – (N1114E) Quân hậu ................................................................... 143
KẾT LUẬN ....................................................................................................... 145
TÀI LIỆU THAM KHẢO ................................................................................. 146 10 Algorithm with C++
PHẦN I – ĐẶT VẤN ĐỀ 1.1. Lý do chọn đề tài
Theo Chƣơng trình giáo dục phổ thông 2018 đƣợc Bộ Giáo dục và Đào
tạo ban hành kèm Thông tƣ số 32/2018/TT-BGDĐT ngày 26/12/2018, môn Tin
học có triết lý cốt lõi tạo ra một thế hệ mới có tƣ duy áp dụng công nghệ trong
giải quyết các vấn đề thực tế. Vì vậy, những kiến thức về phần giải thuật và lập
trình đóng vai trò rất quan trọng trong chƣơng trình tin học ở bậc THPT.
Hiện tại chất lƣợng việc dạy học Tin học ở nhà trƣờng THCS và THPT
trong cả nƣớc nói chung, tỉnh Nghệ An nói riêng còn ở mức độ khá thấp, tuy đã
đƣợc chú trọng, song trình độ giáo viên còn hạn chế, việc tìm tòi kiến thức còn
gặp nhiều khó khăn trong xu thế liên tục đổi mới công nghệ nói chung và bộ
môn Tin học nói riêng. Lập trình là một phần rất quan trọng trong nội dung
chƣơng trình bộ môn Tin học hiện tại và cả nội dung chƣơng trình Giáo dục phổ
thông 2018, là mạch kiến thức quan trọng nhất trong 3 mạch kiến thức của Tin học bao gồm: CS, ICT, DL.
Hiện tại phần lập trình trong SGK Tin học cơ bản đang minh họa bằn g
ngôn ngữ lập trình Pascal. Đây là ngôn ngữ có nhiều đóng góp trong lịch sử phát
triển của Tin học thế giới. Tuy nhiên, với xu thế phát triển của thời đại 4.0, ngôn
ngữ Pascal không còn đƣợc hỗ trợ nhiều và chính thức bị Tổ chức Olympic Tin
học Quốc tế đƣa ra ngoài danh sách ngôn ngữ lập trình trong nhà trƣờng phổ thông từ năm 2020.
Trƣớc nhu cầu học tập của học sinh theo chƣơng trình giáo dục phổ thông
2018 và hỗ trợ giáo viên có công cụ giảng dạy tốt nhập môn lập trình, chúng tôi
thiết kế “Hệ thống giải bài trực tuyến nhập môn lập trình với C++” với từng
chƣơng và các bài tập vận dụng từ thấp đến cao theo hệ thống đánh giá Bloom.
1.2. Mục đích nghiên cứu
Nghiên cứu một số vấn đề khó khăn gặp phải khi giảng dạy lập trình trong
nhà trƣờng phổ thông và đƣa ra giải pháp xây dựng một hệ thống bài tập và một
công cụ E-learning đi kèm.
Nghiên cứu hệ thống đánh giá Bloom (2001) từ đó tạo ra hệ thống bài tập
phân loại theo 6 mức: Nhớ, Hiểu, Vận dụng, Phân tích, Đánh giá, Sáng tạo. 11 Algorithm with C++
1.3. Nhiệm vụ nghiên cứu
Chúng tôi xây dựng là một hệ thống học tập Elearning bao gồm:
- Website JUDGE có chức năng có thể chấm bài tự động, kiểm tra đánh
giá, hỗ trợ học tập cho học sinh, hỗ trợ giáo viên soạn bài giảng môn lập trình
một cách dễ dàng, giảm thiểu khó khăn cho giáo viên, tăng cƣờng tính hợp tác,
thi đua trong việc dạy và học môn lập trình.
- Hệ thống bài tập nhập môn C+
+ với nhiều ví dụ chọn lọc và phân loại các
mức nhận biết theo thang đánh giá Bloom.
1.4. Các phƣơng pháp nghiên cứu chính
- Nghiên cứu lý luận: Chúng tôi xem xét cách phân chia các mức độ nhận
thức theo thang Bloom để vận dụng trong việc phân loại hệ thống bài tập.
- Điều tra, quan sát: Thực trạng về tình hình dạy và học lập trình trong nhà trƣờng phổ thông.
- Tổng kết kinh nghiệm: Tổng hợp kinh nghiệm dạy và học của bản thân,
đồng nghiệp, học sinh trong quá trình dạy học nhập môn lập trình. 12 Algorithm with C++
PHẦN II – NỘI DUNG NGHIÊN CỨU
2.1. CÀI ĐẶT WEBSITE LAPTRINHPHOTHONG.VN
Trong phần này chúng tôi đã sử dụng nền tảng của NTUCoder xây dựng
nên một trang web dạng JUDGE – có chức năng chấm bài tự động với nhiều loại
ngôn ngữ khác nhau nhƣ: C, C++, Python2, Python3 – đây là các ngôn ngữ đƣợc
chƣơng trình 2018 khuyến khích sử dụng.
2.1.1. Giới thiệu về laptrinhphothong.vn
Từ phía ngƣời dùng giao diện của laptrinhphothong.vn bao gồm các
menu: Trang chủ, Bài tập, Kỳ thi, Hỏi & đáp, Bảng chấm bài, Bài viết, Chaxbox.
Ngƣời dùng có thể đăng ký để làm bài tập thông qua chức năng đăng ký.
Các chức năng của trang đều đơn giản dễ sử dụng. Khi vào menu bài tập,
sẽ hiển thị hệ thống bài tập. Click vào các bài tập cụ thể ta sẽ có nội dung và qua
đó sử dụng chức năng giải bài và nạp bài: 13 Algorithm with C++
Hệ thống bao gồm một máy chấm đƣợc cài đặt trên server online. Ngƣời
sử dụng có thể nạp bài bất cứ thời điểm nào khi có kết nối internet.
2.1.2. Hƣớng dẫn sử dụn g cho quản trị viên
Để đăng nhập có thể sử dụng:
Tài khoản: hieptt@nghean.edu.vn - Mật khẩu: 0983713301
2.1.2.1. Nhập nội dung bài tập mới Các nội dung cần nhập:
Mã bài tập: duy nhất trong toàn bộ danh sách bài tập.
Tên bài tập: Mô tả tên của bài tập.
Giới hạn thời gian và bộ nhớ: có thể thiết lập thời gian và bộ nhớ cần dùng cho chƣơng trình.
Nội dung bài tập: Phát biểu bài toán.
Giải thích ví dụ: phần xuất hiện bên dƣới ví dụ. TestType: có 2 dạng
o Output Matching: So sánh kết quả của user với kết quả đáp án,
đƣợc áp dụng khi kết quả đáp án là duy nhất.
o Verify Output: áp dụng khi có nhiều đáp án, lúc này cần viết
chƣơng trình chấm test, tức đọc kết quả của user để kiểm tra.
Trong trƣờng hợp này cần nhập thêm TestCompiler (trình biên
dịch code chấm test) và Code chấm test.
ReviewCoder: mời một ProblemSetter khác tham gia xem lại bài này.
Ngƣời đƣợc mời chỉ có thể xem và test thử, không sửa đƣợc bài tập.
Nếu không mời ngƣời review thì để trống.
Published: Check vào thì bài tập mới xuất hiện cho user thấy . 14 Algorithm with C++
2.1.2.2. Nhập các test case của bài tập
Nhấn nút Thêm mới để đƣa vào testcase mới.
- Sample test: là test case sẽ hiển thị khi user xem bài tập.
- PreTest: hiện tại chƣa sử dụng
2.1.2.3. Kiểm tra lại trƣớc khi publish 15 Algorithm with C++
Xem trước: Chọn nút cái kính lúp
, giống nhƣ là user bình thƣờng xem
một bài tập, kể cả bài này chƣa đƣợc publish
Chạy test trước: Chọn nút 2 bánh xe :
2.1.3. Hƣớng dẫn sử dụng cho ngƣời dùng
2.1.2.1. Đăng ký sử dụng
Chức năng đăng ký sử dụng nằm ở góc phải trên của website. Sau khi
click vào ô đăng ký, website sẽ cho ta khung đăng ký sau: 16 Algorithm with C++
Sau khi nhập tên tài khoản (user), đặt password, email thì một đƣờng dẫn
kích hoạt sẽ gửi cho ngƣời dùng qua tài khoản email. Việc đăng ký là dễ dàng
đối với ngƣời sử dụng.
2.1.2.2. Đăng nhập và giải bài
Sau khi đăng nhập ngƣời dùng có thể sử dụng các chức năng chatbox, nạp
bài, comment trên các bài viết. Cụ thể phần giải bài nằm trong menu bài tập nhƣ sau:
Để giải bài tập nào ngƣời dùng click vào mã bài đó, đọc đề và tiến hành giải bài.
Ngƣời dùng có thể giải bài trên CodeBlock rồi copy mã nguồn nạp lên trang nhƣ sau:
Click vào menu Nộp bài, sẽ hiển thị ra ô TextBox để nạp mã nguồn : 17 Algorithm with C++
Ngƣời dùng có thể sao chép mã nguồn và dán trực tiếp vào ô soạn thảo
của website, hoặc có thể upload file chƣơng trình từ bộ nhớ ngoài của máy tính.
Sau đó click vào nút Nộp bài và chờ kết quả trả về.
Trình chấm của website sẽ trả về các kết quả sau:
- Accepted: bài làm đúng tất cả các test.
- Wrong answer: có một test cho kết quả sai.
- Runtime error: lỗi chạy chƣơng trình (tràn mảng, chia cho 0, exit code khác 0...).
- Time limit exceed: chạy quá giới hạn thời gian của bài tập.
- Memory limit exceed: chạy quá giới hạn bộ nhớ của bài tập.
- Output size limit exceed: xuất kết quả quá lớn.
- Compilation error: Biên dịch lỗi.
Ngƣời sử dụng thông qua kết quả chấm có thể điều chỉnh lại code của
mình và tiếp tục nạp để giải bài. 18 Algorithm with C++
2.2. XÂY DỰNG HỆ THỐNG BÀI TẬP
2.2.1. Các nguyên tắc xây dựn g
Thang đo Bloom về các cấp độ tƣ duy đƣợc Benjamin Bloom, một giáo
sƣ của trƣờng Đại học Chicago, đƣa ra vào năm 1956. Trong đó Bloom có nêu
ra sáu cấp độ nhận thức (gọi là thang đo Bloom) với sáu mức độ nhận thức
tƣơng ứng là: Biết, Hiểu, Vận dụng, Phân tích, Tổng hợp, Đánh giá. Thang đo
này đã đƣợc sử dụng trong hơn năm thập kỷ qua đã khẳng định ƣu điểm của
phƣơng pháp dạy học nhằm khuyến khích và phát triển các kỹ năng tƣ duy của
ngƣời học ở mức độ cao. Sau đó vào năm 2001, tiến sỹ Lorin Anderson cùng
với các cộng sự đƣa ra Thang đánh giá Bloom (2001) phân chia sáu cấp độ nhận
thức nhƣ sau: Nhớ (Remmember), Hiểu (Understand), Vận dụng (Apply), Phân
tích (Analyze), Đánh giá (Evaluate), Sáng tạo (Create). Hiện tại, đây là một
thang đo các cấp độ nhận thức đƣợc sử dụng phổ biến trong nghiên cứu về giáo dục trên thế giới. Mức độ Ý nghĩa Hành động A – Nhớ Nhớ thông tin
Xác định, mô tả, gọi tên, phân loại. B – Hiểu
Hiểu nghĩa, diễn giải khái Tóm tắt, biến đổi, giải thích. niệm C – Vận dụn g
Sử dụng thông tin hay khái Thiết lập, thực hiện, tạo dựng,
niệm trong tình huống mới
mô phỏng, dự đoán, chuẩn bị lập kế hoạch.
D – Phân tích Chia nhỏ thông tin và khái So sánh, đối chiếu, phân chia,
niệm thành những phần nhỏ phân biệt, lựa chọn, phân tích 19 Algorithm with C++
hơn để hiểu đầy đủ hơn. E – Đánh giá
Đánh giá vấn đề, khả năng Đánh giá, phê bình, phán đoán
phán xét giá trị, quyết định. chứng minh, tranh luận, biện hộ. F – Sáng tạo
Tạo ra cái mới từ thông tin Tập hợp, sáng tạo, xây dựng, đã có.
phát minh, chế tạo, lên kế hoạch.
Cụ thể các mức độ nhận thức trong sáu cấp độ ở sơ đồ trên đƣợc hiểu chi tiết hơn nhƣ sau:
Cấp độ 1: Nhớ (remember)
Ở đây, nhớ là khả năng ghi nhớ và nhận diện thông tin. Nhớ là cần thiết
cho tất cả các mức độ tƣ duy và đƣợc hiểu là nhớ lại những kiến thức đã học một
cách máy móc và nhắc lại.
Để đánh giá mức độ nhớ của ngƣời học, khi xây dựng hệ thống câu hỏi,
chúng tôi đƣa vào nhóm các bài tập nhắc lại một hoặc hai câu lệnh trong vùng
kiến thức đang đƣợc học.
Cấp độ 2: Hiểu (understand)
Hiểu là khả năng hiểu, diễn dịch, diễn giải, giải thích hoặc suy diễn (dự
đoán đƣợc kết quả hoặc hậu quả). Hiểu không đơn thuần là nhắc lại cái gì đó,
ngƣời học phải có khả năng diễn đạt khái niệm theo ý hiểu của họ.
Với mục đích đánh giá xem ngƣời học hiểu bài đến đâu, chúng tôi đƣa ra
các bài tập vẫn là sử dụng ít câu lệnh nhƣng đƣợc biến tấu cho những tình huống
đòi hỏi phải thay đổi một vài tham số để chƣơng trình hoạt động.
Cấp độ 3: Vận dụng (appy)
Vận dụng là khả năng sử dụng thông tin và chuyển đổi kiến thức từ dạng
này sang dạng khác (sử dụng những kiến thức đã học trong hoàn cảnh mới). Vận
dụng là bắt đầu của mức tƣ duy sáng tạo, tức là vận dụng những gì đã học vào
đời sống hoặc một tình huống mới.
Để đánh giá khả năng vận dụng của ngƣời học, chúng tôi phát biểu bài
toán có xem lẫn các dữ kiện cần mô hình hóa toán học trƣớc khi lập trình.
Cấp độ 4: Phân tích (analysis)
Phân tích là khả năng nhận biết chi tiết, phát hiện và phân biệt các bộ
phận cấu thành của thông tin hay tình huống. Ở mức độ này đòi hỏi khả năng 20 Algorithm with C++
phân nhỏ đối tƣợng thành các hợp phần cấu thành để hiểu rõ hơn cấu trúc của nó.
Muốn đánh giá khả năng phân tích của ngƣời học, chúng tôi đƣa ra các
bài tập cần sử dụng khả năng phân tích độ phức tạp của thuật toán. Với các bài
tập dạng này chúng tôi chia thành các sub – với mục đích giúp ngƣời học có
đƣợc cách phân tích các thuật toán khác nhau để giải bài tập đó.
Cấp độ 5: Đánh giá (evaluate)
Đánh giá là khả năng phán xét giá trị hoặc sử dụng thông tin theo các tiêu
chí thích hợp (hỗ trợ đánh giá bằng lý do/lập luận). Để sử dụng đúng mức độ
này, ngƣời học phải có khả năng giải thích tại sao sử dụng những lập luận giá trị
để bảo vệ quan điểm.
Ở cấp độ này chúng tôi đƣa ra các bài tập đƣợc phát biểu ở dƣới nhiều
phƣơng diện khác nhau, ngƣời học cần biết tổng hợp nhiều vùng kiến thức để
đƣa ra chiến lƣợc giải quyết vấn đề một cách hiệu quả
Cấp độ 6: Sáng tạo (create)
Sáng tạo là khả năng hợp nhất các thành phần để tạo thành một tổng
thể/sự vật lớn và trên cơ sở đó tạo ra những sự vật mới. Ở mức độ này ngƣời học
phải sử dụng những gì đã học để tạo ra hoặc sáng tạo một cái gì đó hoàn toàn mới.
Với mức độ này, chúng tôi xây dựng các mô hình contest, ngƣời học có
thể tham gia xây dựng bài tập, sáng tạo đề thi. Bên cạnh đó chúng tôi xây dựng
các group thảo luận sau khi kết thúc contest. Vì vậy, trong hệ thống bài tập
chúng tôi thiết kế sẽ chỉ có 5 mức độ. Mức độ thứ sáu sẽ là mức độ tùy biến
trong giảng dạy của giáo viên và ngƣời học dựa trên các contest.
2.2.2. Các bƣớc xây dựng
Bƣớc 1. Xác định mục đích của hệ thống bài tập
- Mục đích xây dựng hệ thống bài tập nhập môn lập trình với C++ nhằm
giúp ngƣời học tiếp cận bộ môn lập trình thuật toán với ngôn ngữ lập
trình C++ theo thang đo Bloom (2001).
- Tạo ra một sân chơi trí tuệ cho bộ môn lập trình thuật toán.
Bƣớc 2. Xác định nội dung hệ thống bài tập
- Hệ thống lại các kiến thức cơ bản trong từng chƣơng 21 Algorithm with C++
- Xây dựng hệ thống bài tập nhập môn lập trình với ngôn ngữ C++ bao
gồm 11 chƣơng với các kiến thức từ nền tảng đến nâng cao.
Bƣớc 3. Xác định loại bài tập, các kiểu bài tập
- Hệ thống bài tập xây dựng trong đề tài là các bài tập nhập môn lập
trình, nghĩa là phải phủ hết toàn bộ kiến thức cơ bản của ngôn ngữ C++.
- Trên cơ sở thang đo Bloom, chúng tôi phân loại bài tập trong mỗi
chƣơng theo 5 mức độ và đƣợc ký hiệu theo thứ tự A – Nhớ, B – Hiểu,
C – Vận dụng, D – Phân tích, E – Đánh giá.
Bƣớc 4. Thu thập thông tin để soạn hệ thống bài tập
- Thu thập các sách bài tập, tài liệu liên quan đến hệ thống bài tập cần
xây dựng; tham khảo sách, báo, tạp chí… có liên quan.
- Tìm hiểu, nghiên cứu về các version mới nhất của C+ + trên trang web
chính thức http://cplusplus.com/.
- Số tài liệu thu thập đƣợc càng nhiều và càng đa dạng thì việc biên soạn
càng nhanh chóng và có chất lƣợng, hiệu quả. Vì vậy, cần tổ chức sƣu
tầm tƣ liệu một cách khoa học.
Bƣớc 5. Tiến hành soạn thảo bài tập
- Xây dựng dàn ý các dạng bài tập theo từng chƣơng.
- Lồng ghép các nội dung thuật toán đi kèm kiến thức về ngôn ngữ.
- Phân dạng bài tập theo 5 mức độ A, B, C, D, E.
Bƣớc 6. Tham khảo, trao đổi ý kiến với đồng nghiệp
- Sau khi xây dựng xong các bài tập, giáo viên tham khảo ý kiến các
đồng nghiệp về tính chính xác, khoa học và tính vừa sức với trình độ của học sinh.
- Thảo luận trên các diễn đàn để đánh giá về mức độ tƣ duy của hệ thống bài tập.
Bƣớc 7. Thực nghiệm, chỉnh sửa và bổ sung
- Để khẳng định lại mục đích của hệ thống bài tập là nhằm củng cố kiến
thức và phát triển tƣ duy sáng tạo cho học sinh, giáo viên trao đổi với
các giáo viên thực nghiệm về khả năng nắm vững kiến thức và phát
triển năng lực vận dụng cho học sinh thông qua hoạt động giải các bài tập.
- Bổ sung thêm các bài tập mới trong quá trình giảng dạy. 22