Задача.

Дано: массив на N элементов.
Требуется: сдвинуть массив циклически на K позиций вправо.
K и N — любые положительные числа (разумные).

Доп.условия:
1. Дополнительную память не выделять (кроме нескольких временных переменных).
То есть не пропорционально K или N.
2. Рекурсией в глубину K или N не пользоваться.
3. Алгоритм должен обладать сложностью не хуже o(N).

Пример:
Для массива 1 2 3 4 5 6 7 при сдвиге на 3 позиции должно получиться
5 6 7 1 2 3 4.

IK>Попалась мне сегодня интересная задачка. Может кому-нибудь тоже понравится .

Принцип такой. 

Дано:

1 2 3 4 5 6 7

Меняем попарно 1 - 4, 2 - 3, 5 - 7

4 3 2 1 7 6 5 

Меняем попарно 4 - 5, 3 - 6, 2 - 7

5 6 7 1 2 3 4

Все.

Легко формализуется. 

Для  K < N

Берешь с конца K + 1 элемент, получаешь 2 части маасива

Разворачиваешь их попарными обменами

Получившийся массив целиком разворачиваешь еще раз.

int gcd (int a, int b); // определяет НОД(a,b).
int swap(int &a, int &b); // меняет местами а и b.

void cyclic_shift_right (int *A, int N, int K)
{
    for (int init = 0; init < gcd(N,K); init++)
    {
        int n = N / gcd(N,K);
        int temp = A[init];
        int current = init;
        while (n--) {
            current = (current + K) % N;
            swap(temp,A[current]);
        }
    }
}

int gcd(int a, int b)
{
  if(a < 0) a = -a;
  if(b < 0) b = -b;
  int c;
  while(b)
  {
    c = a % b; a = b; b = c;
  }
  return a;
}

void swap (int &a, int &b)
{
    int t = a; a = b; b = t;
}

void cyclic_shift_right (int *A, int N, int K)
{
    for (int init = 0; init < gcd(N,K); init++)
    {
        int n = N / gcd(N,K);
        int temp = A[init];
        int current = init;
        while (n--) {
            current = (current + K) % N;
            swap(temp,A[current]);
        }
    }
}

void print_array (int *A, int N)
{
    for (int i = 0; i < N; i++) std::cout << A[i] << " ";
}


int main(int argc, char* argv[])
{
    int A[] = {1,2,3,4,5,6,7,8,9};
    cyclic_shift_right (A,9,12);
    print_array (A,9);
    return 0;
}

IK>Попалась мне сегодня интересная задачка. Может кому-нибудь тоже понравится .

//n - размерность массива
//m - на сколько сдвинуть
shift(arr[], n, m)
{
  reverse(arr, 0, m);
  reverse(arr, m, n);
  reverse(arr, 0, n);
}

    int tmp[2];
    tmp[0]=a[0];
    for(int i=0, j=0;i<N;i++)
    {
        j+=K;j%=N;
        tmp[~i&1]=a[j];
        a[j]=tmp[i&1];
    }

WH>    int tmp[2];
WH>    tmp[0]=a[0];
WH>    for(int i=0, j=0;i<N;i++)
WH>    {
WH>        j+=K;j%=N;
WH>        tmp[~i&1]=a[j];
WH>        a[j]=tmp[i&1];
WH>    }
WH>

