分享
 
 
 

内存移动算法

王朝other·作者佚名  2006-06-24
窄屏简体版  字體: |||超大  

原文参见《程序员》杂志2006年第6期。现对原文做部分摘录,并给出自己的算法。

问题: 对于有K个元素的数组int a[k]={.......};写一个高效算法将数组内容循环左移m位,

比如:int a[6]={1,2,3,4,5,6},循环左移3位后得到结果{4,5,6,1,2,3}.

要求:1.不允许另外申请数组空间,但可以申请少许变量;

2.不允许采用每次左移。

最直观的想法,就是从第一个元素开始,把他一步移动到最终目的位置,而该位置原有的元素的值取出,移动到它的新位置。递归进行这个步骤。

首先,我们在数学上很容易理解,这是一个一一对应映射,绝不会在一个位置上出现两次移动。所以不会出现移动的递归过程中途指向了已经移动过的元素。

那么,这个递归过程唯一的终止条件就是,当前移动的元素,目的位置就是移动过程的起始位置。

如果按照元素的索引下标标示元素,0到k-1中的任意元素i,会移动到什么位置?

对于任意的i,它的新位置i'=((k-m) + i)%k.

那么,我们可以定义这个循环链,取整数i0,使得0=<i0<m,定义i1=((k-m) + i0)%k,i2=((k-m) + i1)%k....ix=((k-m) + ix-1)%k.当ix=i0时循环终止。此时有i0=ix=((k-m) + ix-1)%k=....

=(x(k-m) + i0)%k

因为我们知道0<i0<m,所以有0=x(k-m)%k,也就是说,x(k-m)=yk,因为我们是遇到第一个x(k-m)=yk就终止,显然等号左右的值就是k-m和k的最小公倍数。根据数论知识,我们知道,k,m,k-m这三个数有最大公约数q,使得k=aq,m=bq,k-m=cq,a,b,c三个数两两互质,进而推出x=a,y=c。也就是说,这个递归过程会经历a步。

因为我们知道整个过程一共a步,k=aq,那么i到ix的序列会形成一个步长为q的等差序列,所以我们要移动整个0到k-1的区间,应该对0到q-1的元素应用这个递归算法。

该算法的时间复杂度为O(n),空间复杂度为O(1).

int CommonFactor(int dividend,int divisor)//求最大公约数函数

{

if(dividend<divisor)

{

int temp=dividend;

dividend=divisor;

divisor=temp;

}

int remainder=dividend%divisor;

while(remainder!=0)

{

dividend=divisor;

divisor=remainder;

remainder=dividend%divisor;

}

return divisor;

}

void shift1(int a[],int k,int m)//k是数组a的元素个数,m是循环左移m位

{

int i,j,n,q=CommonFactor(k,k-m);

for(n=0;n<q;n++)

{

int temp=x[n]; i=n;j=(i+m)%k;

while(j!=n)

{

x[i]=x[j];

i=j;

j=(i+m)%k;

}

x[i]=temp;

}

}

同理可以分析循环右移m位的算法

void shift1(int a[],int k,int m)//k是数组a的元素个数,m是循环右移m位

{

int i,j,n,q=CommonFactor(k,m);

for(n=0;n<q;n++)

{

int temp=x[n]; i=n;j=(k+i-m)%k;

while(j!=n)

{

x[i]=x[j];

i=j;

j=(k+i-m)%k;

}

x[i]=temp;

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有