C++研究

C++细节深度探索及软件工程

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  37 随笔 :: 0 文章 :: 74 评论 :: 0 Trackbacks

算法要求:试设计一个算法,将数组A[0..n-1]中的元素循环右移K位,并要求只用一个元素大小的存储

空间。元素移动或交换的次数为O(n)


【分析】:本题的应用环境很广泛,在实用中有很重要意义,如:实现高阶乘除法,在游戏选关和各种

特效中经常用到。目前手机等移动设备应用开发方兴未艾,对此常用算法做一个深入的探讨很有必要。

作者: 天津大学计算机系    常兴龙  MSN:cxl82116@msn.com 

    本题的难点在于同时对空间复杂度与时间复杂度都做了很高的要求,但就本题来讲,仍有很多种解

法。这里,探讨常见的三种解法:
               1.由于每个元素,跟与它相距r×k位形成了一个“循环”,因此算法保证每次都有一至

二个元素正确归位,设一个计数变量,当计数变量到达n时,算法结束
               2.对1解法求精,1解中可能使一个元素多于一次的移动,但如果找到n与k的最大公约数

,就可以解决此问题,从而保证每个元素只移动一次。
               3.第三种思想有一定的技巧,直观理解比较困难,但手有有一副扑克牌,就能清楚地看

到整个过程(把整个排列看成是一个环形)。它的算法是:先逆转前n-k个元素,再逆转后K个元素,再

把整个序列逆转。

void EMove(int A[n] , int k)
{
    
for(int i = 0 ; i < n;) //i为到位的元素个数,做为算法出口
    {
    
/**//* t是需要到位的元素的静态指针 s 指向下一个K步到达的位置 ,
        r初值为1 ,在每一循环圈中置初值一次,做为步进值
*/

        s 
= ( t + r * k ) % n ;  
        A[t]
<-->A[s]; //用A[t]为缓冲空间 , 使此链上一个记录到位,到位位置的记录缓存到缓冲区中
        r++ ; i++;
        s 
= ( t +*k) %n;
        
if(s == t) //使两个记录到位,一圈结束
        {
            t
++;    //选择亲的起始点
            r=1;
            i
++;
        }
//if
    }
//for
}

[解二]
void EMove(int A[n] , int k)
{
    
for ( int i = 1; i <= k; i++ )
        
if ( n%== 0 && k%==0 ) p = j; 
        
/**//*上面为求最大公约数的O(n)写法之一,还可以这么写:
            int p= int();  //这也是一个C++新奇的写法,int = 0,稍用一下构造函数
            while( n !=0 && k !=0)
            {
            n>k ? n%=k:k%=n;
            }
            p = n==0?k:n;
            p为n与k的最大公约数
            比较性能:注释中的log(N)性能更好,但是破坏原来数据,
            如果保留原数据,辗转一下,得不偿失,这也是弃用的理由
        
*/

        
for ( i = 0 ; i < p ; i++//最大公约数,实质为保证每个元素都到位的子圈数目
        //极限情况,若 n与k最大公约为1,则一圈就能成功,无需另先起点
            j = i;
            m 
= ( i + k ) % n;
            temp 
= A[i]; //缓存
            while( m != i)
            
{
                
//利用A[j],交换 temp 与A[m]的值
                
//A[j]为本次要到位的元素
                
//A[m]存本次己位的元素
                
//temp 缓存下次要到位的元素
                A[j] = temp ; 
                temp 
= A[m] ; 
                A[m] 
= A[j] ; 
                
//前进一步
                j = m ;
                m 
= ( j + k ) % n ;
                
            }
//while
        }
//for
}
//Emove

[解三]
void Emove ( int A[n] , int k )
{
    
for ( i=0 ; i < ( n - k ) / 2 ; i++ )
    
{
        A[i]
<-->A[ n-k-1-i];
        
    }
//逆转前n-k
    for( i = n - k ; i < ( 2*- k) /2 ; i++)
    
{
        A[n
-k+i]<-->A[k-1+i];
    }
 //逆转后K项
    for ( i = 0 ; i < n/2 ; i++ )
    
{
        A[i]
<-->A[n-1-i];
    }
//逆转整个链
}



