/*
  Name: 向量旋转算法集锦
  Copyright: 始发于goal00001111的专栏;允许自由转载,但必须注明作者和出处
  Author: goal00001111
  Date: 28-12-08 23:28
  Description:
  向量旋转算法:将具有n个元素的向量a向左旋转r个位置。
  例如 :将字符串"abcdefghij"旋转成"defghjabc",其中n=10,r=3。
  其实就是将 AB 转换成 BA 的过程,这里A ="abc", B="defghij"。
  本文总共采用了四种方法来解决向量旋转问题,依次是:
  方法一:最简单的直接移动向量旋转算法;
  方法二:简明的的逆置数组旋转算法;
  方法三:传说中的杂耍旋转算法;
  方法四:一个类似于欧几里得算法的旋转算法;
  其中方法一需要一个辅助数组,空间复杂度较高;方法二每个元素都要移动两次,效率相对较低;
  方法三和方法四都是极牛的算法,空间和时间复杂度都很低。
  这是牛书《编程珠玑》中的一个例题,在书的网站上有详细的源码,我把它改成了我所熟悉的样子。
  源码的网站是:http://www.cs.bell-labs.com/cm/cs/pearls/code.html
*/
#include<iostream>
#include <time.h>

using namespace std;

template <class T> //最简单的直接移动向量旋转算法
void SlideRotate(T a[], int n, int r);

template <class T> //逆置数组的原子操作
void Reverse(T a[], int left, int right);

template <class T> //简明的的逆置数组旋转算法
void ReverseRotate(T a[], int n, int r);

int Gcd(int m, int n); //欧几里德算法求最大公约数

template <class T> //传说中的杂耍旋转算法
void JuggleRotate(T a[], int n, int r);

template <class T> //交换两个长度均为len的向量块a[left_1..left_1+len) 和 a[left_2..left_2+len)
void Swap(T a[], int left_1, int left_2, int len);

template <class T> //一个类似于欧几里得算法的旋转算法
void GcdRotate(T a[], int n, int r);

template <class T> //创建一个向量
void InitVector(T a[], int n);

template <class T> //输出一个向量
void PrintVector(const T a[], int n);

template <class T> //判断向量旋转是否成功
bool CheckRotate(const T a[], int n, int r);

int main()
{
    const int N = 601; //测试次数
    const int MAX = 500000; //向量长度
    int a[MAX] = {0};
    int rotateDistance = 100000;
    time_t startTime, endTime;
    
   ////////最简单的直接移动向量旋转算法///////////////////////////////  
    time(&startTime);
    InitVector(a, MAX);
   // PrintVector(a, MAX);
    for (int i=0; i<N; i++)
        SlideRotate(a, MAX, rotateDistance);
  //  PrintVector(a, MAX);
    if (CheckRotate(a, MAX, rotateDistance))
        cout << "True" << endl;
    else
        cout << "False" << endl;
       
    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl << endl;
    ///////////////////////////////////////////////////////////////////////////////////////////
    //////////简明的的逆置数组旋转算法//////////////////////////////////////////////////  
    time(&startTime);
    InitVector(a, MAX);
  //  PrintVector(a, MAX);
    for (int i=0; i<N; i++)
        ReverseRotate(a, MAX, rotateDistance);
  //  PrintVector(a, MAX);
    if (CheckRotate(a, MAX, rotateDistance))
        cout << "True" << endl;
    else
        cout << "False" << endl;
       
    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl << endl;
    ///////////////////////////////////////////////////////////////////////////////////////////
    ////////////传说中的杂耍旋转算法 //////////////////////////////////////  
    time(&startTime);
    InitVector(a, MAX);
  //  PrintVector(a, MAX);
    for (int i=0; i<N; i++)
        JuggleRotate(a, MAX, rotateDistance);
  //  PrintVector(a, MAX);
    if (CheckRotate(a, MAX, rotateDistance))
        cout << "True" << endl;
    else
        cout << "False" << endl;
       
    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl << endl;
    ///////////////////////////////////////////////////////////////////////////////////////////
    /////////////一个类似于欧几里得算法的旋转算法///////////////////////////////////  
    time(&startTime);
    InitVector(a, MAX);
  //  PrintVector(a, MAX);
    for (int i=0; i<N; i++)
        GcdRotate(a, MAX, rotateDistance);
  //  PrintVector(a, MAX);
    if (CheckRotate(a, MAX, rotateDistance))
        cout << "True" << endl;
    else
        cout << "False" << endl;
       
    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl << endl;
    ///////////////////////////////////////////////////////////////////////////////////////////
       
    system("pause");
    return 0;
}

