Cho số nguyên N và K. Nhiệm vụ: tính hoán vị của N và sắp xếp lại sao cho mỗi phần tử cách nhau đúng K vị trí.
Các trường hợp đầu vào/đầu ra
Đầu vào - n = 20, k = 2
Đầu ra - Sắp xếp N số đầu tiên cách nhau K: 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18.
Giải thích - Hoán vị 1..20. Sắp xếp sao cho mỗi phần tử cách K=2 vị trí.
Đầu vào - n = 10, k = 3
Đầu ra - Sắp xếp N số đầu tiên cách nhau K: Not Possible
Giải thích - Với n=10, k=3 không thể sắp xếp thỏa mãn.
Phương pháp sử dụng trong chương trình dưới đây
Nhập N, K. Gọi Rearrangement(n, k).
Trong Rearrangement:
temp = n % (2*k).
Mảng ptr[n+1].
Nếu k==0: in 1..n.
Nếu temp != 0: in "Not Possible".
Khởi tạo ptr[i] = i (1..n).
Vòng for i=1 đến n bước 2*k: vòng for j=1 đến k: swap(ptr[i+j-1], ptr[k+i+j-1]).
In ptr[1..n].
In kết quả.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; void Rearrangement(int n, int k){ int temp = n % (2 * k); int ptr[n + 1]; if(k == 0){ for(int i = 1; i <= n; i++){ cout << i << " "; } return; } if(temp != 0){ cout<<"Not Possible"; return; } for(int i = 1; i <= n; i++){ ptr[i] = i; } for(int i = 1; i <= n; i += 2 * k){ for(int j = 1; j <= k; j++){ swap(ptr[i + j - 1], ptr[k + i + j - 1]); } } for(int i = 1; i <= n; i++){ cout << ptr[i] << " "; } } int main(){ int n = 20; int k = 2; cout<<"Sắp xếp N số đầu tiên cách nhau K: "; Rearrangement(n, k); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Sắp xếp N số đầu tiên cách nhau K: 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18