C / C ++-在不使用内置函数的情况下旋转数组的有效方法（作业） [英] C/C++ - efficient method of rotating an array without using build-in functions (homework)

问题描述

任务是向左旋转或向右旋转给定次数的数组子数组。

The task is to rotate left or rotate right a subarray of an array given number of times.

让我在一个示例中对此进行解释：

Let me explain this on an example:

• 让数据成为数组。

data = {0，1，2，3，4，5，6，7，8，9};

data = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

• 子数组由参数begin和end决定。

如果begin = 3和end = 7，则子数组为{0，1，2， 3，4，5 ，6，7， 8，9};

if begin = 3 and end = 7, then subarray is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

如果begin = 7且end = 3，则子数组为{ 0，1，2 ，3 ，4、5、6， 7、8、9 }；

if begin = 7 and end = 3, then subarray is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

• 向右旋转两次

如果begin = 3和end = 7，则结果为{0，1，2， 6、7、3、4、5， 8、9}；

if begin = 3 and end = 7, then the result is {0, 1, 2, 6, 7, 3, 4, 5, 8, 9};

如果begin = 7且end = 3，则结果为{ 8、9、0、1，，4、5、6， 2、3、7 }；

if begin = 7 and end = 3, then the result is {8, 9, 0, 1,, 4, 5, 6, 2, 3, 7};

我已经编写了执行此任务的代码，但速度很慢。
有人可以提示我如何使其更快吗？
重要提示：除数据，子程序和内置函数外，不允许使用其他数组。

I've written code that performs this task but it's to slow. Can someone give me a hint how to make it quicker? Important: I'm not allowed to use other arrays than data, subprograms and build-in functions.

#include <iostream>
using namespace std;

int main(){

    int dataLength;

    cin >> dataLength;

    int data [ dataLength ];

    for (int i = 0; i < dataLength; i++){
        cin >> data [ i ];
    }


    int begin;
    int end;
    int rotation;
    int forLoopLength;
    int tempBefore;
    int tempAfter;

    cin >> begin;
    cin >> end;
    cin >> rotation;

    if (end > begin)
       forLoopLength = (end - begin) + 1;
    else
       forLoopLength = (end - begin) + 1 + dataLength;

    if (rotation < 0) 
       rotation = forLoopLength + (rotation % forLoopLength);
    else
        rotation = rotation % forLoopLength;

    for (int i = 0; i < rotation; i++) {

        tempBefore = data [ end ];

        for (int i = 0; i < forLoopLength; i++) {
            tempAfter = data [ (begin + i) % dataLength ];
            data [ (begin + i) % dataLength ] = tempBefore;
            tempBefore = tempAfter;
        }
    }

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

    return 0;
}

推荐答案

这有一个窍门。如果在课堂上没有提到这个技巧，您会把它当作家庭作业是很奇怪的。无论如何...

There's a trick to this. It's pretty weird that you'd get this for homework if the trick wasn't mentioned in class. Anyway...

要旋转M留下的N个元素的序列：

To rotate a sequence of N elements left by M:

• 反转整个序列


• 反转最后M个元素


• 反转第一个NM元素

完成

例如由2留下：
1234567
->
7654321
->
7654312
->
3456712

e.g. left by 2: 1234567 -> 7654321 -> 7654312 -> 3456712

这篇关于C / C ++-在不使用内置函数的情况下旋转数组的有效方法（作业）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！