Bài giảng Tin học Lớp 8 - Bài 5: Từ bài toán đến chương trình

Bài 5TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNHa) biết 2x – 6 = 0b) của các số tự nhiên từ 1 đến 100.c) điểm, cửu chươngd) RôbốtBài toán: là một công việc hay một nhiệm vụ cần phải giải quyếtTìm xTính tổngLập bảnglập bảngnhặt rácBài toán1. Bài toán và xác định bài toánBài toán: Tính diện tích hình chữ nhật có chiều dài a, chiều rộng b.Điều kiện cho trước: chiều dài a, chiều rộng bKết quả thu được: diện tích hình chữ nhật Bài toán: Rôbốt nhặt rác bỏ vào thùng rácThông tin vào (Input): Thông tin ra (Output):	 Để giải bài toán này trước tiên em cần phải xác định cái gì? (thông tin vào-Input)(thông tin ra-Output)rác bỏ vào thùng rácRôbốt, rác, thùng rác Xác định bài toán: + Xác định rõ các điều kiện cho trước ( thông tin vào – Input) + Xác định kết quả cần thu được ( thông tin ra – Output)Trước khi giải một bài toán em cần phải xác định được bài toán.ab Cách thức xác định bài toán 1. Bài toán và xác định bài toánVD1: Tính điểm trung bình của 3 môn Toán, Lý, Tin- Thông tin vào (Input):Điểm của 3 môn Toán, Lý, Tin- Thông tin ra (Output):§iÓm trung b×nh của 3 m«n Toán, Lý, TinVD2: Bµi to¸n “Giặc áo quần”- Thông tin vào (Input):Áo quần bẩn, vật dụng hiện có (xà phòng, nước,)- Thông tin ra (Output):Áo quần sạch1. Bài toán và xác định bài toán Từ điều kiện cho trước(Input) làm thế nào để tìm ra kết quả cần thu được(Output) ?Tìm ra cách giải* Để Rôbốt nhặt rác bỏ vào thùng rác ta có các bước giải:Rẽ phải 2 bướcTiến tới 1 bướcNhặt rácRẽ phải 2 bướcBỏ rác vào thùngThùng rácrácRôbốtThuật toán: là dãy hữu hạn các thao tác cần thực hiện để giải mộtbài toánMáy tính có thể tự động trực tiếp thực hiện được không ?Lµm thÕ nµo ®Ó m¸y tÝnh hiÓu vµ trùc tiÕp thùc hiÖn ®­îc thuËt to¸n? Cần diễn tả thuật toán bằng một ngôn ngữ mà 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. Thuật toán2. Quá trình giải bài toán trên máy tínhĐể giải một bài toán hoàn chỉnh trên máy tính em cần thực hiện các bước nào ? Quá trình giải bài toán trên máy tính: 3 bước- Xác định bài toán: xác định Input, Output- Mô tả thuật toán : trình tự các bước giải- Viết chương trình: bằng ngôn ngữ lập trình2. Quá trình giải bài toán trên máy tínhVí dụTính tổng của N số tự nhiên đầu tiên:S= 1+2+  + nThông tin vào (Input): Thông tin ra (Output):1,2,..,nTổng của 1 + 2 ++ n3. Thuật toán và mô tả thuật toán- Mô tả thực toán là liệt kê các bước cần thiết để giải một một bài toánBài toán: “Việc pha trà mời khách” INPUT: Trà, nước sôi, ấm và chén. OUTPUT: Chén trà đã pha để mời khách. Bước 1: Tráng ấm, chén bằng nước sôi. Bước 2: Cho trà vào ấm. Bước 3: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút. Bước 4: Rót trà ra chén để mời khách.Bài toán: “Giải phương trình bậc nhất dạng tổng quát bx + c =0” INPUT: Các số b và c. OUTPUT: Nghiệm của phương trình bậc nhất. Bước 1: Nếu b=0 chuyển tới bước 3. Bước 2: Tính nghiệm của phương trình x= - và chuyển tới bước 4 Bước 3: Nếu c  0, thông báo phương trình đã cho vô nghiệm. Ngược lại (c=0), thông báo phương trình có vô số nghiệm. Bước 4: Kết thúc. 3. Thuật toán và mô tả thuật toán3. Thuật toán và mô tả thuật toánBài toán: “Làm món trứng tráng” INPUT: Trứng, dầu ăn, muối và hành. OUTPUT: Trứng tráng. Bước 1: Đập trứng tách vỏ và cho trứng vào bát. Bước 2: Cho một chút muối và hành tươi thái nhỏ vào bát trứng. Dùng đũa khuấy mạnh cho đến khi đều. Bước 3: Cho một thìa dầu ăn vào chảo, đun nóng đều rồi đổ trứng vào. Đun tiếp trong khoảng một phút. Bước 4: Lật mặt trên của miếng trứng úp xuống dưới. Đun tiếp trong khoảng 1 phút. Bước 5: Lấy trứng ra đĩa.Vậy thuật toán là gì?Thuật toán là dãy hữu hạn các thao tác cần thực hiện theo một trình tự xác định để thu được kết quả cần thiết từ những điềukiện cho trước Ví dụ 2: Một hình A được ghép từ một hình chữ nhật với chiều rộng 2a, chiều dài b và một hình bán nguyệt như hình 29 dưới đây:? Xác định được bài toán và mô tả thuật toán.b a aHình 29+ INPUT: Số a là ½ chiều rộng HCN và là bán kính của hình bán nguyệt, b là chiều dài HCN + OUTPUT: Diện tích hình A.S1=2abS=S1+S2 S1 2abS2S S1+S2 Bước 1: S1 2ab Bước 2:S2Bước 3: S S1+S24. Một số ví dụ về thuật toán Ví dụ 3: Tính tổng của 100 số tự nhiên đầu tiên.+ Input: Dãy 100 số tự nhiên đầu tiên: 1,2,..., 100 + Output: Giá trị tổng 1+2+....+100.4. Một số ví dụ về thuật toánBước 1: S  0.Bước 2: S  S + 1....Bước 101: S  S + 100.Để mô tả được thuật toán trên ta dùng biến S để lưu giá trị của tổng và thực hiện phép toán : cộng thêm vào biến tổng S lần lược các giá trị 1,2,3,..,100 tức là thao tác “cộng” được lặp đi lặp lại 100 lần . Mặc khác việc cộng thêm số i vào S khi biến i không vượt quá 100.Vì vậy thuật toán tìm tổng S được mô tả như sau.Bước 1. S← 0; i← 0Bước 2. i← i+1;Bước 3. Nếu i b, kết quả là “a lớn hơn b”. Và chuyển đến bước 3.Bước 2: Nếu a b, kết quả là “a lớn hơn b”.Bước 2: Nếu a Max thì gán b cho max, còn nếu c> Max thì gán c cho max. Bài toán xác định4. Một số ví dụ về thuật toánVí dụ 6: Tìm số lớn nhất trong dãy A gồm các số a1,a2, ..., an cho trước Input: dãy A các số a1,a2,...,an (n>=0) Output: Giá trị Max= Max {a1,a2,...,an }Ta có thể thực hiện như sau: + Đầu tiên gán giá trị a1 cho biến Max . +Sau đó lần lượt so sánh các số a2,...an của dãy A với Max. Nếu a i > Max thì ta gán a i cho Max.Do vậy ta có thuật toán như sau:4. Một số ví dụ về thuật toánBước 1. Max← a1; i ← 1.Bước 2. i← i +1Bước 3. Nếu i >n thì chuyển đến bước 5.Bước 4. Nếu a i > Max thì Max ← ai và quay lại bước 2Bước 5 . Kết thúc thuật toán.4. Một số ví dụ về thuật toána) Tr­íc hÕt, ta giả sö thá lín nhÊt lµ thá sè 1, tøc MAX = 1.b) So s¸nh MAX (thá sè 1) víi thá sè 2. Vi thá sè 2 nhá h¬n thá sè 1, do ®ã MAX vÉn b»ng 1.c) TiÕp theo, so s¸nh MAX (thá sè 1) víi thá sè 3. Vi thá sè 3 lín h¬n thá sè 1, do ®ã MAX ®­îc ®Æt l¹i b»ng 3 (thá sè 3).d) Cuèi cïng, so s¸nh MAX (thá sè 3) víi thá sè 4. Thá sè 3 lín h¬n thá sè 4, do ®ã MAX vÉn b»ng 3 (thá sè 3). KÕt quả, thá lín nhÊt lµ thá sè 3.Dãy số534763159ii>nai > SMAXSMAXMô tả thuật toán tìm số lớn nhất trong dãy số với n=8,tương ứng với dãy: 5,3,4,7,6,3,15,9  aiSaiSaiSaiSaiSaiSaiSaiSaiĐúngSaiSaiĐúngSaiSaiĐúngSaiKết thúc5557771515123456789GHI NHỚX¸c ®Þnh bµi to¸n lµ viÖc x¸c ®Þnh c¸c ®iÒu kiÖn ban ®Çu (th«ng tin vµo - INPUT) vµ c¸c kÕt qu¶ cÇn thu ®­îc (th«ng tin ra – OUTPUT). Gi¶i bµi to¸n trªn m¸y tÝnh nghÜa lµ ®­a cho m¸y tÝnh d·y h÷u h¹n c¸c thao t¸c ®¬n gi¶n (thuËt to¸n) mµ nã cã thÓ thùc hiÖn ®­îc ®Ó cho ta kÕt qu¶. Qu¸ tr×nh gi¶i mét bµi to¸n trªn m¸y tÝnh gåm c¸c b­íc: x¸c ®Þnh bµi to¸n; x©y dùng thuËt to¸n; lËp ch­¬ng tr×nh.ThuËt to¸n lµ d·y h÷u h¹n c¸c thao t¸c cÇn thùc hiÖn theo mét tr×nh tù x¸c ®Þnh ®Ó thu ®­îc kÕt qu¶ cÇn thu ®­îc tõ nh÷ng ®iÒu kiÖn cho tr­íc.