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

#1

Xin chào mọi người.

Mình có 1 bài tập như sau: Cho người dùng nhập vào 1 mảng số nguyên. Sau đó dịch trái hoặc phải xoay vòng k lần (với k là số do người dùng nhập vào, t là ký tự để phân biệt dịch trái hoặc phải). Xuất mảng sau khi dịch.

VD: Mảng ban đầu là 1 2 3 4 5

Dịch trái xoay vòng 1 lần => 2 3 4 5 1

Dịch trái xoay vòng 2 lần => 3 4 5 1 2

Dịch trái xoay vòng 3 lần => 4 5 1 2 3

Dịch trái xoay vòng 4 lần => 5 1 2 3 4

Dịch trái xoay vòng 5 lần => 1 2 3 4 5

Dịch trái xoay vòng 6 lần => trở về giống như dịch trái xoay vòng 1 lần

Dịch trái xoay vòng 7 lần => trở về giống như dịch trái xoay vòng 2 lần

Source code:

void DichXoayVong(int a[], int n, int k, char t) // char t dùng để xác định dịch xoay vòng bên trái hay phải
{ // k là số lần dịch xoay vòng
	while (k >= 5) // Nếu k >= 5 thì trừ k cho 5 vì bản chất, dịch xoay vòng 6 giống như dịch xoay vòng 1, dịch 7 giống dịch 2, ...
		k -= 5;
	for (int x = 0; x < k; x++)
	{
		if (t == 't') // t là trái (t)
		{
			int bienphu = a[0];
			int Solan = 0;
			for (int i = 0; i < n; i++)
			{
				if (Solan == n)
					break;
				if (i == n - 1)
					a[i] = bienphu;
				else
					a[i] = a[i + 1];
				Solan++;
			}
		}
		else // ngược lại là phải (p)
		{
			int bienphu = a[n - 1];
			int Solan = 0;
			for (int i = n - 1; i >= 0; i--)
			{
				if (Solan == n)
					break;
				if (i == 0)
					a[i] = bienphu;
				else
					a[i] = a[i - 1];
				Solan++;
			}
		}
	}
}

Mình xin nhờ mọi ngưới góp ý và cải thiện thuật toán của mình với bài toán trên cho ngắn gọn - tối ưu hơn (vì code của mình trong có vẻ dài dòng và lưa thưa)

Xin cảm ơn mọi người nhiều !

#2

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

3 Likes
#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:

2 Likes
#4

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

#5

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

#6

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

#7

Perfect :thumbsup:

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 !

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

#8

Code update :slight_smile: 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]);
}
#9

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… =))

1 Like
#10

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];
    }
}
#11

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

#13

Mình có phần code này dễ hiều hơn và cũng thấy đúng mn tham khảo ạ

#include <bits/stdc++.h>
using namespace std;
int n , d ;
int a[1000000] ;
int main()
{
    cin >> n >> d ;
    for ( int i=1 ; i<=n ; i++ ) cin >> a[i] ;
    d = d%n ;
    for ( int i=d+1 ; i<=n ; i++) cout << a[i] << " " ;
    for ( int i=1 ; i<=d ; i++ )
    {
        cout << a[i] << " " ;
    }
    return 0;
}
#14

Mình lười :

void Shift(int *data, int datasize, int steps, bool left){
    if(step >= datasize) return;
    int *buffer = new int[step];
    if(left){
        memcpy(buffer,data,steps);
        memcpy(data, data + steps, datasize-steps);
        memcpy(data + steps, buffer, steps);
    }
    else{
        memcpy(buffer, data + datasize - steps, steps);
        memcpy(data + datasize - steps, data, steps);
        memcpy(data, buffer, steps);
    }

    delete[] buffer;
}

PS : Ó đào mộ à .

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?