有没有人懂编这个算法?

苏格拉底柏拉图

数据结构上机作业第5章第18题有没有会做？
就是一个元素个数为n的数组要实现它k位循环右移。要求元素被移动次数为O（n），而且只能用一个附加储存空间。

liuaa24

5．18试设计一算法，将数组An中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O（n）。

（教材上的答案）本题难点在于找到O（n）的算法。注意分析研究此问题的数学性质，以寻求好的算法。本题有多种解法，但要注意不要将在特殊条件下出现的现象当作一般规律。例如，本题易犯的错误是，从第i个分量中的元素起，循环右移k位，顶掉第（j+k）%n的元素，依次类推。这似乎是个漂亮的算法，但只是在某些情况下可得到正确结果。

参考程序：

void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间
{
  for(i=1;i<=k;i++)
    if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p
  for(i=0;i<p;i++)
  {
    j=i;l=(i+k)%n;temp=A;
    while(l!=i)
    {
      A[j]=temp;
      temp=A[l];
      A[l]=A[j];
      j=l;l=(j+k)%n;
    }// 循环右移一步
    A=temp;
  }//for
}//RSh

分析:
要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起 点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:
n=15,k=6,则p=3.
第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].
第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].
第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].
恰好使所有元素都右移一次.


不是我做的

苏格拉底柏拉图

谢谢佳哥！

iptton

不提倡直接帖作业代码，虽然这些代码在网上很轻易就能找得到

[ 本帖最后由 iptton 于 2007-5-29 18:05 编辑 ]

苏格拉底柏拉图

我是编来编去失败了才找上门来的。

九月鹰飞

我想问一下怎么想到求公约数那去了？

投降输一半

这里用到了循环群的理论。

onttpi

C++下的测试……
如＃2所说，这是一道数学题……
算法没搞明白的话
本程序大概也读不大懂……

1. 
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. typedef char ElemType;
   
6. typedef char Array1D[30];
   
7. 
   
8. void Rotate(Array1D a, int len, int step)
   
9. {
   
10.     ElemType tmp1,tmp2;
    
11.     int times=1,i,j,k;//k为最大公约数
    
12.     step=step%len;
    
13.     cout<<"step="<<step<<"\t";
    
14.     if(0==step)return;   
    
15.     /*用i,j为临时变量求 len和step的最大公约数*/
    
16.     i=len;
    
17.     j=step;
    
18.     while(times=i%j){        
    
19.         i=j;
    
20.         j=times;
    
21.     }
    
22.     cout<<"j="<<j<<"\tstep="<<step<<endl;
    
23.     /*j为最大公约数*/
    
24.     k=j;
    
25.     times=len/k;
    
26.     for(i=0;i<k;++i){
    
27.         tmp2=a[i];
    
28.         tmp1=a[i+step];
    
29.         a[(i+step)%len]=tmp2;
    
30.         tmp2=tmp1;
    
31.         for(j=1;j<times;++j){
    
32.             tmp1=a[(i+(j+1)*step)%len];
    
33.             a[(i+(j+1)*step)%len]=tmp2;
    
34.             tmp2=tmp1;
    
35.         }//for
    
36.     }//for
    
37. }
    
38. 
    
39. int main(){
    
40.         Array1D p="ABCDEFGHIJKLMNOPQRST";
    
41.         for(int i=0;i<13;++i){
    
42.                 Rotate(p,8,i);　//8可以换成＜＝20的数，i任意
    
43.                 cout<<p<<endl;
    
44.         }
    
45.         cout<<p<<endl;
    
46.         return 0;
    
47. }
    

复制代码

onttpi

极不喜欢作业系统上的调试……

另：
作业系统对于 ++a=b++;　这样的语句，表现诡异
有写了这样句子的建议改成三句……

powerwind

++a=b++
这种东西应该像鄙视goto一样BS

onttpi

原帖由 powerwind 于 2007-6-5 13:17 发表
++a=b++
这种东西应该像鄙视goto一样BS

MS见过这样的代码：

while(src!='\0')
   *des++=*src++;


不过这个的确和一个前加一个后加不同……
发现现在较熟练前加后加了……
上次做数据结构题目时就用了一个前加和一个后加……
为了省打字，而且那代码只是我看我改……