Bài giảng Tin học 10 - Bài 4: Bài toán và thuật toán

Vũ Thị Dung_K59A_CNTT_ĐHSPHN1CHÀO MỪNG QUÝ THẦY CÔ ĐẾN DỰ GiỜVỚI LỚP 10A1Chào mừng các thầy cô về dự giờLớp 10A3TRƯỜNG THPT TRẦN VĂN LANGiáo viên: Vũ Thị Dung122Kiểm tra bài cũHãy trình bày khái niệm bài toán, các thành phần của một bài toán và các cách biểu diễn thuật toán?Bµi 4 Bài toán và thuật toán Tin học 10Thuật toán tìm giá trị lớn nhất của một dãy số nguyêna. Xác định bài toán Input: Số nguyên dương N và dãy N số nguyên a1,..., aNEm hãy xác định Input và Output của bài toán? Output: Giá trị lớn nhất Max của dãy sốb. Ý tưởng So sánh Đổi chỗTheo em, để tìm được Max thì phép toán thực hiện chủ đạo ở đây là gì?XÂY DỰNG: Giả sử có dãy 4 số phần tử a1, a2, a3, a4 Goïi Max laø giaù trò lớn nhaát caàn tìm Gaùn Max = a1 Xét a2 và so sánh a2 với Max:+ Nếu a2 > Max thì Max mới 1 = a2 + Nếu a2 Max mới 1 thì Max mới 2 = a3+ Nếu a3 Max mới 2 thì Max mới 3 = a4 + Nếu a4 Max?a3 >Max mới 1?a4 >Max mới 2? 11 6 20 8Max=11Max=20Giá trị lớn nhaát: 20=> Đối với dãy số có n phần tử thì làm như thế nào?b. Ý tưởng Khởi tạo giá trị Max = a1 Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là aic. Biểu diễn thuật toán Input: Số nguyên dương N và dãy N số nguyên a1,..., aN Output: Giá trị lớn nhất Max của dãy số Ý tưởng: Khởi tạo giá trị Max = a1 Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai Bước 1: Nhập N và dãy a1,..., aN; Bước 2: Max ← a1, i ← 2; Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc; Bước 4:Bước 4.1: Nếu ai > Max thì Max ← ai;Bước 4.2: i ← i + rồi quay lại bước 3.Biểu diễn theo cách liệt kêc. Biểu diễn thuật toán Biểu diễn bằng sơ đồ khốid. Mô phỏng thuật toán a1a2a3a4a5a6a7a8a9a10Dãy số615378109124i 2345678910ai > max?kkkccckckMax66667810101212e. Các tính chất của thuật toán 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ả phép 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 bước của thuật 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ả các phép 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 ← ai nếu > ai Max 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.Củng cố Bài học hôm nay các em cần nắm được:Input và Output của thuật toán tìm Max; Biểu diễn thuật toán tìm Max theo cách liệt kê hoặc sơ đồ khối. Bài tập về nhàBiểu diễn thuật toán tìm giá trị nhỏ nhất của một dãy số nguyên bằng phương pháp liệt kê hoặc sơ đồ khối.Mô phỏng thuật toán với dãy số sau:15 3 8 9 7 18 213. Đọc trước thuật toán kiểm tra tính nguyên tố của một số nguyên dươngCảm ơn sự quan tâm theo dõi của các thầy cô và các em