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

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!
Nội dung trích xuất từ tài liệu:
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 PHÁT BIỂU BÀI TOÁN Khoa Công nghệ thông tinTrường đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)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 2BÀI TOÁN TÍNH TOÁNBà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. 4Bà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 • … 5Bà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 • … 6Phâ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 7Phâ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 8Phát biểu bài toánYou are given a range of positive integers from ?? to ??. Find DivisibleFind 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 ofInputEach 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 onesuitable pair.Print ?? lines, each line should contain the answer — two integers ?? and ?? suchthat ?? ≤ ??, ?? ≤ ??, ?? ≠ ?? and ?? divides ??. The answer in the ?? − ?? ? line shouldOutputcorrespond to the ?? − ?? ? query from the input.If there are multiple answers, print any of them. 9Phát biểu bài toánExampleinput31 103 141 10output17395 10 10Phá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ánYou 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ả inputThe first line contains a single integer ?? (1 ≤ ?? ≤ 1000) — the number ofInputEach 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 onesuitable pair. 11 Phát biểu bài toán • 4 thành phần của một bài toán • Mô tả outputPrint ?? lines, each line should contain the answer — two integers ?? and ?? such thatOutput?? ≤ ??, ?? ≤ ??, ?? ≠ ?? and ?? divides ??. The answer in the ?? − ?? ? line should correspond tothe ?? − ?? ? 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 ...