Thuật ToánBạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (4.7 MB, 41 trang ) Đỗ 22 1. Khái niệm bài toán Là việc nào đó ta muốn máy thực hiện để từ thông tin đưa vào (INPUT) tìm được thông tin ra (OUTPUT). Ví dụ 3: Tìm ước số chung lớn nhất của hai số nguyên dương. INPUT: Hai số nguyên dương M và N. OUTPUT: ước số chung lớn nhất của M và N. Ví dụ 4: Bài toán xếp loại học tập của một lớp. INPUT: Bảng điểm của học sinh trong lớp. OUTPUT: Bảng xếp loại học lực của học sinh. Bài 4. Bài toán và thuật Toán 2. Khái niệm thuật toán Từ INPUT làm thế nào để tìm ra OUTPUT ? Các em cần tìm ra cách giải của bài 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à b0 => Phương trình vô nghiệm =>B5; B4: Nếu a0 => Phương trình có nghiệm x=-b/a =>B5; B5: Kết thúc. Thuật toán để 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 ấy, từ Input của bài toán, ta nhận được Output cần tìm. Có hai cách thể hiện một thuật toán: Cách 1: Liệt kê các bước. Cách 2: Vẽ sơ đồ khối. B7: Kết thúc. B1: Bắt đầu; B2: Nhập a, b, c; B3: Tính = b 2 4ac; B4: Nếu < 0 => PT vô nghiệm => B7; B5: Nếu = 0 => PT có nghiệm kép x = -b/2a => B7; B6: Nếu > 0 => PT có hai nghiệm x1, x2 = (-b )/2a => B7; 3. Một số ví dụ về thuật toán Thuật toán giải phương trình bậc hai (a 0). Cách 1: Liệt kê các bước Quy ước các khối trong sơ đồ thuật toán Bắt đầu thuật toán. Dùng để nhập và xuất dữ liệu. Dùng để gán giá trị và tính toán. Xét điều kiện rẽ nhánh theo một trong hai điều kiện đúng, sai. Kết thúc thuật toán. BĐ ĐK đ S KT Cách 2: Vẽ sơ đồ khối Nhập vào a, b, c = b - 4ac < 0 PT vô nghiệm = 0 PT có nghiệm x= - b/2a KT BD đ s Sơ đồ thuật toán giải phương trình bậc hai 2 PT có 2 nghiệm x1,x2 = ( -b )/2a B1 B2 B3 B4 B5 B6 s đ B7 a,b,c= 1 3 5 = 33 45 = 11 11 < 0 PT v« nghiÖm = 0 PT cã nghiÖm x = -b/2a KT BD -11 531 c b a S PT cã 2 nghiÖm x1, x2 = (-b ± )/2a § S = b*b 4*a*c nhËp vµo a,b,c < 0 M« pháng thuËt to¸n gi¶i ph¬ng tr×nh bËc hai Bé TEST 1: a,b,c= 1 2 1 = 22 411 = 0 PT v« nghiÖm PT cã nghiÖm x=-b/2a KT BD 0 121 c b a S PT cã 2 nghiÖm x1, x2 = (-b ± )/2a § S = b*b 4*a*c nhËp vµo a,b,c < 0 M« pháng thuËt to¸n gi¶i ph¬ng tr×nh bËc hai Bé TEST 2: § = 0 PT cã nghiÖm kÐp x=-1 a,b,c= 1 -5 6 = 25 24 = 1 PT v« nghiÖm PT cã nghiÖm x=-b/2a KT BD 1 6-51 c b a S PT cã 2 nghiÖm x1, x2 = (-b ± )/2a § S = b*b 4*a*c nhËp vµo a,b,c < 0 M« pháng thuËt to¸n gi¶i ph¬ng tr×nh bËc hai Bé TEST 3: § = 0 PT cã nghiÖm x1 = 3 x2 = 2 Thuật toán tìm max 3 Người ta đặt 5 quả bóng có kích thước khác nhau trong hộp đã được đậy nắp như hình bên. Chỉ dùng tay hãy tìm ra quả bóng có kích thước lớn nhất . Quả này lớn nhất Quả này mới lớn nhất ồ! Quả này lớn hơn Tìm ra quả lớn nhất rồi! Cùng tìm thuật toán MAX Thuật toán tìm số 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 a 1 , a 2 , , a N (a i với i: 1N). OUTPUT: Số lớn nhất (Max) của dãy số. ý tưởng: - Đặt giá trị Max = a 1 . - Lần lượt cho i chạy từ 2 đến N, so sánh giá trị a i với giá trị Max, nếu a i > Max thì Max nhận giá trị mới là a i . |
