Циклический сдвиг элементов массива влево на k шагов

Question

Смог реализовать слишком банальный код для того чтоб циклично сдвинуть массив на одно значение. Нужно как-то реализовать сдвиг на k-значений, при этом нельзя использовать какие-либо функции, только циклы. Прошу Вашей помощи!

Мой код:

#include <iostream>

using namespace std;

int main()
{
    const int N = 4;
    int arr[N] = { 1, 2, 3, 4 };

    int el = arr[0];
    for (int i = 1; i < N; ++i)
        arr[i - 1] = arr[i];
    arr[N - 1] = el;

    for (int i = 0; i < N; ++i)
        cout << arr[i] << " ";
}

Answer 1

Общий алгоритм циклического сдвига легко реализуется с помощью обращения порядка элементов. Рассмотрим, например, массив

a b c d e f g h i j k l

который надо сдвинуть на 4 позиции вправо. Это значит, что слева должны оказаться элементы i j k l. При обращении порядка элементов они именно там и окажутся, правда, в обратном порядке:

l k j i h g f e d c b a

Но если теперь развернуть только первые 4 элемента, они оказываются на своем месте...

i j k l h g f e d c b a

Осталось развернуть вторую часть - остальные 8 элементов:

i j k l a b c d e f g h

Вот и все, мы получили, что нужно.

Теперь осталось реализовать это в коде. Напишем функцию обращения массива от i-го до j-го элемента.

void rev(int * a, int i, int j)
{
    while(i < j)
    {
        int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
        i++; j--;
    }
}

Теперь сдвиг написать запросто:

int main()
{
    const int N = 10;
    int arr[N] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    int k = 4;

    rev(arr,0,N-1);
    rev(arr,0,k-1);
    rev(arr,k,N-1);

    for (int i = 0; i < N; ++i)
        cout << arr[i] << " ";
}

Понятно, что для больших k надо брать остаток от деления на N, для сдвига в обратную сторону — отрицательное значение и приводить его в диапазон от 0 до N-1.

Answer 2

#include <iostream>

using namespace std;

int main()
{
// массив из 5 елементов
    const int SIZE = 5;
    int arr[SIZE]{1,2,3,4,5};
    
    cout << "Number of shifts: \n";
    int shift = 0;
    cin >> shift;

    for (int i = 0; i < shift; i++) // количество сдвигов
    {
        int temp = arr[SIZE - 1]; // сохраняєм последний елемент

        // rerighting array
        for (int j = SIZE - 2; j >= 0; j--)
        {
            arr[j + 1] = arr[j];
        }
        arr[0] = temp; // записываем последний елемент в первый
    }
            
    cout << endl;

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }

    system("pause>0");

}

БЛОГ НА HUSL

Циклический сдвиг элементов массива влево на k шагов

Ответы (2 шт):