Bài toán hoán đổi

a[1..n] là một mảng với phần gồm n phần tử. Ta cần chuyển m phần tử đầu tiên của mảng với phần còn lại của mảng ( n-m phân tử) mà không dùng một mảng phụ .

Chẳng n, với n = 8 a[8] = (1, 2, 3, 4,5, 6, 7, 8)

Nếu m = 3, thì kết quả là : ( 4, 5, 6, 7, 8, 1, 2, 3)

Nếu m = 5, thì kết quả là : ( 6, 7, 8, 1, 2, 3, 4, 5)

Nếu m = 4, thì kết quả là : ( 5, 6, 7, 8, 1, 2, 3, 4)

Nếu m = n- m : Hoán đổi các phần tử của 2 nửa mảng có độ độ dài bằng nhau :

Nếu m <> n-m :

- Nếu m < n - m : hoán đổi m phần tử đầu với m phân tử cuối của phần còn lại. Sau đó trong mảng a[1..n-m] ta chỉ cần hoán đổi m phần tử đầu với phần còn lại.

- Nếu m > n - m : hoán đổi n-m phần tử đầu tiên với n-m phần tử sau. Sau đó trong mảng a[n-m+1 . .n] ta hoán đổi n-m phần tử cuối mảng với các phần tử của phần đầu.

Như vậy, bằng cách áp dụng phương pháp chia để trị, ta chia bài toán thành 2 bài toán con:

- Bài toán thứ nhất là hoán đổi hai mảng con có độ dài bằng nhau, cụ thể là phần tử đầu và cuối của mảng cho nhau bằng cách đổi chỗ từng cặp phần tử tương ứng.

- Bài toán thứ hai cùng dạng với bài toán đã cho nhưng kích thước nhỏ hơn, nên có thể gọi thuật toán đệ qui để giải và quá trình gọi đệ qui sẽ dừng khi đạt tới sự hoán đổi 2 phần có độ dài bằng nhau

// Hoán đổi m phần tử

Input : a[1..n], m. (m <=n)

Output : a[1..n] với tính chất m phần tử đầu mảng a ( mảng nhập ) nằm cuối mảng kết quả, n-m phần tử cuối mảng nhập nằm ở đầu mảng kết quả.

Kí hiệu : T(i, j) là số phần tử cần đổi chỗ để hoán đổi dãy i phần tử và dãy j phần tử, ta có công thức truy hồi sau:

=> T(i,j) = i + j – UCLN(i,j) (Ước chung lớn nhất của i, j)