Chinaunix首页 | 论坛 | 博客
  • 博客访问: 571026
  • 博文数量: 50
  • 博客积分: 571
  • 博客等级: 中士
  • 技术积分: 1162
  • 用 户 组: 普通用户
  • 注册时间: 2012-01-20 14:01
个人简介

希望成为一个有思想,有信仰的程序设计师。

文章分类

全部博文(50)

文章存档

2016年(2)

2015年(2)

2014年(13)

2013年(10)

2012年(23)

分类:

2012-07-28 17:57:04

--------------------------------------------分割线(转载部分)--------------------------------------
  1.  /* 
  2.   Name: 向量旋转算法集锦  
  3.   Copyright: 始发于goal00001111的专栏;允许自由转载,但必须注明作者和出处 
  4.   Author: goal00001111 
  5.   Date: 28-12-08 23:28 
  6.   Description:  
  7.   向量旋转算法:将具有n个元素的向量a向左旋转r个位置。 
  8.   例如 :将字符串"abcdefghij"旋转成"defghjabc",其中n=10,r=3。 
  9.   其实就是将 AB 转换成 BA 的过程,这里A ="abc", B="defghij"。 
  10.   本文总共采用了四种方法来解决向量旋转问题,依次是: 
  11.   方法一:最简单的直接移动向量旋转算法; 
  12.   方法二:简明的的逆置数组旋转算法; 
  13.   方法三:传说中的杂耍旋转算法; 
  14.   方法四:一个类似于欧几里得算法的旋转算法; 
  15.   其中方法一需要一个辅助数组,空间复杂度较高;方法二每个元素都要移动两次,效率相对较低; 
  16.   方法三和方法四都是极牛的算法,空间和时间复杂度都很低。  
  17.   这是牛书《编程珠玑》中的一个例题,在书的网站上有详细的源码,我把它改成了我所熟悉的样子。 
  18.   源码的网站是: 
--------------------------------------------分割线----------------------------------------------
 
「方法1
利用memcpy函数,需开辟临时空间。先把从a+n-k到a+n-1这k个字符,存到tmp中;然后,把以a开始的地址空间中的字符复制到a+k开始的地址空间中去;最后,把tmp的k个字符放回以a开始的地址空间中去。

 a ...a+n-k-1 a+n-k  ... a+n-1

void loopRightShiftV2(char a[], int n, int k)
{
    char *tmp = (char *)malloc(sizeof(char)*k);

    k %= n;
    memcpy(tmp, a+n-k, k);
    memcpy(a+k, a, n-k);
    memcpy(a, tmp, k);
}


「方法1版本2
先看循环右移一个字符的思路:首先,保存最有一个非'\0'字符;然后将字符数组从最后一个非'\0'字符开始,依次后移;最后将已保存的最后一个字符放到第一字符所在位置处。循环右移k个字符,只需将上述过程重复k次即可。

void loopRightShift(char a[], int n, int k)
{
    int tmp;
    int i;

    k %= n;
    while(k--){
        tmp = a[n-1];
        for(i = n-1; i >0; i--){
            a[i] = a[i-1];
        }
        a[0] = tmp;
    }
}


「方法2
初始状态

 c1

 c2

 ...

 cn-k-1

 cn-k

 cn-k+1

cn-k+2 

 ...

 cn-1

cn 


逆序一次后 |

 cn-k

 cn-k-1

 ...

c2 

c1 

 cn

cn-1 

 ...

 cn-k+2

cn-k+1 


再整体逆序,循环右移完成。

 cn-k+1

 cn-k+2

 ...

 cn-1

 cn

 c1

c2 

 ...

cn-k-1 

 cn-k


补充:来自《编程珠玑》,将数组看成一个向量x=ab,那么循环右移后数组就变成ba。从向量的角度考虑
(a-1b-1)-1=ba

/* 不用临时变量交换a[begin]和a[end]两内存单元的内容 */
void stringReverse(char a[], int begin, int end)
{
    for(; begin < end; begin++, end--){
        a[begin] ^= a[end];
        a[end] ^= a[begin];
        a[begin] ^= a[end];
    }
}

void loopRightShift(char a[], int n, int k)
{
    k %= n;
    
    stringReverse(a, 0, n-k-1); /* 先对a[0...n-k-1]这(n-k)个字符逆序 */
    stringReverse(a, n-k, n-1); /* 再对a[n-k...n-1]这k个字符逆序 */
    stringReverse(a, 0, n-1);   /* 最后对整个字符串逆序 */
}


