Chào mừng bạn đến với t2sit.violet.vn
baitap_tkdgtt.doc
- 0 / 0
-
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Hoàng Thái Sơn (trang riêng)
Ngày gửi: 10h:53' 09-08-2012
Dung lượng: 52.0 KB
Số lượt tải: 26
Nguồn:
Người gửi: Hoàng Thái Sơn (trang riêng)
Ngày gửi: 10h:53' 09-08-2012
Dung lượng: 52.0 KB
Số lượt tải: 26
Số lượt thích:
0 người
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:
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 đó)
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 đó.
Đá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).
Mã hóa bằng ngôn ngữ C, C++ hoặc Java.
Đưa ra các ví dụ để test lại chương trình.
1. Cho xâu S (độ dài <10) chỉ gồm các kí tự ‘A’ đến ‘Z’. Các ký tự trong xâu S đôi một khác nhau. Hãy liệt kê các hoán vị khác nhau của xâu S.
2. Cho số nguyên dương n (n<20), hãy liệt kê tất cả các xâu độ dài n chỉ gồm các kí tự ‘A’ hoặc ‘B’ mà không có 2 kí tự ‘B’ nào đứng cạnh nhau
3. Cho dãy số A gồm n (n<10) số nguyên a1, a2, .. an và một số nguyên dương k (1
4. Một xâu X =x1x2...xm được gọi là xâu con của xâu Y=y1y2...yn nếu ta có thể nhận được xâu X từ xâu Y bằng cách xóa đi một số kí tự. Nhập vào một xâu S (độ dài <15). Hãy liệt kê các xâu con khác nhau của xâu S.
5. Cho số nguyên dương n (n<10), liệt kê tất cả các cách khác nhau đặt n dấu ngoặc mở và n dấu ngoặc đóng đúng đắn.
6. Cho n (n<10) số nguyên dương a1, a2, ... an . Tìm số nguyên dương m nhỏ nhất sao cho m không phân tích được dưới dạng tổng của một số các số (mỗi số sử dụng không quá một lần) thuộc n số trên.
7. Cho xâu S (độ dài < 10) chỉ gồm các kí tự ‘A’ đến ‘Z’. Các ký tự trong xâu S không nhất thiết phải khác nhau. Hãy liệt kê tất cả các hoán vị khác nhau của xâu S.
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ải củ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 (n<10), hay đưa ra các số siêu nguyên tố có n chữ số cùng các số đó.
10. Cho một xâu S (chỉ gồm các ký tựu ‘0’ đến ‘9’, độ dài nhỏ hơn 10) và một số nguyên M, hãy đưa ra một cách chèn vào S các dấu ‘+’ hoặc ‘-’ để thu được số M cho trước (nếu có thể).
11. Cho bàn cờ n x n ô, hai quân tượng (trong cờ vua) gọi là chiếu nhau nếu chúng cùng nằm trên một đường chéo (chính hoặc phụ). Cho K quân tượng. Hỏi có bao nhiêu các đặt các quan tượng vào bàn cờ mà các quân tượng không chiếu nhau.
12. N-mino là hình thu được từ N hình vuông 1x1 ghép lại (cạnh kề nhau). Hai N-mino được gọi là đồng nhất nếu chúng có thể đặt chồng khít lên nhau. Cho một số nguyên N (1< N <8). Tính và vẽ ra tất cả các N-mino trên màn hình.
13. Cho bàn cờ vua 8x8, mỗi ô ghi một số nguyên dương. Hãy xếp 8 con hậu lên bàn cờ sao cho không quan nào ăn con nào và tổng các số ghi trên các ô mà quân hậu đứng là lớn nhất.
14. Một chiếc ba lô có thể chứa được một khối lượng w. Có n (n<20) đồ vật được đánh số 1, 2, ..., n. Đồ vật i có khối lượng là ai và giá trị ci. Cần chọn các đồ vật cho vào ba lô để tổng qiá trị các đồ vật là lớn nhất.
15. Dominoes:
Mỗi con domino là một hình hộp vuông sáu mặt, chỉ trên đúng 2 mặt đối diện (trong số 3 cặp mặt đối diện) ghi các số từ 1 đến 6.
Có N con
Thư viện
banner2ben
Các ý kiến mới nhất