Tổng hợp bài giảng Thuật toán ứng dụng_Thầy Đỗ Phan Thuận| Bài giảng Thuật toán ứng dụng| Trường Đại học Bách Khoa Hà Nội

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 −2^20 ≤ A, B ≤ 2^20, 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.

17 9 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Thuật toán ứng dụng

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

438 trang 3 tuần trước

Tác giả:

Profile Trịnh Thảo Anh
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
thuandp.sinhvien@gmail.com
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
giải một cách hiệu quả,
I
sử dụng các thuật toán và cấu trúc dữ liệu,
I
chuyển lời giải thành chương trình,
I
làm càng nhanh càng tốt (dưới áp lực: thời gian, kết quả..),
I
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
I
khóa học cơ bản về cấu trúc dữ liệu
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
Competitive Programming by Steven Halim http://libgen.io/
ads.php?md5=f6f195012783a8b3c8bb7628882a51b7
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 Giới thiệu
2 Cấu trúc dữ liệu và thư viện
3 Thực hành
4 Kỹ thuật đệ qui và nhánh cận
5 Chia để trị
6 Qui hoạch động
7 Thực hành
8 Thực hành và Kiểm tra giữa kỳ
9 Qui hoạch động
10 Đồ thị
11 Thực hành
12 Đồ thị
13 Xử lý xâu
14 Thực hành
15 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
Mô tả bài toán
I
Mô tả định dạng dữ liệu vào
I
Mô tả định dạng kết quả ra
I
Ví dụ Dữ liệu vào/Kết quả ra
I
Giới hạn thời gian theo giây
I
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 −2
20
≤ A, B ≤ 2
20
, 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 # include < iostream >
2 using na mespace std ;
3 int main () {
4 int T;
5 cin >> T;
6 for (int t = 0; t < T; t ++) {
7 int A , B;
8 cin >> A >> B;
9 cout << A * B << endl ;
10 }
11 return 0;
12 }
Lời giải này có đúng không?
KHÔNG!
Điều gì xảy ra nếu A = B = 2
20
?
Kết quả ra 0...
10 / 45
Lời giải ví dụ
13 # include < iostream >
14 using na mespace std ;
15 int main () {
16 int T;
17 cin >> T;
18 for (int t = 0; t < T; t ++) {
19 int A , B;
20 cin >> A >> B;
21 cout << A * B << endl ;
22 }
23 return 0;
24 }
Lời giải này có đúng không?
KHÔNG!
Điều gì xảy ra nếu A = B = 2
20
?
Kết quả ra 0...
10 / 45
Lời giải ví dụ
25 # include < iostream >
26 using na mespace std ;
27 int main () {
28 int T;
29 cin >> T;
30 for (int t = 0; t < T; t ++) {
31 int A , B;
32 cin >> A >> B;
33 cout << A * B << endl ;
34 }
35 return 0;
36 }
Lời giải này có đúng không?
KHÔNG!
Điều gì xảy ra nếu A = B = 2
20
?
Kết quả ra 0...
10 / 45
Lời giải ví dụ
37 # include < iostream >
38 using na mespace std ;
39 int main () {
40 int T;
41 cin >> T;
42 for (int t = 0; t < T; t ++) {
43 int A , B;
44 cin >> A >> B;
45 cout << A * B << endl ;
46 }
47 return 0;
48 }
Lời giải này có đúng không?
KHÔNG!
Điều gì xảy ra nếu A = B = 2
20
? Kết quả ra 0...
10 / 45
Lời giải ví dụ
49 # include < iostream >
50 using na mespace std ;
51 int main () {
52 int T;
53 cin >> T;
54 for (int t = 0; t < T; t ++) {
55 int A , B;
56 cin >> A >> B;
57 cout << A * B << endl ;
58 }
59 return 0;
60 }
Lời giải này có đúng không? KHÔNG!
Điều gì xảy ra nếu A = B = 2
20
? Kết quả ra 0...
10 / 45
Lời giải ví dụ
Khi A = B = 2
20
, kết quả phải là 2
40
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ụ
Khi A = B = 2
20
, kết quả phải là 2
40
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ụ
Khi A = B = 2
20
, kết quả phải là 2
40
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ụ
61 # include < iostream >
62 using na mespace std ;
63 int main () {
64 int T;
65 cin >> T;
66 for (int t = 0; t < T; t ++) {
67 long long A , B;
68 cin >> A >> B;
69 cout << A * B << endl ;
70 }
71 return 0;
72 }
Lời giải này có đúng không?
ĐÚNG!
Làm thế nào nếu giá trị A, B lớn nữa?
XỬ LÝ SỐ LỚN!
12 / 45
Lời giải ví dụ
73 # include < iostream >
74 using na mespace std ;
75 int main () {
76 int T;
77 cin >> T;
78 for (int t = 0; t < T; t ++) {
79 long long A , B;
80 cin >> A >> B;
81 cout << A * B << endl ;
82 }
83 return 0;
84 }
Lời giải này có đúng không?
ĐÚNG!
Làm thế nào nếu giá trị A, B lớn nữa?
XỬ LÝ SỐ LỚN!
12 / 45
Lời giải ví dụ
85 # include < iostream >
86 using na mespace std ;
87 int main () {
88 int T;
89 cin >> T;
90 for (int t = 0; t < T; t ++) {
91 long long A , B;
92 cin >> A >> B;
93 cout << A * B << endl ;
94 }
95 return 0;
96 }
Lời giải này có đúng không? ĐÚNG!
Làm thế nào nếu giá trị A, B lớn nữa?
XỬ LÝ SỐ LỚN!
12 / 45
| 1/438
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

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 thuandp.sinhvien@gmail.com
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 giải một cách hiệu quả,
I sử dụng các thuật toán và cấu trúc dữ liệu,
I chuyển lời giải thành chương trình,
I làm càng nhanh càng tốt (dưới áp lực: thời gian, kết quả..),
I 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
I khóa học cơ bản về cấu trúc dữ liệu
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
Competitive Programming by Steven Halim http://libgen.io/
ads.php?md5=f6f195012783a8b3c8bb7628882a51b7
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 Giới thiệu 2
Cấu trúc dữ liệu và thư viện 3 Thực hành 4
Kỹ thuật đệ qui và nhánh cận 5 Chia để trị 6 Qui hoạch động 7 Thực hành 8
Thực hành và Kiểm tra giữa kỳ 9 Qui hoạch động 10 Đồ thị 11 Thực hành 12 Đồ thị 13 Xử lý xâu 14 Thực hành 15
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 Mô tả bài toán
I Mô tả định dạng dữ liệu vào
I Mô tả định dạng kết quả ra
I Ví dụ Dữ liệu vào/Kết quả ra
I Giới hạn thời gian theo giây
I 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 12 3 4 0 13 0 8 1 8 10000 100 100 9 / 45 KHÔNG! Kết quả ra 0...
Lời giải này có đúng không?
Điều gì xảy ra nếu A = B = 220? Lời giải ví dụ 1
# i n c l u d e < i o s t r e a m > 2
u s i n g n a m e s p a c e std ; 3 int m a i n () { 4 int T ; 5 cin > > T ; 6
for ( int t = 0; t < T ; t ++) { 7 int A , B ; 8 cin > > A > > B ; 9
c o u t < < A * B < < e n dl ; 10 } 11 r e t u r n 0; 12 } 10 / 45 Kết quả ra 0... KHÔNG!
Điều gì xảy ra nếu A = B = 220? Lời giải ví dụ 13
# i n c l u d e < i o s t r e a m > 14
u s i n g n a m e s p a c e std ; 15 int m a i n () { 16 int T ; 17 cin > > T ; 18
for ( int t = 0; t < T ; t ++) { 19 int A , B ; 20 cin > > A > > B ; 21
c o u t < < A * B < < e n dl ; 22 } 23 r e t u r n 0; 24 }
Lời giải này có đúng không? 10 / 45 KHÔNG! Kết quả ra 0... Lời giải ví dụ 25
# i n c l u d e < i o s t r e a m > 26
u s i n g n a m e s p a c e std ; 27 int m a i n () { 28 int T ; 29 cin > > T ; 30
for ( int t = 0; t < T ; t ++) { 31 int A , B ; 32 cin > > A > > B ; 33
c o u t < < A * B < < e n dl ; 34 } 35 r e t u r n 0; 36 }
Lời giải này có đúng không?
Điều gì xảy ra nếu A = B = 220? 10 / 45 KHÔNG! Lời giải ví dụ 37
# i n c l u d e < i o s t r e a m > 38
u s i n g n a m e s p a c e std ; 39 int m a i n () { 40 int T ; 41 cin > > T ; 42
for ( int t = 0; t < T ; t ++) { 43 int A , B ; 44 cin > > A > > B ; 45
c o u t < < A * B < < e n dl ; 46 } 47 r e t u r n 0; 48 }
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ụ 49
# i n c l u d e < i o s t r e a m > 50
u s i n g n a m e s p a c e std ; 51 int m a i n () { 52 int T ; 53 cin > > T ; 54
for ( int t = 0; t < T ; t ++) { 55 int A , B ; 56 cin > > A > > B ; 57
c o u t < < A * B < < e n dl ; 58 } 59 r e t u r n 0; 60 }
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
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 Lời giải ví dụ
Khi A = B = 220, kết quả phải là 240 11 / 45
Sử dụng biến nguyên 64-bit sẽ cho lời giải đúng 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 ĐÚNG! XỬ LÝ SỐ LỚN!
Lời giải này có đúng không?
Làm thế nào nếu giá trị A, B lớn nữa? Lời giải ví dụ 61
# i n c l u d e < i o s t r e a m > 62
u s i n g n a m e s p a c e std ; 63 int m a i n () { 64 int T ; 65 cin > > T ; 66
for ( int t = 0; t < T ; t ++) { 67 l o n g l o n g A , B ; 68 cin > > A > > B ; 69
c o u t < < A * B < < e n dl ; 70 } 71 r e t u r n 0; 72 } 12 / 45 XỬ LÝ SỐ LỚN! ĐÚNG!
Làm thế nào nếu giá trị A, B lớn nữa? Lời giải ví dụ 73
# i n c l u d e < i o s t r e a m > 74
u s i n g n a m e s p a c e std ; 75 int m a i n () { 76 int T ; 77 cin > > T ; 78
for ( int t = 0; t < T ; t ++) { 79 l o n g l o n g A , B ; 80 cin > > A > > B ; 81
c o u t < < A * B < < e n dl ; 82 } 83 r e t u r n 0; 84 }
Lời giải này có đúng không? 12 / 45 XỬ LÝ SỐ LỚN!
Làm thế nào nếu giá trị A, B lớn nữa? Lời giải ví dụ 85
# i n c l u d e < i o s t r e a m > 86
u s i n g n a m e s p a c e std ; 87 int m a i n () { 88 int T ; 89 cin > > T ; 90
for ( int t = 0; t < T ; t ++) { 91 l o n g l o n g A , B ; 92 cin > > A > > B ; 93
c o u t < < A * B < < e n dl ; 94 } 95 r e t u r n 0; 96 }
Lời giải này có đúng không? ĐÚNG! 12 / 45