Bài giảng Tin học Lớp 10 - Bài 4: Bài toán & thuật toán (Tiếp theo)

Nội dung text: Bài giảng Tin học Lớp 10 - Bài 4: Bài toán & thuật toán (Tiếp theo)

1. Cõu hỏi kiểm tra bài cũ Cõu 1: Trong sơ đồ khối, người ta dựng một số biểu tượng thể hiện A. Thể hiện cỏc thao tỏc nhập, xuất dữ liệu B. Thể hiện cỏc phộp toỏn C. Thể hiện cỏc thao tỏc so sỏnh D. Quy định trỡnh tự thực hiện cỏc thao tỏc
2. Cõu hỏi kiểm tra bài cũ Cõu 2: Chọn phỏt biểu đỳng trong cỏc cõu sau: A. Trong phạm vi Tin học, ta cú thể quan niệm bài toỏn là việc nào đú mà ta muốn mỏy tớnh thực hiện. B. Thuật toỏn( giải thuật) để giải một bài toỏn là một dóy hữu hạn cỏc thao tỏc được sắp xếp theo một trỡnh tự xỏc định sao cho sau khi thực hiện dóy thao tỏc đú, từ Input của bài toỏn này, ta nhận được Output cần tỡm. C. Sơ đồ khối là sơ đồ mụ tả thuật toỏn. D. Cả ba cõu trờn đều đỳng.
3. Cõu hỏi kiểm tra bài cũ Cõu 3: Hóy chọn phương ỏn ghộp đỳng: Trong tin học sơ đồ khối là A. Ngụn ngữ lập trỡnh bậc cao B. Sơ đồ mụ tả thuật toỏn C. Sơ đồ về cấu trỳc mỏy tớnh D. Sơ đồ thiết kế vi điện tử
4. Cõu hỏi kiểm tra bài cũ Cõu 4: Thuật toỏn cú cỏc tớnh chất: A. Tớnh xỏc định, tớnh liờn kết, tớnh đỳng đắn. B. Tớnh dừng, tớnh liờn kết, tớnh xỏc định. C. Tớnh tuần tự: Từ input cho ra output. D. Tớnh dừng, tớnh xỏc định, tớnh đỳng đắn.
5. Cõu hỏi kiểm tra bài cũ Cõu 5: Khi giải bài toỏn trờn mỏy tớnh ta cần quan tõm đến yếu tố nào? A. Giả thiết. B. Kết luận. C. Input và Output. D. Tất cả đều đỳng.
6. BÀI 4: BÀI TOÁN & THUẬT TOÁN (TT) 7
7. BÀI TOÁN Người ta đặt 9 quả búng cú kớch thường khỏc nhau trong một cỏi hộp đậy kớnh, hóy dựng tay để lấy ra quả búng cú kớch thước lớn nhất ?
8. Tỡm giỏ trị lớn nhất trong một dóy số nguyờn a1, a2, , aN Bước 1 Bước 2 Bước 3 Biểu diễn thuật toỏn Xỏc định theo 2 cỏch : í tưởng bài toỏn ➢ Liệt kờ ➢ Sơ đồ khối
9. Tỡm giỏ trị lớn nhất trong 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, a2, , aN (ai với i : 1→N). ⚫ Output : ? Số lớn nhất (Max) của dóy số 10
10. í tưởng Quả này TỡmQuả ra này quả Quả này lớn mới lớn mớilớn đỳng nhất là nhất nhất lớnrồi! nhất MAX
11. Tỡm giỏ trị lớn nhất trong một dóy số nguyờn 4 9 15 35 7 5 50 3 8 a1 a2 a3 a4 a5 a6 a7 a8 a9 í tưởng 1: - Đặt giỏ trị Max = a1 - Lần lượt cho i chạy từ 2 đến n , so sỏnh giỏ trị ai với giỏ trị Max, nếu ai > Max thỡ Max nhận giỏ trị mới là ai
12. Tỡm giỏ trị lớn nhất trong một dóy số nguyờn 4 9 15 35 7 5 50 3 8 a1 a2 a3 a4 a5 a6 a7 a8 a9 í tưởng 2: • Sắp xếp dóy số tăng dần • Max = a9 3 4 5 7 8 9 15 35 50 a1 a2 a3 a4 a5 a6 a7 a8 a9
13. CÁCH 1: LIỆT Kấ CÁC BƯỚC Bước 1 : Nhập N và dóy a1,a2, .,aN ; Bước 2: Max a1 ; i  2 ; Bước 3: Nếu i > N thỡ đưa ra giỏ trị Max rồi kết thỳc ; Bước 4 : Bước 4.1: Nếu ai > Max thỡ Max  ai ; Bước 4.2: i  i+1 rồi quay lại bước 3.
14. CÁCH 2: SƠ ĐỒ KHỐI Nhập N và dóy B1 nhập N và dóy a1,a2 ,an; a1,a2, an B2: Max a ; i 2; Max  a1 ; i  2  1  Đ In ra giỏ trị i > N ? Max B3: Nếu i>N thỡ in giỏ trị Max S S ai > Max ? B4 : Đ 4.1: nếu ai > Max thỡ Max  ai; Max  ai i  i + 1 4.2: i  i + 1 rồi quay lại B3.
15. Mễ PHỎNG THUẬT TOÁN N=5 N=5 Nhập N và dóy i a1=5,a2=4,a3=1,a4=7,a5=6 2 3 4 5 6 a1,a2, an 5 4 1 7 6 MaxMax  5a1; ;i i 22 a1 a2 a3 a4 a5 Đ 32i456 >>>>> N 5 555 ? ???? In raMax giỏ trị7Max MaxMax 57 S S a7461 > > >Max 575 ?? ? i Max  7 Đ Max  a7i iii i 3524i ++++ 1 111
16. CỦNG CỐ BÀI ➢ Nắm vững cỏch diễn đạt thuật toỏn bằng sơ đồ khối hoặc liệt kờ. ➢ Thuật toỏn tỡm giỏ trị lớn nhất của dóy số, tương tự ỏp dụng để viết thuật toỏn tỡm giỏ trị nhỏ nhất của một dóy số.
17. DẶN Dề Về nhà học bài và làm bài tập SGK trang 44. Xem trước bài toỏn sắp xếp và bài toỏn tỡm kiếm.
18. Thuật toá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).
19. Thuật toán tìm kiếm Bông trốn đâu nhỉ ? Hai bạn chó (Bi và Bông) chơi trốn tìm, Bông đã trốn vào một trong những chiếc mũ của ông già Nôen trên. Hãy chỉ ra các cách tìm chiếc mũ mà Bông đang trốn? Cho biết có những cách nào?