Nhờ góp ý thuật toán: Dịch xoay vòng k lần các phần tử trong mảng 1 chiều

Bạn xem cách của mình thử:
Gọi rev(A) là reverse của mảng A. Ví dụ k = 3:
rev (A) = 5 4 3 2 1
rev (A [ 0 … (n - 1- k) ]) = 4 5 3 2 1
rev (A [ (n - k) … (n - 1) ] = 4 5 1 2 3

Gọi n là số lượng phần tử của arr, k là số lần xoay. Đầu tiên chúng ta phải chia lấy dư k với n, vì sao?

Giả sử k = 6 và n = 5, k % n == 1 -> chỉ cần xoay vòng 1 lần -> hợp lý. Sau khi mod xong thì k chắc chắn sẽ nhỏ hơn n, dễ dàng tính toán hơn.

k = k % n

Tiếp theo là thực hiện xoay, tùy theo giá trị k mà xoay bấy nhiêu lần thôi:

for j = 0, j < k, j++:    
    for i = 0, i < n - 1, i++:
        swap(arr[i], arr[i+1])

P.S. Mình quên đọc tới phần dịch phải, nhưng cũng tương tự dịch trái thôi. Bạn nên bỏ mấy câu comment đi, đặt tên biến rõ nghĩa ra chứ đừng có k, n, t này nọ. Chỉ đặt tên biến 1 ký tự khi viết loop, còn lại nên viết đầy đủ, cái tên biến phải giải thích được vai trò của nó chứ không phải dùng comment để giải thích.

Mấy bài dạng này có nhiều đề rất thú vị, ví dụ như bài này:

100 gunmen in a circle kill next person

This post was flagged by the community and is temporarily hidden.

nhưng cấp phát động cho mảng mới thì khá chậm

This post was flagged by the community and is temporarily hidden.

Tiếp theo là thực hiện xoay, tùy theo giá trị k mà xoay bấy nhiêu lần thôi:

Perfect

Bạn nên bỏ mấy câu comment đi,

Mục đích mình để mấy comments là để cho mấy người đọc / xem code sẽ dễ hiểu hoặc hiểu nhanh hơn, vì nó có phần hơi “dài” nên sợ có người đọc rồi nản.
Chứ khi code, mình không bao giờ để comments đâu bạn !

đặt tên biến rõ nghĩa ra chứ đừng có k, n, t này nọ

OK, làm biếng quá !!!
Thanks everyone

Code update Nhờ mọi người góp ý và cải thiện tiếp !

void DichXoayVong(int a[], int n, int k, char t)
{
	k %= n;
	if (t == 't')
		for (int i = 0; i < k; i++)
			for (int j = 0; j < n - 1; j++)
				swap(a[j], a[j + 1]);
	else
		for (int i = 0; i < k; i++)
			for (int j = n - 1; j > 0; j--)
				swap(a[j], a[j - 1]);
}

Còn một cách nữa, đó là chỉ xoay một lần duy nhất tại vị trí k sau khi lấy k mod n, cần chia trường hợp khi k và n chẵn hoặc lẻ. Mình đang đi du lịch nên không có máy test… =))

Cách này thì hơi lằng nhằng với các bác tí nhưng được cái độ phức tạp nhỏ.

void Xoay(int a[], int k)
{
    int temp[5];
    int i_temp=k%5;
    int j_temp=i_temp;
    int count_temp=0;
//Copy tạm qua clone
    for (; i_temp<5; i_temp++) {
        temp[i_temp-j_temp]=a[i_temp];
        count_temp++;
    }
    for (int i=0; i<j_temp; i++) {
        temp[i+count_temp]=a[i];
    }
//Copy qua mảng ban đầu lại
    for (int i=0; i<5; i++) {
        a[i]=temp[i];
    }
}

Bài này kết hợp đồng dư với nhân đôi mảng =)))

Xoay mảng có thể thực hiện trong Theta(n) và O(1) mem.

Chắc thế :V