Bài giảng Tin học đại cương: Bài 4 - ĐH Bách khoa Hà Nội

Chia sẻ: Khang Duy | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

156
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài 4 Giải quyết bài toán thuộc bài giảng "Tin học đại cương", cùng nắm kiến thức trong chương này thông qua các các nội dung sau: bài toán (problem), giải quyết bài toán bằng máy tính, biểu diễn thuật toán, các phương pháp thiết kế thuật toán.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tin học đại cương: Bài 4 - ĐH Bách khoa Hà Nội

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Nội dung VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 4.1. Bài toán (problem) 4.2. Giải quyết bài toán bằng máy tính TIN HỌC ĐẠI CƯƠNG 4.3. Biểu diễn thuật toán Phần 2. Giải quyết bài toán 4.4. Các phương pháp thiết kế thuật toán Bài 4: Giải quyết bài toán 2 Nội dung 4.1. Bài toán (problem) 4.1. Bài toán (problem) • “Bài toán” hay “Vấn đề” 4.2. Giải quyết bài toán bằng máy tính – Vấn đề có nghĩa rộng hơn bài toán 4.3. Biểu diễn thuật 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 4.4. Các phương pháp thiết kế thuật toán vật lý, hóa học, xây dựng, kinh tế… • Hai loại vấn đề (Pitago) – 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 đó. 3 4 1
4.1. Bài toán (2) Nội dung • Biểu diễn vấn đề-bài toán 4.1. Bài toán (problem) –A→B 4.2. Giải quyết bài toán bằng máy tính • A: Giả thiết, điều kiện ban đầu 4.3. Biểu diễn thuật toán • B: Kết luận, mục tiêu cần đạt 4.4. Các phương pháp thiết kế thuật toán • 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 6 4.2. Giải quyết bài toán bằng máy tính 4.2. Giải quyết bài toán bằng máy tính (2) • Máy tính không thể dùng để giải quyết các • Phương án giải quyết bài toán được gọi vấn đề liên quan đến hành động vật lý hoặc là thuật toán/giải thuật trong tính toán biểu thị cảm xúc • Một thuật toán là: • Máy tính chỉ làm được những gì mà nó được – một dãy hữu hạn các thao tác và trình tự thực bảo phải làm. Máy tính không thông minh, hiện các thao tác đó sao cho sau khi thực hiện nó không thể tự phân tích vấn đề và đưa ra dãy thao tác này theo trình tự đã chỉ ra, với đầu giải pháp. vào (input) ta thu được kết quả đầu ra (output) mong muốn. • 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 8 2
4.2. Giải quyết bài toán bằng máy tính (3) Hai giai đoạn chính để hiện thực hóa bài toán • 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ì Giai đoạn giải quyết vấn đề Giai đoạn thực hiện 9 10 Nội dung 4.3. Biểu diễn thuật toán 4.1. Bài toán (problem) • Cách 1: Ngôn ngữ tự nhiên 4.2. Giải quyết bài toán bằng máy tính • Cách 2: Ngôn ngữ lưu đồ (lưu đồ/sơ đồ khối) 4.3. Biểu diễn thuật toán • Cách 3: Mã giả (pseudocode) gọi là ngôn ngữ mô phỏng chương trình PDL (Programming 4.4. Các phương pháp thiết kế thuật toán 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. 11 12 3
4.3.1. Ngôn ngữ tự nhiên Ví dụ 1 • Sử dụng một loại ngôn ngữ tự nhiên để • Bài toán: Đưa ra kết luận về tương quan liệt kê các bước của thuật toán của hai số a và b (>, < hay =). • Ưu điểm – Đầu vào: Hai số a và b – Đơn giản – Đầu ra: Kết luận a>b hay a b, hiển thị “a>b” và kết thúc Bắt đầu hoặc kết thúc • B3: Nếu a=b, hiển thị “a=b” và kết thúc Thao tác tính toán hoặc phức tạp • B4: (a
Ví dụ 1 - Mô tả bằng lưu đồ thuật toán 4.3.2. Sơ đồ khối (2) Nhập a, b Thể hiện thao tác bắt đầu hoặc kết thúc • Ư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 Đ a>b Hiển thị “a>b” • Nhược điểm Biểu diễn thao – Cồng kềnh, đặc biệt với bài toán phức tạp S tác so sánh Đ a=b Hiển thị “a=b” S Hiển thị “a
VD2 - Ngôn ngữ tự nhiên (tuần tự các bước) Ví dụ 2 - Mô tả bằng lưu đồ thuật toán Nhập a, b • B1: Nhập số a và số b. • B2: s  a + b; d  a – b; p  a * b s  a + b; d  a – b; p  a * b; • Hiển thị Biểu diễn thao tác tính toán đơn giản – Tổng là s hoặc phức tạp Hiển thị – Hiệu là d “Tổng là s, Hiệu là d, Tích là p” – Tích là p • B3: Nếu b = 0, hiển thị “Không thực hiện được Đ Hiển thị b=0 “Không thực hiện được phép chia” và kết thúc phép chia” • B4: (b0) Hiển thị “Thương là a/b” và kết thúc S Hiển thị “Thương là a/b” 21 22 Ví dụ 3 Ví dụ 3 - Mô tả tuần tự các bước • Bài toán: Giải phương trình bậc I • B1: Nhập a và b. – Đầu vào: Hai hệ số a, b • B2: Nếu a0 thì hiển thị “Phương trình có 1 – Đầu ra: Nghiệm của phương trình ax + b = 0 nghiệm duy nhất x = -b/a”. • Ý tưởng: • B3: (a=0) Nếu b 0 thì hiển thị “Phương – Lần lượt xét a = 0 rồi xét b = 0 để xét các trường trình vô nghiệm” và kết thúc hợp của phương trình • B4: (a=0)(b=0) Hiển thị “Phương trình vô số nghiệm” và kết thúc 23 24 6
Ví dụ 3 - Mô tả bằng lưu đồ thuật toán Ví dụ 4 Nhập a và b • Bài toán: Tìm giá trị lớn nhất của một dãy số nguyên có N số Đ Hiển thị – Đầu vào: Số số nguyên dương N và N số nguyên a0 “Nghiệm là: x = -b/a” a1, a2,…, aN S – Đầu ra: số nguyên lớn nhất của dãy ak, k trong khoảng [1…N] b0 Đ Hiển thị “Phương trình vô nghiệm” • Ý tưởng: – Khởi tạo giá trị Max = a1 S – Lần lượt so sánh Max với ai với i=2,3,…, N; Hiển thị nếu ai > Max ta gán giá trị mới cho Max “Phương trình vô số nghiệm” 25 26 Ví dụ 4 – Ý tưởng Ví dụ 4 - Mô tả tuần tự các bước max 3 5 7 9 2 8 • B1: Nhập N và dãy số a1, a2,…,aN. max = 3 3 • B2: Max  a1; i=2. max N, Hiển thị Max là giá trị lớn nhất max2 9 • B5: Tăng i lên 1 đơn vị. max>8 9 • B6: Quay lên B3. • B7: Kết thúc. Kết quả 9 27 28 7
Ví dụ 4 - Mô tả bằng lưu đồ thuật toán Bài tập Nhập N và dãy số a1, a2,…,aN • Bài toán: Giải phương trình bậc II – Đầu vào: Ba hệ số a, b, c Max  a1; i=2 – Đầu ra: Nghiệm của phương trình Đ Hiển thị ax2 + bx + c = 0 i>N “Max là số lớn nhất” • Ý tưởng: S – 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 ai > Max Max  ai S ii+1 29 30 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. • Tính đúng đắ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. 31 8