Bài giảng Tin học 10 - Tiết 2, Bài 4: Bài toán và thuật toán

 TIN HỌC 10
 Đặng Hữu Hoàng KIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ 
 NGUYÊN DƯƠNG
@ Xác định bài tốn 
 * INPUT : Số nguyên dương N;
 * OUTPUT : “ N là số nguyên tố “ hoặc “ N khơng là số nguyên tố “ 
 @ Ý tưởng 
 * Nếu N = 1 thì N khơng là số nguyên tố;
 * Nếu 1 < N < 4 thì N là số nguyên tố;
 * Nếu N ≥ 4 và khơng cĩ ước số trong phạm vi từ 2 đến phần 
 nguyên căn bậc hai của N thì N là số nguyên tố; SƠ ĐỒ THUẬT TỐN KIỂM TRA TÍNH NGUYÊN 
 TỐ CỦA MỘT SỐ NGUYÊN 
 Nhập N
 DƯƠNG
 §
 N =1 
 ?
 S
 §
 N < 4 
 ?
 S
 i 2
 §
 Thơng báo N là số 
 i>[ N ] nguyên tố rồi kết thúc.
 ?
 S
 S
 i i +1 N cĩ chia 
 hết cho i 
 ?
 §
 Thơng báo N khơng 
 là số nguyên tố rồi 
 kết thúc. THUẬT TỐN SẮP XẾP
 H nh a H nh b
Hãy tìm cách sắp xếp học sinh đứng chào cờ (hình a) 
theo thứ tự thấp trước cao sau (hình b) THUẬT TỐN 
 SẮP XẾP TRÁO ĐỔI
Cách 1 : Liệt kê các bước
 B1: Nhập N, các số hạng a1, a2,  , aN;
 B2: M  N;
 B3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
 B4: M  M – 1, i  0;
 B5: i  i + 1;
 B6: Nếu i > M thì quay lại bước 3;
 B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
 B8: Quay lại bước 5. MƠ PHỎNG THUẬT TỐN SẮP XẾP TRÁO ĐỔI
Với N = 6 và dãy A gồm 6 số hạng sau : 3 5 9 8 1 7
 Lượt thứ nhất Lượt thứ hai
 3 5 9 8 1 7 3 5 8 1 7 9
 3 5 8 9 1 7 3 5 1 8 7 9
 3 5 1 7 8 9
 3 5 8 1 9 7
 3 5 8 1 7 9 Lượt thứ ba 
 Lượt thứ tư 
 3 1 5 7 8 9 3 5 1 7 8 9
 3 1 5 7 8 9
 1 3 5 7 8 9 TÌM KIẾM TUẦN TỰ
@ Xác định bài tốn 
 * INPUT : Dãy A gồm N số nguyên khác nhau a1, a2,,aN và số 
 nguyên k;
 * OUTPUT : Chỉ số i mà ai = k hoặc thơng báo khơng cĩ số hạng 
 nào của dãy A cĩ giá trị bằng k.
 @ Ý tưởng 
 Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang 
 xét với khố k cho đến khi cĩ sự trùng nhau, nếu đã xét tới cuối 
 cùng mà khơng cĩ sự trùng nhau thì cĩ nghĩa là dãy A khơng 
 cĩ số hạng nào cĩ giá trị k . Nhập N, a1, a2,..., aN SƠ ĐỒ THUẬT TỐN 
 và k
 TÌM KIẾM TUẦN TỰ
 i 1
 Đ
 Đưa ra i
 ai = k 
 ? rồi kết thúc
 S
 i i + 1
S
 i > N 
 ?
 Đ
 Thơng báo dãy A khơng cĩ 
 số hạng cĩ giá trị bằng dãy 
 k, rồi kết thúc TÌM KIẾM NHỊ PHÂN
@ Xác định bài tốn 
 •INPUT : Dãy A là dãy tăng gồm N số nguyên khác nhau 
 a1, a2,,aN và số nguyên k;
 * OUTPUT : Chỉ số i mà ai = k hoặc thơng báo khơng cĩ số hạng 
 nào của dãy A cĩ giá trị bằng k. THUẬT TỐN 
 TÌM KIẾM NHỊ PHÂN
Cách 1 : Liệt kê các bước
 B1: Nhập N, các số hạng a1, a2,, aN và giá trị khố k;
 B2: Dau 1, Cuoi N;
 Dau+ Cuoi 
 B3: Giua 2 ; 
 B4: Nếu agiua = k thì thơng báo chỉ số Giua, rồi kết thúc;
 B5: Nếu agiua > k thì đặt Cuoi = Giua – 1, rồi chuyển đến B7;
 B6: Dau Giua +1;
 B7: Nếu Dau > Cuoi thì thơng báo dãy A khơng cĩ số hạng 
 cĩ giá trị bằng k, rồi kết thúc;
 B8: Quay lại B3; MƠ PHỎNG THUẬT TỐN TÌM KIẾM NHỊ PHÂN
 Với k = 21 và dãy A gồm 10 số hạng như sau: 
 A 2 4 5 6 9 21 22 30 31 33
 i 1 2 3 4 5 6 7 8 9 10
 Lượt thứ nhất: agiua là a5 = 9; 9 < 21 
  vùng tìm kiếm thu hẹp trong phạm vi từ a6→ a10;
 Lượt thứ hai: agiua là a8 = 30; 30 > 21
  vùng tìm kiếm thu hẹp trong phạm vi từ a6→ a7;
 Lượt thứ ba: agiua là a6 = 21; 21= 21 
  Vậy số cần tìm là i = 6. Bài học đã 
KẾT THÚC
 Thân Ái Chào Các Em
 Thực hiện tháng 8 năm 2006