Lý thuyết tổng hợp Tin học 8 Bài 5: Từ bài toán đến chương trình chọn lọc năm 2021 – 2022 mới nhất gồm tóm tắt lý thuyết và hơn 500 bài tập ôn luyện Tin 8. Hy vọng bộ tổng hợp lý thuyết Tin học lớp 8 sẽ giúp học sinh củng cố kiến thức, ôn tập và đạt điểm cao trong các bài thi trắc nghiệm môn Tin học 8.
Bạn đang xem: Thuật toán là gì tin 8
Bài 5: Từ bài toán đến chương trình
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 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 đótamcó 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ố
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.
Xem thêm: Lắng đọng cảm xúc ngày ra trường của học sinh lớp 9 trong lễ ra trường
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.
Bạn đang xem tài liệu "Tin học 8 - Bài 4: Bài toán và thuật toán", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tuần 5,6Ngày soạn: 04/09Tiết 10,11,12Ngày dạy:§4. BÀI TOÁN VÀ THUẬT TOÁN I. Mục tiêu1. Kiến thức- Học sinh biết khái niệm về Bài toán và thuật toán, các tính chất của thuật toán- Học sinh chỉ ra được Input và Output của mỗi bài toán đưa ra.2. Kỹ năng - Hiểu và nhận biết được Input và Output trong mỗi bài toán. 3. Thái độ - Chú ý nghe giảng, hăng hái phát biểu ý kiến. - Có thái độ học tập nghiêm túc. II. Chuẩn bị của giáo viên và học sinh 1. Chuẩn bị của giáo viên: SGK, Giáo án, Tài liệu tham khảo. 2. Chuẩn bị của học sinh: SGK, vở ghi
III. Phương pháp: Hướng dẫn giảng giải, minh họa trực quan, nêu câu hỏi để học sinh thảo luận trả lời. Hoạt động nhóm, hoạt động cá nhân
IV. Hoạt động dạy - học 1. Ổn định tổ chức 2. Kiểm tra bài cũ: 3. Nội dung bài mới
Hoạt động của thầy và trò
Nội dung
GV: Đặt vấn đề: Để viết được chương trình cho máy tính thực hiện ta cần biết thế nào là thuật toán và bài toán. Đó chính là nội dung của bài học hôm nay.GV: Trong toán học "Bài toán" được hiểu là những việc mà con người cần phải thực hiện sao cho từ những dữ liệu đã có phải tìm ra kết quả hay chứng minh một kết quả nào đó. Vậy khái niệm "Bài toán" trong Tin học có gì khác không ?
HS: Trả lời.GV: Trong nhà trường có phần mềm quản lý học sinh : Nếu ta yêu cầu đưa ra những học sinh có điểm trung bình từ 7 trở lên, đó là bài toán. Hay đơn gian hơn yêu cầu máy tính cho ra kết quả của một phép tính nhân, chia,... Đó cũng là bài toán. Vậy bài toán là gì ?
HS: Suy nghĩ và trả lời.GV: Để giải được một bài toán thì công việc đầu tiên ta cần làm là gì ?
HS: Cụng việc đầu tiên là đi xỏc định đâu là dữ kiện đó cho và đâu là cái cần tìm.1. Bài toán* Khái niệm: Bài toán là những việc mà con người muốn máy tính thực hiện.* Các yếu tố: Khi máy tính giải bài toán cần quan tâm đến 2 yếu tố:- Input (Thông tin đưa vào máy)- Output (Thông tin muốn lấy ra từ máy)GV: Ta cần đi xác định đầu vào (Input) và đầu ra (Output) của bài toán. Input là thông tin được đưa vào máy, Output là thông tin cần lấy ra khỏi máy.nput của bài toàn là gì ?
Output của bài toàn là gì ?
HS: Đứng tại chỗ trả lời câu hỏi
GV: Cho học sinh lấy thêm ví dụ và phân tích đâu là Input và đâu là Output.HS: Trả lời.GV: Muốn máy tính đưa ra được Output từ Input đã cho thì cần phải có chương trình, mà muốn viết chương trình thì cần phải có thuật toán. Vậy thuật toán là gì ?
HS: Trả lời.GV: Giải thích thêm về các khái niệm như: Dãy hữu hạn các lệnh, sắp xếp theo một trình tự nhất định.HS: Lắng nghe và ghi nhớ.GV: Đưa ra ví dụ tìm UCLN của 2 số M và N. Xác định Input và Output của bài toán.HS: Đứng tại chỗ xác định Input và Output
GV: Ghi thuật toán lên bảng GV: Lấy ví dụ cụ thể với 2 số (12,8) và giải thích thuật toán qua từng bước:B1: Nhập M=12, N=8 --> M>NB2: M=12-8=4, N=8-->N>MB3: M=4, N=8-4=4 --> M=N => UCLN(M,N)=4GV: Cách viết thuật toán theo từng bước như trên gọi là cách liệt kê, còn có cách làm khác đó là dùng Sơ đồ khối.HS: Lắng nghe.GV: Lấy lại ví dụ tìm UCLN của 2 số M,NGV: Vẽ sơ đồ thuật toán lên bảng. Chỉ cho học sinh thấy các bước của thuật toán được mô tả trong sơ đồ.HS: Ghi lại sơ đồ thuật toán và hình dung ra các bước giải của thuật toán.GV: Xoá các ghi chú Đ và S trên sơ đồ, yêu cầu 1 học sinh viết lại và giải thích vì sao ?
HS: Lên bảng điền lại các ghi chú và giải thích vì sao lại điền như thế.2. Thuật toán- Khái niệm thuật 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.- Tác dụng của thuật toán: Dùng để giải một bài toán.- Ví dụ: Thuật toán tìm UCLN của 2 số M, N.* Xác định bài toán + Input: M, N + Ontput: UCLN(M, N)* ý tượng: - Nếu M = N thì gán UCLN=M - Nếu M > N thì gán M = M - N - Nếu M N thì thay M= M - N, rồi quay lại B2.-B4: Nếu MN ?
Đưa ra
UCNN là M và Kết thúc
N