Bài giảng Chương trình tin học lớp 10 - Bài 4: Bài toán và thuật toán

Bài giảng Chương trình tin học lớp 10 - Bài 4: Bài toán và thuật toán sẽ giới thiệu tới các bạn một số bài toán và thuật toán thường được sử dụng trong tin học. Hy vọng tài liệu là nguồn thông tin hữu ích cho quá trình học tập và nghiên cứu của các bạn.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương trình tin học lớp 10 - Bài 4: Bài toán và thuật toán CHƯƠNG TRÌNH TIN HỌC LỚP 10 (SGK thí điểm) Chƣơng I Bài 4. BÀI TOÁN và THUẬT TOÁN I. BÀI TOÁN • Xét các yêu cầu sau : 1. Giải phương trình bậc hai ax2+bx+c=0 2. Viết một dòng chữ ra màn hình máy tính. 3. Quản lý các cán bộ trong một cơ quan. 4. Tìm ước chung lớn nhất của hai số nguyên dương a và b. 5. Xếp loại học tập các học sinh trong lớp. Trong TOÁN HỌC Trong TIN HỌC Trong các yêu Yêu cầu 1 và 4 đƣợc cầu trên, yêu cầu Tất cả các yêu cầu trên nào đƣợc xem nhƣ là một bài toán? xem là bài toán đều đƣợc xem là bài toán Khái niệm bài toán trong Tin học? Bài toán là việc nào đó ta muốn máy tính thực hiện. Các yếu tố cần quan tâm khi giải một bài toán TOÁN HỌC TIN HỌC THUẬT NGỮ - Giả thiết Đưa vào máy Input thông tin gì TOÁN HỌC? - Kết luận Cần lấy ra Output thông tin gì  Trong Tin học, để phát biểu một bài toán, ta cần trình bày rõ Input và Output của bài toán đó. CÁC VÍ DỤ VD1 : Giải phƣơng trình bậc hai ax2 + bx + c = 0 (a ≠ 0).  Input : Các số thực a,b,c (a ≠ 0)  Output : Số thực x thỏa : ax2+bx+ c = 0 VD2 : Tìm giá trị nhỏ nhất của các số trong một dãy số.  Input : Các số trong dãy số.  Output : Giá trị nhỏ nhất trong dãy số. CÁC VÍ DỤ (tt) VD3 : Tìm ƣớc chung lớn nhất của hai số nguyên dƣơng a và b.  Input : ? Hai số nguyên dương a và b.  Output : ?UCLN của a và b. VD4 : Xếp loại học tập các học sinh trong lớp.  Input :?Bảng điểm của học sinh.  Output : ? Bảng xếp loại học tập. Nêu một bài toán và chỉ rõ Input, Output của bài toán đó? Xem thêm các ví dụ trong SGK/24, 25 TÓM LẠI Một bài toán đƣợc cấu tạo bởi 2 thành phần cơ bản :  Input (Các thông tin đã có)  Output (Các thông tin cần tìm từ Input) II. THUẬT TOÁN Bài toán Bằng cách nào? Input Output Giải bài toán Thuật toán Hƣớng dẫn các thao tác cho máy thực hiện để tìm ra lời giải BÀI TOÁN THUẬT TOÁN Input Output (Thao tác 1Thao tác 2...Thao tác n) Thuật toán để giải một bài toán là : Thuật • Một dãy để giải toánhữu hạnmột cácbài toán thao là một dãy tác. hữu hạn các thao tác đƣợc sắp xếp theo • Các một thao trình xác đƣợc tự tác sắpcho định sao xếpsau khimột theo thực hiện tự xác trìnhdãy thaođịnh. tác đó, từ Input của bài toán này, ta nhận đƣợc Output cần tìm. • Sau khi thực hiện dãy thao tác đó, từ Input ta tìm đƣợc Output của bài toán. MÔ TẢ CÁC THAO TÁC TRONG THUẬT TOÁN Nêu ra tuần tự các thao tác cần tiến hành Liệt kê Có 2 cách mô tả Dùng sơ đồ khối Dùng một số biểu tƣợng thể hiện các thao tác a) LIỆT KÊ VD : Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 () Giải toán thông thƣờng: LIỆT KÊ :  Nếu a = 0 thì () không • Bước 1 : Nhập a, b. phải là pt bậc nhất. • Bước 2 : Nếu a = 0 thì + Neáu b = 0 thì () voâ số quay lại bước 1, ngược lại nghieäm. thì qua bước 3. + Neáu b ≠ 0 thì () voâ • Bước 3 : Gán cho x giá nghieäm. trị -b/a, rồi qua bước 4.  Nếu a ≠ 0 thì () có • Bước 4 : Đưa ra kết quả nghiệm x = -b/a. x và kết thúc. b) DÙNG SƠ ĐỒ KHỐI  Trong sơ đồ khối, người ta dùng một số biểu tượng thể hiện các thao tác như : : Thể hiện các thao tác nhập, xuất dữ liệu : Thể hiện các phép toán : Thể hiện các thao tác so sánh : Quy định trình tự thực hiện các thao tác VD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 LIỆT KÊ SƠ ĐỒ KHỐI Nhaäp a, b • Bước 1 : Nhập a, b. • Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược a=0 Ñuùng lại thì qua bước 3. • Bước 3 : Gán cho x Sai giá trị -b/a, rồi qua bước x = -b/a 4. • Bước 4 : Đưa ra kết quả x và kết thúc. Ñöa ra x vaø keát thuùc LƢU Ý Ta cần diễn tả thuật toán bằng một ngôn ngữ sao cho máy tính có thể hiểu và thực hiện được, ngôn ngữ đó gọi là ngôn ngữ lập trình. Kết quả diễn tả thuật toán như vậy gọi là chương trình. III. VÍ DỤ VỀ THUẬT TOÁN Bài toán 1 : Cho dãy số gồm N số sau (N = 5): 11 6 20 4 8 Tìm giá trị NHỎ NHẤT của dãy số trên ? HÖÔÙNG DAÃN: - Goïi Min laø giaù trò nhoû nhaát caàn tìm. Min - Gaùn Min baèng giaù trò phaàn töû ñaàu tieân cuûa daõy. Min=6 - Laàn löôït so saùnh Min vôùi caùc phaàn töû 11 6 20 4 8 Gán i = 2 tieáp theo trong daõy. Taïi moãi vò trí so saùnh : Min=11 Min=4 + Neáu Min lôùn hôn giaù trò phaàn töû caàn so saùnh trong daõy thì laáy giaù trò cuûa Giaù trò nhoû nhaát: 4 phaàn töû ñoù gaùn laïi cho Min. - Khi so saùnh ñeán phaàn töû cuoái cuøng trong Biến i lưu trữ vị trí daõy+ soá thì Min tiếp theo mà Min sẽ T ...