Bài giảng Thuật toán ứng dụng - Bài 1: Tư duy thuật toán và cấu trúc dữ liệu. Kỹ năng lập trình - Đỗ Phan Thuận
Thuật toán ứng dụng
TƯ DUY THUẬT TOÁN VÀ CTDL + KỸ NĂNG LẬP TRÌNH
Đỗ Phan Thuận
Bộ môn Khoa Học Máy Tính, Viện CNTT & TT,
Trường Đại Học Bách Khoa Hà Nội.
Ngày 5 tháng 2 năm 2020
1 / 45
Mô hình Bài tập lập trình Thuật toán ứng dụng
Yếu tố chính : giải bài toán nhanh nhất có thể!
2 / 45
Mục tiêu
Cho một bài toán lập trình, ta sẽ phải
I
I
I
I
I
giải một cách hiệu quả,
sử dụng các thuật toán và cấu trúc dữ liệu,
chuyển lời giải thành chương trình,
làm càng nhanh càng tốt (dưới áp lực: thời gian, kết quả..),
và phải làm đúng (không sinh lỗi)
Mục tiêu của bài giảng này là thực hành giải quyết những vấn đề trên.
3 / 45
Làm thế nào?
Học những dạng bài phổ biến khác nhau
Chỉ ra những ứng dụng của các thuật toán và cấu trúc dữ liệu bạn
biết từ
I
khóa học cơ bản về các thuật toán
khóa học cơ bản về cấu trúc dữ liệu
I
Giới thiệu các dạng thuật toán và cấu trúc dữ liệu phổ biến khác
Học một số lý thuyết hay dùng
Thực hành giải bài toán
Thực hành lập trình
Thực hành nữa
.. và thực hành mãi
4 / 45
Sách tham khảo
Slides bài giảng Phân tích và thiết kế thuật toán Nguyễn Đức Nghĩa
Bài giảng Chuyên đề Lê Minh Hoàng
5 / 45
Các bài giảng
Dự kiến các chủ đề
Thứ tự.
Thời gian
Chủ đề
Hoạt động
1
2
Giới thiệu
Cấu trúc dữ liệu và thư viện
Thực hành
3
4
Kỹ thuật đệ qui và nhánh cận
Chia để trị
5
6
Qui hoạch động
Thực hành
7
8
Thực hành và Kiểm tra giữa kỳ
Qui hoạch động
Đồ thị
9
10
11
12
13
14
15
Thực hành
Đồ thị
Xử lý xâu
Thực hành
Lớp bài toán NP-đầy đủ
6 / 45
Mẫu đề bài
Mẫu chuẩn trong hầu hết các kỳ thi bao gồm
I
I
I
I
I
I
Mô tả bài toán
Mô tả định dạng dữ liệu vào
Mô tả định dạng kết quả ra
Ví dụ Dữ liệu vào/Kết quả ra
Giới hạn thời gian theo giây
Giới hạn bộ nhớ theo bytes/megabytes
Yêu cầu viết chương trình giải bài toán đúng càng nhiều bộ dữ liệu
càng tốt. Mặc định là dữ liệu vào không cần kiểm tra tính đúng đắn
Chương trình không được chạy quá giới hạn thời gian và giới hạn bộ
nhớ
7 / 45
Bài toán ví dụ
Mô tả bài toán
Viết chương trình nhân hai số nguyên.
Mô tả dữ liệu vào
Dòng đầu tiên chứa một số nguyên T, với 1 ≤ T ≤ 100, là số lượng bộ
test. T dòng tiếp theo, mỗi dòng chứa một test. Mỗi test bao gồm 2 số
nguyên A, B, với −220 ≤ A, B ≤ 220, cách nhau ít nhất một dấu cách.
Mô tả kết quả ra
Kết quả ghi ra mỗi dòng tương ứng với một test chứa một số là giá trị
A × B.
8 / 45
Bài toán ví dụ
Ví dụ dữ liệu vào
Dữ liệu kết quả ra
4
3 4
13 0
1 8
100 100
12
0
8
10000
9 / 45
Lời giải ví dụ
1
2
3
4
5
6
7
8
9
0
1
2
#include <iostream >
using namespace std;
int main () {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
10 / 45
Lời giải ví dụ
3
4
5
6
7
8
9
0
1
2
3
4
#include <iostream >
using namespace std;
int main () {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
Lời giải này có đúng không?
10 / 45
Lời giải ví dụ
5
6
7
8
9
0
1
2
3
4
5
6
#include <iostream >
using namespace std;
int main () {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
Lời giải này có đúng không?
Điều gì xảy ra nếu A = B = 220?
10 / 45
Lời giải ví dụ
7
8
9
0
1
2
3
4
5
6
7
8
#include <iostream >
using namespace std;
int main () {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
Lời giải này có đúng không?
Điều gì xảy ra nếu A = B = 220? Kết quả ra 0...
10 / 45
Lời giải ví dụ
9
0
1
2
3
4
5
6
7
8
9
0
#include <iostream >
using namespace std;
int main () {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
Lời giải này có đúng không? KHÔNG!
Điều gì xảy ra nếu A = B = 220? Kết quả ra 0...
10 / 45
Lời giải ví dụ
Khi A = B = 220, kết quả phải là 240
11 / 45
Lời giải ví dụ
Khi A = B = 220, kết quả phải là 240
Quá lớn với biến nguyên 32-bit, nên bị tràn số
11 / 45
Lời giải ví dụ
Khi A = B = 220, kết quả phải là 240
Quá lớn với biến nguyên 32-bit, nên bị tràn số
Sử dụng biến nguyên 64-bit sẽ cho lời giải đúng
11 / 45
Lời giải ví dụ
1
2
3
4
5
6
7
8
9
0
1
2
#include <iostream >
using namespace std;
int main () {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
long long A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
12 / 45
Lời giải ví dụ
3
4
5
6
7
8
9
0
1
2
3
4
#include <iostream >
using namespace std;
int main () {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
long long A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
Lời giải này có đúng không?
12 / 45
Lời giải ví dụ
5
6
7
8
9
0
1
2
3
4
5
6
#include <iostream >
using namespace std;
int main () {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
long long A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
Lời giải này có đúng không? ĐÚNG!
12 / 45
Tải về để xem bản đầy đủ
46 trang
15780
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thuật toán ứng dụng - Bài 1: Tư duy thuật toán và cấu trúc dữ liệu. Kỹ năng lập trình - Đỗ Phan Thuận", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_thuat_toan_ung_dung_bai_1_tu_duy_thuat_toan_va_cau.pdf
