Trang bìa
Trang bìa
Ảnh
CHUYÊN ĐỀ 2. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ
BÀI 5. THỰC HÀNH TỔNG HỢP ỨNG DỤNG CHIA ĐỂ TRỊ
Mở đầu
Yêu cầu
Hình vẽ
Học xong bài này em sẽ - Áp dụng được cách làm thuật toán sắp xếp trộn vào bài toán tính số nghịch thế trong mảng. - Vận dụng được tư tưởng chia để trị vào giải quyết một số bài toán thực tế - Viết được chương trình đơn giản cho một số bài toán áp dụng kĩ thuật đệ quy trong chia để trị
Tính số nghịch thế trong mảng
Bài toán
BÀI TOÁN Cho một mảng A gồm n phần tử latex(A_0, A_1,....,A(n-1)) đôi một khác nhau. Hai phần tử latex(A_i, A_j) với i < j được gọi là nghịch thế nếu như latex(A_i < A_j) Hãy tính số lượng nghịch thế trong mảng
Yêu cầu
Sản phẩm của mỗi nhóm qua bài thực hành này bao gồm: Thực hành 1: Mô tả chi tiết thuật toán giải quyết bài toán Thực hành 2: Viết chương trình giải quyết bài toán Thực hành 3: Kết quả thử nghiệm trên các bộ dữ liệu đầu vào mẫu và tự tạo
Thực hành
Thực hành 1: Áp dụng trực tiếp thuật toán sắp xếp trộn ở trên để mô tả chi tiết phương pháp chia để trị giải bài toán đếm số lượng nghịch thế ở trên Thực hành 2: Viết chương trình nhập vào một số nguyên dương n và n giá trị latex(A_0, A_1,...,A(n-1)) đôi một khác nhau, đưa ra số lượng nghịch thế của mảng vừa nhập vào.
Ảnh
Thực hành
Thực hành 1: Áp dụng trực tiếp thuật toán sắp xếp trộn ở trên để mô tả chi tiết phương pháp chia để trị giải bài toán đếm số lượng nghịch thế ở trên Thực hành 2: Viết chương trình nhập vào một số nguyên dương n và n giá trị latex(A_0, A_1,...,A(n-1)) đôi một khác nhau, đưa ra số lượng nghịch thế của mảng vừa nhập vào.
Ảnh
Thực hành
Thực hành 3: Viết chương trình thực hiện thuật toán đơn giản bằng vòng lặp để đếm số lượng nghịch thế. Tiếp theo, em hãy đếm số bước thực hiện bởi thuật toán này so với thuật toán chia để trị ở trên trong một số ví dụ cụ thể
Luyện tập
Bài tập
Cho một mảng A gồm n phần tử latex(A_0,A_1,...,A_(n-1)), hai phần tử bất kì có thể bằng nhau. Hãy tính số lượng những cặp hai phần từ mà không phải là nghịch thế trong mảng a) Vẫn dụng bài Thực hành 1 ở trên để mô tả chi tiết phương pháp chia để trị cho bài toán này b) Viết chương trình nhập vào giá trị n và n giá trị latex(A_0,A_1,...,A_(n-1)), đưa ra số lượng các cặp không phải nghịch thế trong mảng A c) Tạo các bộ dữ liệu thử nghiệm để kiểm thử chương trình
Ảnh
Kết thúc
Tạm biệt
Ảnh