「方法3杂耍(杂技)旋转算法(转载部分,来源http://sstrive.javaeye.com/blog/410649)

/*
函数名称:gcd
函数功能:欧几里德算法求最大公约数
输入参数:int m:正整数之一
          int n:正整数之二
输出参数:无
返回值:正整数m和n的最大公约数
*/

int gcdLoop(int m, int n)
{
    int t;
    assert(m > 0 && n >0);

    if(m < n){
        swapInt(&m, &n);
    }

    while( n > 0){
        t = m % n;
        m = n;
        n = t;
    }
    return m;
}
int gcdRecursive(int m, int n)
{
    if(m < 0 || n < 0){
        printf("Error! not positive integer!\n");
        return 0;
    }
    
    if(m < n){
        swapInt(&m, &n);
    }
    if(n == 0) {
        return m;
    }else{
        return gcdRecursive(n, m % n);
    }
}

/*
函数名称:juggleRotate
函数功能:杂耍(杂技)旋转算法:
            1. 将a[0]存储到临时变量t中;
            2. 将a[r%n]移动到a[0],将a[2r%n]移动到a[r%n]...a[x*r%n]移动到a[(x-1)*r%d],直到(x*r)%n == 0;
            3. a[x*r%n] = t;
         如果该过程不能移动所有的元素,那么我们从a[1]开始移动,循环,共重复gcd(n, n)次
说明: 此算法每个元素只需移动一次就可以到达正确位置,理论上效率是最高的,
         但由于要做求最大公约数和求余运算等准备工作,所以没有显示出优势。
输入参数:char a[]:需要被旋转的向量
          int n:向量的长度
          int r:向量左半段长度
输出参数:char a[]:旋转后的向量
返回值:无
*/

void juggleRotate(char a[], int n, int r)
{
    int i, j, k;
    int t;
    int gcdNum = gcdLoop(n, r); //用r和n的最大公约数作为循环次数


    for(i = 0; i < gcdNum; i++){//总共需要重复开始移动gcdNum次,才能使得所有的元素都移动到正确位置

        j = i;
        t = a[j];
        while(1){ //依次移动元素,直到 (k*r)%n == 0

            k = (j+r) % n;
            if(k == i) break;
            a[j] = a[k];
            j = k;

        }
        a[j] = t;
    }

}


「方法4一个类似于欧几里得算法的旋转算法;(转载部分,来源http://sstrive.javaeye.com/blog/410649)

/*
函数名称:swapArrayp
函数功能:交换两个长度均为len的数组a[left1..left1+len-1) 和 a[left2..left2+len-1)
输入参数:char a[]:需要被处理的数组
          int left1:向量块a[left1..left1+len-1)的左界
          int left2:向量块a[left2..left2+len-1)的左界
          int len: 两个向量块的长度
输出参数:char a[]:交换了部分元素的向量
返回值:无
*/

void swapArray(char a[], int left1, int left2, int len)
{
    int t;
    while (len > 0)
    {
        t = a[left1];
        a[left1] = a[left2];
        a[left2] = t;
        left1++;
        left2++;
        len--;
    }
}

/*
函数名称:gcdRotate
函数功能:一个类似于欧几里得辗转相除算法的旋转算法:
          就像一个做阻尼振动的弹簧振子一样,按照由两边到中间的顺序,整段的交换向量块,
          并且被交换的向量块长度不断缩减,直到lLen == rLen。
          由于重复移动的元素较少,所以效率比逆置数组旋转算法要高。
输入参数:char a[]:需要被旋转的向量
          int n:向量的长度
          int r:向量左半段长度
输出参数:char a[]:旋转后的向量
返回值:无
*/

void gcdRotate(char a[], int n, int r)
{
    int lLen, pos, rLen;
    
    lLen = pos = r;
    rLen = n - r;

    while(lLen != rLen){
        if(lLen > rLen){
            swapArray(a, pos-lLen, pos, rLen);
            lLen -= rLen;
        }else{
            swapArray(a, pos-lLen, pos+rLen-lLen, lLen);
            rLen -= lLen;
        }
    }
    swapArray(a, pos-lLen, pos, lLen);
    
}



3. (算法思想对,但方法2和方法3的代码实现部分有问题)
阅读(4554) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~