Giáo án Tin học 10 - Bài 4: Bài toán và thuật toán

Nội dung tài liệu: Giáo án Tin học 10 - Bài 4: Bài toán và thuật toán

1. Tuần: 5, tiết: 9, 10, 11, 12, 13, 14 Bài 4: BÀI TOÁN VÀ THUẬT TOÁN I. MỤC TIÊU: - Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán. - Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước. - Biểu diễn được thuật toán bằng liệt kê hoặc bằng sơ đồ khối. II. NỘI DUNG BÀI HỌC 1. Khái niệm bài toán: Trong phạm vi tin học bài toán là một việc nào đó ta muốn máy tính thực hiện. Ví dụ: - Viết một dòng chữ ra màn hình; - Giải phưng trình bậc hai - Quản lí học sinh trong trường học . ❖ Các thành phần cơ bản của một bài toán Toán học Tin học Thuật ngữ •Giả thiết • Đưa vào máy tính thông tin gì • Input •Kết luận • Cần lấy ra thông tin gì • Output Kết luận: Trong tin học để phát biểu một bài toán cần trình bày rõ Input và Output của bài toán đó. Ví dụ 1: Giải pt bậc 2: ax 2 bx c 0 (a 0) • Input: Các số thực a, b, c (a 0). • Output: Số thực x thoả ax 2 bx c 0 Ví dụ 2: Tìm ước chung lớn nhất của hai số nguyên dương a và b. • Input: Cho hai số nguyên dương a và 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: 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. b. Mô tả các thao tác trong thuật toán Có hai cách: Liệt kê và sơ đồ khối. Cách 1: Liệt kê Ví dụ: Tìm nghiệm phương trình bậc nhất tổng quát. B1: Nhập a, b B2: Nếu a chuyển đến B5 B3 Nếu b=0 thi trả lơi PT vô số nghiệm -> chuyển đến B5 B4 Trả lời Phương trình vô nghiệm -> chuyển đến B5 B5 Kết thúc. Cách 2: Sơ đồ khối. Dùng một só khối và đường có mũi tên trong sơ đồ khối. •Hình thoi thể hiện các thao tác so sánh. •Hình chữ nhật thể hiện các phép tính toán. •Hình ô van thể hiện các thao tác nhập, xuất dữ liệu. Các mũi tên → quy định trình tự thực hiện các thao tác. VD: về sơ đồ khối tìm nghiệm của phương trình bậc nhất tổng quát.
2. ❖ Một số 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 một 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 một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để thực hiện bước 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. c. Ví dụ: Bài toán tìm giá trị lớn nhất (Max) của một dãy số nguyên Bài toán: Cho dãy số nguyên a1, a2, , aN. Hãy tìm giá trị lớn nhất (Max) của dãy số trên. Input: Nhập N và dãy a1 . . . aN Output: Đưa ra GTLN (Max) Thuật toán: Liệt kê: Sơ đồ khối B1: Nhập N và dãy số a1,a2, , aN. B2: Max  a1, i 2; B3: Nếu i>N thì đưa ra giá trị Max rồi kết thúc B4: B4.1: Nếu ai > Max thì Max  ai B4.2: i i+1 rồi quay lại bước 3; ❖ Chú ý: Dấu mũi tên () trong thuật toán trên biểu diễn cho phép gán. Ví dụ1: Bài toán tìm Max đã xét - Tính dừng: Vì giá trị của i mỗi lần tăng lên 1 nên sau N lần thì i> N, khi đó kết quả so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc. - Tính xác định: Thứ tự thực hiện các phép toán được mặc định là tuần tự nên sau bước 1 là bước 2, sau bước 2 là bước 3. Kết quả so sánh trong bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cần thực hiện. - Tính đúng đắn: Vì thuật toán so sánh Max với từng số hạng của dãy số và thực hiện Max ← a i nếu Max < ai nên sau khi so sánh hết N số hạng của dãy thì Max là giá trị lớn nhất.
3. 3. Một số ví dụ về thuật toán ❖ Ví dụ 1: Mô tả thuật toán giải phương trình bậc 2. Xác định bài toán. Input: Ba số thực a, b, c (a 0). Output: Kết luận về nghiệm của pt. Ý tưởng: - Kiểm tra a. - Tính . - Kiểm tra . - Tìm nghiệm. • Thuật toán: Mô tả theo cách liệt kê. B1. Nhập ba số a, b, c. B2. Nếu a = 0 thì quay lại B1 B3. Tính  b2 – 4ac. B4. Nếu < 0 thì thông báo ptvn rồi kết thúc. Ngược lại chuyển sang B5. b B5. Nếu = 0 thì x  ; thông báo pt có nghiệm kép x rồi kết thúc. Ngược lại chuyển sang B6. 2a b b B6. Nếu > 0 thì x1  , x2  ; thông báo pt có 2 nghiệm x1 và x2, rồi kết thúc. 2a 2a b7. Kết thúc. ❖ Ví dụ 2: Tìm ước chung lớn nhất(ƯCLN) của hai số nguyên dương M, N . Xác định bài toán: Input: Cho M, N nguyên dương. Output: ƯCLN(M,N). Cách 1: Liệt kê các bước; Cách 2: Sơ đồ khối; B1: Nhập M, N; B2: Nếu M = N thì trả lời ƯCLN = M (hoặc N), chuyển đến B5; B3: Nếu M >N thì M  M - N rồi quay lại B2; B4: N  N – M rồi quay B2; B5: Đa ra kết quả ƯCLN; Kết thúc. ❖ Ví dụ 3: Bài toán tìm kiếm Cho dãy A gồm N số nguyên, đôi một khác nhau: a1, a2,..., aN và một số nguyên k. Cần biết có hay không chỉ số i (1 i N) mà ai = k. Nếu có hãy cho biết chỉ số đó. Số nguyên k được gọi là khoá tìm kiếm (gọi tắt là khoá). Xác định bài toán - Input: Dãy A gồm N số nguyên đôi một khác nhau a1, a2,..., aN và số nguyên k; - Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k. Ý tưởng: Tìm kiếm tuần tự được thực hiện một cách tự nhiên. Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.
4. • Thuật toán tìm kiếm tuần tự a) Cách liệt kê b/ Sơ đồ khối Bước 1: Nhập N, các số hạng a 1, a2,..., aN và khoá k; Bước 2: i  1; Bước 3: Nếu a i = k thì thông báo chỉ số i, rồi kết thúc; Bước 4: i  i + 1; Bước 5: Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc; Bước 6: Quay lại bước 3. ❖ Bài tập 1: Cho dãy A gồm N số nguyên: a1, a2,..., aN và một số k . Đếm trong dãy A có bao nhiêu phần tử bằng k. Mô tả thuật toán: Xác định bài toán. Input: N, a1, a2, ...,an, k Output: Đếm trong dãy có bao nhiêu phần tử bằng k. Ý tưởng: Tìm trong dãy phần tử = k thi Đếm <- Đếm +1 Tìm cho đến khi hết các phần tử trong dãy thì kết thúc. Thuật toán: Bước 1: Nhập N, các số hạng a1, a2,..., aN và khoá k; Bước 2: i  1; Bước 3: Nếu ai = k thì demdem+1 Bước 4: i  i + 1; Bước 5: Nếu i > N thì thông báo có dem giá trị bằng k, rồi kết thúc; Bước 6: Quay lại bước 3. ❖ Bài tập 2: Cho dãy A gồm N số nguyên: a 1, a2,..., aN và một số k . Tính tổng các phần tử bằng K trong dãy.. Xác định bài toán: Input: Dãy A gồm N số nguyên dương a1, , aN. Output: : Tính tổng các phần tử bằng K trong dãy. Ý tưởng: Tìm trong dãy phần tử ai = k thi Tong<- Tong + ai Tìm cho đến khi hết các phần tử trong dãy thì kết thúc Đưa ra kết quả tong. Thuật toán: Bước 1: Nhập N, các số hạng a1, a2,..., aN; Bước 2: i  1; Bước 3: Nếu ai = k thì Tong  Tong +ai Bước 4: i  i + 1; Bước 5: Nếu i > N thì thông báo Tong, rồi kết thúc; Bước 6: Quay lại bước 3.
5. ❖ Bài tập 3: Cho dãy A gồm N số nguyên: a 1, a2,..., aN và một số k . Tính trung bình cộng các phần tử bằng k trong dãy.. Xác định bài toán: Input: Dãy A gồm N số nguyên dương a1, , aN. Output: : Tính trung bình cộng các phần tử dương trong dãy. Ý tưởng: Tìm trong dãy phần tử ai = 0 thi Tong<- Tong + ai và Dem  Dem +1 Tìm cho đến khi hết các phần tử trong dãy thì TBC  Tong div Dem Kết thúc Đưa ra kết quả trung bình cộng. Thuật toán: Bước 1: Nhập N, các số hạng a1, a2,..., aN; Bước 2: i  1; Bước 3: Nếu ai = k thì Tong  Tong +ai và Dem Dem +1 Bước 4: i  i + 1; Bước 5: Nếu i > N thì TBC  Tong div Dem , Thông báo TBC, rồi kết thúc; Bước 6: Quay lại bước 3. III. CỦNG CỐ, LUYỆN TẬP Câu 1 : Khi dùng máy tính giải toán ta cần quan tâm đến các yếu tố : Đưa vào máy thông tin gì ( Input ) . Cần lấy ra thông tin gì ( Output ) . Phương pháp giải toán . Cả hai câu a , b đều đúng . Câu 2: Một thuật toán phải có các tính chất sau. Tính dừng Tính đúng đắn Tính xác định Cả 3 câu trên đều đúng Câu 3 : Bài toán tìm Max, xác định Output: Output: Số nguyên dương N và dãy N số nguyên a1, ,aN Output: Số nguyên dương N Output: Dãy N số nguyên dương a1, ,aN Output: Giá trị lớn nhất Max Câu 4 : Bài toán tìm kiếm tuần tự, xác định Input: Input: Dãy A gồm N số nguyên khác nhau a1, ,aN và số nguyên k Input: Dãy A gồm N số nguyên a1, ,aN và số nguyên k Input: Dãy A gồm N số nguyên khác nhau a1, ,aN Input: Dãy A gồm N số nguyên k Câu 5 : Bài toán tìm kiếm tuần tự, xác định Output: Output: Dãy A gồm N số nguyên khác nhau a1, ,aN và số nguyên k Output: Dãy A gồm N số nguyên a1, ,aN và số nguyên k Output: Chỉ số i mà ai=k hoặc thông báo không có giá trị nào của dãy A bằng k Output: Thông báo tìm thấy số Câu 6 : Cho Thuật toán sau đây, Hỏi Thuật toán làm công việc gì? B1: Nhập vào 2 số nguyên dương a và N B2: Nếu N= 0 thì thông báo kết quả bằng 1 -->B7 Ngược lại : B3 B3: M <-- a ; i:=2; B4: Nếu i> N thì Thông báo M --> B7 B5: M <-- M * a B6: i <-- i+1 ; quay lên B4 B7: Kết Thúc A.Tính lũy thừa aN B. Tính tích a x2 x3 x . xN xa C.Tính lũy thừa Na D.Tính tích của a với N
6. Câu 7 : Cho thuật toán sau. Với x=3, n=3 cho biết kết quả của S và T sau khi thực hiện thuật toán: B1 : Nhập n, x; B2 : s<--0 ; i<--1 ;T<--0 ; B3 : Nếu i>n thì thông báo S, T ; kết thúc B4 : T<--T * X ; B5 : S<--S+T B6 : i<--i+1 ; quay lại B3. A. S= 0, T= 27 B. S= 39, T= 27 C. S=0, T=0 D. Không tìm được kết quả S,T Câu 8 : Cho thuật toán sau: Với X= 45; Y= - 45. Sau khi thực hiện thuật toán sau, hãy cho biết kết quả X, Y B1 : Nhập X, Y ; B2 : Z<--X ; B3 : X<--Y ; B4 : Y<--Z ; B5 : thông báo giá trị X, Y rồi kết thúc A. X= 0, Y= 456 B. X= - 45 , Y= 45 C. X= 56, Y= 0 D. Không tìm được kết quả X, Y Câu 9 : Khi mô tả thuật toán bằng sơ đồ khối thì dùng các ký hiệu hình học nào ? A. Hình thoi, hình ô van, hình vuông, mũi tên B. Hình chữ nhật, hình thoi, hình ô van, mũi tên C. Hình chữ nhật, hình tròn, hình vuông, mũi tên D. Hình ô van, hình vuông, hình tròn, hình chữ nhật Câu 10 : Cho thuật toán sau. Với x=3, n=3 cho biết kết quả của S và T sau khi thực hiện thuật toán: B1 : Nhập n, x; B2 : s<--0 ; i<--1 ;T<-- -1 ; B3 : Nếu i>n thì thông báo S, T ; kết thúc B4 : T<--T * X ; B5 : S<--S+T B6 : i<--i+1 ; quay lại B3. A. S= -39, T= -27 B. S= 39, T= 27 C. S=0, T=0 D. Không tìm được kết quả S,T IV. DẶN DÒ - Nắm vững khái niệm bài toán và thuật toán trong tin học. - Diễn tả được thuật toán. - Học bài - Sử dụng các kí hiệu trên diễn đạt lại thuật toán giải phương trình bậc hai - Tìm hiểu xem từ định nghĩa thuật toán ta cần chú ý những điều gì. - Làm bài tập 1, 2, 3, 4, 5, 7 sách giáo khoa trang 44 - Làm bài tập trang 17, 18, 19 sách bài tập.