Một số ví dụ về thuật toán Tin 8
|
Lý thuyết Tin học 8: Bài 5. Từ bài toán đến chương trình
Show a. Bài toán Bài toán là một công việc hay một nhiệm vụ cần phải giải quyết. Ví dụ về bài toán: + Bài toán 1: Tính tổng của các số tự nhiên từ 1 đến 100 + Bài toán 2: Tính quãng đường ô tô đi được trong 3 giờ với vận tốc 60km/giờ + Bài toán 3: Tính diện tích hình tam giác + Bài toán 4: Tính điểm trung bình của 3 môn Toán, Lý, Tin + Bài toán 5: Bài toán điều khiển Rô-bốt nhặt rác + Bài toán 6: Lập bảng điểm của các bạn trong lớp b. Xác định bài toán Để giải quyết được một bài toán cụ thể, người ta cần xác định bài toán, tức là xác định rõ các điều kiện cho trước và kết quả thu được. Ví dụ xác định các bài toán sau: Bài toán 3: Tính diện tích hình tam giác + Điều kiện cho trước: Một cạnh và đường cao tương ứng với cạnh đó + Kết quả cần thu được: Diện tích hình tam giác 2. Quá trình giải bài toán trên máy tínha. Khái niệm thuật toán - Thuật toán là dãy hữu hạn các thao tác cần thực hiện để giải một bài toán - 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áy tính thực hiện và cho kết quả - Chương trình chỉ là thể hiện của thuật toán trong một ngôn ngữ lập trình cụ thể Ví dụ Bài toán điều khiển rô-bốt nhặt rác: 1. Tiến 2 bước; 2. Quay trái, tiến 1 bước; 3. Nhặt rác; 4. Quay phải, tiến 3 bước; 5. Quay trái, tiến 2 bước; 6. Bỏ rác vào thùng; b. Quá trình giải bài toán trên máy tính Hình 1. Quá trình giải bài toán trên máy tính Quá trình giải bài toán trên máy tính gồm 3 bước: - Xác định bài toán: + Xác định thông tin đã cho (Input) + Thông tin cần tìm (Output) - Mô tả thuật toán: Tìm cách giải bài toán và diễn tả bằng các lệnh cần phải thực hiện - Viết chương trình: Dựa vào mô tả thuật toán, ta viết chương trình bằng một ngôn ngữ lập trình 3. Thuật toán và mô tả thuật toána. Khái niệm Mô tả thuật toán là liệt kê các bước cần thiết để giải một bài toán b. Các ví dụ Ví dụ 1:Thuật toán 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 Các bước thực hiện để pha trà mời khách: + Bước 1. Tráng ấm chén bằng nước sôi. + Bước 2. Cho một ít trà vào ấm. + Bước 3. Tráng trà + Bước 4. Rót nước sôi vào ấm và đợi 3 – 4 phút + Bước 5. Rót trà ra chén để mời khách Ví dụ 2: Thuật toán "Làm món trứng tráng" + Input: Trứng, dầu ăn, muối, hành + Output: Món trứng tráng - Các bước thực hiện để làm món 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 quấ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 1 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 1. Khái niệm bài toán - Bài toán là một việc nào đó mà con người muốn máy tính thực hiện. - Các yếu tố của một bài toán: + Input: Thông tin đã biết, thông tin đưa vào máy tính. + Output: Thông tin cần tìm, thông tin lấy ra từ máy tính. - Ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương, khi đó: + Input: hai số nguyên dương A, B. + Output: ước chung lớn nhất của A và B 2. Khái niệm thuật toán a) Khái niệm Thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 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. b) Biểu diễn thuật toán - Sử dụng cách liệt kê: nêu ra tuần tự các thao tác cần tiến hành. - Sử dụng sơ đồ khối để mô tả thuật toán.  c) Các tính chất của thuật toán - Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác. - Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo. - Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm. 3. Một số ví dụ về thuật toán Ví dụ 1: Kiểm tra tính nguyên tố của 1 số nguyên dương • Xác định bài toán - Input: N là một số nguyên dương; - Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″. Xem thêm: Hoán Vị, Chỉnh Hợp, Tổ Hợp Và Bài Tập Tổ Hợp Xác Suất Có Đáp Án
A. Lý Thuyết • Nội dung chính - Khái niệm về bài toán và xác định bài toán - Quá trình giải bài toán trên máy tính - Thuật toán và cách thức mô tả thuật toán 1. Xác định bài toán - Khái niệm bài toán: là 1 công việc hay 1 nhiệm vụ cần được giải quyết. - Xác định bài toán là đi xác định điều kiện cho trước và xác định kết quả cần thu được. - Ví dụ: Tính diện tích tam giác + Điều kiện cho trước: 3 cạnh của tam giác + Kết quả cần thu được: Diện tích tam giác 2. Quá trình giải bài toán trên máy tính - Máy tính hoạt động dưới sự chỉ đạo của con người, để giải quyết 1 bài toán trên máy tình là đưa cho máy tính dãy hữu hạn các thao tác đơn giản mà nó có thể thực hiện để từ các điều kiện cho trước, ta được kết quả cần tìm. - Khái niệm thuật toán: các thao tác cần thiết để giải quyết 1 bài toán. - Quá tình giải bài toán gồm các bước: + B1: Xác định bài toán, bao gồm xác định điều kiện cho trước và xác định kêt quả cần đạt được + B2: Mô tả thuật toán, liệt kê các thao tác cần thực hiện. + B3: Viết chương trình, dùng thuật toán vừa viết ra chuyển thành chương trình để máy tính có thể hiểu và thực hiện. 3. Mô tả thuật toán - Xét ví dụ: 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 + B1: Tráng ấm, chén bằng nước sôi + B2: Cho trà vào ấm + B3: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút. + B4: Rót trà ra chén để mời khách. - Khái niệm thuật toán: là dãy các thao tác cần thực hiện theo 1 trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước. - Khái niệm mô tả thuật toán: là việc liệt kê các bước thực hiện công việc( như ví dụ pha trà). Các bước của thuật toán thực hiện tuần tự từ trên xuống dưới. 4. Một số ví dụ về thuật toán Ví dụ 1: một hình A được ghép từ hình chữ nhật với chiều rộng 2a, chiều dài b và 1 hình bán nguyệt bán kính a như hình 5.2 INPUT: các số a là ½ chiều rộng của hình chữ nhật và là bán kính của hình bán nguyệt, b là chiều dài của HCN. OUTPUT: Diện tích của A Thuật Toán: B1: tính S hình chữ nhật, S1 = 2a∗b; B2: tính S hình bán nguyệt, S2 = πa2/2; B3: tính S tổng, S = S1 + S2; Ví dụ 2: 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. Thuật toán: - B1: SUM 0; I 0. - B2: SUM SUM + I; I I + 1. - B3: nếu I ≤ 100, thì quay lại bước 2. Ngược lại, thông báo giá trị SUM và kết thúc thuật toán. Ví dụ 3: Đổi giá trị của 2 biến x và y., INPUT: Hai biến x, y có giá tri tương ứng là a và b OUTPUT: Hai biến x, y có giá trị tương ứng là b và a Thuật Toán: - B1: z := x, khi đó z có giá trị là a - B2: x := y, khi đó x có giá trị là b - B3: y := z, khi đó y có giá trị là a. Ví dụ 4: Cho hai số thực a, b. Hãy cho biết kết quả so sánh hai số đó dưới dạng ″a lớn hơn b″, ″a nhỏ hơn b″ hoặc ″a bằng b″. INPUT: hai số thực a và b OUTPUT: kết quả so sánh Thuật Toán: - B1: Nếu a >b, kết quả là ″a lớn hơn b″ và chuyển đến Bước 3 - B2: Nếu a < b, kết quả là "a nhỏ hơn b"; ngược lại, kết quả là ″a bằng b″ - B3: Kết thúc thuật toán Ví dụ 5: Tìm số lớn nhất trong dãy các số A1, A2,… An cho trước. INPUT: Dãy A các số A1, A2,.. An ( n ≥ 1) OUTPUT: Giá trị MAX = max{A1, A2,..An} Thuật Toán: - B1: MAX := A1, I := 1. - B2: Nếu Ai > MAX, gán MAX := Ai. - B3: I := i+1. - B4: Nếu I ≤ n, quay lại bước 2. - B5: Thông báo giá trị MAX và kết thúc thuật toán. B. Bài tập trắc nghiệm Câu 1:Quá trình giải bài toán trên máy tính gồm mấy bước? A. 2 B. 3 C. 4 D. 5
Quá trình giải bài toán trên máy tính gồm 3 bước + B1: Xác định bài toán, bao gồm xác định điều kiện cho trước và xác định kêt quả cần đạt được + B2: Mô tả thuật toán, liệt kê các thao tác cần thực hiện. + B3: Viết chương trình, dùng thuật toán vừa viết ra chuyển thành chương trình để máy tính có thể hiểu và thực hiện. Đáp án: B Câu 2:Thứ tự các bước giải bài toán trên máy tính: A. Xác định bài toán → Viết chương trình → Mô tả thuật toán B. Xác định bài toán → Mô tả thuật toán → Viết chương trình C. Mô tả thuật toán → Xác định bài toán → Viết chương trình D. Viết chương trình → Xác định bài toán → Mô tả thuật toán
các bước giải bài toán trên máy tính là: Xác định bài toán (xác định Input, Output) → Mô tả thuật toán (các bước giải bài toán) → Viết chương trình (dùng ngôn ngữ lập trình để viết chương trình giúp máy tính hiểu và thực hiện được). Đáp án: B Câu 3:Hãy cho biết kết quả sau khi thực hiện thuật toán sau: Bước 1. Tam←x; Bước 2. x←y; Bước 3. y← tam; A. Giá trị của biến x bằng giá trị của biến y B. Hoán đổi giá trị hai biến x và y C. Giá trị của biến y bằng giá trị của biến x D. Khác
kết quả thuật toán trên là hoán đổi giá trị hai biến x và y. với ý tưởng thuật toán là: - B1: tam:= x, khi đó tam có giá trị của x - B2: x := y, khi đó x có giá trị của y - B3: y := tam, khi đó y có giá trị của x. Đáp án: B Câu 4:Hãy xác đinh bài toán sau: "Tìm số lớn nhất trong dãy n số tự nhiên cho trước"? A. INPUT: Dãy n số tự nhiên. OUTPUT: Số lớn nhất trong dãy n số. B. INPUT: Dãy n số tự nhiên. OUTPUT: Số các số lớn nhất trong dãy n số. C. INPUT: Số lớn nhất trong dãy n số. OUTPUT: Dãy n số tự nhiên. D. INPUT: Số các số lớn nhất trong dãy n số. OUTPUT: Dãy n số tự nhiên.
Trong bài toán thì Input là giá trị đề bài đã cho, Output là giá trị cần tìm. Vậy trong bài toán trên INPUT là dãy n số tự nhiên. OUTPUT là số lớn nhất trong dãy n số. Đáp án: A Câu 5:Hãy chọn phát biểu Đúng: A. Các bước giải bài toán trên máy tính là: Mô tả thuật toán → Xác định bài toán → Viết chương trình B. Cần phải xác định bài toán trước khi giải bài toán trên máy tính C. Máy tính có hiểu được chương trình viết bằng ngôn ngữ tự nhiên D. Với mỗi bài toán cụ thể, phải lựa chọn ngôn ngữ lập trình phù hợp rồi mới xây dựng thuật toán giải bài toán đó
Để giải một bài toán cần phải xác định bài toán (Input, Output) trước khi giải bài toán trên máy tính. Đáp án: B Câu 6:Hãy chọn phát biểu Sai? A. Việc thực hiện cả 3 bước khi giải bài toán trên máy tính là cần thiết, nhất là đối với bài toán phức tạp B. Xác định bài toán là xác định rõ các điều kiện cho trước và kết quả cần thu được C. Dãy hữu hạn các thao tác cần thực hiện để giải một bài toán được gọi là thuật toán D. Đối với mỗi bài toán cụ thể chúng ta chỉ có 1 thuật toán duy nhất để giải bài toán đó trên máy tính
Đối với mỗi bài toán cụ thể chúng ta có thể có 1 hoặc nhiều thuật toán (lời giải) để giải bài toán đó trên máy tính. Nhưng mỗi thuật toán chỉ giải một bài toán cụ thể. Đáp án: D Câu 7:Xác định bài toán: “ kiểm tra n có phải là số nguyên tố hay không? ” A. Input: Nhập số n; Output: n là số nguyên tố hoặc n không là số nguyên tố B. Input: n là số nguyên tố hoặc n không là số nguyên tố; Output: Nhập số n C. Input: n là số nguyên tố; Output: Nhập số n D. Input: Nhập số n; Output: n là số nguyên tố
xác định bài toán: + Input là điều kiện cho trước + Output là kết quả cần thu được. Đáp án: A Câu 8:Thuật toán là: A. Dãy các thao tác cần thực hiện theo 1 trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước. B. Một thao tác cần thực hiện để thu được kết quả cần thiết từ những điều kiện cho trước. C. Dãy các thao tác cần thực hiện để thu được kết quả cần thiết từ những điều kiện cho trước. D. Tất cả đều sai
thuật toán là dãy các thao tác cần thực hiện theo 1 trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước. Đáp án: Câu 9:Mô tả thuật toán là: A. Liệt kê các bước thực hiện công việc. B. Liệt kê các cách thực hiện công việc. C. Liệt kê một bước thực hiện công việc. D. Tất cả đều đúng
Mô tả thuật toán là việc liệt kê các bước thực hiện công việc. Các bước của thuật toán thực hiện tuần tự từ trên xuống dưới. Đáp án: A Câu 10:Mô tả thuật toán pha trà mời khách + B1: Tráng ấm, chén bằng nước sôi + B2: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút. + B3: Cho trà vào ấm + B4: Rót trà ra chén để mời khách. A. B1- B3-B4- B2 B. B1- B3- B2-B4 C. B2-B4-B1-B3 D. B3-B4-B1-B2
Mô tả thuật toán pha trà mời khách + B1: Tráng ấm, chén bằng nước sôi + B2: Cho trà vào ấm + B3: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút. + B4: Rót trà ra chén để mời khách. Đáp án: B |
