Đang chuẩn bị liên kết để tải về tài liệu:
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ứ. | 110. SỐ HIỆU VÀ GIÁ TRỊ 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ị ai 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ố p Kế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 . bn Cá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ách Ví dụ PERMUTE.INP PERMUTE.OUT 2 1 3 4 3 2 3 1 120 111. PHÉP CO Xét dãy số nguyên dương a ai a2 . an 2 n 100 1 ai 100 . Ban đầu dãy số được viết theo thứ tự từ trái sang phải từ ai 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 a và 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.OUT Gồ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ện Ví dụ SEQ.INP SEQ.OUT 5 -1 4 5 1 4 2 3 3 1 1 121 112. CHỮA NGOẶC Mộ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ãy tì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à .