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

Bài giảng Thuật toán ứng dụng - Đỗ Phan Thuận

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

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

Bài giảng "Thuật toán ứng dụng" trang bị cho người học tư duy thuật toán, kiến thức về cấu trúc dữ liệu và kỹ năng lập trình. Nội dung tập trung vào các cấu trúc dữ liệu cơ bản và việc sử dụng thư viện. Kỹ thuật đệ quy và nhánh cận được giới thiệu như một phương pháp giải quyết vấn đề hiệu quả. Các thuật toán chia để trị và quy hoạch động cũng được trình bày chi tiết. Các buổi thực hành giúp người học áp dụng kiến thức vào giải quyết các bài toán thực tế. Bài giảng này là nền tảng quan trọng cho việc phát triển các ứng dụng phần mềm phức tạp. 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 Thuật toán ứng dụng - Đỗ Phan Thuận

  1. 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
  2. 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
  3. Mục tiêu Cho một bài toán lập trình, ta sẽ phả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
  4. 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ừ 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 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
  5. 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
  6. 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
  7. Mẫu đề bài Mẫu chuẩn trong hầu hết các kỳ thi bao gồm 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
  8. 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
  9. 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
  10. Lời giải ví dụ 1 # include < iostream > 2 using namespace 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
  11. Lời giải ví dụ 3 # include < iostream > 4 using namespace std ; 5 int main () { 6 int T ; 7 cin >> T ; 8 for ( int t = 0; t < T ; t ++) { 9 int A , B ; 0 cin >> A >> B ; 1 cout
  12. Lời giải ví dụ 5 # include < iostream > 6 using namespace std ; 7 int main () { 8 int T ; 9 cin >> T ; 0 for ( int t = 0; t < T ; t ++) { 1 int A , B ; 2 cin >> A >> B ; 3 cout
  13. Lời giải ví dụ 7 # include < iostream > 8 using namespace std ; 9 int main () { 0 int T ; 1 cin >> T ; 2 for ( int t = 0; t < T ; t ++) { 3 int A , B ; 4 cin >> A >> B ; 5 cout
  14. Lời giải ví dụ 9 # include < iostream > 0 using namespace std ; 1 int main () { 2 int T ; 3 cin >> T ; 4 for ( int t = 0; t < T ; t ++) { 5 int A , B ; 6 cin >> A >> B ; 7 cout
  15. Lời giải ví dụ Khi A = B = 220 , kết quả phải là 240 11 / 45
  16. 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
  17. 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
  18. Lời giải ví dụ 1 # include < iostream > 2 using namespace std ; 3 int main () { 4 int T ; 5 cin >> T ; 6 for ( int t = 0; t < T ; t ++) { 7 long long A , B ; 8 cin >> A >> B ; 9 cout
  19. Lời giải ví dụ 3 # include < iostream > 4 using namespace std ; 5 int main () { 6 int T ; 7 cin >> T ; 8 for ( int t = 0; t < T ; t ++) { 9 long long A , B ; 0 cin >> A >> B ; 1 cout
  20. Lời giải ví dụ 5 # include < iostream > 6 using namespace std ; 7 int main () { 8 int T ; 9 cin >> T ; 0 for ( int t = 0; t < T ; t ++) { 1 long long A , B ; 2 cin >> A >> B ; 3 cout
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
2=>2