////////////方法一:创建一个长度为min{r, n-r)的辅助数组,以帮助完成旋转任务//////////////////
/*
函数名称:SlideRotate
函数功能:最简单的直接移动向量旋转算法:先利用一个辅助数组将较短的那一段元素存储起来,
          再移动原向量中未另外存储的那部分元素,最后将辅助数组中的元素再复制到正确位置
输入参数:T a[]:需要被旋转的向量
          int n:向量的长度
          int r:向量左半段长度
输出参数:T a[]:旋转后的向量
返回值:无
*/
template <class T>
void SlideRotate(T a[], int n, int r)
{   
    if (r < n - r) //如果左半段小于右半段,存储左半段的元素
    {
        T *buf = new T[r];
        for (int i=0; i<r; i++)//存储左半段的元素
            buf[i] = a[i];
           
        for (int i=r; i<n; i++)//移动右半段的元素
            a[i-r] = a[i];
       
        for (int i=0; i<r; i++)//复制左半段的元素到右半段
            a[n-r+i] = buf[i];
       
        delete []buf; 
    }
    else //否则存储右半段的元素 
    {
        T *buf = new T[n-r];
        for (int i=r; i<n; i++)//存储右半段的元素
            buf[i-r] = a[i];
           
        for (int i=r-1; i>=0; i--)//移动左半段的元素
            a[i+n-r] = a[i];
       
        for (int i=0; i<n-r; i++)//复制右半段的元素到左半段
            a[i] = buf[i];
       
        delete []buf;
    }
}
////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////方法二:使用一个逆置数组的原子操作////////////////////////////////////
/*
函数名称:Reverse
函数功能:逆置数组的原子操作
输入参数:T a[]:需要被逆置的向量 
          int left: 数组的左界
          int right:数组的右界
输出参数:T a[]:逆置后的数组
返回值:无
*/
template <class T>
void Reverse(T a[], int left, int right)
{   
    T t;
    while (left < right)
    {
        t = a[left];
        a[left] = a[right];
        a[right] = t;
        left++;
        right--;
    }
}

/*
函数名称:ReverseRotate
函数功能:简明的的逆置数组旋转算法:构造一个逆置数组的原子操作子函数,然后设置不同的数组左右界,
          分三次调用子函数就行了。因为每个元素都需要移动两次,所以效率不是很高。
输入参数:T a[]:需要被旋转的向量
          int n:向量的长度
          int r:向量左半段长度
输出参数:T a[]:旋转后的向量
返回值:无
*/
template <class T>
void ReverseRotate(T a[], int n, int r)
{   
    Reverse(a, 0, r-1); //逆置左半段数组
    Reverse(a, r, n-1); //逆置右半段数组
    Reverse(a, 0, n-1); //逆置整段数组
}
////////////////////////////////////////////////////////////////////////////////////////////////
//////////////方法三:传说中的杂耍旋转算法////////////////////////////////////////////////

/*
函数名称:Gcd
函数功能:欧几里德算法求最大公约数
输入参数:int m:正整数之一
          int n:正整数之二
输出参数:无
返回值:正整数m和n的最大公约数
*/
int Gcd(int m, int n)
{   
    int t;
    while (m > 0)
    {
        t = n % m;
        n = m;
        m = t;
    }
    return n;
}

