[算法]出个题目给大伙儿做得了

soloforce

那么冷清~ :beat
看谁先做出来，权当是工作之余的脑保键操

设计一个把一含有n个元素的数组循环右移k位的算法，要求时间复杂度为O(n)，且只允许使用2个附加变量~

:rolleyes:

well

[php]
C伪代码如下：
/* 思路是第1个与第K+1个交换，然后第K+1个与第K+1+K个交换，依此类推
   用到了一个变量交换2个值的方法， c = a+b; a = c -a; b = c -a
    时间复杂度为O(N)                                                 */
int A[N]; /*  设N为一已知常量 */
初始化A;
int i = 0, j = A[0];

do {
    j = j + A[(i+k) mod N];    /* k 为题中给出的已知常量 */
    A[(i+k) mod N] = j - A[(i+k) mod N];
    j = j - A[(i+k) mod N];
    i = (i+k) mod N;
} while ( i != 0);   /* 处理完N个元素结束 */
[/php]

soloforce

接近正确了，但还有纰漏
请考虑n=6, k=3的情况。

另外，交换两个变量的值其实不需要借助临时变量的。比如

1. 
   
2. a=a+b;
   
3. b=a-b;
   
4. a=a-b;
   

复制代码

同理还可以有异或运算^：采用如下表达式

1. 
   
2. a=a^b;
   
3. b=a^b;
   
4. a=a^b;
   

复制代码

bbbush

全忘了，依稀记得是群和群的分划，但是忘了怎么找 1-1 的函数了
N 不能整除 k 的时候会证明 O(n)，分划的一点都不会了，怎么做啊？

well

最近脑子经常进水，唉，抱歉

[php]
C伪代码如下：
/* 思路是第1个与第K+1个交换，然后第K+1个与第（K+1+K）mod N 个交换，依此类推
   用到了不借助中间变量的方法
     时间复杂度为O(N)                                                 */
int A[N]; /*  设N为一已知常量 */
初始化A;
int i = 0, j = 0;

do {
    if ( j == ((i+k) mod N) )             /* 处理部分特殊情况 */
        i = (j + 1) mod N;

    if ( (i != j) && (i == 0) )    /* 处理完N个元素结束 */
        return 1;                        
  
    A = A + A[(i+k) mod N];    /* k 为题中给出的已知常量 */
    A[(i+k) mod N] = A - A[(i+k) mod N];
    A = A - A[(i+k) mod N];

    j = i;     /*  记录刚处理过的位置 */
   
    i = (i+k) mod N;
} while ( 1 );
[/php]

另外谢谢教了个新东西：

同理还可以有异或运算^：采用如下表达式

代码:
a=a^b;
b=a^b;
a=a^b;

另外 bbbush 兄说的群环域的概念才是这个问题的数学模型，唉，回去好好补补数学
果然集体的感觉很好！谢谢

soloforce

Post by bbbush
全忘了，依稀记得是群和群的分划，但是忘了怎么找 1-1 的函数了
N 不能整除 k 的时候会证明 O(n)，分划的一点都不会了，怎么做啊？

bb兄高见，的确应当从划分的角度设计和证明。
[php]
/************************************************
把A[n]循环右移k位的时间复杂度为O(n)的C语言算法示例。
思路是把A[t]移到A[(t+k) mod n],其中t=0~n-1。
为尽量满足低空间复杂度要求，以某一元素作为移动的起
点，比如A,同时作为元素交换的枢纽，用next代表i右边
k位的元素关键字。

每次把A和A[next]交换，交换后更新next值(i不变)，
然后重复交换过程，直到i等于next时为止。

考虑到类似于n=6,k=3的情况，交换进行2次后(j=2)，虽然
i=next，但没有完成所有右移动作。故而此时需更新i值，即
i=i+1,然后再继续进行上面的交换过程。

可以证明，交换次数最多为n-1次;且按等k间隔对集合A[1..n]
进行划分的话，至多只有(k%n)个划分，故当i从0自增至k-1时，
应当终止外层循环。在"交换循环体"中，j的增量为j1，故当外层
循环中j+j1>=n时，也应当终止外层循环。

虽然有两个循环，但可以发现，其时间复杂度为O(n)。
*************************************************/
#include <stdio.h>
#define n 5
#define k 2
int A[n]={1,2,3,4,5};

int main()
{
        int i=0;        /* 数组索引关键字 */
        int j=0;        /* 交换次数计数器 */
        int j1=0;        /* 交换循环体执行完成后交换次数增量 */
        int next;        /* 下一个元素 */
        do
        {
                next=(i+k)%n; /* 右边k位*/
                j1=0;
                /* 交换循环体 */
                while(i!=next)
                {
                        /*swapping*/
                        A=A+A[next];
                        A[next]=A-A[next];
                        A=A-A[next];
                       
                        next=(next+k)%n;
                        j1++;
                }
                i++;
                j+=j1;
        }while(i<k%n && j+j1<n);

        for(i=0;i<n;i++)printf("%d ",A);
        printf("\nswap times=%d\n",j);
}[/php]

怎么也没办法只用两个附加变量来完成  怀疑原题有错 :confused:


哎，思维僵化了，看标准答案，真简洁：

1. 
   
2. void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间
   
3. {
   
4.   for(i=1;i<=k;i++)
   
5.     if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p
   
6.   for(i=0;i<p;i++)
   
7.   {
   
8.     j=i;l=(i+n-k)%n;temp=A[i];
   
9.     while(l!=i)
   
10.     {
    
11.       A[j]=A[l];
    
12.       j=l;l=(j+n-k)%n;
    
13.     }// 循环右移一步
    
14.     A[j]=temp;
    
15.   }//for
    
16. }//RSh
    

复制代码

bbbush

1. 
   
2. k = (k>=N) ? (k%N) : k;
   
3. if(k==0) goto out:
   
4. 
   
5.   for (i = 0; i < ((N % k) ? 1 : k); i++) {
   
6.       j = (i + N - k)%N;
   
7.       while(j != i) {
   
8.                   swap (a[j], a[(j + N - k)%N]);
   
9.                   j = (j + N - k)%N;
   
10.         }
    
11.    }
    

复制代码

只为我疯狂

答案的确是很好
不知道还有没有更好的办法

bbbush

一看就有问题，k<0 时候第一句就是错的，并且在代码里不应该有第二句 k==0 这种比较

light_zls

假设原序列为abcdef1234，要变换成1234abcdef。
可以这么做：
首先，反置abcdef：abcdef1234 -> fedcba1234
然后，反置1234：fedcba1234 -> fedcba4321
最后，全部反置：fedcba4321 -> 1234abcdef
反置用的函数只需要使用一个中间变量（甚至可以不要反置函数，直接用循环做）
算法复杂度为O(n)

来源：Programming Pearls