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

 TIN HỌC 10
 Ñaëng Höõu Hoaøng Ví dụ : Giải phương trình bậc nhất ax + b = 0
 * INPUT : Các hệ số a và b ; 
 * OUTPUT : Nghiệm của phương trình
 Với a = 1 ; b = -5
 Phương trình có nghiệm x = 5 BÀI TOÁN VÀ THUẬT TOÁN
1. Khái niệm bài toán 
2. Khái niệm thuật toán 
3. Một số ví dụ về thuật toán Xét ví dụ 2 : giải phương trình bậc nhất ax+ b = 0
 B1 : xác định hệ số a, b;
 B2 : nếu a = 0 và b = 0  phương trình vô số nghiệm  B5;
 B3 : nếu a = 0 và b ≠ 0  phương trình vô nghiệm  B5;
 B4 : nếu a ≠ 0  phương trình có nghiệm x = -b/a  B5;
 B5 : Kết thúc. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN
!. Tìm nghiệm của phương trình bậc hai
!!. Tìm giá trị lớn nhất của một dãy số nguyên
!!!. Kiểm tra tính nguyên tố của một số nguyên dương .
!!!!. Sắp xếp bằng trao đổi .
!!!!!. Tìm kiếm tuần tự .
!!!!!!. Tìm kiếm nhị phân . THUẬT TOÁN 
 BÀI TOÁN TÌM NGHIỆM CỦA PHƯƠNG TRÌNH 
 BẬC HAI ax2 + bx = c (a ≠ 0)
Cách 2 : Vẽ sơ đồ khối Qui ước vẽ sơ đồ khối
 Dùng để nhập và xuất dữ liệu 
 Dùng để gán giá trị tính toán . 
 Xét điều kiện rẽ nhánh theo một trong 
 §K
 hai điều kiện đúng, sai.
 Trình tự thực hiện các thao tác MÔ PHỎNG THUẬT TOÁN 
 BÀI TOÁN TÌM NGHIỆM CỦA PHƯƠNG TRÌNH 
 BẬC HAI ax2 + bx = c (a ≠ 0)
 Bộ test 
 nha,b,cËp vµo= 1, a,b,c3, 5 a b c 
 1 3 5 -11
 == 3*3b*b -- 4*54*a*c = - 11
 §
 - 11 << 00 PT v« nghiÖm
 S
 KT
 = 0 PT cã nghiÖm x = -b/2a
 S PT cã 2 nghiÖm 
 x1, x2 = (-b  )/2a MÔ PHỎNG THUẬT TOÁN 
 BÀI TOÁN TÌM NGHIỆM CỦA PHƯƠNG TRÌNH 
 BẬC HAI ax2 + bx = c (a ≠ 0)
 Bộ test 
 nha,b,c=Ëp vµo 1 -a,b,c5 6 
 a b c 
 1 - 5 6 1
 = = 25 b*b - 24- 4*a*c = 1 
 §
 < 0 PT v« nghiÖm
 S
 §
 = 0 PT cã nghiÖm x=-b/2a KT
 S
 PTPT cãcã 2nghiÖm nghiÖm x 1 = 3 
 x x12, x=2 2 = (-b  )/2a TÌM GIÁ TRỊ LỚN NHẤT CỦA MỘT DÃY SỐ 
 NGUYÊN 
@ Xác định bài toán 
 * INPUT : Số nguyên dương N và dãy N số nguyên a1,  ,aN
 * OUTPUT : giá trị lớn nhất Max của dãy số 
 @ Ý tưởng 
 * Đặt giá trị Max = a1
 * Lần lượt cho i từ 2 đến N, so sánh giá trị số hạng ai với giá trị 
 Max, nếu ai > Max thì Max nhận giá trị mới là ai, SƠ ĐỒ THUẬT TOÁN 
 TÌM GIÁ TRỊ LỚN NHẤT CỦA MỘT DÃY SỐ NGUYÊN 
 B1: Nhập N và dãy a1,,aN;
 Nhập N và dãy a1,,aN
 Max  a1 ; i  2 B2: Max  a1; i  2;
 §
 i > N ? Đưa ra Max rồi kết thúc
 S
 S B3: Nếu i > N thì đưa ra giá trị 
 ai > Max ? Max rồi kết thúc; 
 §
 B4 :
 Max  ai
 4.1: nếu ai > Max thì Max  ai;
 4.2: i  i + 1 rồi quay lại B3.
 i  i + 1 MÔ PHỎNG THUẬT TOÁN KhiKhiKhi iii === 3425
 A 5 1 4 7 6
 NhậpN=5 ;N A và[ 5 dãy 1 4 a71 6,,a ] N
 i 2 3 4 5
 Max 5 5 5 7 7
 MaxMax  a51 ;; ii  22
 §
 32456I >> N5 ?? SốĐưa lớn ra nhấtMax củarồi kết dãy thúc là 7
 S
 S
 a76i1>4>> > Max 557 ?? ?
 §
 Max 7ai
 TÌM GIÁ TRỊ LỚN NHẤT CỦA 
 ii i   3+14+15+12+1 i+1 MỘT DÃY SỐ NGUYÊN