150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 7

Xét tất cả các hoán vị của dãy số tự nhiên (1, 2, ..., n); (1 ≤ n ≤ 12).Giả sử rằng các hoán vị được sắp xếp theo thứ tự từ điển. Ví dụ với n = 3, có 6 hoán vị: 1. 1 2 3 2. 1 3 2 3. 2 1 3 4. 2 3 1 5. 3 1 2 6. 3 2 1 Vấn đề đặt ra là: Cho trước một hoán vị (a1, a2, ..., an), hãy cho biết số thứ tự q của hoán vị đó và ngược lại: Cho trước một số thứ...
Nội dung trích xuất từ tài liệu:
150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 7 110. S HI U VÀ GIÁ TRXét tất cả các hoán vị của dãy số tự nhiên (1, 2, ..., n); (1 ≤ n ≤ 12).Giả sử rằng các hoán vị được sắpxếp theo thứ tự từ điển.Ví dụ với n = 3, có 6 hoán vị: 1. 1 2 3 2. 1 3 2 3. 2 1 3 4. 2 3 1 5. 3 1 2 6. 3 2 1Vấn đề đặt ra là: Cho trước một hoán vị (a1, a2, ..., an), hãy cho biết số thứ tự q của hoán vị đó vàngược lại: Cho trước một số thứ tự p (1 ≤ p ≤ n!) hãy tìm dãy hoán vị (b1, b2, ..., bn) mang số thứt ự p.Dữ liệu: Vào từ file văn bản PERMUTE.INP• Dòng 1: Chứa n số a1, a2, ..., an• Dòng 2: Chứa số pKết quả: Ghi ra file văn bản PERMUTE.OUT• Dòng 1: Ghi số q• Dòng 2: Ghi n số b1, b2, ..., bnCác số trên một dòng của Input / Output file ghi cách nhau ít nhất một dấu cáchVí dụ: PERMUTE.INP PERMUTE.OUT 213 3 4 231 120 111. PHÉP COXét dãy số nguyên dương a = (a1, a2, ..., an) (2 ≤ n ≤ 100; 1 ≤ ai ≤ 100). Ban đầu dãy số được viếttheo thứ tự từ trái sang phải, từ a1 tới an.Xét phép co R(i): Thay hai phần tử liên tiếp ai và ai+1 thành (ai - ai+1). Sau đó dãy được đánh chỉ sốlại: Từ trái sang phải, bắt đầu từ 1.Ví dụ: dãy a = (5, 1, 4, 2, 3)Với phép co R(1) ta có a = (4, 4, 2, 3)Với phép co R(3) ta có a = (4, 4, -1)Với phép co R(2) ta có a = (4, 5)Với phép co R(1) ta có a = (-1).Yêu cầu: Cho trước dãy a và số k. Hãy tìm một dãy n - 1 phép co để biến dãy a thành (k). (Dãy avà số k được cho để luôn tồn tại ít nhất một phương án)Dữ liệu: Vào từ file văn bản SEQ.INP• Dòng 1: Chứa hai số n, k• Dòng 2: Chứa n số a1, a2, ..., an.Kết quả: Ghi ra file văn bản SEQ.OUTGồm n - 1 dòng, mỗi dòng ghi vị trí của một phép biến đổi, các phép biến đổi phải được liệt kê theođúng thứ tự thực hiệnVí dụ SEQ.INP SEQ.OUT 5 -1 4 51423 3 1 1 121 112. CH A NGO CMột dãy dấu ngoặc đúng là một dãy các ký tự ( và ) được định nghĩa đệ quy như sau:1. () là một dãy dấu ngoặc đúng.2. Nếu A là một dãy dấu ngoặc đúng thì (A) là dãy dấu ngoặc đúng.3. Nếu B và C là hai dãy dấu ngoặc đúng thì BC là dãy dấu ngoặc đúng.Yêu cầu: Cho một xâu ký tự S độ dài n chỉ gồm các dấu ( và ) (n chẵn, 2 ≤ n ≤ 200). Hãytìm xâu T thoả mãn:• T là dãy dấu ngoặc đúng độ dài n• T là giống S nhất theo nghĩa: Số vị trí i mà T[i] ≠ S[i] là cực tiểuDữ liệu: Vào từ file văn bản BRACKETS.INP, chỉ gồm 1 dòng chứa xâu SKết quả: Ghi ra file văn bản BRACKETS.OUT cũng chỉ gồm một dòng ghi xâu T.Ví dụ: BRACKETS.INP BRACKETS.OUT )())())()))) ()((()))((())) 122 113. MÃ HOÁ BURROWS WHEELERCho một từ W độ dài n, người ta có một cách mã hoá như sau: Ví dụ với từ banana.Bước 1: Xét n hoán vị vòng quanh của W: banana ananab nanaba anaban nabana abananBước 2: Sắp xếp n hoán vị vòng quanh đó theo thứ tự từ điển: abanan anaban ananab banana (*) nabana nanabaBước 3:Gọi k là vị trí của từ ban đầu trong dãy hoán vị vòng quanh sau khi đã sắp xếp (ở đây k là 4).Lấy của mỗi hoán vị vòng quanh (theo đúng thứ tự sau khi đã sắp xếp theo thứ tự từ điển) một ký tựcuối và ghép thành một từ W (ở đây W = nnbaaa)Ta gọi cặp (W, k) là mã công khai của từ W.Yêu cầu:Viết chương trình đọc file văn bản DECODE.INP gồm nhiều cặp dòng: Cứ hai dòng liên tiếpchứa một mã công khai: dòng 1 chứa từ W và dòng 2 ghi số k. Tương ứng với mỗi cặp dòng đó,hãy giải mã và ghi vào file văn bản DECODE.OUT một dòng chứa từ W là từ đã giải mã rađược.Ràng buộc dữ liệu: Các từ được cho luôn khác rỗng, chỉ gồm các chữ cái in thường và có độ dàikhông quá 10000. Mã công khai luôn được cho đúng đắn.Ví dụ: DECODE.INP DECODE.OUT DECODE.INP DECODE.OUT nnbaaa Banana drtyeesya yesterday 4 8 all lla my 1 troubles ym seemed ...