BÀI TẬP PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN

Sử dụng các phương pháp: Quay lui, nhánh cận, tham lam, chia để trị và quihoạch động. Yêu cầu chung với sinh viên:1. Trình bày ý tưởng giải bài toán và phương pháp sử dụng (nói cách khác tại saolại sử dụng phương pháp đó)2. Trình bày thuật toán (dạng mã giả) cho bài toán cùng ý nghĩa của các biến, thủtục sử dụng trong đó.3. Đánh giá độ phức tạp của thuật toán (nếu sử dụng đệ qui thì phải trình bàyhoặc dùng phương pháp thế hoặc hoặc dùng định lý “chính” để tính độ phứctạp).4. Mã hóa bằng...
Nội dung trích xuất từ tài liệu:
BÀI TẬP PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN BÀI TẬP PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN (Sử dụng các phương pháp: Quay lui, nhánh cận, tham lam, chia để trị và qui hoạch động)Yêu cầu chung với sinh viên: 1. Trình bày ý tưởng giải bài toán và phương pháp sử dụng (nói cách khác tại sao lại sử dụng phương pháp đó) 2. Trình bày thuật toán (dạng mã giả) cho bài toán cùng ý nghĩa của các biến, thủ tục sử dụng trong đó. 3. Đánh giá độ phức tạp của thuật toán (nếu sử dụng đệ qui thì phải trình bày hoặc dùng phương pháp thế hoặc hoặc dùng định lý “chính” để tính độ phức tạp). 4. Mã hóa bằng ngôn ngữ C, C++ hoặc Java. 5. Đưa ra các ví dụ để test lại chương trình.1. Cho xâu S (độ dài 8. Cho bàn cờ n x n ô, tìm cách di chuyển một quân mã (di chuyển theo luật cờ vua)trên bàn có xuất phát từu ô (1,1) đi qua tất cả các ô, mỗi ô qua đúng một lần.9. Số siêu nguyên tố là số nguyên tố mà khi bỏ đi một số tùy ý các chữ số bên phảicủa nó thì phần còn lại vẫn là một số nguyên tố. Cho một số nguyên dương n (n18. Có N tệp chương trình với dung lượng S1, S2, ..., SN và loại đĩa CD có dung lượngD. Hỏi cần ít nhất bao nhiêu đĩa CD để có thể sao chép đủ tất cả các tệp chương trình(mỗi tệp chỉ nằm trên một đĩa CD). Giải bài toán bằng phương pháp nhánh cận vàtham lam để so sánh kết quả.19. Cho một xâu S (độ dài không quá 200) chỉ gồm ba kí tự ‘A’, ‘B’ và ‘C’. Ta có phépđổi chỗ hai kí tự bất kỳ trong xâu. Hãy tìm cách biến đổi ít bước nhất để được xâutheo thứ tự tăng dần.20. Cho N (N≤1000) đoạn số [ai, bi], hãy chọn một tập hợp gồm ít số nhất mà mỗiđoạn số nguyên trên đều có ít nhất 2 số trong tập đó.21. Cho phân số M/N ()29. Palindrome: Một xâu được gọi là đối xứng nếu đọc từ trái qua phải cũng giốngnhư đọc từ phải qua trái. Cho một xâu gồm các ký tự ‘a’ đến ‘z’, hãy chèn vào xâu đóít nhất các kí tự để thu được một xâu đối xứng.30. Stones: Có N đống sỏi, đống thứ i có Ai viên sỏi. Ta có thể ghép hai đống sỏi kềnhau thàh một đống và mật một chi phí bằng tổng số sỏi của hai đống. Hãy tìm cáchghép N đống sỏi thành một đống với chi phí là nhỏ nhất.31. Cắt hình 1: Có một hình chủ nhật MxN ô vuông, mỗi lần ta được cắt một hình chủnhật thành hai hình chủ nhật con theo chiều ngang hoặc chiều dọc và lại tiệp tục cắtcác hình chữ nhật con cho đến khi được hình vuông thì dừng lại. Hỏi có thể cắt hìnhchủ nhật MxN thành ít nhất bao nhiêu hình vuông.32. Cắt hình 2:Cho một bảng số gồm M dòng, N cột, các giá trị của bảng A chỉ là 0 hoặc 1. Ta muốncắt bảng A thành các hình chữ nhật con sao cho các hình chữ nhật con có giá trị toànbằng 1 hay toàn bằng 0. Một lần cắt là một nhát cắt thẳng theo dòng hoặc theo cộtcủa một hình chữ nhật thành hai hình chữ nhật riêng biệt. Cứ tiếp tục cắt cho đên khihình chữ nhật có các giá trị taòn ằng 1 hay toàn bằng 0. Hãy tìm cách cắt để số hìnhchữ nhật con nhận được, có giá trị toàn là 1 hay toàn bằng 0, là nhỏ nhất.33. TKSEG:Cho dãy số A gồm N số nguyên và số nguyên K. Tìm dãy chỉ số 1≤ i1 < i2< ...