Bài giảng Tin học Lớp 10 - Bài: Bài toán và thuật toán

Nội dung text: Bài giảng Tin học Lớp 10 - Bài: Bài toán và thuật toán

1. BàiHỏi bàimới: cũ: Em hãy cho biết một thuật toán phải thoã mãn những tínhTiết 12chất: nào? Bài toán và thuật toán (T3) -b)Tính Các dừng cách: diễn tả thuật toán: Thuậtb.1) Cách toán liệtphải kê kết từng thúc b sauớc: một số hữu hạn lần thực hiện các thao tác. (Liệt kê từng thao tác của thuật toán theo các bớc nh ở ví dụ tìm UCLN- Tính của xác 2 số định: nguyên dơng m,n đã học) Saub.2) khi Cách thực dùng hiện sơmột đồ thao khối: tác thì hoặc là thuật toán kết thúc, hoặc là có Sửđúng dụng một các thao khối tác sau:xác định để đợc thực hiện tiếp theo. Hình- Tínhthoi đúng đắn: : thể hiện thao tác so sánh. Sau khi thuật toán kết thúc, ta phải nhận đợc Output cần tìm. Hình chữ nhật : thể hiện các phép tính toán . Hình ôVan : thể hiện thao tác nhập, xuất DL. Các mũi tên : quy định trình tự thực hiện các thao tác.
2. Chú ý: nh vậy thực chất hai cách diễn tả này chỉ khác nhau về hình thức trình bày còn chúng đều đảm bảo cùng các bớc giải nh nhau. 3/. Một số ví dụ về thuật toán: 3.1/. Ví dụ 1: Tìm giá trị lớn nhất của dãy số nguyên. * Xác định bài toán: - Input: Số nguyên dBàiơng toánn vàcho dãy biết n số nguyên a 1, a 2 , , a n . những gì và yêu cầu - Output: Giá trị lớnchúng nhấtMax ta tìmcủa gì? dãy số.
3. * Chú ý: 1) i là biến chỉ số có gá trị nguyên thay đổi từ 2 đến n + 1. 2) Mũi tên ( ) đợc hiểu: gán giá trị của biểu thức phía bên phải mũi tên cho biến ở bên trái mũi tên (Vd: i i + 1 nghĩa là tăng biến i lên 1 đơn vị) Cách 2: Dùng sơ đồ khối
4. * Kiểm tra thuật toán với dãy gồm 5 phần tử nh sau: 4, 5, 1, 10, 2 i = 1 2 3 4 5 6 > n Dừng ai 4 5 1 10 2 Max 4 5 5 10 10 Diễn giải: Với n = 5, Max = a1 = 4, i = 2 Max = 4 -> Max = a2 = 5, i = i + 1 = 3 Max = a2 = 5, i = i + 1 = 4 Max = 5 -> Max = a4 = 10, i = i + 1 = 5 (=n) a5 = 2 Max = a4 = 10, i = i + 1 = 6 > n -> Thuật toán dừng lại. Vậy giá trị lớn nhất của dãy số trên là Max = 10 ứng với vị trí thứ i = 4
5. * Thuật toán: + Cách liệt kê từng bớc B1: Nhập a, b B2: Nếu a 0 thì nghiệm là -b/a. Ngợc lại thì sang B3 B3: Nếu b = 0 thì mọi số đều là nghiệm. Ngợc ại thì sang B4. B4: Phơng trình vô nghiệm. + Cách dùng sơ đồ khối: Nhập a,b Nghiệm Đúng a 0 x = -b/a Sai Nhớ để phần PT có học Đsinhúng với vô số nghiệm b = 0 Sai PT vô nghiệm