Lý thuyết chương 2

A. KIẾN THỨC CHUNG - Sắp xếp trong là sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy tính, ở đó ta có thể sử dụng khả năng truy nhập ngẫu nhiên của bộ nhớ và do vậy sự thực hiện rất nhanh. - Sắp xếp ngoài là sự sắp xếp được sử dụng khi số …

Lý thuyết chương 1

1. Sự cần thiết phải phân tích, đánh giá giải thuật Cần phải phân tích, đánh giá giải thuật để: §         Lựa chọn một giải thuật tốt nhất trong các giải thuật để cài đặt chương trình giải quyết bài toán đặt ra. §         Cải tiến giải thuật hiện có để được một giải thuật tốt hơn. …

Cây trò chơi

1. Mô tả Xét một trò chơi trong đó hai người thay phiên nhau đi nước của mình như cờ vua, cờ tướng, carô... Trò chơi có một trạng thái bắt đầu và mỗi nước đi sẽ biến đổi trạng thái hiện hành thành một trạng thái mới. Trò chơi sẽ kết thúc theo một quy …

Tính toán tổ hợp

1. Giải thuật đệ quy Một bài toán khá quen thuộc là tính số tổ hợp chập k của n theo công thức truy hồi: Công thức trên đã gợi ý cho chúng ta một giải thuật đệ quy như sau: int Comb(int n, int k) {             if (k==0 || k==n)                         return 1;             return Comb(n-1, k-1) + Comb(n-1,k); } Gọi T(n) là …

Cái ba lô

A GIẢI THUẬT THAM ĂN 1. Bài toán Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật, mỗi đồ vật i có một trọng lượng gi và một giá trị vi. Tất cả các loại đồ vật đều có số lượng không hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào ba lô, …