/*
函数名称:JuggleRotate
函数功能:传说中的杂耍旋转算法:
          先将a[0]存储到临时变量t中,然后将a[r]移动到a[0],将a[2r] 移动到 a[r],
          依此类推(数组中所有的下标都要对数组的长度n取模),直到(k*r)%n == 0,
          此时我们不能在a[0]中取数,而是在临时变量t中取数,然后结束该过程。
          如果该过程不能移动所有的元素,那么我们从a[1]开始移动,一直依次下去,
          直到移动了所有的元素为止。
          那么总共要重复开始移动几次呢?数学证明是Gcd(r, n)次。
          此算法每个元素只需移动一次就可以到达正确位置,理论上效率是最高的,
          但由于要做求最大公约数和求余运算等准备工作,所以没有显示出优势。
输入参数:T a[]:需要被旋转的向量
          int n:向量的长度
          int r:向量左半段长度
输出参数:T a[]:旋转后的向量
返回值:无
*/
template <class T>
void JuggleRotate(T a[], int n, int r)
{   
    int i, j, k;
    int cyc = Gcd(r, n); //用r和n的最大公约数作为循环周期
   
    for (i=0; i<cyc; i++) //总共需要重复开始移动cyc次,才能使得所有的元素都移动到正确位置
    {
        T t = a[i]; //临时变量t存储a[i]
        j = i;
        while (1)//依次移动元素,直到 (k*r)%n == 0
        {
            k = j + r;
            if (k >= n) //用除法运算替代模运算
                k -= n;
               
            if (k == i)
                break;
            a[j] = a[k];
            j = k;
        }
        a[j] = t;
    }
}
////////////////////////////////////////////////////////////////////////////////////////////////
//////////////方法四:一个类似于欧几里得辗转相除算法的旋转算法/////////////////////////////////
/*
函数名称:Swap
函数功能:交换两个长度均为len的向量块a[left_1..left_1+len) 和 a[left_2..left_2+len)
输入参数:T a[]:需要被处理的向量
          int left_1:向量块a[left_1..left_1+len)的左界
          int left_2:向量块a[left_2..left_2+len)的左界
          int len: 两个向量块的长度
输出参数:T a[]:交换了部分元素的向量
返回值:无
*/
template <class T>
void Swap(T a[], int left_1, int left_2, int len)
{   
    T t;
    while (len > 0)
    {
        t = a[left_1];
        a[left_1] = a[left_2];
        a[left_2] = t;
        left_1++;
        left_2++;
        len--;
    }
}

/*
函数名称:JuggleRotate
函数功能:一个类似于欧几里得辗转相除算法的旋转算法:
          就像一个做阻尼振动的弹簧振子一样,按照由两边到中间的顺序,整段的交换向量块,
          并且被交换的向量块长度不断缩减,直到lLen == rLen。
          由于重复移动的元素较少,所以效率比逆置数组旋转算法要高。
输入参数:T a[]:需要被旋转的向量
          int n:向量的长度
          int r:向量左半段长度
输出参数:T a[]:旋转后的向量
返回值:无
*/
template <class T>
void GcdRotate(T a[], int n, int r)
{   
    if (r == 0 || r == n) //特殊情况不用旋转
        return;
   
    int lLen, rLen, pos;   
    lLen = pos = r;
    rLen = n - r;
    while (lLen != rLen)
    {
        if (lLen > rLen) //左半段大于右半段,移动右半段
        {
            Swap(a, pos-lLen, pos, rLen);
            lLen -= rLen; //减少移动范围
        }
        else
        {
            Swap(a, pos-lLen, pos+rLen-lLen, lLen);
            rLen -= lLen;
        }
    }
    Swap(a, pos-lLen, pos, lLen); //最后交换中间段
}
////////////////////////////////////////////////////////////////////////////////////////////////
/*
函数名称:InitVector
函数功能:创建一个向量
输入参数:T a[]:需要被赋值的向量
          int n:向量的长度
输出参数:T a[]:创建好的向量
返回值:无
*/
template <class T>
void InitVector(T a[], int n)
{
    for (int i=0; i<n; i++) //创建一个向量
        a[i] = i;
}

/*
函数名称:PrintVector
函数功能:输出一个向量
输入参数:const T a[]:需要被输出的向量
          int n:向量的长度
输出参数:无
返回值:无
*/
template <class T>
void PrintVector(const T a[], int n)
{
    for (int i=0; i<n; i++)
        cout << a[i] << ' ';
    cout << endl;  
}

/*
函数名称:CheckRotate
函数功能:判断向量旋转是否成功
输入参数:T a[]:需要被旋转的向量
          int n:向量的长度
          int r:向量左半段长度
输出参数:无
返回值:旋转成功返回true,否则返回false
*/
template <class T>
bool CheckRotate(const T a[], int n, int r)
{   
    for (int i=0; i<n-r; i++) //判断左半段
    {
        if (a[i] != i+r)
            return false;
    }
   
    for (int i=0; i<r; i++)//判断右半段
    {
        if (a[n-r+i] != i)
            return false;
    }
   
    return true;
}


Posted on 2008-12-29 12:36 梦想飞扬 阅读(736) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理