有没有人懂编这个算法?
数据结构上机作业第5章第18题有没有会做？就是一个元素个数为n的数组要实现它k位循环右移。要求元素被移动次数为O（n），而且只能用一个附加储存空间。 5．18试设计一算法，将数组An中的元素A至A循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O（n）。
（教材上的答案）本题难点在于找到O（n）的算法。注意分析研究此问题的数学性质，以寻求好的算法。本题有多种解法，但要注意不要将在特殊条件下出现的现象当作一般规律。例如，本题易犯的错误是，从第i个分量中的元素起，循环右移k位，顶掉第（j+k）%n的元素，依次类推。这似乎是个漂亮的算法，但只是在某些情况下可得到正确结果。
参考程序：
void RSh(int A,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=temp;
temp=A;
A=A;
j=l;l=(j+k)%n;
}// 循环右移一步
A=temp;
}//for
}//RSh
分析:
要把A的元素循环右移k位,则A移至A,A移至A......直到最终回到A.然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A,A,...A为起 点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:
n=15,k=6,则p=3.
第一条链:A->A,A->A,A->A,A->A,A->A.
第二条链:A->A,A->A,A->A,A->A,A->A.
第三条链:A->A,A->A,A->A,A->A,A->A.
恰好使所有元素都右移一次.
不是我做的 谢谢佳哥！ 不提倡直接帖作业代码，虽然这些代码在网上很轻易就能找得到
[ 本帖最后由 iptton 于 2007-5-29 18:05 编辑 ] 我是编来编去失败了才找上门来的。 我想问一下怎么想到求公约数那去了？ 这里用到了循环群的理论。 C++下的测试……
如＃2所说，这是一道数学题……
算法没搞明白的话
本程序大概也读不大懂……
#include <iostream>
using namespace std;
typedef char ElemType;
typedef char Array1D;
void Rotate(Array1D a, int len, int step)
{
ElemType tmp1,tmp2;
int times=1,i,j,k;//k为最大公约数
step=step%len;
cout<<"step="<<step<<"\t";
if(0==step)return;
/*用i,j为临时变量求 len和step的最大公约数*/
i=len;
j=step;
while(times=i%j){
i=j;
j=times;
}
cout<<"j="<<j<<"\tstep="<<step<<endl;
/*j为最大公约数*/
k=j;
times=len/k;
for(i=0;i<k;++i){
tmp2=a;
tmp1=a;
a[(i+step)%len]=tmp2;
tmp2=tmp1;
for(j=1;j<times;++j){
tmp1=a[(i+(j+1)*step)%len];
a[(i+(j+1)*step)%len]=tmp2;
tmp2=tmp1;
}//for
}//for
}
int main(){
Array1D p="ABCDEFGHIJKLMNOPQRST";
for(int i=0;i<13;++i){
Rotate(p,8,i); //8可以换成＜＝20的数，i任意
cout<<p<<endl;
}
cout<<p<<endl;
return 0;
}
极不喜欢作业系统上的调试……
另：
作业系统对于 ++a=b++; 这样的语句，表现诡异
有写了这样句子的建议改成三句…… ++a=b++
这种东西应该像鄙视goto一样BS 原帖由 powerwind 于 2007-6-5 13:17 发表
++a=b++
这种东西应该像鄙视goto一样BS
MS见过这样的代码：
while(src!='\0')
*des++=*src++;
不过这个的确和一个前加一个后加不同……
发现现在较熟练前加后加了……
上次做数据结构题目时就用了一个前加和一个后加……
为了省打字，而且那代码只是我看我改……
页:
[1]