补充:

[1]反转链的下标确定方法,可以通俗的描写

从 『链开始下标』到 (『链终止下标』-『链开始下标』)/2 ,反复做

     交换 『链开始下标+i』,『链终止下标-i』

[2]定义符号<-->为

Swap( int & i , int & j )
{
    
int temp = i ;
    i 
= j ; 
    j 
= temp
}


关于交换算法,还有一种线性代数矩阵的写法

//交换x,y
Swap( int & x , int & y )
{
    
    x
=x+y;
    y
=x-y;
    x
=x-y;
}


【思考】如果把本题扩充一下,改为把A中的一个子序列扩右移K位(其余要求不变)的算法?(进一步

要求能够处理K>子序列长度的情况?)(下次提供答案)

posted on 2007-05-15 10:03 常兴龙 阅读(2426) 评论(6)  编辑 收藏 引用 所属分类: Algorithm

评论

# re: 精炼循环右移[未登录] 2007-07-06 16:53 yong
第三种有意思,呵呵,怎么推出来的,琢磨琢磨...  回复  更多评论
  

# re: 精炼循环右移 2008-08-29 20:08 李锐
我也要好好看看,谢谢了  回复  更多评论
  

# re: 精炼循环右移 2010-04-18 20:52 zy天
A[n-k+i]<-->A[k-1+i];
应该是A[n-k+1]<-->A[k-1+i]  回复  更多评论
  

# re: 精炼循环右移 2010-04-28 22:28 tengzhao201
//最高效的循环右移算法!!
//这个是递归的写法
//author:tengzhao201 QQ:715572192
//time:2010-4-24
//时间复杂度为O(n),空间复杂度O(1),交换点在中间时比逆序法快一倍!!!
//提速要点:由于取模运算的效率很低,去掉了取模运算后效率得到大提升;swap函数效率低,引入了temp变量
void TZshift1(int* arr,int N,int K)
{
K=K%N;

if(0==K)return;

int temp,qq,pp=0;
pp=0;qq=K;
for(int i=0;i<N-K;i++,pp++,qq++)
{
//swap(arr[i%K],arr[i+K]);//问题的关键在于找到原来的第i个元素现在在哪里,通过观察可以发现在arr[i%K]的位置,下面的代码实现了arr[i%K]和arr[i+K]的互换
if(K==pp)pp=0;
temp=arr[pp];
arr[pp]=arr[qq];
arr[qq]=temp;
}

TZshift1(arr,K,K-pp);
}

//最高效的循环右移算法!!
//非递归的写法
//author:tengzhao201 QQ:715572192
//time:2010-4-24
//时间复杂度为O(n),空间复杂度O(1),交换点在中间时比逆序法快一倍!!!
//提速要点:采用非递归算法
void TZshift2(int* arr,int N,int K)
{
K=K%N;
if(0==K)
return;

//int count=0;
int temp,qq,pp=0;

while(K>0)
{
pp=0;qq=K;
for(int i=0;i<N-K;i++,pp++,qq++)
{
//swap(arr[i%K],arr[i+K]);//问题的关键在于找到原来的第i个元素现在在哪里,通过观察可以发现在arr[i%K]的位置,下面的代码实现了arr[i%K]和arr[i+K]的互换

if(K==pp)pp=0;
temp=arr[pp];
arr[pp]=arr[qq];
arr[qq]=temp;
//count+=2;
}
N=K;
if(0==pp)
return;
K-=pp;
//TZshift(arr,K,K-pp);
}
//cout<<"In tatal,has used "<<count<<" steps."<<endl;
}  回复  更多评论
  

# re: 精炼循环右移 2010-04-29 10:46 tengzhao201
http://download.csdn.net/source/2296222  回复  更多评论
  

# re: 精炼循环右移 2010-04-29 10:47 tengzhao201
最高效循环右移课程设计下载地址:
http://download.csdn.net/source/2296222  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


> hi的博客