Đang tạo bản xem trước...
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 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 ThiNganHang.com4.4. Một số thuật toán cơ bản 2 ThiNganHang.com 1
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. Một số thuật toán cơ bả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 ThiNganHang.com• Hai loại vấn đề– Theorema: là vấn đề cần được khẳng địnhtrong vật lý, hóa học, xây dựng, kinh tế… 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 ThiNganHang.com 2
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 ThiNganHang.com4.4. Một số thuật toán cơ bản 6 ThiNganHang.com 3
4.2. Giải quyết bài toán bằng máy tính • Máy tính không thể dùng để giải quyết các vấn đề liên quan đến hành động vật lý hoặc biểu thị cảm xúc • Máy tính chỉ làm được những gì mà nó được bảo phải làm. Máy tính không thông minh, nó không thể tự phân tích vấn đề và đưa ra giải pháp. • 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 đề (chương trình), và máy tính sẽ thực hiện các chỉ dẫn đó 7 4.2. Giải quyết bài toán bằng máy tính (2) • 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ự ThiNganHang.comthực hiện các thao tác đó sao cho sau khithự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. 8 ThiNganHang.com 4
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 số bước hữu hạn. • Tính đúng : 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. 9 4.2. Giải quyết bài toán bằng máy tính (3) • 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 ThiNganHang.com– 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ì 10 ThiNganHang.com 5
Hai giai đoạn chính để hiện thực hóa bài toán Giai đoạn giải quyết vấn đề Giai đoạn thực hiện 11 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 ThiNganHang.com4.4. Một số thuật toán cơ bản 12 ThiNganHang.com 6
4.3. 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. 13 4.3.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 ThiNganHang.com– Không yêu cầu người viết và người đọc phảicó 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 14 ThiNganHang.com 7
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 15 VD1 - Ngôn ngữ tự nhiên (tuần tự các bước) • B0: Bắt đầu • B1: Nhập số a và số b. • B2: Nếu a > b, hiển thị “a>b”. Kết thúc. ThiNganHang.com• B3: Nếu a = b, hiển thị “a=b”.Ngược lại sang B3. Ngược lại, hiển thị “a < b”. • B4: Kết thúc 16 ThiNganHang.com 8
4.3.2. Lưu đồ thuật toán Một số khối trong sơ đồ khối dùng biểu diễn thuật toán 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 Nối tiếp đoạn lệnh Luồng thực hiện 17 Cấu trúc tuần tự • Các bước được thực hiện theo 1 trình tự tuyến tính, hết bước này đến bước khác Công việc 1 ThiNganHang.comCông việc 2 … Công việc n 18 ThiNganHang.com 9
Cấu trúc rẽ nhánh • Nếu biểu thức điều kiện đúng (giá trị chân lý là True) thực hiện công việc 1. • Nếu biểu thức điều kiện sai (giá trị chân lý là False) thực hiện công việc 2. 19 Cấu trúc lặp ThiNganHang.com • Khi biểu thức điều kiện • Thực hiện công việc khi còn đúng, thực hiện công biểu thức điều kiện còn việc đúng 20 ThiNganHang.com 10
Ví dụ 1 - Mô tả bằng lưu đồ thuật toán B0: Bắt đầu B1: Nhập a, b B2: Nếu a > b hiển thị “a>b” và kết thúc Ngược lại sang B3 B3: Nếu a = b hiển thị “a=b”, Ngược lại, báo “a<b” B4: Kết thúc 21 4.3.2. 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 ThiNganHang.com– Cồng kềnh, đặc biệt với bài toán phức tạp 22 ThiNganHang.com 11
4.3.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 23 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 ThiNganHang.com– Đầ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 24 ThiNganHang.com 12
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 • B3: Hiển thị – Tổng là s – Hiệu là d – Tích là p • B4: Nếu b = 0, hiển thị “Không thực hiện được phép chia” và kết thúc Ngược lại Hiển thị “Thương là a/b” và kết thúc 25 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 ThiNganHang.com• Ý 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 26 ThiNganHang.com 13
Ví dụ 3 - Mô tả tuần tự các bước • B1: Nhập a và b. • B2: Nếu a ≠ 0 thì x ← -b/a. Hiển thị “Phương trình có 1 nghiệm duy nhất x”. Ngược lại sang B3 • B3: Nếu b ≠ 0 thì hiển thị “Phương trình vô nghiệm”. Ngược lại Hiển thị “Phương trình vô số nghiệm” B4: Kết thúc 27 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 ThiNganHang.com• Ý tưởng:– Đầu ra: số nguyên lớn nhất của dãy – 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 28 ThiNganHang.com 14
Ví dụ 4 – Ý tưởng max 3 5 7 9 2 8 max = 3 3 max<5 5 max<7 7 max<9 9 max>2 9 max>8 9 Kết quả 9 29 Ví dụ 4 - Mô tả tuần tự các bước • B1: Nhập n và dãy số a0, a1, a2,…,an-1. • B2: Max a0; i=1 (chỉ số của phần tử tiếp theo). ThiNganHang.com• B3: Nếu i <= n-1, sang bước 4Ngược lại in ra giá trị Max. Kết thúc. • B4: Nếu ai > Max, Max ai • B5: Tăng i lên 1 đơn vị. Quay lên B3. • B6: Kết thúc. 30 ThiNganHang.com 15
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 31 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 ThiNganHang.com4.4. Một số thuật toán cơ bản 32 ThiNganHang.com 16
4.4.1. Thuật toán số học • Các bài toán về số học – Xác định một số nguyên có phải là số nguyên tố/hợp số hay không – Tìm USCLN, BSCNN của 2 số nguyên – .. 33 Bài toán số nguyên tố • Cho một số nguyên dương p. Làm thế nào để biết được p có phải số nguyên tố hay không? – Input: p nguyên dương – Output: kết luận về tính nguyên tố của p ThiNganHang.com• Ý tưởng? – p = 0 hoặc 1? Không phải số nguyên tố – p > 1? • Kiểm tra từ 2 đến p-1 có phải là ước số của p không • Nếu có thì kết luận p không là số nguyên tố, ngược lại không có số nào thì kết luận p là số nguyên tố 34 ThiNganHang.com 17
Tìm UCLN, BCNN của hai số • B1 : Nhập 2 số a, b • B2 : x a, y b • B3 : Nếu y ≠ 0, sang B4 Ngược lại, UCLN x, BCNN (a*b)/ UCLN. Hiển thị UCLN, BCNN. Kết thúc • B4 : r x mod y x y y r Quay lại B3. 35 Ví dụ 1. Tìm tất cả các ước số của một số nguyên dương N • Ý tưởng : Duyệt lần lượt các giá trị từ 1 tới N và in ra nếu giá trị đó là ước số của N. Giải thuật ThiNganHang.com 36 ThiNganHang.com 18
Ví dụ 2. Tìm tất cả các ước số lẻ của một số nguyên dương N • Ý tưởng : Duyệt lần lượt các số lẻ từ 1 tới N và in ra nếu giá trị đó là ước số của N. Giải thuật 37 Ví dụ 3. Kiểm tra tính hoàn hảo của số nguyên dương N. ThiNganHang.com 38 ThiNganHang.com 19
Ví dụ 4. Hiển thị tất cả các số hoàn hảo trong đoạn [1,10000] 39 Ví dụ 5. Tìm số Fibonacci thứ N Thuật giải ThiNganHang.com 40 ThiNganHang.com 20
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!