Блог

Главная - Вопросы по программированию - Операция поворота вправо

Операция поворота вправо

#c #rotation

#c #поворот

Вопрос:

 int main()
{
    int shiftSteps, newposition;
    int numbers[10], numberscopy[10];
    cin >> shiftSteps;

    for (int i = 0; i < 10; i  )
        cin >> numbers[i];

    for (int i = 0; i < 10; i  )
        numberscopy[i] = numbers[i];

    //----------------------------------------

    for (int i = 0; i < 10; i  )
    {
        newposition = (i   shiftSteps) % 10;
        numbers[newposition] = numberscopy[i];
    }

     for (int i = 0; i < 10; i  )
        cout << numbers[i] << "  ";
}

Я написал этот код, чтобы повернуть 10 чисел вправо с помощью вспомогательного массива «numberscopy», но я хочу переписать код без вспомогательного массива, и я не знаю как.

Ответ №1:

Вы можете повернуть массив на месте, то есть без использования вспомогательного массива с помощью std::rotate, который является стандартным алгоритмом.

 std::rotate(numbers, numbers   shiftSteps, numbers   10);

Ответ №2:

Без вспомогательного массива вы можете использовать алгоритм разворота для поворота массива на «shiftSteps». Она включает в себя следующие три шага,

  • изменение массива с 0 на размер массива-1
  • изменение массива с 0 на shiftSteps-1
  • изменение массива с shiftSteps на sizeOfArray-1

Вот окончательный код,

 void reverseArray(int numbers[], int begin, int end) 
{ 
    while (begin < end) 
    { 
        swap(numbers[begin], numbers[end]); 
        begin  ; 
        end--; 
    } 
} 

void rightRotate(int numbers[], int shiftSteps, int sizeOfArray) 
{ 
    reverseArray(numbers, 0, sizeOfArray-1);
    reverseArray(numbers, 0, shiftSteps-1);
    reverseArray(numbers, shiftSteps, sizeOfArray-1);
    
} 


int main()
{
    int shiftSteps;
    int numbers[10];
    cin >> shiftSteps;

    for (int i = 0; i < 10; i  )
        cin >> numbers[i];

    rightRotate(numbers, shiftSteps, 10);
 
    for (int i = 0; i < 10; i  )
        cout << numbers[i] << "  ";
}

Источник для получения дополнительной информации.

Комментарии:

1. Это интересный подход, хотя и немного неэффективный. Вы все равно можете использовать std::reverse вместо написания функции разворота самостоятельно.

2. @cigien да, мы можем использовать std::reverse , и даже тогда std::rotate , вероятно, будет быстрее, насколько я помню, это выиграет от оптимизации memmove(), но я думаю, что автор искал ответ с алгоритмической точки зрения. Кстати, этот подход использовался в ранних редакторах UNIX для перемещения текста.

3. @cigien Вращение «в три оборота» на самом деле имеет хорошую производительность и используется в реализациях стандартной библиотеки libstdc и Microsoft C .

4. @Blastfurnace О, это очень интересно, я этого не знал. Наивно, я бы ожидал, что это будет иметь худшую производительность. Спасибо за информацию.

5. @cigien Reversal очень удобен для кэширования смежных контейнеров. Тремя наиболее распространенными алгоритмами поворота являются обмен блоками Гриса-Миллса, жонглирование (GCD) и разворот. Все это можно найти в реализациях стандартной библиотеки C в зависимости от типов итераторов.

Метки: