intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Kỹ thuật lập trình: Chương 1 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST
Báo xấu
14
lượt xem 8
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình: Chương 1 Phát biểu bài toán, cung cấp cho người đọc những kiến thức như: Bài toán tính toán; Biểu diễn dữ liệu của bài toán; Dữ liệu vô hướng; Dữ liệu dạng danh sách; Dữ liệu dạng bảng; Dữ liệu dạng khác;...Mời các bạn cùng tham khảo!

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 Kỹ thuật lập trình: Chương 1 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

  1. PHÁT BIỂU BÀI TOÁN Khoa Công nghệ thông tin Trường đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)
  2. Nội dung • Bài toán tính toán • Định nghĩa "Bài toán tính toán" • Phân loại bài toán • Phát biểu bài toán • Quy trình phân tích • Biểu diễn dữ liệu của bài toán • Dữ liệu vô hướng • Dữ liệu dạng danh sách • Dữ liệu dạng bảng • Dữ liệu dạng khác 2
  3. BÀI TOÁN TÍNH TOÁN
  4. Bài toán tính toán • Bài toán tính toán • Bài toán tính toán (computational problem) là một tập các câu hỏi toán học mà máy tính có thể giải quyết được • Ví dụ: • "Given a positive integer n, determine if n is prime." • "Given a positive integer n, find a nontrivial prime factor of n." 4
  5. Bài toán tính toán • Giải quyết bài toán tính toán • Có tư duy logic, tư duy toán học cơ bản • Có tư duy tính toán/kỹ thuật lập trình (computational thinking) • Nghiên cứu các Data structures • Mảng (array) • Bảng (table) • Stack • Queue • Cây (Tree) • Set • Hash • Graph • … 5
  6. Bài toán tính toán • Giải quyết bài toán tính toán • Nghiên cứu một số loại Algorithms Nghiên cứu các phương pháp/mô hình giải quyết cho từng lĩnh vực • Graph Algorithms • Tree Algorithms • Geometric Algorithms • Algorithms on strings • Cryptographic algorithms • Machine learning algorithms • … 6
  7. Phân loại bài toán • Chúng ta có thể chia bài toán thành 4 loại: • Bài toán ra quyết định (decision problem) • Câu trả lời là: Yes hay No • "Given a positive integer n, determine if n is prime." • Bài toán tìm kiếm (search problem) • Yêu cầu: tìm các đáp án/nghiệm • "Given a positive interger n, print all prime factors of n" 7
  8. Phân loại bài toán • Bài toán đếm (counting problem) • Yêu cầu: tìm số lượng lời giải (đếm) của bài toán tìm kiếm • "Given a positive integer n, count the number of nontrivial prime factors of n." • Bài toán tối ưu (optimization problem) • Yêu cầu: tìm lời giải tối ưu nhất có thể của bài toán tìm kiếm • "Given a graph G, find a shortest path from x to y" 8
  9. Phát biểu bài toán You are given a range of positive integers from 𝑙𝑙 to 𝑟𝑟. Find Divisible Find such a pair of integers (𝑥𝑥, 𝑦𝑦) that 𝑙𝑙 ≤ 𝑥𝑥, 𝑦𝑦 ≤ 𝑟𝑟, 𝑥𝑥 ≠ 𝑦𝑦 and 𝑥𝑥 divides 𝑦𝑦. You are also asked to answer 𝑇𝑇 independent queries. If there are multiple answers, print any of them. The first line contains a single integer 𝑇𝑇 (1 ≤ 𝑇𝑇 ≤ 1000) — the number of Input Each of the next 𝑇𝑇 lines contains two integers 𝑙𝑙 and 𝑟𝑟 (1 ≤ 𝑙𝑙 ≤ 𝑟𝑟 ≤ 998244353) queries. — inclusive borders of the range. It is guaranteed that testset only includes queries, which have at least one suitable pair. Print 𝑇𝑇 lines, each line should contain the answer — two integers 𝑥𝑥 and 𝑦𝑦 such that 𝑙𝑙 ≤ 𝑥𝑥, 𝑦𝑦 ≤ 𝑟𝑟, 𝑥𝑥 ≠ 𝑦𝑦 and 𝑥𝑥 divides 𝑦𝑦. The answer in the 𝑖𝑖 − 𝑡𝑡 𝑡 line should Output correspond to the 𝑖𝑖 − 𝑡𝑡 𝑡 query from the input. If there are multiple answers, print any of them. 9
  10. Phát biểu bài toán Example input 3 1 10 3 14 1 10 output 17 39 5 10 10
  11. Phát biểu bài toán • 4 thành phần của một bài toán • Mô tả ngữ cảnh/bối cảnh/yêu cầu của bài toán You are given a range of positive integers from 𝑙𝑙 to 𝑟𝑟. Find such a pair of integers (𝑥𝑥, 𝑦𝑦) that 𝑙𝑙 ≤ 𝑥𝑥, 𝑦𝑦 ≤ 𝑟𝑟, 𝑥𝑥 ≠ 𝑦𝑦 and 𝑥𝑥 divides 𝑦𝑦. You are also asked to answer 𝑇𝑇 independent queries. If there are multiple answers, print any of them. • Mô tả input The first line contains a single integer 𝑇𝑇 (1 ≤ 𝑇𝑇 ≤ 1000) — the number of Input Each of the next 𝑇𝑇 lines contains two integers 𝑙𝑙 and 𝑟𝑟 (1 ≤ 𝑙𝑙 ≤ 𝑟𝑟 ≤ 998244353) queries. — inclusive borders of the range. It is guaranteed that testset only includes queries, which have at least one suitable pair. 11
  12. Phát biểu bài toán • 4 thành phần của một bài toán • Mô tả output Print 𝑇𝑇 lines, each line should contain the answer — two integers 𝑥𝑥 and 𝑦𝑦 such that Output 𝑙𝑙 ≤ 𝑥𝑥, 𝑦𝑦 ≤ 𝑟𝑟, 𝑥𝑥 ≠ 𝑦𝑦 and 𝑥𝑥 divides 𝑦𝑦. The answer in the 𝑖𝑖 − 𝑡𝑡 𝑡 line should correspond to the 𝑖𝑖 − 𝑡𝑡 𝑡 query from the input. If there are multiple answers, print any of them. • Các ví dụ và giải thích ví dụ (nếu có) input output 3 17 1 10 39 3 14 5 10 1 10 12
  13. Quy trình phân tích • Bước 1. Đọc bài toán vài lần • Bước 2. Giải thử bài toán trên giấy, trên bảng • Bước 3. Đánh giá, tinh chỉnh lời giải ban đầu tốt hơn • Bước 4. Viết mã giả • Bước 5. Cài đặt chương trình • Bước 6. Kiểm tra chương trình 13
  14. Quy trình phân tích • Bước 1. Đọc bài toán vài lần • Đọc ngữ cảnh/bối cảnh/yêu cầu của bài toán • Gạch dưới những yêu cầu chính, những điều kiện ràng buộc • Đọc phần input, output của bài toán • Mục tiêu: • Hiểu bài toán • Có cảm giác thân thuộc với các khái niệm trong bài toán • Tiêu chí đánh giá: có thể mô tả/giải thích đề cho người khác 14
  15. Quy trình phân tích You are given a range of positive integers from 𝑙𝑙 to 𝑟𝑟. Find Divisible Find such a pair of integers (𝑥𝑥, 𝑦𝑦) that 𝑙𝑙 ≤ 𝑥𝑥, 𝑦𝑦 ≤ 𝑟𝑟, 𝑥𝑥 ≠ 𝑦𝑦 and 𝑥𝑥 divides 𝑦𝑦. You are also asked to answer 𝑇𝑇 independent queries. If there are multiple answers, print any of them. The first line contains a single integer 𝑇𝑇 (1 ≤ 𝑇𝑇 ≤ 1000) — the number of Input Each of the next 𝑇𝑇 lines contains two integers 𝑙𝑙 and 𝑟𝑟 (1 ≤ 𝑙𝑙 ≤ 𝑟𝑟 ≤ 998244353) queries. — inclusive borders of the range. It is guaranteed that testset only includes queries, which have at least one suitable pair. Print 𝑇𝑇 lines, each line should contain the answer — two integers 𝑥𝑥 and 𝑦𝑦 such that 𝑙𝑙 ≤ 𝑥𝑥, 𝑦𝑦 ≤ 𝑟𝑟, 𝑥𝑥 ≠ 𝑦𝑦 and 𝑥𝑥 divides 𝑦𝑦. The answer in the 𝑖𝑖 − 𝑡𝑡 𝑡 line should Output correspond to the 𝑖𝑖 − 𝑡𝑡 𝑡 query from the input. If there are multiple answers, print any of them. 15
  16. Quy trình phân tích Example input 3 1 10 3 14 1 10 output 17 39 5 10 16
  17. Quy trình phân tích • Bước 2. Thử giải quyết bài toán trên giấy/trên bảng • Giải các ví dụ trong bài toán • Lấy thêm ví dụ khác để giải, từ số nhỏ đến số lớn • Trong quá trình giải các ví dụ, hình dung/chú ý các bước cần thực hiện bằng tư duy tính toán • Mục tiêu: • Hiểu rõ bài toán hơn • Hình thành các bước giải ban đầu cho bài toán • Tiêu chí đánh giá: Có thể giải được các ví dụ cụ thể 17
  18. Quy trình phân tích • Ví dụ: 18
  19. Quy trình phân tích • Bước 3. Đánh giá, tinh chỉnh lời giải ban đầu tốt hơn • Chú ý các điều kiện ràng buộc trong bài toán • Kiểm tra lời giải ban đầu có đúng chưa • Thời gian chạy có hợp lý không • Từ lời giải ban đầu, từ mô tả bài toán • Tìm thêm các mối quan hệ • Biến đổi các quan hệ để được các bước tính toán ngắn gọn hơn • Mục tiêu: • Kiểm tra tính đúng đắn của lời giải • Cải tiến tốc độ của lời giải • Tiêu chí đánh giá: Lời giải có độ phức tạp phù hợp với ràng buộc miền giá trị các biến 19
  20. Quy trình phân tích • Bước 4. Viết mã giả • Mô tả cấu trúc dữ liệu quan trọng của bài toán • Phát họa ra giấy/trên bảng các bước của lời giải • Dự kiến các hàm, các lớp trong chương trình • Bước 5. Cài đặt chương trình • Khai báo các biến • Cài đặt từng bước của thuật toán • Suy nghĩ rõ từng lệnh trước khi viết (các lệnh được viết một cách chắc chắn, có lý do) 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0