Bài giảng Tin học đại cương - Bài 4: Giải quyết bài toán - Đỗ Bá Lâm

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TIN HỌC ĐẠI CƯƠNG Bài 4: Giải quyết bài toán Đỗ Bá Lâm lamdb@soict.hut.edu.vn Nội dung 4.1. Bài toán (problem) 4.2. Giải quyết bài toán bằng máy tính 4.3. Biểu diễn thuật toán 4.4. Các phương pháp thiết kế thuật toán 2 Nội dung 4.1. Bài toán (problem) 4.2. Giải quyết bài toán bằng máy tính 4.3. Biểu diễn thuật toán 4.4. Các phương pháp thiết kế thuật toán 3 4.1. Bài toán (problem) • “Bài toán” hay “Vấn đề” – Vấn đề có nghĩa rộng hơn bài toán – Bài toán là một loại vấn đề mà để giải quyết phải liên quan ít nhiều đến tính toán: bài toán trong vật lý, hóa học, xây dựng, kinh tế • Hai loại vấn đề – Theorema: là vấn đề cần được khẳng định tính đúng sai. – Problema: là vấn đề cần tìm được giải pháp để đạt được một mục tiêu xác định từ những điều kiện ban đầu nào đó. 4 4.1. Bài toán (2) • Biểu diễn vấn đề-bài toán A → B • A: Giả thiết, điều kiện ban đầu • B: Kết luận, mục tiêu cần đạt • Giải quyết vấn đề-bài toán – Từ A dùng một số hữu hạn các bước suy luận có lý hoặc hành động thích hợp để đạt được B – Trong Tin học, A là đầu vào, B là đầu ra 5 Nội dung 4.1. Bài toán (problem) 4.2. Giải quyết bài toán bằng máy tính 4.3. Biểu diễn thuật toán 6 4.2. Giải quyết bài toán bằng máy tính • Lập trình viên là người phân tích vấn đề, tạo ra các chỉ dẫn để giải quyết vấn đề và máy tính sẽ thực hiện các chỉ dẫn đó • Phương án giải quyết bài toán được gọi là thuật toán/giải thuật trong tính toán • Một thuật toán là: – một dãy hữu hạn các thao tác và trình tự thực hiện các thao tác đó sao cho sau khi thực hiện dãy thao tác này theo trình tự đã chỉ ra, với đầu vào (input) ta thu được kết quả đầu ra (output) mong muốn. 7 4.2. Giải quyết bài toán bằng máy tính • Không chỉ đơn giản là lập trình • Phức tạp, gồm nhiều giai đoạn phát triển • Các giai đoạn quan trọng – Bước 1. Xác định yêu cầu bài toán – Bước 2. Phân tích và thiết kế bài toán • Lựa chọn phương án giải quyết (thuật toán) • Xây dựng thuật toán – Bước 3. Lập trình – Bước 4. Kiểm thử và hiệu chỉnh chương trình – Bước 5. Triển khai và bảo trì 8 Nội dung 4.1. Bài toán (problem) 4.2. Giải quyết bài toán bằng máy tính 4.3. Biểu diễn thuật toán 9 10 4.2. Biểu diễn thuật toán • Cách 1: Ngôn ngữ tự nhiên • Cách 2: Ngôn ngữ lưu đồ (lưu đồ/sơ đồ khối) • Cách 3: Mã giả (pseudocode) gọi là ngôn ngữ mô phỏng chương trình PDL (Programming Description Language). • Cách 4: Các ngôn ngữ lập trình như Pascal, C/C++ hay Java. Tuy nhiên, không nhất thiết phải sử dụng đúng ký pháp của các ngôn ngữ đó mà có thể được bỏ một số ràng buộc. 4.2.1. Ngôn ngữ tự nhiên • Sử dụng một loại ngôn ngữ tự nhiên để liệt kê các bước của thuật toán • Ưu điểm – Đơn giản – Không yêu cầu người viết và người đọc phải có kiến thức nền tảng • Nhược điểm – Dài dòng – Không làm nổi bật cấu trúc của thuật toán – Khó biểu diễn với những bài toán phức tạp 11 12 Ví dụ 1 • Bài toán: Đưa ra kết luận về tương quan của hai số a và b (>, < hay =). – Đầu vào: Hai số a và b – Đầu ra: Kết luận a>b hay a<b hay a=b. • Ý tưởng: – So sánh a và b rồi đưa ra kết luận 13 VD1 - Ngôn ngữ tự nhiên (tuần tự các bước) • B1: Nhập số a và số b. • B2: Nếu a> b, hiển thị “a>b” và kết thúc • B3: Nếu a=b, hiển thị “a=b” và kết thúc • B4: (a<b) Hiển thị “a<b” và kết thúc. 4.2.1. Sơ đồ khối Bắt đầu hoặc kết thúc Thao tác tính toán hoặc phức tạp Lệnh vào, lệnh ra (read hoặc write) Kiểm tra điều kiện Luồng thực hiện Nối tiếp đoạn lệnh Một số khối trong sơ đồ khối dùng biểu diễn thuật toán 14 15 Ví dụ 1 - Mô tả bằng lưu đồ thuật toán Biểu diễn thao tác so sánh Thể hiện thao tác bắt đầu hoặc kết thúc Nhập a, b a>b a=b Hiển thị “a>b” Hiển thị “a=b” Hiển thị “a<b” Đ Đ S S 4.2.1. Sơ đồ khối (2) • Ưu điểm – Trực quan, dễ hiểu, dễ thiết kế – Cung cấp toàn cảnh, tổng quan về thuật toán • Nhược điểm – Cồng kềnh, đặc biệt với bài toán phức tạp 16 4.3. Mã giả (pseudocode) • Ngôn ngữ tựa (gần giống) với ngôn ngữ lập trình được gọi là mã giả – Mệnh đề có cấu trúc – Ngôn ngữ tự nhiên • Ưu điểm – Tiện lợi, đơn giản – Dễ hiểu, dễ diễn đạt • Giới thiệu chi tiết trong bài sau 17 18 Ví dụ 2 • Bài toán: Đưa ra tổng, tích, hiệu, thương của hai số a và b. – Đầu vào: Hai số a và b – Đầu ra: Tổng, tích, hiệu và thương của a và b. • Ý tưởng: – Tính tổng, tích, hiệu của a và b – Nếu b khác 0, đưa ra thương – Nếu b bằng 0, đưa ra thông báo không thực hiện được phép chia 19 VD2 - Ngôn ngữ tự nhiên (tuần tự các bước) • B1: Nhập số a và số b. • B2: s  a + b; d  a – b; p  a * b • Hiển thị – Tổng là s – Hiệu là d – Tích là p • B3: Nếu b = 0, hiển thị “Không thực hiện được phép chia” và kết thúc • B4: (b0) Hiển thị “Thương là a/b” và kết thúc 20 Ví dụ 2 - Mô tả bằng lưu đồ thuật toán Nhập a, b b = 0 Hiển thị “Không thực hiện được phép chia” Hiển thị “Thương là a/b” s  a + b; d  a – b; p  a * b;Biểu diễn thao tác tính toán đơn giản hoặc phức tạp Hiển thị “Tổng là s, Hiệu là d, Tích là p” 21 Ví dụ 3 • Bài toán: Giải phương trình bậc I – Đầu vào: Hai hệ số a, b – Đầu ra: Nghiệm của phương trình ax + b = 0 • Ý tưởng: – Lần lượt xét a = 0 rồi xét b = 0 để xét các trường hợp của phương trình 22 Ví dụ 3 - Mô tả tuần tự các bước • B1: Nhập a và b. • B2: Nếu a0 thì hiển thị “Phương trình có 1 nghiệm duy nhất x = -b/a”. • B3: (a=0) Nếu b 0 thì hiển thị “Phương trình vô nghiệm” và kết thúc • B4: (a=0)(b=0) Hiển thị “Phương trình vô số nghiệm” và kết thúc Ví dụ 3 - Mô tả bằng lưu đồ thuật toán 23 Nhập a và b a0 Hiển thị “Nghiệm là: x = -b/a” b0 S S Đ Đ Hiển thị “Phương trình vô nghiệm” Hiển thị “Phương trình vô số nghiệm” 24 Ví dụ 4 • Bài toán: Tìm giá trị lớn nhất của một dãy số nguyên có N số – Đầu vào: Số số nguyên dương N và N số nguyên a1, a2,, aN – Đầu ra: số nguyên lớn nhất của dãy ak, k trong khoảng [1N] • Ý tưởng: – Khởi tạo giá trị Max = a1 – Lần lượt so sánh Max với ai với i=2,3,, N; nếu ai > Max ta gán giá trị mới cho Max Ví dụ 4 – Ý tưởng 25 3 5 7 9 2max 3 5max<5 max = 3 7 9 9 8 9 9 max<7 max<9 max>2 max>8 Kết quả 26 Ví dụ 4 - Mô tả tuần tự các bước • B1: Nhập N và dãy số a1, a2,,aN. • B2: Max  a1; i:=2. • B3: Nếu i > N, Hiển thị Max là giá trị lớn nhất của dãy và kết thúc • B4: Nếu ai > Max, Max  ai • B5: Tăng i lên 1 đơn vị. • B6: Quay lên B3. • B7: Kết thúc. 27 Ví dụ 4 - Mô tả bằng lưu đồ thuật toán Nhập N và dãy số a1, a2,,aN i > N Hiển thị “Max là số lớn nhất” Max  a1; i=2 ai > Max i i + 1 S S Đ Max  ai Đ 28 Bài tập • Bài toán: Giải phương trình bậc II – Đầu vào: Ba hệ số a, b, c – Đầu ra: Nghiệm của phương trình ax2 + bx + c = 0 • Ý tưởng: – Lần lượt xét a = 0, b = 0 rồi xét c=0 để xét các trường hợp của phương trình 29 Bài tập • Bài toán: Nhập vào ba số nguyên dương a, b, c. Cho biết đây có phải 3 cạnh của một tam giác vuông hay không? – Đầu vào: ba số a, b, c – Đầu ra: Kết luận tam giác vuông hay không • Ý tưởng: – Đìều kiện tam giác vuông • Điều kiện vuông: tổng bình phương 2 cạnh = bình phương cạnh còn lại 30 Bài tập • Bài toán: Nhập vào hai số nguyên dương a, b. Cho biết ước số chung lớn nhất của hai số – Đầu vào: hai số a, b – Đầu ra: USCLN của a, b • Ý tưởng: – Nếu a>b USCLN(a,b)=USCLN(a-b,b) – Nếu a<b USCLN(a,b)=USCLN(a,b-a) – Nếu a=b USCLN(a,b)=USCLN(a,a)=a 31 Ví dụ 5 • Bài toán: Sắp xếp bằng phương pháp tráo đổi (Exchange Sort) – Đầu vào: Dãy A gồm N số nguyên a1, a2,, aN – Đầu ra: Dãy A được sắp lại theo thứ tự không giảm. • Ý tưởng: – Với mỗi cặp số liên tiếp trong dãy, nếu số trước không lớn hơn số sau ta đổi chỗ chúng cho nhau. – Việc đó được lặp cho đến khi không có sự đổi chỗ nào cho nhau 32 Ví dụ 5 - Mô tả tuần tự các bước • B1: Nhập số N và dãy số a1,a2,,aN • B2: M  N. • B3: Nếu M < 2 thì thuật toán kết thúc và hiển thị dãy đó. • B4: M  M – 1, i  0. • B5: Tăng i lên 1 đơn vị. • B6: Nếu i > M thì quay lại B3. • B7: Nếu ai > ai+1 thì tráo đổi hai số đó cho nhau • B8: Quay lên B5. 33 S Đ Nhập N và dãy số a1, a2,,aN M < 2 Hiển thị Dãy đã sắp xếp M  N i > M S Đ ai ai+1 M M – 1, i  0 i i + 1 ai > ai+1 S Đ Ví dụ 5 - Mô tả bằng lưu đồ thuật toán 34 Các tiêu chí giải thuật cần thỏa mãn • Tính hữu hạn: giải thuật phải dừng sau một thời gian hữu hạn. • Khi kết thúc, giải thuật phải cung cấp kết quả đúng đắn. • Tính hiệu quả: – Thời gian tính toán nhanh – Sử dụng ít tài nguyên không gian như bộ nhớ, thiết bị, – Mang tính phổ dụng, dễ hiểu, dễ cài đặt và mở rộng cho các lớp bài toán khác.