enum
{
    N=7,
    K=17,
};
int a[N];
void Rec(int p, int l1, int l2)
{
    if((!l1)||(!l2))return;
    if(l1<l2)
    {
        for(int i=p, t;i<p+l1;i++)
        {
            t=a[i];
            a[i]=a[i+l2];
            a[i+l2]=t;
        }
        Rec(p, l1, l2-l1);
    }
    else if(l1>l2)
    {
        for(int i=p, t;i<p+l2;i++)
        {
            t=a[i];
            a[i]=a[i+l1];
            a[i+l1]=t;
        }
        Rec(p+l2, l1-l2, l2);
    }
    else
    {
        for(int i=p, t;i<p+l1;i++)
        {
            t=a[i];
            a[i]=a[i+l2];
            a[i+l2]=t;
        }
    }
}
int main()
{
    Rec(0, N-K%N, K%N);//shift right
    Rec(0, K%N, N-K%N);//shift left
    return 0;
}

    if(int k=K%N)
    {
        for(int i=0, t;i<k/2;i++)
        {
            t=a[i];
            a[i]=a[k-i-1];
            a[k-i-1]=t;
        }
        for(int i=0, t;i<(N-k)/2+1;i++)
        {
            t=a[i+k];
            a[i+k]=a[N-i-1];
            a[N-i-1]=t;
        }
        for(int i=0, t;i<N/2;i++)
        {
            t=a[i];
            a[i]=a[N-i-1];
            a[N-i-1]=t;
        }
    }

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* rotate.c -- time algorithms for rotating a vector
    Input lines:
        algnum numtests n rotdist
        algnum:
          1: reversal algorithm
          2: juggling algorithm
          22:  juggling algorithm with mod rather than if
          3: gcd algorithm
          4: slide (don't rotate): baseline alg for timing
    To test the algorithms, recompile and change main to call testrot
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXN 10000000

int x[MAXN];
int rotdist, n;

/* Alg 1: Rotate by reversal */

void reverse(int i, int j)
{    int t;
    while (i < j) {
        t = x[i]; x[i] = x[j]; x[j] = t;
        i++;
        j--;
    }
}

void revrot(int rotdist, int n)
{    reverse(0, rotdist-1);
    reverse(rotdist, n-1);
    reverse(0, n-1);
}

/* Alg 2: Juggling (dolphin) rotation */

int gcd(int i, int j)
{    int t;
    while (i != 0) {
        if (j >= i)
            j -= i;
        else {
            t = i; i = j; j = t;
        }
    }
    return j;
}

void jugglerot(int rotdist, int n)
{    int cycles, i, j, k, t;
    cycles = gcd(rotdist, n);
    for (i = 0; i < cycles; i++) {
        /* move i-th values of blocks */
        t = x[i];
        j = i;
        for (;;) {
            k = j + rotdist;
            if (k >= n)
                k -= n;
            if (k == i)
                break;
            x[j] = x[k];
            j = k;
        }
        x[j] = t;
    }
}

void jugglerot2(int rotdist, int n)
{    int cycles, i, j, k, t;
    cycles = gcd(rotdist, n);
    for (i = 0; i < cycles; i++) {
        /* move i-th values of blocks */
        t = x[i];
        j = i;
        for (;;) {
          /* Replace with mod below
            k = j + rotdist;
            if (k >= n)
                k -= n;
           */
            k = (j + rotdist) % n;
            if (k == i)
                break;
            x[j] = x[k];
            j = k;
        }
        x[j] = t;
    }
}

/* Alg 3: Recursive rotate (using gcd structure) */

void swap(int i, int j, int k) /* swap x[i..i+k-1] with x[j..j+k-1] */
{    int t;
    while (k-- > 0) {
        t = x[i]; x[i] = x[j]; x[j] = t;
        i++;
        j++;
    }

}

void gcdrot(int rotdist, int n)
{    int i, j, p;
    if (rotdist == 0 || rotdist == n)
        return;
    i = p = rotdist;
    j = n - p;
    while (i != j) {
        /* invariant:
            x[0  ..p-i  ] is in final position
            x[p-i..p-1  ] = a (to be swapped with b)
            x[p  ..p+j-1] = b (to be swapped with a)
            x[p+j..n-1  ] in final position
        */
        if (i > j) {
            swap(p-i, p, j);
            i -= j;
        } else {
            swap(p-i, p+j-i, i);
            j -= i;
        }
    }
    swap(p-i, p, i);
}

int isogcd(int i, int j)
{    if (i == 0) return j;
    if (j == 0) return i;
    while (i != j) {
        if (i > j)
            i -= j;
        else 
            j -= i;
    }
    return i;
}

void testgcd()
{
    int i,j;
    while (scanf("%d %d", &i, &j) != EOF)
        printf("%d\n", isogcd(i,j) );
}

/* Test all algs */

void slide(int rotdist, int n) /* Benchmark: slide left rotdist (lose 0..rotdist-1) */
{    int i;

    for (i = rotdist; i < n; i++)
        x[i-rotdist] = x[i];
}

void initx()
{
    int i;
    for (i = 0; i < n; i++)
        x[i] = i;
}

void printx()
{    int i;
    for (i = 0; i < n; i++)
        printf(" %d", x[i]);
    printf("\n");
}

void roterror()
{
    fprintf(stderr, " rotate bug %d %d\n", n, rotdist);
    printx();
    exit (1);
}

void checkrot()
{    int i;
    for (i = 0; i < n-rotdist; i++)
        if (x[i] != i+rotdist)
            roterror();
    for (i = 0; i < rotdist; i++)
        if (x[n-rotdist+i] != i)
            roterror();
}

void testrot()
{    for (n = 1; n <= 20; n++) {
        printf(" testing n=%d\n", n);
        for (rotdist = 0; rotdist <= n; rotdist++) {
            /* printf("  testing rotdist=%d\n", rotdist); */
            initx(); revrot(rotdist, n);     checkrot();
            initx(); jugglerot(rotdist, n);  checkrot();
            initx(); jugglerot2(rotdist, n); checkrot();
            initx(); gcdrot(rotdist, n);     checkrot();
        }
    }
}

/* Timing */

void timedriver()
{    int i, algnum, numtests, start, clicks;
    while (scanf("%d %d %d %d", &algnum, &numtests, &n, &rotdist) != EOF) {
        initx();
        start = clock();
        for (i = 0; i < numtests; i++) {
            if (algnum == 1)
                revrot(rotdist, n);
            else if (algnum == 2)
                jugglerot(rotdist, n);
            else if (algnum == 22)
                jugglerot2(rotdist, n);
            else if (algnum == 3)
                gcdrot(rotdist, n);
            else if (algnum == 4)
                slide(rotdist, n);
        }
        clicks = clock() - start;
        printf("%d\t%d\t%d\t%d\t%d\t%g\n",
            algnum, numtests, n, rotdist, clicks,
            1e9*clicks/((float) CLOCKS_PER_SEC*n*numtests));
    }
}

/* Main */

int main()
{    /* testrot(); */
    timedriver();
    return 0;
}