Tài liệu

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

Science and Technology

Bài toán

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)

Phân tích thuật toán

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

Thuật toán

// 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ả.

Độ phức tạp thuật toán

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)

Đánh giá:
0 dựa trên 0 đánh giá

Tuyển tập sử dụng module này

Nội dung cùng tác giả
 
Nội dung tương tự